Chương trình học Bài 135 trên tổng số 156 · Công nghệ quyền riêng tư vượt ra ngoài việc chặn
Công nghệ quyền riêng tư vượt ra ngoài việc chặn

Private Set Intersection

Vì sao điều này quan trọng Các công ty thường muốn biết họ có chung những khách hàng nào, cho một ưu đãi chung hay để đo xem một quảng cáo có hiệu quả không. Cách dễ là trao đổi danh sách khách hàng, nghĩa là email của bạn rơi vào cơ sở dữ liệu của một công ty khác. Private Set Intersection cho phép họ tìm phần giao nhau mà không bên nào trao đi danh sách của mình. Biết nó hoạt động ra sao giúp bạn phân biệt quyền riêng tư thật với câu "chúng tôi chỉ chia sẻ email đã băm".

Mật mã dạy học, không an toàn: các con số trong các bài thực hành của mô-đun này đủ nhỏ để đọc và tính ngẫu nhiên có seed để việc chấm điểm lặp lại được. Các hệ thống thật dùng những thư viện đã kiểm định và các con số lớn hơn nhiều. Đừng bao giờ chép mã dạy học vào một sản phẩm.

Vấn đề

Một cửa hàng và một ứng dụng mỗi bên có một danh sách email khách hàng. Họ muốn các email có trên cả hai danh sách, và không gì khác: cửa hàng không được biết những người dùng khác của ứng dụng, và ứng dụng không được biết những khách hàng khác của cửa hàng.

Giao của tập hợp (set intersection): các phần tử mà hai danh sách có chung. Private Set Intersection (PSI): một cách để hai bên tính nó trong khi không để lộ gì khác về danh sách của mình.

Vì sao "cứ băm nó" thất bại

Hàm băm (hash): một hàm biến văn bản thành một chuỗi xáo trộn có độ dài cố định (SHA-256 là một hàm phổ biến). Cùng đầu vào luôn cho cùng đầu ra, và bạn không thể chạy nó ngược lại trực tiếp.

"Chúng tôi trao đổi email đã băm, nên không ai thấy email thật" nghe có vẻ an toàn. Nhưng email đoán được. Bất kỳ ai nắm một danh sách email có khả năng có thể băm mọi phỏng đoán và tìm chỗ khớp, như thử mọi chìa trên một chùm chìa lớn. Hàm naive_reverse của bạn sẽ làm đúng điều đó với 200 email tổng hợp của thế giới luyện tập. Băm chỉ giấu được dữ liệu khi đầu vào không thể đoán, và email, số điện thoại và tên đều đoán được.

Mẹo hai ổ khóa

Hãy nhớ từ bài toán: đặt bí mật a vào, rồi bí mật b, cho cùng kết quả như b rồi a. Hình dung mỗi email là một chiếc hộp. Alice đặt ổ khóa riêng của mình lên mỗi hộp của cô và gửi chúng cho Bob. Bob thêm ổ khóa của anh và gửi chúng lại. Bob cũng khóa các hộp của chính mình và gửi chúng cho Alice, người thêm ổ khóa của cô. Giờ mọi hộp đều có cả hai ổ khóa, và hai hộp có cùng email bên trong trông giống hệt nhau, bất kể ổ khóa nào được đặt trước.

Bằng các con số, với nhóm luyện tập từ watched.leg7a_privacy (P, hash_to_group, random_secret):

  1. Alice gửi blind(alice_items, a): mỗi phần tử được băm vào nhóm rồi lũy thừa a.
  2. Bob lũy thừa chúng với b (reblind) và gửi lại theo cùng thứ tự.
  3. Bob gửi blind(bob_items, b).
  4. Alice lũy thừa các giá trị của Bob với a. Bất kỳ giá trị khóa hai lần nào của cô xuất hiện trong tập khóa hai lần của Bob là một phần tử chung. Vì cô giữ thứ tự, cô biết mỗi cái là phần tử nào của mình.

Vì sao điều này an toàn ở nơi việc băm thất bại? Để thử một phỏng đoán, bạn cần cả hai bí mật, và mỗi bên giữ bí mật của mình. Bob chỉ bao giờ thấy các giá trị của Alice có bí mật của cô trên đó, chúng trông như các số ngẫu nhiên.

Diffie-Hellman PSI: tên của giao thức này, theo ý tưởng trao đổi khóa năm 1976 mà nó mượn (hai bên kết hợp các số mũ bí mật). Các phiên bản thật dùng đường cong elliptic (một loại nhóm khác, có cùng tính chất "thứ tự không quan trọng" và các con số ngắn hơn nhiều) và việc băm cẩn thận.

Bản thân đáp án là một sự tiết lộ

Ngay cả PSI hoàn hảo cũng cho Alice biết một người cụ thể là khách hàng của Bob. Nếu Bob là một phòng khám hay một người tư vấn nợ, điều đó là nhạy cảm. Thường thì một công ty chỉ cần biết bao nhiêu khách hàng là chung. Trong PSI cardinality Bob xáo trộn câu trả lời của mình ở bước 2, nên Alice có thể đếm số chỗ khớp nhưng không biết chúng thuộc về phần tử nào của mình. Hãy yêu cầu ít nhất những gì trả lời được câu hỏi.

Trong các ngôn ngữ khác

Bước làm mù trong JavaScript với BigInt (dùng một hàm trợ giúp powMod như cái trong bài toán):

const blind = (items, secret) => items.map(x => powMod(hashToGroup(x), secret, P));
const reblind = (values, secret) => values.map(v => powMod(v, secret, P));

Và trong Go với math/big:

func reblind(values []*big.Int, secret, p *big.Int) []*big.Int {
    out := make([]*big.Int, len(values))
    for i, v := range values {
        out[i] = new(big.Int).Exp(v, secret, p)
    }
    return out
}

Với sản phẩm thật, hãy dùng một thư viện PSI đã được kiểm toán thay vì tự viết.

Tóm tắt

  • Email đã băm dễ đảo ngược bằng một danh sách phỏng đoán, nên "chúng tôi chỉ chia sẻ hàm băm" không phải là quyền riêng tư.
  • Diffie-Hellman PSI khóa hai lần mọi phần tử bằng hai bí mật mà thứ tự không quan trọng, nên chỗ khớp hiện ra mà không danh sách nào bị lộ.
  • Giữ thứ tự để lộ những phần tử nào khớp; xáo trộn (PSI cardinality) chỉ để lộ bao nhiêu.
  • Bản thân phần giao là dữ liệu cá nhân, nên hãy yêu cầu ít nhất những gì trả lời được câu hỏi.
Đến lượt bạn

Viết năm hàm. naive_reverse(hashes, candidates) trả về list đã sắp xếp các ứng viên có digest hex SHA-256 (hashlib.sha256(c.encode()).hexdigest()) nằm trong hashes. blind(items, secret) trả về [pow(hash_to_group(x), secret, P) for x in items]. reblind(values, secret) lũy thừa mỗi giá trị với secret modulo P, giữ thứ tự. psi(alice_items, bob_items, a_secret, b_secret) theo bốn bước của bài dùng blind và reblind, và trả về list đã sắp xếp các phần tử của Alice mà Bob cũng có. psi_cardinality(alice_items, bob_items, a_secret, b_secret, rng) làm tương tự nhưng xáo trộn câu trả lời của Bob bằng rng.shuffle và chỉ trả về số phần tử chung.

Bạn thấy vấn đề gì trong bài học này? Hãy báo cáo nó · Hỏi về bài học này

Bài tập này sẽ sớm mở.

Hoàn thành bài học trước đó để mở khóa bài này. Toàn bộ khóa học là miễn phí, không cần tài khoản, và bạn có thể đọc bài học này ngay bây giờ.