Beaver Triples: Giải pháp mật mã học giúp tính toán bảo mật mà không cần lộ dữ liệu gốc

Bạn và nhóm bạn đang lên kế hoạch đi ăn tối. Thông thường, bạn là người luôn trả tiền cho cả nhóm. Nhưng gần đây, thị trường không thuận lợi, nên mọi người cần bắt đầu tự chi trả.

Tuy nhiên, không phải ai cũng dư dả tài chính, và một người trong nhóm vẫn là sinh viên. Dù hoàn cảnh bên ngoài khó khăn, nhóm bạn vẫn muốn tụ tập và thưởng thức một bữa ăn ngon. Để có một bữa tối vui vẻ, mọi người cần thống nhất chọn một nhà hàng. Nhưng không phải ai cũng thích cùng một loại ẩm thực và giá cả ở các nhà hàng cũng khác nhau. Với tình hình tài chính và sở thích ăn uống khác nhau, bạn muốn tìm một cách tôn trọng quyền riêng tư để nhóm có thể đạt được đồng thuận về nơi sẽ đến.

Mô phỏng khái niệm bảo mật và tính toán

Vấn đề về quyền riêng tư trong việc ra quyết định

Là một nhà mật mã học, bạn biết rằng mình có thể tận dụng chia sẻ bí mật (secret sharing) để giải quyết vấn đề này. Bạn đưa ra một quy tắc tính điểm đơn giản để xác định nhà hàng mà mọi người sẽ đến: Đối với một nhà hàng j, người i sẽ gửi hai giá trị:

• $a_{ij}$: Mức độ tôi có thể chi trả cho nhà hàng này (khả năng tài chính).
• $f_{ij}$: Mức độ tôi muốn ăn ở nhà hàng này (sở thích).

Mỗi $a_{ij}$ và $f_{ij}$ được chấm điểm từ thang điểm 0-10. Điểm của từng người cho nhà hàng sẽ là $s_{ij} = a_{ij} \times f_{ij}$. Điểm tổng hợp của nhóm cho nhà hàng j sẽ là $S_{j} = \Sigma s_{ij}$.

Cuối cùng, ít nhất 2 bạn bè sẽ công bố điểm số cho nhà hàng và sau đó quyết định nơi sẽ tổ chức bữa tối. Chúng ta muốn giữ điểm $a_{ij}$ và $f_{ij}$ của mỗi người riêng tư để giữ hòa khí trong nhóm chat.

Giả sử nhóm có 4 người: Alice, Ben, Chloe và Stoffel. Nhóm đang phân vân giữa 3 nhà hàng: A, B và C. Mỗi người gửi một cặp giá trị $(a, f)$. Mục tiêu là không công bố các con số này cho cả nhóm. Mục tiêu là sử dụng chúng để tính toán điểm số nhà hàng một cách riêng tư và chỉ công bố điểm số tổng hợp cuối cùng.

Thách thức trong phép nhân với chia sẻ bí mật

Sử dụng ký pháp chia sẻ bí mật, mọi đầu vào riêng tư đều được chuyển đổi thành các phần chia sẻ (shares). Thay vì Alice công bố điểm khả năng chi trả của mình cho Nhà hàng A, nhóm nhận được một phần chia sẻ của giá trị đó, ký hiệu là $[a_{ij}]$. Tương tự cho điểm sở thích là $[f_{ij}]$.

Chúng ta muốn tính toán các phần chia sẻ của điểm cá nhân $[s_{ij}] = [a_{ij}f_{ij}]$, sau đó là các phần chia sẻ của điểm nhóm $[S_{j}] = \Sigma [s_{ij}]$.

Vấn đề phát sinh khi thực hiện phép nhân. Nếu chúng ta nhân trực tiếp các đa thức đại diện cho các phần chia sẻ, bậc của đa thức sẽ tăng lên. Điều này có nghĩa là thay vì cần ít nhất 2 bạn bè để khôi phục điểm cuối cùng, chúng ta sẽ cần ít nhất 3 người, gần như là cả nhóm. Điều này đi ngược lại yêu cầu ban đầu.

Vậy làm thế nào để tính toán $[x][y]$ mà không làm tăng ngưỡng (threshold) cần thiết để tái thiết?

Giải pháp: Beaver Triples

Để giải quyết vấn đề này, chúng ta sử dụng một kỹ thuật gọi là Beaver Triples (Bộ ba Beaver), được đặt theo tên của tác giả Don Beaver.

Hãy tưởng tượng chúng ta muốn tính diện tích hình chữ nhật $xy$. Chúng ta có thể chia hình chữ nhật lớn này thành các hình chữ nhật nhỏ hơn bên trong. Nếu chọn ngẫu nhiên một điểm $(a, b)$ bên trong hình chữ nhật $xy$, chúng ta có thể biểu diễn $x$ và $y$ dưới dạng: $x = a + (x-a)$ $y = b + (y-b)$

Diện tích $xy$ có thể được viết lại dưới dạng tổng của các diện tích nhỏ hơn: $xy = ab + b(x-a) + a(y-b) + (x-a)(y-b)$

Đặt $d = x-a$, $e = y-b$ và $c = ab$. Khi đó: $xy = c + bd + ae + de$

Trong bối cảnh chia sẻ bí mật, nếu chúng ta có các bộ ba được tạo trước $[a], [b], [c]$ (trong đó $c=ab$), chúng ta có thể tính toán $[xy]$ bằng công thức: $[xy] = [c] + [bd] + [ae] + [de]$

Chìa khóa ở đây là chúng ta sẽ công bố giá trị của $d$ và $e$ để sử dụng như các số công khai. Tuy nhiên, điều này có làm lộ $x$ và $y$ không?

Câu trả lời là không, miễn là $a$ và $b$ được tạo ngẫu nhiên và chỉ sử dụng một lần duy nhất. Vì $a$ và $b$ đóng vai trò là các "mặt nạ" ngẫu nhiên che giấu $x$ và $y$, việc công bố $d$ và $e$ không cung cấp bất kỳ thông tin có ý nghĩa nào về dữ liệu gốc.

Quy trình tính toán bảo mật

Áp dụng vào ví dụ bữa tối

Giả sử có một dịch vụ cung cấp Beaver Triples được tạo ra từ entropy của vệ tinh. Mọi người trong nhóm đều nhận được các phần chia sẻ của cùng một bộ ba Beaver $[a], [b], [c]$. Không ai biết giá trị thực của $a, b, c$, họ chỉ nắm giữ các phần chia sẻ.

Vì có 4 người và 3 nhà hàng, chúng ta cần 12 điểm cá nhân, tương ứng với 12 bộ ba Beaver mới. Mỗi bộ ba chỉ được dùng một lần.

Hãy xem xét điểm số của Ben cho Nhà hàng B. Ben gửi $a=8$ (khả năng chi trả) và $f=8$ (sở thích). Điểm của Ben nên là $8 \times 8 = 64$.

Nhóm có các phần chia sẻ $[8]$ và $[8]$. Giả sử bộ ba Beaver được sử dụng có các giá trị cơ bản là $a=5, b=6, c=30$ (lưu ý: đây là các biến mặt nạ, không phải điểm của Ben).

Nhóm tính toán:

• $[d] = [8] - [5]$
• $[e] = [8] - [6]$

Sau đó, nhóm công bố $d=3$ và $e=2$. Điều này an toàn vì 5 và 6 là các mặt nạ ngẫu nhiên vẫn được giữ bí mật.

Bây giờ mọi người có thể tính toán: $[xy] = [c] + d[b] + e[a] + de$ $[64] = [30] + 3[6] + 2[5] + 3 \times 2$ $[64] = [30] + [18] + [10] + 6 = [64]$

Nhóm giờ đây có các phần chia sẻ của điểm Ben cho Nhà hàng B là $[64]$, mà Ben không cần công bố khả năng chi trả hay sở thích của mình.

Quy trình này lặp lại cho mọi người và mọi nhà hàng. Vì chia sẻ bí mật có tính chất tuyến tính, nhóm có thể tính toán điểm số cho từng nhà hàng bằng cách cộng các phần chia sẻ lại:

• Nhà hàng A: $[148]$
• Nhà hàng B: $[212]$
• Nhà hàng C: $[123]$

Cuối cùng, 2 thành viên được chỉ định (ví dụ Alice và Chloe) sẽ công bố các phần chia sẻ của điểm số cuối cùng. Sử dụng nội suy Lagrange, nhóm tái thiết được điểm số: Nhà hàng B có 212 điểm, cao nhất. Bữa tối đã được quyết định.

Kết luận

Beaver Triples cho phép thực hiện tính toán đa phương an toàn (MPC) một cách hiệu quả. Dữ liệu thô vẫn ở nơi thuộc về nó (trên thiết bị của người dùng). Việc tính toán diễn ra riêng tư. Và trách nhiệm pháp lý về dữ liệu không còn nằm trên vai bạn.

Đây là một bước tiến quan trọng trong lĩnh vực bảo mật và điện toán đám mây, mở đường cho các ứng dụng nơi quyền riêng tư dữ liệu là ưu tiên hàng đầu mà không làm giảm khả năng phân tích và cộng tác.