Tôi không thấy bất cứ nơi nào trên trang đó mô tả chuyển giao không đáng kể theo cách bạn mô tả.
Chuyển giao rõ ràng:
- Alice cầm hai sợi dây $x_0, x_1$
- Bob giữ một chút $b$
- Bob học $x_b$ nhưng không học được gì về $x_{1-b}$
- Alice không học được gì về $b$
Mạch bị cắt xén:
- Khi Alice đá vụn một mạch boolean $f$, cô ấy có được một bộ sưu tập lớn các bản mã $F$ ("mạch bị cắt xén") và cô ấy cũng học được hai phím (nhãn) trên mỗi dây của mạch. Trên dây #$i$ cô ấy học $W_i^0$ đại diện cho sai trên dây đó và $W_i^1$ đại diện cho true trên dây đó.
- Nếu Bob biết mạch bị cắt xén $F$ và cho mỗi đầu vào dây điện $i$ của mạch anh ta biết chính xác một trong số $\{ W_i^0, W_i^1\}$ sau đó anh ấy có thể đánh giá mạch bị cắt xén để tìm hiểu chính xác một nhãn trên mỗi dây của mạch (không chỉ dây đầu vào). Anh ta học nhãn dây "đúng" (nghĩa là nhãn tương ứng với hành vi của $f$) trên mỗi dây, tùy theo nhãn đầu vào mà anh ấy bắt đầu.
- Khi Bob đánh giá mạch bị cắt xén, anh ấy không biết liệu mình có đang giữ $W_i^0$ hoặc $W_i^1$ cho bất kỳ dây $i$. Nói cách khác, anh ta không biết bất kỳ dây nào trong mạch mang đúng hay sai. Anh ta đánh giá mạch một cách "mù quáng".
Nếu Alice & Bob muốn đánh giá một chức năng bằng cách sử dụng các mạch bị cắt xén, thì Alice sẽ cắt xén mạch và gửi mạch bị cắt xén $F$ gửi Bob.
Nhưng Bob cũng cần phải học, vì mỗi đầu vào dây điện $i$ trong mạch, chính xác một trong số $\{ W_i^0, W_i^1\}$.
Cả Alice & Bob đều có đầu vào cho tính toán này.
Nếu dây #$i$ là một trong các dây đầu vào của Alice, thì cô ấy chỉ cần gửi một dây "đúng" từ $\{W_i^0, W_i^1\}$, vì cô ấy biết cả hai điều này và cô ấy biết bit đầu vào của mình trên dây đó.
Nếu dây #$i$ là một trong những dây đầu vào của Bob, phải có cách để Bob chọn để tìm hiểu chính xác một trong những $\{W_i^0, W_i^1\}$.
Vì Bob chọn giữa các giá trị này theo thông tin đầu vào riêng tư của anh ấy, nên Alice không nên biết anh ấy đã chọn giá trị nào.
Chuyển giao không rõ ràng được sử dụng cho chính xác bước này.
Đối với dây đầu vào #$i$ thuộc về đầu vào của Bob, Alice cung cấp $W_i^0$ và $W_i^1$ đến một trường hợp chuyển giao không biết gì và Bob chọn cái nào trong số này để tìm hiểu.
Có các biến thể của chuyển giao không biết trong đó Alice có $N$ chuỗi và Bob chọn một trong số chúng để học.
Nếu Alice & Bob muốn tính một hàm rất đơn giản $f(a,b)$, nơi chỉ có $N$ đầu vào có thể cho Bob ($b \in \{1, \ldots, N\}$), thì vâng, họ có thể sử dụng chuyển giao không biết gì để tính toán hàm trực tiếp như bạn đề xuất mà không có bất kỳ mạch bị cắt xén nào.
Alice sử dụng $f(a,1), f(a,2), \ldots, f(a,N)$ như đầu vào để chuyển quên.
Bob chọn học $b$thứ trong số này, đó là $f(a,b)$.
Điều này chỉ hoạt động khi $N$ là rất nhỏ, bởi vì nó yêu cầu giao tiếp và tính toán tỷ lệ thuận với $N$.
Nhớ lấy $N$ là số lượng đầu vào có thể có cho Bob.
Nếu có một mạch mà Bob có $k$ dây đầu vào, sau đó anh ta có $N=2^k$ đầu vào có thể.
Do đó, thông thường Bob có quá nhiều đầu vào để sử dụng phương pháp này.
Trả lời bài đăng đã chỉnh sửa:
Cách tiếp cận của bạn đối với vấn đề của triệu phú không thực sự rõ ràng, vì vậy tôi phải đoán một vài điều.
Nó không hoạt động để tiết lộ một phần thông tin về đầu vào trong giao thức.
Nếu Alice có đầu vào 1, cô ấy sẽ không thể phân biệt giữa Bob có đầu vào 2 và đầu vào $2^{20}$ -- nhưng hai đầu vào này sẽ trông rất khác nhau nếu đầu ra của phép so sánh được tiết lộ rõ ràng.
Với suy nghĩ này, bạn đề xuất mã hóa mọi thứ bằng cách nào đó. Nhưng về cơ bản, bạn đang đề xuất tìm kiếm nhị phân. Tìm kiếm nhị phân yêu cầu bạn biết kết quả của các phép so sánh trước đó để quyết định phép so sánh nào sẽ thực hiện tiếp theo. Nếu bạn đang mã hóa kết quả so sánh thì sẽ không rõ cách tiếp tục trong các vòng tiếp theo.
Một vấn đề lớn với đề xuất của bạn là nó vốn đã tuần tự. Các bên không thể biết đầu vào của họ cho vòng tiếp theo cho đến khi nhận được đầu ra từ vòng trước.
Vì vậy đối với $k$ so sánh bạn cần $\Theta(k)$ vòng giao tiếp.
So sánh điều này với cách tiếp cận dựa trên GC luôn có số vòng liên lạc không đổi.
Tuy nhiên, tôi nghĩ rằng bạn đang có một kết nối khái niệm tốt.
Hãy tưởng tượng chức năng $f$ rất nhỏ nên có thể viết được toàn bộ bảng chân trị của $f$.
Hãy cùng nói nào $f : \{1,2,3,4\}^2 \to \{0,1\}$.
Alice chọn các khóa mã hóa ngẫu nhiên $A_1, \ldots, A_4$ và $B_1, \ldots, B_4$.
Cô cũng mã hóa bảng chân lý của $f$ như
$$\textsf{Enc}( A_1 \| B_1, f(1,1)), ~~
\textsf{Enc}( A_1 \| B_2, f(1,2)), ~~\ldots,
\textsf{Enc}( A_i \| B_j, f(i,j)), ~~\ldots$$
Để đánh giá $f$ trên đầu vào riêng của họ, Alice có thể gửi tất cả các bản mã này cho Bob.
Cô ấy có thể gửi đúng $A_i$ giá trị và họ có thể sử dụng 1 trong 4 OT để cho Bob học đúng $B_j$ giá trị.
Bây giờ Bob có thể giải mã chính xác một trong những bản mã này, bản mã này sẽ chứa đầu ra chính xác của $f$.
Các mạch bị cắt xén chỉ là những gì bạn nhận được khi thực hiện cấu trúc đơn giản này, nhưng thay vì mã hóa đầu ra chức năng cuối cùng, bạn mã hóa các khóa cho một tiện ích khác cùng loại.
