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

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:

$$E(m_1).E(m_2) = E(m_1+m_2)$$

Đâ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=p.q\)

3. Tính \(\lambda \) là bộ số chung nhỏ nhất của \((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 \(μ = (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

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)\)

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 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, C_3, \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 \(i\) sẽ lấy bản mã tổng \(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:

$$\begin{align*} T = PD_1.PD_2.PD_3. \dots (\bmod n^2)\\ T = (C_{sum}^{s_1}).(C_{sum}^{s_2}).(C_{sum}^{s_3}). \dots (\bmod n^2) \\ T = (C_{sum}^{s_1+s_2+s_3+\dots}) = C_{sum}^\lambda (\bmod n^2) \end{align*}$$

Giá trị \(T\) này 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