Tin nhanh

2020 ngày 21 tháng 3
Xem tất cả bài viết

Đặc biệt cảm ơn Dankrad Feist để xem xét

Các mạch bị cắt xén là một nguyên thủy mã hóa khá cũ và đơn giản một cách đáng ngạc nhiên; chúng hoàn toàn có thể là hình thức đơn giản nhất của “tính toán đa bên” (MPC) có mục đích chung để khiến bạn phải bận tâm.

Đây là thiết lập thông thường cho chương trình:

• Giả sử rằng có hai bên, Alice và Bob, muốn tính toán một hàm nào đó f(alice_inputs, bob_inputs), lấy đầu vào từ cả hai bên. Alice và Bob đều muốn biết kết quả của phép tính f, nhưng Alice không muốn Bob tìm hiểu đầu vào của cô ấy và Bob không muốn Alice tìm hiểu đầu vào của mình. Lý tưởng nhất là cả hai sẽ không học được gì ngoại trừ đầu ra của f.
• Alice thực hiện một thủ tục đặc biệt (“cắt xén”) để mã hóa một mạch (có nghĩa là một tập hợp các cổng AND, OR…) để đánh giá chức năng f. Cô chuyển các đầu vào, cũng được mã hóa theo cách tương thích với mạch mã hóa, cho Bob.
• Bob sử dụng một kỹ thuật gọi là “1-of-2 oblivious transfer” để tìm hiểu dạng mã hóa của dữ liệu đầu vào của chính anh ấy mà không cho Alice biết anh ấy đã nhận được dữ liệu đầu vào nào.
• Bob chạy mạch được mã hóa trên dữ liệu được mã hóa và nhận được câu trả lời rồi chuyển nó cho Alice.

Các gói mật mã bổ sung có thể được sử dụng để bảo vệ lược đồ chống lại việc Alice và Bob gửi thông tin sai và đưa ra câu trả lời sai cho nhau; vì đơn giản, chúng tôi sẽ không đi sâu vào những vấn đề đó ở đây, mặc dù có thể nói rằng “quấn ZK-SNARK xung quanh mọi thứ” là một giải pháp (nhiệm vụ khá nặng nề và dưới mức tối ưu!) hoạt động tốt.

Vậy sơ đồ cơ bản hoạt động như thế nào? Hãy bắt đầu với một mạch:

Đây là một trong những ví dụ đơn giản nhất về một mạch không hoàn toàn tầm thường thực sự làm một việc gì đó: đó là một bộ cộng hai bit. Nó nhận đầu vào là hai số ở dạng nhị phân, mỗi số có hai bit và xuất ra số nhị phân ba bit là tổng.

Bây giờ, hãy mã hóa mạch. Đầu tiên, đối với mọi đầu vào, chúng tôi tạo ngẫu nhiên hai “nhãn” (nghĩ: số 256 bit): một để biểu thị đầu vào đó là 0 và nhãn còn lại để biểu thị đầu vào đó là 1. Sau đó, chúng tôi cũng làm tương tự cho mọi dây trung gian, không bao gồm các dây đầu ra. Lưu ý rằng dữ liệu này không phải là một phần của “việc cắt xén” mà Alice gửi cho Bob; cho đến nay đây chỉ là thiết lập.

Bây giờ, đối với mỗi cổng trong mạch, chúng tôi thực hiện như sau. Đối với mọi tổ hợp đầu vào, chúng tôi đưa vào “sự cắt xén” mà Alice cung cấp cho Bob nhãn của đầu ra (hoặc nếu nhãn của đầu ra là đầu ra “cuối cùng”, thì đầu ra sẽ được mã hóa trực tiếp bằng khóa được tạo bằng cách băm các nhãn đầu vào dẫn đến đầu ra đó cùng nhau. Để đơn giản, thuật toán mã hóa của chúng tôi chỉ có thể là enc(out, in1, in2) = out + hash(k, in1, in2) ở đâu k là chỉ số của cổng (đó có phải là cổng đầu tiên trong mạch, thứ hai, thứ ba không?). Nếu bạn biết nhãn của cả hai đầu vào và bạn có phần bị cắt xén, thì bạn có thể tìm hiểu nhãn của đầu ra tương ứng, bởi vì bạn chỉ có thể tính toán hàm băm tương ứng và trừ nó ra.

Đây là sự cắt xén của cổng XOR đầu tiên:

Lưu ý rằng chúng tôi đang bao gồm (dạng mã hóa của) 0 và 1 trực tiếp, bởi vì đầu ra của cổng XOR này là đầu ra trực tiếp cuối cùng của chương trình. Bây giờ, hãy nhìn vào cổng AND ngoài cùng bên trái:

Ở đây, đầu ra của cổng chỉ được sử dụng làm đầu vào cho các cổng khác, vì vậy chúng tôi sử dụng nhãn thay vì bit để ẩn các bit trung gian này khỏi bộ đánh giá.

“Cắt xén” mà Alice sẽ cung cấp cho Bob chỉ là mọi thứ trong cột thứ ba cho mỗi cổng, với các hàng của mỗi cổng được sắp xếp lại (để tránh tiết lộ liệu một hàng đã cho tương ứng với 0 hay 1 trong bất kỳ dây nào). Để giúp Bob biết giá trị nào cần giải mã cho mỗi cổng, chúng ta sẽ sử dụng một thứ tự cụ thể: đối với mỗi cổng, hàng đầu tiên trở thành hàng có cả hai nhãn đầu vào là số chẵn, ở hàng thứ hai, nhãn thứ hai là số lẻ, ở hàng thứ ba hàng nhãn đầu tiên là số lẻ và ở hàng thứ tư, cả hai nhãn đều là số lẻ (chúng tôi đã cố tình chọn các nhãn trước đó để mỗi cổng sẽ có nhãn chẵn cho một đầu ra và nhãn lẻ cho đầu ra kia). Chúng tôi cắt xén mọi cổng khác trong mạch theo cách tương tự.

Nói chung, Alice gửi cho Bob bốn số ~256 bit cho mỗi cổng trong mạch. Hóa ra bốn là không tối ưu; xem tại đây để biết một số tối ưu hóa về cách giảm số này xuống còn ba hoặc thậm chí hai số đối với cổng AND và số không (!!) đối với cổng XOR. Lưu ý rằng những tối ưu hóa này dựa trên một số thay đổi, ví dụ:. sử dụng XOR thay vì cộng và trừ, mặc dù điều này vẫn nên được thực hiện để bảo mật.

Khi Bob nhận được mạch, anh ấy hỏi Alice về các nhãn tương ứng với đầu vào của cô ấy và anh ấy sử dụng một giao thức gọi là “chuyển giao không biết 1 trong 2” để hỏi Alice về các nhãn tương ứng với đầu vào của chính anh ấy mà không tiết lộ cho Alice biết đầu vào của anh ấy là gì. Là. Sau đó, anh ta lần lượt đi qua các cổng trong mạch, phát hiện ra các dây đầu ra của từng cổng trung gian.

Giả sử đầu vào của Alice là hai dây bên trái và cô ấy cho (0, 1) và đầu vào của Bob là hai dây bên phải và anh ấy cho (1, 1). Đây là mạch có nhãn một lần nữa:

• Lúc đầu, Bob biết các nhãn 6816, 3621, 4872, 5851
• Bob đánh giá cổng đầu tiên. Anh ta biết 6816 và 4872, vì vậy anh ta có thể trích xuất giá trị đầu ra tương ứng với (1, 6816, 4872) (xem bảng ở trên) và trích xuất bit đầu ra đầu tiên, 1
• Bob đánh giá cổng thứ hai. Anh ta biết 6816 và 4872, vì vậy anh ta có thể trích xuất giá trị đầu ra tương ứng với (2, 6816, 4872) (xem bảng trên) và trích xuất nhãn 5990
• Bob đánh giá cổng thứ ba (XOR). Anh ta biết 3621 và 5851, và học 7504
• Bob đánh giá cổng thứ tư (OR). Anh ta biết 3621 và 5851, và học 6638
• Bob đánh giá cổng thứ năm (AND). Anh ta biết 3621 và 5851, và học 7684
• Bob đánh giá cổng thứ sáu (XOR). Anh ta biết 5990 và 7504, và học bit đầu ra thứ hai, 0
• Bob đánh giá cổng thứ bảy (AND). Anh ta biết 5990 và 6638, và học 8674
• Bob đánh giá cổng thứ tám (OR). Anh ta biết 8674 và 7684, và học bit đầu ra thứ ba, 1

Và vì vậy Bob biết được đầu ra: 101. Và trong hệ nhị phân 10 + 11 thực sự bằng 101 (các bit đầu vào và đầu ra đều được cho theo thứ tự từ nhỏ nhất đến lớn nhất trong mạch, đó là lý do tại sao đầu vào 10 của Alice được biểu thị là (0, 1) trong mạch), vì vậy nó đã hoạt động!

Lưu ý rằng phép cộng là một cách sử dụng mạch bị cắt xén khá vô nghĩa, bởi vì Bob biết 101 chỉ có thể trừ đi đầu vào của chính mình và nhận được 101 – 11 = 10 (đầu vào của Alice), vi phạm quyền riêng tư. Tuy nhiên, nói chung, các mạch bị cắt xén có thể được sử dụng cho các tính toán không thể đảo ngược và do đó, không vi phạm quyền riêng tư theo cách này (ví dụ: người ta có thể tưởng tượng một phép tính trong đó đầu vào của Alice và đầu vào của Bob là câu trả lời của họ cho một bài kiểm tra tính cách và đầu ra là một bit duy nhất xác định xem thuật toán có cho rằng chúng tương thích hay không; một bit thông tin đó sẽ không cho phép Alice hoặc Bob biết bất cứ điều gì về các câu trả lời bài kiểm tra riêng lẻ của nhau).

1 trong 2 chuyển giao rõ ràng

Bây giờ chúng ta hãy nói nhiều hơn về chuyển giao quên 1 trong 2, kỹ thuật này mà Bob đã sử dụng để lấy nhãn từ Alice tương ứng với đầu vào của chính anh ta. Vấn đề là thế này. Tập trung vào bit đầu vào đầu tiên của Bob (thuật toán cho bit đầu vào thứ hai giống nhau), Alice có nhãn tương ứng với 0 (6529) và nhãn tương ứng với 1 (4872). Bob có bit đầu vào mong muốn: 1. Bob muốn tìm hiểu nhãn chính xác (4872) mà không cho Alice biết rằng bit đầu vào của anh ấy là 1. Giải pháp tầm thường (Alice chỉ gửi cho Bob cả 6529 và 4872) không hiệu quả vì chỉ có Alice muốn từ bỏ một trong hai nhãn đầu vào; nếu Bob nhận được cả hai nhãn đầu vào, điều này có thể làm rò rỉ dữ liệu mà Alice không muốn từ bỏ.

Đây là một giao thức khá đơn giản sử dụng các đường cong elip:

1. Alice tạo ra một điểm đường cong elip ngẫu nhiên, H.
2. Bob tạo ra hai điểm, P1 và P2với yêu cầu là P1 + P2 số tiền để H. Bob chọn một trong hai P1 hoặc là P2 được G * k (tức là một điểm mà anh ta biết khóa riêng tư tương ứng). Lưu ý rằng yêu cầu đó P1 + P2 = H đảm bảo rằng Bob không có cách nào để tạo ra P1 và P2 sao cho anh ta biết khóa riêng tương ứng cho. Điều này là bởi vì nếu P1 = G * k1 và P2 = G * k2 nơi Bob biết cả hai k1 và k2sau đó H = G * (k1 + k2)do đó có nghĩa là Bob có thể trích xuất logarit rời rạc (hoặc “khóa riêng tương ứng”) cho Hđiều này có nghĩa là tất cả mật mã đường cong elip đã bị hỏng.
3. Alice xác nhận P1 + P2 = Hvà mã hóa v1 Dưới P1 và v2 Dưới P2 sử dụng một số sơ đồ mã hóa khóa công khai tiêu chuẩn (ví dụ: El-Gamal). Bob chỉ có thể giải mã một trong hai giá trị, bởi vì anh ấy biết khóa riêng tương ứng với nhiều nhất một trong hai giá trị đó. (P1, P2)nhưng Alice không biết cái nào.

Điều này giải quyết vấn đề; Bob học một trong hai nhãn dây (6529 hoặc 4872), tùy thuộc vào bit đầu vào của anh ấy là gì và Alice không biết Bob đã học nhãn nào.

Các ứng dụng

Các mạch bị cắt xén có khả năng hữu ích cho nhiều thứ hơn là chỉ tính toán 2 trên 2. Ví dụ: bạn có thể sử dụng chúng để thực hiện các tính toán đa bên có độ phức tạp tùy ý với số lượng người tham gia cung cấp đầu vào tùy ý, có thể chạy trong một số vòng tương tác không đổi. Tạo một mạch bị cắt xén là hoàn toàn song song; bạn không cần phải hoàn thành việc cắt xén một cổng trước khi có thể bắt đầu cắt xén các cổng phụ thuộc vào cổng đó. Do đó, bạn có thể đơn giản là có một phép tính nhiều bên lớn với nhiều người tham gia tính toán một loạt các cổng của một mạch và xuất bản các nhãn tương ứng với đầu vào của họ. Bản thân các nhãn là ngẫu nhiên và do đó không tiết lộ gì về đầu vào, nhưng sau đó bất kỳ ai cũng có thể thực hiện mạch bị cắt xén đã xuất bản và tìm hiểu đầu ra “rõ ràng”. Xem ở đây để biết ví dụ gần đây về giao thức MPC sử dụng cắt xén làm thành phần.

Tính toán nhiều bên không phải là bối cảnh duy nhất mà kỹ thuật chia tách tính toán thành một phần có thể song song hóa hoạt động trên dữ liệu bí mật, theo sau là một phần tuần tự có thể chạy rõ ràng là hữu ích và các mạch bị cắt xén không phải là kỹ thuật duy nhất cho hoàn thành việc này. Nói chung, tài liệu về mã hóa ngẫu nhiên bao gồm nhiều kỹ thuật phức tạp hơn. Nhánh toán học này cũng hữu ích trong các công nghệ như mã hóa chức năng và che giấu.