Multi Party Computing với đồng cấu Paillier

Trong kỷ nguyên số, dữ liệu là tài sản vô giá. Làm thế nào chúng ta có thể khai thác giá trị từ dữ liệu mà không làm lộ những thông tin nhạy cảm bên trong? Bài viết này mình xin giới thiệu Tính toán Đa bên Bảo mật (Multi-Party Computation - MPC) và Mã hóa Đồng cấu (Homomorphic Encryption) như là một giải pháp.

Tính toán Đa bên Bảo mật (MPC) là gì?

Về cốt lõi, MPC là một lĩnh vực của mật mã học giải quyết bài toán sau:

Làm thế nào để một nhóm các bên (người, công ty, tổ chức) có thể cùng nhau tính toán một hàm số dựa trên các đầu vào riêng tư của họ, sao cho kết quả cuối cùng được tiết lộ cho mọi người, nhưng không một thông tin riêng tư nào bị rò rỉ trong suốt quá trình?

Ví dụ kinh điển là "Bài toán Lương trung bình": An, Bình, và Chi muốn biết mức lương trung bình của cả ba, nhưng không ai muốn nói cho người khác biết mình kiếm được bao nhiêu. MPC chính là giao thức cho phép họ tìm ra con số trung bình mà vẫn giữ kín tuyệt đối thu nhập cá nhân.

Mã hóa đồng cấu cộng tính Paillier

Hệ mã Paillier là một hệ mã bất đối xứng nổi tiếng với một đặc tính cực kỳ hữu ích: Tính đồng cấu cộng (Additively Homomorphic).

Tính chất này có thể được mô tả bằng một công thức kỳ diệu:

Nếu bạn có bản mã của hai thông điệp m1, m2 ký hiệu là E(m1) và E(m2), bạn có thể nhân hai bản mã này lại với nhau để có được bản mã tổng của hai số đó

Đây chính là chìa khóa để giải quyết bài toán tính lương trung bình. Mọi người sẽ mã hóa lương của mình, gửi các bản mã đến một nơi để nhân lại với nhau, và kết quả sẽ là bản mã của tổng lương, sẵn sàng để được giải mã.

Quy trình mã hóa Paillier

1. Chọn hai số nguyên tố $p,q$

2. Tính $n=pq$

3. Tính $\lambda$ là bội số chung nhỏ nhất của $(p-1), (q-1)$, nghĩa là $\lambda = lcm (p-1,q-1)$. Trường hợp đơn giản: $\lambda=(p-1)(q-1)$

4. Chọn $g$: Một cách chọn đơn giản và phổ biến là $g=n+1$

5. Tính $\mu$: được tính bằng $\mu = (L(g^{\lambda} \pmod{n^2}))^{-1} \pmod{n}$, trong đó $L(x,n) = (x-1)/n$

6. Khóa công khai $(n,g)$, khóa bí mật $(\lambda, \mu)$

Mã hóa

Để mã hóa một thông điệp $m$ thành bản mã $C$

1. Chọn số ngẫu nhiên $0<r<n$

2. Tính bản mã $C = g^m.r^n (\bmod n^2)$

Sự tồn tại của $r$ nhằm đảm bảo mỗi lần mã hóa cùng một tin nhắn $m$ sẽ tạo ra một bản mã $C$ khác nhau.

Giải mã

Để giải mã, ta tính $m = L(C^\lambda (\mod n^2)). \mu (\mod n)$

Bàn luận về công thức giải mã

• Bản mã: $c = g^m \cdot r^n \pmod{n^2}$

• Khóa bí mật: $\lambda = \text{lcm}(p-1, q-1)$, $\mu = (L(g^{\lambda} \pmod{n^2}))^{-1} \pmod{n}$

• $g=n+1$

Như vậy:

Khi tính theo $\pmod{n^2}$, tất cả các số hạng chứa $n^2, n^3, \dots$ đều bằng $0$. Do đó:

Tiếp tục, đối với thành phần $r^n \pmod {n^2}$ ta có

Theo định lý Carmichael (một dạng mở rộng của định lý Fermat nhỏ), với mọi $r$ nguyên tố cùng nhau với $n$ và , thì $r^\lambda \equiv 1 \pmod n$:

Đây là một tính chất nâng cao của nhóm nhân $\mathbb Z^*_{n^2}$

Tiếp tục, tính $c^{\lambda} \pmod {n^2}$:

Áp dụng các kết quả thu được ta có:

• $g^{m\lambda} = (1+n)^{m\lambda} \equiv 1 + m\lambda n \pmod{n^2}$

• $r^{n\lambda} \equiv 1 \pmod{n^2}$

Vậy:

Xét hàm $\displaystyle L(u) = \frac {u-1} n$ với $L(c^\lambda \pmod{n^2})$ ta có:

Tương tự:

Mà $\mu = (L(g^{\lambda} \pmod{n^2}))^{-1} \pmod{n}$, do đó:

Đây là lý do tại sao công thức giải mã lại như vậy.

Loại bỏ người thứ ba, không ai được cầm khóa bí mật

Trong quy trình cơ bản trên, có một điểm yếu: người nắm giữ Khóa Bí mật có thể giải mã mọi thứ. Để xây dựng một hệ thống thực sự an toàn, chúng ta cần phân tán khóa thành nhiều phần.

Tạo Khóa Phân tán (Distributed Key Generation - DKG)

Thay vì một người tạo và giữ toàn bộ Khóa Bí mật, tất cả các bên sẽ cùng tham gia vào một giao thức:

1. Tạo ra một Khóa công khai $(n,g)$ chung cho cả nhóm

2. Phân chia Khóa bí mật. Ví dụ, $\lambda$ sẽ được chia ra thành các "mảnh" $s_1,s_2,\dots$ sao cho $\lambda=s_1+s_2+\dots$ mỗi người sẽ chỉ giữ khóa $s_i$ của riêng mình và không hề biết các mảnh của người khác.

Lúc này không một cá nhân nào có đủ thông tin để tự mình giải mã.

Giải mã Ngưỡng (Threshold Decryption)

1. Tính toán trên bản mã: Giống như trước, các bản mã của từng người $(C_1, C_2, \dots)$ được nhân lại với nhau trong không gian công khai để có được bản mã của tổng: $C_{sum} = C_1 \cdot C_2 \cdot C_3\cdot \dots \pmod{n^2}$

2. Giải mã cục bộ: Mỗi người thứ $i$ sẽ lấy bản mã tổm $C_{sum}$ và dùng mảnh khóa bí mật $s_i$ của mình để tính một "mảnh giải mã cục bộ" $PD_i = C_{sum}^{s_i} (\mod n^2)$

Kết hợp để giải mã: Các mảnh giải mã cục bộ này được công khai và nhân lại với nhau. Phép toán này có một kết quả toán học rất đẹp:

Giá trị $T$ chính là $C_{sum}^{\lambda} \pmod{n^2}$ là bước tính toán cốt lõi trong công thức giải mã Paillier. Từ đây, bất kỳ ai cũng có thể áp dụng các bước cuối cùng của công thức giải mã để tìm ra tổng lương cuối cùng.

Bằng cách này, "bí mật" về tổng lương đã được tính toán thành công mà không một cá nhân nào có đủ quyền năng để xem trộm dữ liệu riêng tư của người khác. Đây chính là bản chất của một hệ thống MPC an toàn và không cần tin tưởng.

Demo