Phần toán bạn cần
Vì sao điều này quan trọng Các công cụ quyền riêng tư trong mô-đun này, như tìm ra khách hàng chung mà không trao đổi danh sách hay công bố thống kê bảo vệ từng người, dựa trên ba mẩu toán nhỏ. Bạn không cần bằng toán học. Bạn cần số học đồng hồ, một cảm nhận về xác suất, và ý tưởng rằng nhiễu ngẫu nhiên triệt tiêu trong các nhóm lớn. Bài này cho bạn đúng những thứ đó, kèm Python để thử.
1. Số học đồng hồ
Bây giờ là 22:00. 5 giờ sau là mấy giờ? Không phải 27:00: đồng hồ quay vòng, nên là 03:00. Bạn đã lấy 22 + 5 = 27 và giữ phần dư sau khi chia cho 24.
Số học modulo: số học trong đó các con số quay vòng sau khi đạt tới một kích thước cố định, gọi là modulus. "27 mod 24" là 3, phần dư sau khi chia 27 cho 24. Trong Python toán tử lấy dư là %: 27 % 24 là 3.
Quay vòng giữ các con số ở kích thước cố định dù bạn cộng hay nhân bao nhiêu, đó là điều làm nó hữu ích cho mật mã. Python cũng có một hàm có sẵn nhanh cho "lũy thừa, rồi quay vòng": pow(base, exponent, modulus).
print((22 + 5) % 24) # 3
print(pow(3, 4, 7)) # 3*3*3*3 = 81, and 81 % 7 = 4
print(pow(5, 200, 23)) # instant, even though 5 to the 200 is huge2. Dễ một chiều, khó chiều kia
Trộn sơn vàng và sơn xanh dương thành xanh lá thì dễ. Tách xanh lá trở lại thành đúng phần vàng và xanh dương thì gần như không thể. Một số phép toán hoạt động theo cùng cách.
Chọn một modulus nguyên tố lớn P và một số h. Tính pow(h, a, P) cho một a bí mật là tức thì. Nhưng chỉ cho biết đáp án, tìm lại a chậm đến mức với các số đủ lớn không ai làm được. Tính chất một chiều này gọi là bài toán logarit rời rạc.
Thêm một sự thật, và nó là động lực cho các bài thực hành tiếp theo. Lũy thừa a rồi lũy thừa b cho cùng kết quả như lũy thừa b rồi lũy thừa a, vì cả hai đều bằng h mũ a nhân b:
P = 1019 # a small prime: fine for learning, useless for security
h, a, b = 42, 123, 456
print(pow(pow(h, a, P), b, P) == pow(pow(h, b, P), a, P)) # TrueNhư hai ổ khóa trên một chiếc hộp, thứ tự bạn khóa chúng không quan trọng. Hai người có thể mỗi người thêm bí mật riêng và kết thúc ở cùng một chỗ mà không bao giờ để lộ bí mật của mình.
3. Xác suất trong một đoạn
Một xác suất là một con số từ 0 (không bao giờ) tới 1 (luôn luôn). Một đồng xu công bằng ra mặt ngửa với xác suất 0.5. Khi hai việc độc lập, xác suất cả hai xảy ra là tích: hai lần ngửa liên tiếp là 0.5 x 0.5 = 0.25. Giá trị kỳ vọng là trung bình dài hạn: tung một con xúc xắc công bằng nhiều lần và trung bình tiến về 3.5.
4. Nhiễu triệt tiêu trong một đám đông
Nhiễu (noise): một lượng ngẫu nhiên được cố ý thêm vào một giá trị thật, để giá trị chính xác bị giấu đi. Nếu nhiễu có khả năng lên hay xuống như nhau, nó trung bình về không qua nhiều giá trị.
Đây là một mẹo khảo sát kinh điển gọi là trả lời ngẫu nhiên hóa (randomised response). Bạn muốn biết bao nhiêu người đã làm một việc đáng xấu hổ. Mỗi người bí mật tung một đồng xu. Ngửa: trả lời thật. Sấp: tung lần nữa và trả lời "có" nếu ngửa và "không" nếu sấp. Mọi câu "có" đơn lẻ đều có thể chỉ là do đồng xu, nên không câu trả lời nào chứng minh được gì về người đó.
Vậy mà tổng của đám đông vẫn hữu ích. Nếu tỉ lệ thật là p, tỉ lệ câu trả lời "có" bạn kỳ vọng là 0.5 x p + 0.25. Nên nếu 35% nói có, p khoảng (0.35 - 0.25) / 0.5 = 0.2, tức 20%. Đám đông càng lớn, ước tính càng gần, vì nhiễu ngẫu nhiên co lại so với tổng khi đám đông lớn lên.
import random
rng = random.Random(1) # seeded: the same "random" numbers every run
truth = [rng.random() < 0.2 for _ in range(10000)] # 20% really did it
answers = []
for did_it in truth:
if rng.random() < 0.5:
answers.append(did_it) # heads: tell the truth
else:
answers.append(rng.random() < 0.5) # tails: random yes or no
yes = sum(answers) / len(answers)
print(round((yes - 0.25) / 0.5, 3)) # close to 0.2Nhiễu dùng trong quyền riêng tư vi sai, gọi là nhiễu Laplace, là một phiên bản mượt của cùng ý tưởng đó: thường nhỏ, đôi khi lớn hơn, khả năng lên hay xuống như nhau. Thang (scale) của nó quyết định nó thường lớn cỡ nào.
Trong các ngôn ngữ khác
% của JavaScript hoạt động theo cùng cách với số dương, và số lớn dùng BigInt (viết kèm một n). Không có hàm lũy thừa modulo có sẵn, nên đây là vòng lặp chuẩn:
function powMod(base, exp, mod) {
let result = 1n;
base %= mod;
while (exp > 0n) {
if (exp & 1n) result = (result * base) % mod;
base = (base * base) % mod;
exp >>= 1n;
}
return result;
}
console.log(powMod(3n, 4n, 7n)); // 4nTrong Go, new(big.Int).Exp(base, exp, mod) từ math/big làm cùng việc đó.
Một hiểu lầm phổ biến
"Thêm nhiễu làm dữ liệu vô dụng." Với giá trị của một người, đúng vậy, và đó chính là mục đích. Với một nhóm lớn, nhiễu phần lớn triệt tiêu, nên tổng và trung bình vẫn hữu ích. Công nghệ quyền riêng tư sống trong khoảng trống đó: mờ với cá nhân, sắc nét với đám đông.
Tóm tắt
- Số học modulo quay vòng các con số quanh một modulus; Python dùng
%vàpow(b, e, m). - Lũy thừa một số mũ bí mật dễ một chiều và gần như không thể gỡ lại, và thứ tự của hai số mũ bí mật không quan trọng.
- Các xác suất độc lập nhân với nhau; giá trị kỳ vọng là trung bình dài hạn.
- Nhiễu ngẫu nhiên giấu cá nhân nhưng triệt tiêu trong các nhóm lớn, đó là cách trả lời ngẫu nhiên hóa hoạt động.
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ờ.
Trình duyệt này đang chặn cookie cho learn.floati.life, nên các bài học bạn đã hoàn thành tại đây không thể mở theo thứ tự. Hãy cho phép cookie cho trang web này và tải lại trang.