Chương trình học Bài 136 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

Tổng hợp an toàn

Vì sao điều này quan trọng Một ứng dụng thể dục muốn tổng số bước đi trong một thành phố; một hãng làm bàn phím muốn biết một từ được gõ thường xuyên cỡ nào trên mọi điện thoại. Trong mỗi trường hợp công ty cần một con số từ nhiều thiết bị. Tổng hợp an toàn cho phép nó biết tổng đó mà không bao giờ thấy giá trị của một người nào, và nó đơn giản đến bất ngờ.

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.

Mẹo lương

Ba người bạn muốn biết lương trung bình của họ mà không ai để lộ lương của mình. Người thứ nhất cộng một số ngẫu nhiên lớn vào lương của cô và thì thầm kết quả cho người thứ hai. Anh cộng lương của mình và thì thầm tiếp. Người thứ ba cộng lương của cô và chuyển lại. Người thứ nhất trừ đi số ngẫu nhiên của cô, và tổng hiện ra. Mỗi lời thì thầm trông như một số ngẫu nhiên với người nghe.

Tổng hợp an toàn (secure aggregation): tính một tổng (hay trung bình) giá trị của nhiều người sao cho không giá trị đơn lẻ nào bị lộ cho ai, kể cả máy chủ thu thập chúng.

Chia sẻ bí mật cộng (additive secret sharing): cắt một số bí mật thành vài phần (share) trông ngẫu nhiên khi đứng riêng nhưng cộng lại bằng bí mật. Bất kỳ phần nào, hay bất kỳ nhóm nào thiếu ít nhất một phần, đều không để lộ gì về bí mật.

Các phần hoạt động ra sao

Để chia số 7.350 thành ba phần, chọn hai số ngẫu nhiên và chọn số thứ ba sao cho cả ba cộng lại bằng 7.350. Với số học quay vòng (modulus M, ở đây là 2 mũ 32, hơn 4 tỉ một chút), mỗi phần đứng riêng là một số ngẫu nhiên phân bố đều:

M = 2 ** 32
s1, s2 = 3919211450, 120775123           # random
s3 = (7350 - s1 - s2) % M                # whatever makes it add up
print((s1 + s2 + s3) % M)                # 7350

Vì sao quay vòng? Không có nó, một phần đôi khi sẽ âm hay gần bí mật một cách đáng ngờ. Có nó, mọi giá trị phần có khả năng như nhau bất kể bí mật là gì, nên một phần đơn lẻ không mang thông tin nào.

Nhiều thiết bị, vài máy chủ

Giờ mỗi điện thoại chia số bước của nó thành một phần cho mỗi máy chủ và gửi phần 1 tới máy chủ 1, phần 2 tới máy chủ 2, và cứ thế. Mỗi máy chủ cộng các phần nó nhận được. Tổng của mỗi máy chủ vẫn trông ngẫu nhiên. Chỉ khi tổng của các máy chủ được cộng lại với nhau thì tổng thật của thành phố mới hiện ra. Chừng nào các máy chủ không gộp các phần thô của một điện thoại, giá trị của không điện thoại nào bị thấy.

Phiên bản trong thế giới thật

Các hệ thống dùng để huấn luyện mô hình trên nhiều điện thoại (gọi là học liên kết, federated learning) dùng một biến thể khéo hơn với một máy chủ: các cặp thiết bị thỏa thuận những mặt nạ ngẫu nhiên triệt tiêu nhau khi mọi thứ được cộng lại, cộng thêm các bước để xử lý những điện thoại rớt mạng giữa chừng. Ý tưởng cốt lõi là cái bạn sẽ xây: những mảnh trông ngẫu nhiên chỉ có nghĩa khi ở cùng nhau.

Tổng hợp an toàn không làm được gì

Tổng bị lộ chính xác. Nếu chỉ hai người đóng góp và một người biết giá trị của mình, họ có thể trừ nó đi và biết giá trị của người kia. Nếu bản thân tổng là nhạy cảm, hãy thêm cả nhiễu quyền riêng tư vi sai vào nó. Hai công cụ phối hợp tốt: tổng hợp giấu đầu vào, DP giấu ảnh hưởng của mỗi người lên đầu ra.

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

Việc chia trong JavaScript, dùng quay vòng 32 bit với >>> 0 và nguồn ngẫu nhiên an toàn của trình duyệt:

function split(value, n) {
  const shares = Array.from(crypto.getRandomValues(new Uint32Array(n - 1)));
  const sum = shares.reduce((a, b) => (a + b) >>> 0, 0);
  shares.push((value - sum) >>> 0);
  return shares;
}

Và trong Rust, nơi wrapping_sub trên một u32 làm việc quay vòng giùm bạn:

let last = value.wrapping_sub(shares.iter().fold(0u32, |a, &b| a.wrapping_add(b)));

Tóm tắt

  • Tổng hợp an toàn để lộ một tổng nhưng không để lộ đóng góp đơn lẻ nào.
  • Chia sẻ bí mật cộng chia một giá trị thành những phần trông ngẫu nhiên cộng lại bằng nó, dùng số học quay vòng.
  • Mỗi máy chủ chỉ thấy các phần trông ngẫu nhiên; chỉ mọi tổng máy chủ cùng nhau mới cho đáp án.
  • Bản thân tổng bị lộ chính xác, nên hãy kết hợp nó với nhiễu DP khi tổng có thể làm lộ ai đó.
Đến lượt bạn

Viết ba hàm, dùng M (2 mũ 32) từ thế giới luyện tập. split(value, n, rng) trả về một list n phần: n - 1 phần đầu từ rng.randrange(M), phần cuối bằng (value - sum(shares)) % M. combine(shares) trả về sum(shares) % M. aggregate(values, n_servers, rng) chia mỗi giá trị bằng split, cộng phần j vào server_totals[j] (mod M), và trả về một tuple (total, server_totals) trong đó total = combine(server_totals).

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ờ.