Tra cứu giá trị an toàn bằng mật mã trong một tập hợp

Tôi đang tìm kiếm một giải pháp hay cho vấn đề có vẻ tầm thường là tìm kiếm giá trị cụ thể trong một tập hợp giá trị đã biết mà không tiết lộ giá trị mà chúng tôi tìm kiếm. Hãy để tôi mô tả nó theo một cách cổ điển:

Alice sẽ sớm tổ chức sinh nhật của cô ấy và cô ấy muốn biết liệu có ai trong lớp của cô ấy có sinh nhật cùng ngày với cô ấy không. Thật không may, người duy nhất biết ngày sinh của tất cả những người trong lớp (ngoại trừ Alice) là Malory. Làm sao Alice có thể hỏi Malory xem có ai có sinh nhật cùng ngày mà không tiết lộ ngày của chính cô ấy không?

Giả thiết:

1. Malory sẵn sàng giúp đỡ Alice và cô ấy sẽ trả lời bất kỳ câu hỏi nào một cách chính đáng. Tuy nhiên, cô ấy chỉ có thể trả lời có hoặc không.
2. Alice sẽ hỏi Malory một lần duy nhất. Malory không thể tác động đến Alice để khiến cô ấy hỏi lại câu hỏi tương tự.Mặc dù vậy, trong tương lai Alice có thể tự mình hỏi về các ngày khác nhau (ví dụ: sinh nhật của Bob).
3. Alice không cần và không muốn biết ngày sinh của mọi người trong lớp. Cô ấy muốn nhận được câu trả lời từ Malory khi đặt một câu hỏi duy nhất.

Một cách khá đơn giản để tiếp cận vấn đề này là áp dụng hàm băm. Alice băm ngày sinh của cô ấy và chuyển thông tin này cho Malory, đồng thời yêu cầu cô ấy băm ngày sinh của tất cả những người cô ấy biết và cho cô ấy biết nếu có sự trùng khớp. Vấn đề là Malory, người muốn biết ngày sinh của Alice, có thể liệt kê tất cả các ngày có thể (vì entropy của đầu vào thấp) và kiểm tra từng cái một xem có cái nào khớp với những gì Alice hỏi không. Tôi muốn loại bỏ mối đe dọa đó.

Tôi đã nghĩ đến việc áp dụng ánh xạ một-nhiều cho ngày sinh nhật. Vì một ngày có thể được biểu thị bằng nhiều giá trị, cuộc tấn công liệt kê sẽ trở nên không khả thi. Vấn đề đầu tiên là tôi không thấy có cách nào dễ dàng để Malory thực hiện phép so sánh toán học nguyên tử với chuỗi ngày tháng của cô ấy. Vấn đề thứ hai là nếu việc so sánh như vậy có thể được thực hiện, thì Malory vẫn có thể tạo một bộ mới và thực hiện lại thao tác tra cứu (nghĩa là tấn công liệt kê). Do đó, ánh xạ một-nhiều mà Alice áp dụng phải được tham số hóa bởi tính năng duy nhất của một tập hợp mà Malory sẽ tìm kiếm.

Tôi hy vọng rằng tôi đã không gây ra quá nhiều nhầm lẫn và tôi sẽ đánh giá cao bất kỳ trợ giúp, tài liệu tham khảo, đề cập nào về thuật toán hoặc các vấn đề tương tự! Tôi cũng sẽ đánh giá cao ý kiến ​​của bạn nếu bạn cho rằng vấn đề này không thể giải quyết được với các giả định đã cho! Nếu một số trong số đó không rõ ràng, hãy cho tôi biết và tôi sẽ cố gắng hết sức để làm rõ ý định của mình.

Bạn đang mô tả vấn đề của 1 trong số $n$ Chuyển giao không rõ ràng với $n=366$ nếu Alice được yêu cầu không nhận được thông tin không liên quan. Các phương pháp của Kolesnikov et al trong bài báo của họ âPRF lãng quên theo đợt hiệu quả với ứng dụng cho giao lộ riêng tưâ mang lại cảm giác về những gì có thể.

Nếu Alice chấp nhận được thông tin bổ sung, thì vấn đề là một trong truy xuất thông tin cá nhân. Bài khảo sát của Ostrovsky và Skeithâs âKhảo sát về truy xuất thông tin cá nhân trên cơ sở dữ liệu đơn: các kỹ thuật và ứng dụng â cung cấp một cái nhìn tổng quan tốt.

Thứ hai, cách tiếp cận đơn giản hơn, nhờ nhận xét của @Mikero:

Alice chọn một khóa riêng ngẫu nhiên thống nhất $b$. Sinh nhật của Alice là vào ngày $k$ngày thứ năm. Alice gửi $A = bH_p(k)$ đến Malory, nơi chức năng $H_p()$ có nghĩa là băm đầu vào và diễn giải kết quả dưới dạng điểm EC.

Malory chọn một khóa riêng ngẫu nhiên thống nhất $e$. Malory có chức năng $F_e(i)$ đầu ra nào $eH_p(i)$ nếu ít nhất một người được sinh ra vào ngày đó trong năm và nếu không thì sẽ đưa ra điểm EC được chọn ngẫu nhiên.

Đối với mỗi giá trị của $i$ như vậy mà $0\leq tôi \leq 365$, Malory gửi $F_e(i)$ đến Alice. Ngoài ra, Malory gửi $Q = eA$ đến Alice.

Alice tính toán $Z = b^{-1}Q == b^{-1}eA == b^{-1}ebH_p(k) == eH_p(k)$.

Alice sau đó kiểm tra nếu $Z$ khớp với bất kỳ trong số 366 đầu ra của $F_e(i)$ mà Malory gửi cho Alice. Nếu trùng khớp thì Alice có cùng ngày sinh với người khác.

Giải thích: Chúng tôi đã tạo một "1-OPRF", có nghĩa là một hàm giả ngẫu nhiên không rõ ràng mà Alice có thể truy vấn một lần với sự trợ giúp mù quáng của Malory, nhưng Malory có thể truy vấn nhiều lần.

PRF chỉ đơn giản là Malory làm mù một điểm EC $H_p(i)$ (ở đâu $H_p(i)$ đại diện cho một ngày cụ thể $i$ của năm dưới dạng điểm EC), với khóa riêng của anh ấy $e$, bằng cách tính toán $eH_p(i)$. Do vấn đề nhật ký rời rạc của đường cong elip, không người quan sát nào (kể cả Alice) có thể dự đoán đầu ra của $eH_p(i)$ bất cứ gì $i$ không biết bí mật $e$. Điều này có nghĩa là khi không có ai sinh vào một ngày cụ thể, Alice không thể biết rằng Malory đã gửi một điểm EC ngẫu nhiên thay vì đầu ra thực của PRF, bởi vì đầu ra của PRF là không thể đoán trước đối với Alice.

Alice che khuất thông tin đầu vào của mình đối với PRF bằng cách chọn một yếu tố che khuất $b$ và gửi $bH_p(k)$ đến Malory thay vì gửi (và do đó tiết lộ) $k$. Alice bỏ mù câu trả lời bằng cách đảo ngược phép nhân với $b$, và do đó có thể truy vấn PRF mà Malory không cần biết về đầu vào mà Alice đang sử dụng.

Hậu quả là Malory đã gửi một danh sách các điểm EC cho Alice chỉ bao gồm đầu ra thực sự của PRF cho những ngày trong năm mà ít nhất một người khác được sinh ra vào ngày đó. Ngoài ra, Alice đã có thể truy vấn PRF một cách mù quáng về đầu ra của ngày sinh nhật cụ thể của cô ấy và có thể xem liệu kết quả đó có xuất hiện trong danh sách các đầu ra PRF khả dĩ mà Malory gửi cho cô ấy hay không.

Malory chưa học $k$, và Alice không thể biết được điều gì khác ngoài việc liệu cô ấy có cùng ngày sinh với ít nhất một người khác hay không.

Một cách tiếp cận là làm 1-trong-n quên chuyển. Malory sẽ gửi cho Alice một danh sách gồm 366 boolean được mã hóa (để cho phép sinh nhật vào ngày 29 tháng 2), trong đó mỗi boolean sẽ biểu thị liệu có ai có sinh nhật vào ngày đó trong năm hay không.Alice sẽ chỉ có thể giải mã một trong 366 booleans và do đó sẽ chỉ có thể biết liệu có ai khác có sinh nhật vào ngày đó trong năm hay không.

Bài viết trên wikipedia mà tôi đã liên kết đến trong đoạn trên tham khảo một số cách tiếp cận triển khai để đạt được chuyển giao không biết 1 lần. Đây là một cách tiếp cận mà tôi vừa mới nghĩ ra (với sự ghi nhận của @IlmariKaronen vì một cải tiến rất tao nhã):

Alice được sinh ra vào ngày $k$ của năm, ở đâu $0\leq k\leq 365$. Alice gửi khóa công khai $P = xG-kH$ đến Malory, nơi $x$ là một khóa riêng vô hướng ngẫu nhiên thống nhất. $H$ được tính như $H = H_p(G)$, trong đó chức năng $H_p()$ có nghĩa là băm giá trị và diễn giải kết quả dưới dạng điểm EC. Lựa chọn $H$ theo cách này có nghĩa là nhật ký rời rạc của $H$ w.r.t. $G$ là không thể biết được, tức là $h$ không thể được biết như vậy mà $H==hG$.

Malory tính toán 366 khóa công khai $\{Q\}$ của hình thức $Q_i=P+iH$ cho tất cả các giá trị của $i$ ở đâu $0\leq i\leq 365$.

Khóa riêng tương ứng với mỗi khóa chung $Q_i$ sẽ là $q_i == x - kh + ih == x+(i-k)h$.

Vì chúng tôi đã chứng minh rằng $h$ là không thể biết được, điều này có nghĩa là $q_i$ sẽ chỉ có thể được biết bởi Alice khi $i==k$, trong trường hợp $q_k$ sẽ bằng $x$.

Do đó, Malory sẽ tính toán được 366 khóa công khai mà Malory có thể chắc chắn rằng Alice chỉ có thể biết khóa riêng tương ứng với một trong số chúng.

Cho mỗi ngày trong năm $i$, Malory sử dụng lược đồ El Gamal như sau: Malory chọn một đại lượng vô hướng ngẫu nhiên đều $e_i$, và cung cấp cho Alice cặp $(E_i, F_i)$ ở đâu $E_i = e_iG$, $F_i = e_iQ_i + H_p(v_i)$ và ở đâu $v_i$ sẽ được chỉ định là $0$ nếu không có ai có sinh nhật vào ngày đó trong năm, hoặc như $1$ nếu ít nhất một người có sinh nhật vào ngày đó trong năm.

Để giải mã $v_k$, Alice tính toán $V_k = F_k - xE_k$. Alice sau đó kiểm tra xem $V_k\overset{?}{=}H_p(0)$ hoặc $V_k\overset{?}{=}H_p(1)$, và do đó biết nếu $v_k$ Là $0$ hoặc $1$. Điều này hoạt động bởi vì $q_k==x$ và $Q_k==xG$, và vì thế $xE_k==x\cdot e_kG==e_k\cdot xG==e_kQ_k$.

Alice sẽ chỉ có thể xác định nếu người khác được sinh ra vào ngày $k$ của năm, và Malory sẽ không thể xác định $k$.

Có một cuốn tiểu thuyết Truy xuất thông tin cá nhân với các hệ thống đồng hình hoàn toàn,

• 2014 Băng thông hiệu quả PIR từ NTRU Yarkin Doröz, B. Sunar, Ghaith Hammouri

Đây là Lược đồ mã hóa riêng có thể có giá trị tại chỉ mục $i$ từ mảng trên máy chủ bán trung thực. Máy chủ không học được gì và chỉ trả về giá trị tại chỉ mục $i$. Chúng tôi có thể sửa đổi điều này như;

1. Mallory mã hóa tất cả các ngày sinh nhật hiện có $b_i$, $0 \leq i \leq 366 $ với khóa công khai FHE của Alice. (Mã hóa của $366\cdot 8$ bit, không nhất thiết phải là tất cả các ngày, các ngày sinh tồn tại là đủ và điều này giúp tiết kiệm không gian trong các tập hợp lớn.

   $$c_i = \operatorname{FHE-Enc}(A_{pub}, b_i)$$

   Nếu chúng tôi sử dụng dựa trên bit (HLibe, TFHE) thì mỗi $c_i$ là một kích thước mảng 8.

2. Alice gửi sinh nhật của cô ấy $A$ được mã hóa bằng khóa công khai của cô ấy tới Mallory (Mã hóa 8-bit).

   $$a = \operatorname{FHE-Enc}(A_{pub}, A)$$

3. Mallory thực hiện Mạch đẳng thức FHE vào mỗi ngày sinh nhật được mã hóa

   $$t_i = \operatorname{FHE-So sánh}(A_{pub}, c_i,a)$$

4. Mallory HOẶC kết quả với FHE sử dụng cách tiếp cận cây nhị phân để giảm độ sâu của mạch (có thể tính tổng thay vì HOẶC) và trả lại kết quả cho Alice.

   $$o = \operatorname{FHE-OrAll}(A_{pub}, [t_0,\ldots,t_n])$$

5. Alice giải mã kết quả chút với khóa riêng của họ;

   $$ b = \operatorname{FHE-Dec}(A_{priv})$$

   • nếu $b=1$ thì có ít nhất một sinh viên có ngày $A$
   • nếu $b=0$ sau đó không có sinh viên với ngày $A$.

những gì được đảm bảo;

1. Mallory không thể tìm hiểu dữ liệu được truy vấn là gì $A$ vì nó được mã hóa bằng FHE - bảo mật ngữ nghĩa tồn tại.
2. Mallory không thể lấy dữ liệu được truy vấn từ kết quả vì lý do tương tự như trên; từ $(A,o)$.
3. Mạch không tiết lộ bất cứ điều gì về phần bên trong của dữ liệu ngoài chức năng được tính toán - mạch tính toán sự tồn tại của dữ liệu mà không tiết lộ kết quả.
4. Alice chỉ biết được sự tồn tại của ngày sinh nhật mà thôi! Alice được chỉ một bit $b$, tồn tại hay không. Điều này không trả về số ngày sinh bằng nhau.
5. Alice chỉ truy vấn một lần.
6. Mallory chỉ gửi mã hóa một bit $b$! Do đó, một chương trình khá hiệu quả về băng tần.

1. Mallory chuẩn bị một mảng bit có kích thước 366 được khởi tạo bằng 0. $$B = [b_0,b_1,\ldots,b_{366}] = 0$$

2. Mallory đặt ngày sinh nhật hiện có thành 1. Thích; $$B = [0,0,1,\ldots,0] $$

3. Mallory mã hóa mảng bit bằng khóa công khai của Alice (khóa công khai FHE) và nhận được một mảng khác có kích thước 366.

   $$c_i = \operatorname{FHE-Enc}(A_{pub}, B[i]) \;\; \text{cho }\; 0\leq i \leq 366 $$

4. Alice chuẩn bị một mảng bit khác có kích thước 366 trong đó chỉ có ngày sinh nhật của cô ấy được đặt thành 1 phần còn lại được đặt thành 0. $$A = [0,0,0,\ldots,1,\ldots,0] $$

5. Tương tự với Mallory, Alice tạo mảng bằng khóa chung của cô ấy và gửi mảng kết quả tới Mallory.

   $$a_i = \operatorname{FHE-Enc}(A_{pub}, A[i]) \;\; \text{cho }\; 0\leq i \leq 366 $$

6. Mallory thực thi thành phần hoạt động FHE-AND một cách khôn ngoan trên các mảng được mã hóa. $$c_i = \operatorname{FHE-And}(A_{pub}, A[i], B[i])$$

7. Mallory HOẶC bit của mảng kết quả và trả lại kết quả cho Alice.

   $$b = \operatorname{FHE-OrAll}(A_{pub}, [c_0,\ldots,c_{366}])$$

8. Alice giải mã kết quả chút với khóa riêng của họ;

   $$ b = \operatorname{FHE-Dec}(A_{priv})$$

   • nếu $b=1$ thì có ít nhất một sinh viên có ngày $A$
   • nếu $b=0$ sau đó không có sinh viên với ngày $A$.

những gì được đảm bảo;

1. Giống như sơ đồ cơ bản.
2. Lần này thay vì mã hóa 9-bit, Alice mã hóa 366-bit (tăng ~40 lần chi phí/thời gian gửi ban đầu)
3. Mặt khác, Mallory đã nhận được rất nhiều cải tiến về thời gian và bộ nhớ
   1. Không cần một hoạt động bình đẳng FHE nặng nề.
   2. Kích thước của bản mã được lưu trữ đã giảm ~40.
4. Mặt khác, kết quả vẫn là mã hóa 1 bit.
5. Đề án này tiết kiệm rất nhiều thời gian cho quá trình này.