Tính toán đa bên (MPC, Multi-Party Computation)

1. Tổng quan

A. Định nghĩa

Giao thức mật mã trong đó nhiều bên tham gia không tin tưởng lẫn nhau, mỗi bên giữ bí mật đầu vào của mình, cùng nhau chỉ tính toán và thu được kết quả của một hàm đã thỏa thuận trước. Nói gọn là "giấu đầu vào, chỉ chia sẻ kết quả".

Thí nghiệm tư duy của MPC thường được giải thích bằng "bài toán triệu phú". Đó là bài toán hai người giàu muốn biết ai giàu hơn mà không tiết lộ số tài sản của mình cho đối phương; MPC được dùng khi, như vậy, cần thu được kết quả tính toán trên dữ liệu mà không để lộ dữ liệu gốc cho bên thứ ba hay cả đối phương. Khác với cách truyền thống gom dữ liệu về một chỗ để tính, MPC khác biệt căn bản ở chỗ cùng tính toán mà không cần gom dữ liệu.

B. Nguyên lý

Ý tưởng cốt lõi là chia đầu vào thành các mảnh (Share) và phân tán. Mỗi bên chia đầu vào của mình thành nhiều mảnh và phân phát cho nhau giữ, được thiết kế sao cho chỉ với một mảnh riêng lẻ thì hoàn toàn không biết được bản gốc (ví dụ chia bí mật s bằng số ngẫu nhiên r thành s−r và r để phân phát). Sau đó các bên thực hiện phép cộng·nhân ngay trên trạng thái mảnh, và cuối cùng gộp các mảnh kết quả lại để chỉ khôi phục kết quả cuối. Phép cộng dễ vì mỗi bên chỉ cần cộng mảnh của mình, còn phép nhân cần thêm truyền thông (Beaver triple, v.v.) nên chi phí lớn — chi phí phép nhân này là biến số then chốt của hiệu năng MPC.

C. Đặc điểm·mô hình bảo mật

Độ an toàn của MPC được biểu thị bằng mức chịu được thông đồng. Dưới ngưỡng (t) bên tham gia gom mảnh lại cũng không khôi phục được bản gốc, và cường độ bảo mật khác nhau tùy mô hình kẻ tấn công.

Ở đây mô hình Semi-honest giả định các bên tuân thủ giao thức một cách trung thực nhưng cố dòm đầu vào của người khác qua thông tin trao đổi, và tương đối nhẹ. Ngược lại, mô hình Malicious giả định các bên vi phạm và thao túng chính giao thức, nên có thêm thủ tục kiểm chứng và nặng hơn nhiều. Khác biệt giả định này là điểm xuất phát của đánh đổi hiệu năng-bảo mật.

2. Các loại kỹ thuật MPC

flowchart LR
  MPC --> SS[Chia sẻ bí mật<br/>Secret Sharing]
  MPC --> GC[Mạch bị xáo trộn<br/>Garbled Circuit]
  MPC --> OT[Oblivious Transfer]
  MPC --> HE[Kết hợp mã hóa đồng cấu]

Các kỹ thuật hiện thực MPC được phân chia theo cách biểu diễn phép tính. Chia sẻ bí mật chia giá trị thành nhiều mảnh và xử lý bằng phép toán số học, mạnh ở tính toán nhiều bên (n bên) và phép toán số quy mô lớn. Mạch bị xáo trộn (garbled circuit) biểu diễn phép tính thành mạch logic rồi mã hóa toàn bộ mạch để đánh giá an toàn giữa hai bên. OT là viên gạch cơ bản trong đó bên gửi truyền đi mà không biết bên nhận đã lấy giá trị nào trong nhiều giá trị, là nền tảng của mạch bị xáo trộn. Kết hợp mã hóa đồng cấu là dạng lai trộn HE — cho phép tính toán trên bản mã — với MPC để giảm lượng truyền thông.

3. Dịch vụ xác thực dựa trên MPC

flowchart LR
  U[Khóa riêng của người dùng] --> S1[Mảnh máy chủ 1]
  U --> S2[Mảnh máy chủ 2]
  U --> S3[Mảnh máy chủ 3]
  S1 & S2 & S3 --> T[Chữ ký ngưỡng<br/>Threshold Signature]
  T --> R[Kết quả ký·xác thực]

Trường hợp thực tiễn tiêu biểu của MPC là quản lý khóa phân tán. Trong xác thực truyền thống, khóa riêng được lưu ở một chỗ, và nếu điểm đó bị xuyên thủng thì mất tất cả (điểm lỗi đơn). Xác thực dựa trên MPC sinh khóa riêng phân tán thành các mảnh chưa từng được gộp làm một (DKG) ngay từ đầu, và khi cần ký thì t/n máy chủ hợp tác tính toán một phần bằng mảnh của mình, tạo ra chữ ký mà không khôi phục khóa riêng hoàn chỉnh ở bất kỳ đâu (chữ ký ngưỡng). Do đó dù một hai máy chủ bị rò rỉ, nếu dưới ngưỡng thì khóa vẫn an toàn.

Ví dụ, ví MPC cho tài sản số không lưu chính khóa riêng (seed), nên giảm về mặt cấu trúc rủi ro mất·bị đánh cắp của ví phần cứng truyền thống.

4. Các lưu ý và hàm ý

Rào cản thực tiễn lớn nhất của MPC là hiệu năng. Mỗi phép nhân đều có truyền thông qua lại giữa các bên, và trong mô hình Malicious còn thêm gánh nặng kiểm chứng, nên chi phí tính toán·truyền thông lớn. Do đó then chốt là giảm độ trễ trực tuyến bằng tối ưu mạch tính toán và tiền xử lý (sinh trước các mảnh ngẫu nhiên ở giai đoạn ngoại tuyến). Dù vậy, MPC là trục cốt lõi của PET (công nghệ tăng cường bảo vệ quyền riêng tư), được dùng trong các kịch bản nhiều tổ chức cùng phân tích mà không chia sẻ dữ liệu gốc — phát hiện gian lận chung trong ngành tài chính, hợp tác dữ liệu y tế giữa các bệnh viện, AI học trong khi bảo vệ thông tin cá nhân. Hơn nữa, MPC bổ trợ lẫn nhau với mã hóa đồng cấu·quyền riêng tư vi phân·học liên kết, phát triển theo hướng dung hòa giữa khai thác và bảo vệ dữ liệu.

Tóm tắt một câu: MPC là công nghệ mật mã cho phép nhiều bên cùng tính toán chỉ ra kết quả trong khi giữ bí mật đầu vào, được hiện thực bằng chia sẻ bí mật·mạch bị xáo trộn·OT, và được ứng dụng trong xác thực phân tán·ví MPC — phân tán khóa riêng để tạo chữ ký ngưỡng không có điểm lỗi đơn — cùng phân tích chung bảo toàn quyền riêng tư.