[Coinbase] ECDSA 2 trong 2 nhanh, an toàn sử dụng DKLs18

Chúng tôi đã thảo luận về các khái niệm chung về chữ ký điện tử và chữ ký ngưỡng trong một bài viết trước. Tại Coinbase, chúng tôi đặc biệt tập trung vào việc ký kết ngưỡng của hai bên; chúng tôi sẽ thảo luận về cài đặt này trong bài đăng này.

DKLs: phần giới thiệu. Trong khi các giao thức ký ngưỡng cho các lược đồ Schnorr và BLS tương đối đơn giản, ECDSA ngưỡng khó hơn nhiều. Một số giao thức tồn tại để ký 2 trong số 2 ECDSA; một số nhắm mục tiêu nó một cách rõ ràng (tức là, họ không hỗ trợ các lựa chọn chung chung hơn về NS và n). Trong bài đăng blog thuần túy về kho lưu trữ này, chúng tôi sẽ nghiên cứu một cách cụ thể: giao thức năm 2018 của Doerner, Kondi, Lee và lánh. Giao thức này được xây dựng dựa trên công việc trước đây của Chou và Orlando và Keller, Orsini và Scholl. Giao thức này – hay gọi tắt là “DKLs” – cho phép hai bên tạo chữ ký ECDSA một cách an toàn chỉ trong một vài phần nghìn giây, bằng cách chỉ trao đổi 3 tin nhắn và đồng thời truyền đi tổng cộng 120 kilobyte dữ liệu. Trong quá trình này, nó sử dụng một số kỹ thuật thú vị trong tính toán an toàn của hai bên và thể hiện một đóng góp có kỷ luật, nổi bật cho lĩnh vực này.

Bây giờ chúng ta hãy nói một vài điều kỹ thuật về cách hoạt động của DKL. Ý tưởng cơ bản liên quan đến chia sẻ bí mật nhân của các phần tử trường nguyên tố. Nếu hai bên của chúng tôi – Alice và Bob, giả sử – tạo cục bộ các đại lượng vô hướng ngẫu nhiên sk_A và sk_B trong 𝔽_NS, sau đó, sau khi thực hiện trao đổi giống như Diffie-Hellman, các bên có thể lấy được khóa công khai cùng sở hữu P = sk_A · sk_B · NS, mà không cần tìm hiểu bất kỳ điều gì về các khóa chia sẻ tương ứng (hoặc khóa bí mật chung) của nhau. Khóa bí mật chung là sản phẩm sk : = sk_A · sk_B (mod NS). DKL là bất thường trong việc sử dụng chia sẻ nhân; giao thức không thể tổng quát hóa thành (NS, n) về cơ bản vì lý do này.

Các bên bắt đầu quá trình ký ECDSA một thông điệp cụ thể NS theo một cách tương tự. Họ tạo ra các nonce-share riêng lẻ k_A và k_B ngẫu nhiên, và xây dựng R: = k_A · k_B · NS như họ đã làm P; sử dụng tọa độ của R (NS, y), cả hai đều có được thành phần chữ ký đầu tiên NS : = NS (mod P). Nó vẫn chỉ để các bên cùng xây dựng NS : = NS(NS) · k⁻¹ + NS · sk · k⁻¹ (mod NS), theo quy định của định nghĩa của ECDSA. Rắc rối là các bên chỉ sở hữu chia sẻ nhân số lượng k và skvà không phải là các giá trị bắt buộc.

DKL quan sát rằng biểu thức xác định NS cũng có thể được viết là:

https://medium.com/media/2a0c40a041fc6a2fe623305df1fa751c/href

Ý tưởng chính đầu tiên là nó sẽ là đủ để các bên có được sự chia sẻ phụ gia ngẫu nhiên của hai biểu thức sản phẩm 1 /k_A · 1 /k_B và sk_A / k_A · sk_B / k_B bên trên. Thật vậy, nếu các bên có được sự chia sẻ như vậy, thì cả hai đều có thể tiến hành bằng cách nhân những chia sẻ cục bộ này với NS(NS) và NStương ứng, và thêm các kết quả (nhớ lại rằng cả hai bên đều biết NS(NS) và NS). Khi làm như vậy, các bên sẽ có được sự chia sẻ bổ sung về NS chính nó, mà cuối cùng họ có thể trao đổi một cách an toàn (tức là, không bị rò rỉ thêm bất kỳ thông tin nào về NStriệu hồi cá nhân). Cuối cùng, lưu ý rằng Alice có thể tính toán cục bộ các phép nhân bên trái và các số 1 /k_A và sk_A/k_A; Bob cũng có thể tính toán cục bộ các bội số bên phải và các số 1 /k_B và sk_B/k_B.

Do đó, nó đủ để xử lý vấn đề “phép nhân an toàn”, đôi khi còn được gọi là “chuyển đổi từ nhân sang cộng”. Trong vấn đề này, hai bên gửi các vô hướng đầu vào tương ứng i_A và i_Avà kết thúc với ngẫu nhiên phụ gia chia sẻ t_a và t_b của sản phẩm i_A · i_B (mod NS). Nói cách khác, danh tính t_A + t_B = i_A · i_B (mod NS) nên giữ, và hơn nữa là kết quả đầu ra t_A và t_B nên là đối tượng ngẫu nhiên của điều kiện này; cuối cùng, các bên không được tìm hiểu gì về đầu vào của nhau i_A và i_B trong quá trình thực thi giao thức (ngay cả khi chúng tham gia vào hành vi độc hại).

DKLs mô tả một giao thức con phép nhân an toàn hấp dẫn, sử dụng một giao thức nguyên thủy khác được gọi là chuyển tiền có liên quan (viết tắt là cOT). Trong một giao thức cOT, các bên Alice và Bob có vai trò không đối xứng. Alice nhập một đại lượng vô hướng, chẳng hạn như ɑ, trong 𝔽_NS; Bob chỉ nhập một bit duy nhất NS. Mỗi bên nhận một vô hướng làm đầu ra; chúng ta hãy gọi lại những cái này t_A và t_B cho bây giờ. Theo định nghĩa của cOT, các kết quả đầu ra t_A và t_B nên tùy thuộc ngẫu nhiên với điều kiện t_A + t_B = ɑ nếu như Bit đầu vào của Bob NS là 1 và chủ đề ngẫu nhiên t_A + t_B = 0 nếu như Bit đầu vào của Bob là 0. Dù bằng cách nào, người gửi sẽ không biết gì về bit của người nhận NS, và người nhận sẽ không biết gì về khả năng vô hướng của người gửi ɑ. Định nghĩa của chuyển giao xiên tương quan được minh họa trong hình bên dưới.

Giả sử rằng chúng ta có một giao thức cOT trong tay, làm thế nào chúng ta có thể khởi động nó thành một giao thức nhân? Điều thú vị là Alice và Bob có thể sử dụng một thuật toán từ trường tiểu học để làm điều này. Hãy nhớ lại cái gọi là nhân dài thuật toán. Về cơ bản, quy trình liên tiếp dịch chuyển bội số trên cùng và sang trái từng vị trí một; trong mỗi bước, nó cũng nhân bội số này với chữ số thích hợp của cấp số nhân thấp hơn. Cuối cùng, nó thêm vào mảng kết quả của các số đã chuyển và nhân. Trong hệ nhị phân, mọi thứ thậm chí còn trở nên đơn giản hơn, bởi vì các “chữ số” của bội số thấp hơn là 0 hoặc 1. Một hình mô tả quá trình này được hiển thị bên dưới:

Trong mỗi hàng của hình này, đầu vào ban đầu của Alice được dịch chuyển sang trái một bước nữa. Hơn nữa, làm việc từ phải sang trái thông qua đầu vào của Bob, chúng tôi cũng gạch ra các hàng tương ứng với các bit mà đầu vào của Bob là 0. Cuối cùng, chúng tôi cộng các số kết quả để thu được sản phẩm. (Trong thực tế, mọi thứ ở đây đều diễn ra theo mod NS, nhưng chúng ta hãy bỏ qua điều đó cho rõ ràng; chúng tôi cũng đã đơn giản hóa các khía cạnh khác nhau của giao thức nhân cho các mục đích lưu trữ.)

Cái nhìn sâu sắc ở đây là chúng ta có thể sử dụng cOT để thực hiện việc này một cách an toàn. Thật vậy, mỗi hàng ngang của mảng đường chéo trên có thể được xử lý bằng chính xác một phép chuyển xiên tương quan. Alice nhập đầu vào ban đầu của cô ấy i_A, được dịch chuyển một cách thích hợp bởi NS bước sang trái; Bob nhập NSᵗʰ chút đầu vào ban đầu của anh ấy i_B. Theo định nghĩa của cOT, các bên kết thúc với mô đun chia sẻ phụ gia ngẫu nhiên NS của một trong hai 0 hoặc 2ʲ · i_A, tùy thuộc vào bit của Bob. Bằng cách thực hiện điều này cho từng hàng riêng lẻ, các bên có được chia sẻ bổ sung của mỗi hàng ngang ở trên, trong khi không tìm hiểu gì về đầu vào của nhau trong quá trình này. Cuối cùng, bằng cách thêm phần phụ gia địa phương có được, các bên kết thúc với phần phụ gia của toàn bộ sản phẩm i_A · i_B. Đây chính xác là những gì chúng tôi muốn ở trên.

Công việc tương lai. Các kỹ thuật ĐKL rất mạnh mẽ và thú vị; điều này làm cho các kỹ thuật của nó dễ hiểu, tổng quát hơn và có thể cải thiện. Hạn chế chính của DKL là yêu cầu băng thông của nó, đứng ở mức tương đối cao ~ 120KB (tổng số byte được trao đổi). Sẽ rất thú vị nếu cố gắng giảm bớt yêu cầu băng thông này, bằng cách cải thiện các kỹ thuật của DKL. Chúng tôi đã xem xét việc cố gắng cải thiện băng thông này bằng cách sử dụng phương pháp giống Karatsuba, nhưng vẫn chưa thể tổng hợp các chi tiết lại với nhau. Đại khái, Karatsuba hoạt động bằng cách thay thế một cách thông minh một tích của các số có độ dài đầy đủ bằng số ba các sản phẩm của số nửa độ dài (và xử lý các sản phẩm này đệ quy, và như vậy). Thực tế quan trọng làm cho cách tiếp cận này nhanh hơn là nhân hai số có độ dài bằng nửa chỉ mất một phần tư của công việc như nhân hai số có độ dài đầy đủ (vì khối lượng công việc liên quan đến bậc hai; xem ở trên). Tất cả đã nói, Karatsuba có thể nhân hai n-bit số chỉ trong

https://medium.com/media/4b4e72cc852ecf167dd90e8efa6f195e/href

hoạt động nguyên tử, trái ngược với O (n²) được yêu cầu bởi phép nhân ngây thơ. Vấn đề khi áp dụng kỹ thuật này cho các DKL là đầu ra của mỗi cOT cần phải là mô đun ngẫu nhiên NS. Điều này buộc mỗi đầu ra phải chiếm nhật ký NS chút ít, thậm chí khi các con số thực tế có liên quan thực sự nhỏ hơn đáng kể so với NS. Điều này làm vô hiệu những lợi ích mà Karatsuba được cho là truyền tải – bởi vì giảm một nửa độ dài không còn tương ứng giảm một nửa băng thông. Có thể điều này có thể được thực hiện để hoạt động bằng cách sử dụng một vài ý tưởng mới.

Nếu bạn quan tâm đến mật mã tiên tiến, kiểm tra các vai trò mở của chúng tôi ở đây.

ECDSA 2 trong 2 Nhanh, An toàn sử dụng DKLs18 ban đầu được xuất bản trên Blog Coinbase trên Phương tiện, nơi mọi người đang tiếp tục cuộc trò chuyện bằng cách đánh dấu và trả lời câu chuyện này.

>> Xem trên Coinbase