biến thể "được chia sẻ" của chuyển giao không biết 1 trong số N

trong truyền thống 1 trong số n OT, chúng tôi nghĩ Alice có một mảng $A=\{x_1,{\cdots},x_n\}$ và Bob có $idx=i\in\{1,{\cdots},n\}$. Sau khi chạy OT, Bob dựa vào $x_i$ và không có gì khác, Alice không học được gì về $i$.

Cho nên, câu hỏi của tôi: có biến thể "được chia sẻ" của chuyển khoản không biết 1 trong số N không?

Chúng tôi coi mảng và chỉ mục được truy vấn được chia sẻ bí mật giữa Alice và Bob (ví dụ., chia sẻ bí mật phụ gia). Đó là, Alice nắm giữ thị phần của mảng $A_{Alice}$ và tỷ lệ của chỉ mục được truy vấn $idx_{Alice}$; Bob nắm giữ thị phần của mảng $A_{Bob}$ và chỉ mục được truy vấn $idx_{Bob}$. Sau khi chạy OT, Alice được $[x_{idx}]_{Alice}$ và Bob được $[x_{idx}]_{Bob}$, ở đâu $([x_{idx}]_{Alice}+[x_{idx}]_{Bob})modN=x_{idx}$.

Cập nhật:

Được thúc đẩy bởi bài báo CCS2021 Hành động và ứng dụng nhóm tuyến tính không rõ ràng, trong Phần 5.1, họ đề xuất một giao thức "Oblivious Selection" (được gọi là biến thể "dùng chung" của OT) dựa trên hoán vị. Nhưng trước mỗi lần chọn ta phải thực hiện hoán vị trên mảng. Vì vậy, tôi đã đề xuất câu hỏi trên: có giao thức nào khác để chọn một phần tử từ mảng được chia sẻ tại một chỉ mục được chia sẻ không?

Alice chọn một danh sách các khóa riêng ngẫu nhiên thống nhất $\{a_i\}$. Cô ấy tính toán một danh sách các khóa công khai tương ứng $\{A_i\}$ như $\{a_iG\}$. Sau đó, cô ấy khai báo một danh sách các giá trị băm khóa công khai tương ứng $\{P_i\}$ tính như $\{hash(A_i)\}$.

$G$ là một điểm cơ sở nổi tiếng trên đường cong, và $hash()$ là một hàm băm an toàn bằng mật mã.

Bob cũng làm như vậy để Bob có khóa riêng $\{b_i\}$, có khóa công khai $\{B_i\}$và khai báo giá trị băm khóa công khai $\{Q_i\}$.

Ở giai đoạn này, Alice và Bob có thể quyết định cộng tác để xác định danh sách bí mật dùng chung của Diffie-Hellman $\{S_i\}$ như $\{a_iB_i\}$ hoặc $\{b_iA_i\}$. Tuy nhiên, họ không làm điều này.

Không mất tính tổng quát, nếu Alice muốn tìm hiểu bí mật được chia sẻ tại chỉ mục $j$ mà Bob không phát hiện ra $j$ hoặc bí mật được chia sẻ:

Alice chọn một yếu tố mù ngẫu nhiên thống nhất $r$, và gửi $X=rA_j+jH$ gửi Bob. $H$ là một điểm cơ sở nổi tiếng thứ hai trên đường cong, trong đó $h$ không được biết đến mức $hG==H$.

Bob gửi lại cho Alice danh sách $\{Z_i\}$ = $\{b_i(X-iH)\}$.

Alice bây giờ chỉ có thể bỏ bịt mắt và tìm hiểu bí mật được chia sẻ $S_j$ bằng cách tính toán $r^{-1}Z_j$. Cô ấy không thể tìm hiểu bất cứ điều gì về bất kỳ bí mật được chia sẻ nào khác, bởi vì $H$ thành phần trong danh sách phản hồi của Bob sẽ chỉ hủy bỏ tại một chỉ mục cụ thể.

Vì bí mật Diffie-Hellman này $S_j$ sẽ bằng $a_jB_j$, Alice sau đó có thể xác minh rằng hàm băm của Bob $Q_j$ phù hợp bằng cách kiểm tra $Q_j\overset{?}{=}hash(a_j^{-1}S_j)$.

Mặc dù tôi sẽ không gọi đây là một biến thể được chia sẻ của OT, nhưng chức năng được đề xuất của bạn thực sự có thể được triển khai chỉ bằng một lệnh gọi tới 1-of-$(|\mathbb{F}|^n\cdot n)$ OT vì OT đã hoàn tất. Đây $\mathbb{F}$ là lĩnh vực của $A$các mục của.
Trước tiên, hãy xem xét chức năng 2 bên khi Bob nhận chức năng $f(x,y)$, $x$ được giữ bởi Alice và $y$ của Bob. Để cho $a,b$ lần lượt là đầu vào của Alice và Bob. Alice đặt mảng $A$ như vậy mà $A[i] = f_i(a) = f(a,i)$. Sau đó, họ sử dụng một OT nơi Bob nhận được $A[b] = f_b(a) = f(a,b)$ theo yêu cầu.
Bây giờ đến chức năng của bạn. Hãy để Alice lấy mẫu ngẫu nhiên $r$, và xét hàm $$f\left(\left(A_{Alice}, idx_{Alice}\right), \left(A_{Bob}, idx_{Bob}\right)\right) = A_{Alice}[idx_{Alice} + idx_{Bob}] + A_{Bob}[idx_{Alice} + idx_{Bob}] - r$$ Tôi bỏ qua modulo cho đơn giản.
Như đã mô tả ở trên, họ sử dụng một cuộc gọi OT duy nhất để cho Bob nhận $[x_{idx}] -r$. Cùng với $r$ mà Alice nắm giữ, họ có một chia sẻ bí mật về $[x_{idx}]$.
Tôi sẽ không gọi đây là OT được chia sẻ vì nó khá khác biệt. Ví dụ: Alice và Bob đóng một vai trò giống nhau trong khi ở OT thông thường, họ có các vai trò riêng biệt (một người chọn mảng, một người chọn mục nhập).