Chống thông tin giả bằng Mật mã
(Hay phương pháp "Minh bạch hoá các hoạt động trong hộp đen")
Nghĩ đến Mật mã (Cryptography) nếu chúng ta chỉ nghĩ rằng nó là mã hoá khoá công khai, chữ ký điện tử thì chúng ta đang sống ở những năm 80s, lạc hậu gần nửa thế kỷ. Mật mã ngày nay giúp làm những điều mà những năm 80s không thể hình dung.
Chẳng hạn chống thông tin giả, fake news.
Một hình ảnh bằng ngàn lời nói. Những cuộc chiến vừa rồi cho thấy, chúng ta đôi khi bị tác động rất mạnh khi một hình ảnh, một video sốc được đưa ra, để rồi vài ngày sau ngã ngửa rằng đó là hình ảnh, video giả, không đúng vị trí hay thời điểm thực (hoặc được tạo bởi AI).
Chứng thực nguồn gốc hình ảnh và vấn đề resize
Có cách nào chống hình ảnh, video giả? Các máy ảnh đã được trang bị chữ ký số, điển hình là hệ thống chứng thực C2PA. Khi phóng viên chụp 1 bức ảnh thì máy ảnh tự động ký lên hình ảnh đó và các metadata như vị trí, thời gian v.v. Hình ảnh đó là thật khi chữ ký số được kiểm thử là chính xác (khoá để ký được gắn vào từ khi sản xuất trong phần bộ nhớ không thay đổi, không trích xuất được). Khổ nỗi các hình ảnh trên media, trên MXH lại không bao giờ là hình ảnh gốc vì quá nặng, thường nó được resize, crop hay biến đổi. Cũng hầu hết phóng viên muốn giữ duy nhất hình ảnh gốc và chỉ cho media hình ảnh đã được làm nhỏ lại. Đó chính là vấn đề, vì sự an toàn của chữ ký số đảm bảo rằng chỉ cần hình ảnh bị biến đổi 1 bít thông tin thì chữ ký sẽ không còn đúng. Do vậy hầu hết các hình ảnh xuất hiện không có khả năng được chứng thực về nguồn gốc, và cũng vì thế mà ảnh, video giả lộng hành.
Vậy phải làm sao để việc chứng thực gốc gác được thực hiện và thực hiện một cách hiệu quả, tự động mà không muốn phải tin tưởng các phần mềm edit?
Zero-Knowledge Proof (ZKP) và SNARK
Đó là khi zero-knowledge proof (ZKP) vào cuộc. ZKP cho phép chứng minh là tôi sở hữu hình ảnh gốc X, chữ ký gốc và đã thực hiện các phép biến đổi cho phép (resize, crop v.v), để cuối cùng cho ra hình ảnh nhỏ tương ứng với chữ ký chính xác trên metadata. Ấy nhưng mà có mâu thuẫn ở đây. ZKP cổ điển thì phép chứng minh trên X rất lớn thì độ dài của chứng minh cũng phải cỡ ngang ngửa X, chứ không mất thông tin? Vậy thì chẳng hoá thay vì công bố X quá to lại công bố cái chứng minh cũng lớn ngang ngửa?
Và một nhánh nghiên cứu gần đây, vẫn đang sôi động, cho phép thực hiện các chứng minh cực ngắn, gọn là SNARK (với S là Succinct - ngắn gọn), nếu có thêm tính chất zero-knowledge proof bảo vệ hình ảnh gốc X thì gọi là zk-SNARK. Chống hình ảnh giả chỉ là 1 ứng dụng, các chứng minh loại này được ứng dụng rộng khắp, nhất là trên blockchain.
Polynomial Commitment: kỹ thuật then chốt
Quay trở lại vấn đề chính, làm sao có thể chứng minh về X rất lớn mà chỉ với 1 chứng minh rất nhỏ? Mật mã luôn thực hiện được những việc phản trực quan như thế. Mọi thứ đều có thể đưa về đa thức, nên một cách nôm na chúng ta có thể nhúng X và các phép biến đổi vào một đa thức \(P\) có bậc \(d\) rất lớn. Bài toán sau đó có thể quy dẫn (thông qua một công cụ IOP - Interactive Oracle Proof, một phiên bản tương tác của PCP) về các phép gọi tính toán trên \(P\).
Gốc gác đơn giản sẽ trở về 1 bài toán cụ thể: cho 1 đa thức \(P\) bậc rất lớn và người chứng minh không cần đưa ra \(P\) (có thể muốn giấu luôn \(P\)) nhưng có thể chứng minh một cách rất ngắn rằng hai giá trị \(u\) và \(v\) thoả mãn \(P(u) = v\).
Bài toán này vẫn phản trực quan, làm sao chứng minh rất ngắn cho một đa thức \(P\) rất lớn! Nó không khác gì đặt \(P\) trong 1 chiếc hộp đen, nhưng vẫn có thể chứng minh được tính đúng đắn của nó: nếu đầu vào là \(u\) thì đầu ra là \(v\). Người chứng minh nhất thiết cần phải không ăn gian, giữ \(P\) cố định trong hộp đen, không thay đổi. Và đó chính là Polynomial Commitment (một trường hợp riêng nhưng quan trọng nhất của Functional Commitment).
Polynomial Commitment cho phép cam kết giữ nguyên \(P\) với 1 cam kết ngắn để rồi có thể tính toán trên đó và thuyết phục \(v\) là giá trị của \(P(u)\). Các bạn có thể dừng 5 phút hoặc 1 ngày, 1 tháng để tự xây dựng trước khi đọc tiếp.
Mấu chốt kỹ thuật rất đơn giản như sau:
- Nếu \(P(u) = v\) thì \(P(u) - v = 0\) và do đó \(u\) là nghiệm của đa thức \(P(x) - v\). Hay nói cách khác sẽ có đa thức \(Q(x)\) sao cho \[P(x) - v = (x - u)\,Q(x). \tag{*}\]
- Do vậy để chứng minh \(P(u) = v\) thì chỉ cần chứng minh \(P, Q\) thoả mãn \((*)\). Mà chứng minh \((*)\) thì thế giới ngẫu nhiên vào cuộc: một đa thức bậc \(d\) trên trường \(\mathbb{F}_p\) rất lớn thì nếu ta lấy ngẫu nhiên 1 điểm \(\tau\), đa thức có giá trị \(= 0\) tại \(\tau\) thì với xác suất gần như tuyệt đối \((1 - d/p)\), đa thức đó đồng nhất bằng 0.
- Tóm lại, chỉ cần kiểm tra \((*)\) tại duy nhất 1 điểm ngẫu nhiên \(\tau\) là xong. Chứng minh chính là phép kiểm tra \((*)\) tại 1 điểm ngẫu nhiên \(\tau\) và có thể làm rất ngắn.
Vấn đề cuối cùng chỉ là làm sao commit và nén \(P, Q\) rất to vào 1 hộp rất bé và kiểm tra được \((*)\) tại 1 điểm ngẫu nhiên \(\tau\).
Cho đa thức \(P(x) = a_d x^d + \cdots + a_1 x + a_0\). Cách thông thường nhét \(P\) vào hộp là nhét \(a_0, \ldots, a_d\). Hoặc nếu ta ở trong 1 nhóm xoắn \(G\) sinh bởi \(g\) có bậc nguyên tố thì có thể nhét \(g^{a_0}, \ldots, g^{a_d}\) vào hộp để che đa thức \(P\). Bài toán logarit rời rạc đảm bảo việc tính lại \(a_0, \ldots, a_d\) là khó và do đó khó tìm lại \(P\). Cách này cũng ổn thôi nhưng mà nó không đạt mục tiêu chính là cái commitment phải cực ngắn.
Và Pedersen's commitment tới, chỉ cần thay đổi một chút: thay vì chỉ có \(g\) thì sinh ra \(d+1\) phần tử sinh của nhóm \(G\) là \(g_0, g_1, \ldots, g_d\) rồi thì gộp tích tất cả lại \[C_P = g_0^{a_0} g_1^{a_1} \cdots g_d^{a_d}\] là thành 1 commitment siêu ngắn - chỉ là 1 phần tử nhóm - và có thể commit được toàn bộ đa thức \(P\) nếu như người chứng minh không biết logarit rời rạc của \(g_i\) (\(i = 1, \ldots, d\)) theo cơ sở \(g_0\). Khi đó, thay đổi \(P\) cũng khó như là giải bài toán logarit rời rạc vậy!
Đến đây đã giải quyết được việc commit, hay là nén cả đa thức lớn \(P\) vào 1 phần tử \(C_P\). Nhưng còn vấn đề là làm sao có thể kiểm tra được \((*)\). Thuật toán KZG (Kate–Zaverucha–Goldberg) làm việc đó: nhúng luôn điểm ngẫu nhiên \(\tau\) vào \(g_0, g_1, \ldots, g_d\) bằng cách sinh \(g_i = g^{\tau^i}\).
Khi đó \(C_P\) chính bằng \(g^{P(\tau)}\). Commit \(Q\) tương tự sẽ cho \(C_Q = g^{Q(\tau)}\).
Và cuối cùng, vì các giá trị đa thức \(P, Q\) nằm trên số mũ không thể đưa xuống, nên để check \((*)\) tại điểm ngẫu nhiên \(\tau\) sẽ cần check trên số mũ và cần thêm cấu trúc Pairing song tuyến tính (có thể dùng Weil Pairing trên đường cong elliptic) để so sánh đơn giản là: \(e(C_P / g^v, g)\) có bằng \(e(C_Q, g^{\tau - u})\) không? (với \(g^{\tau - u} = g_1 / g^u\) có thể tính được).
Và như thế, quay trở lại bài toán chống thông tin giả, chúng ta có thể biến đổi 1 hình ảnh rất lớn về 1 hình ảnh nhỏ để có thể đăng trên media thông qua các phép biến đổi được cho phép (crop, resize, grayscale v.v) và vẫn có chứng minh là ảnh đăng được chứng thực từ một ảnh gốc tại một địa điểm, thời gian gốc. Khi ta mở trình duyệt, nó sẽ tự động kiểm tra chữ ký và Proof rất ngắn kèm theo và chứng thực cho ta nguồn gốc ảnh là thực, bằng không nó sẽ báo hiệu "ảnh giả".
Ứng dụng trong bầu cử: loại bỏ ZKP nhờ Chữ ký đẳng cấu tuyến tính
Mật mã luôn có những bất ngờ thú vị. Và như thường lệ, những điều hay ho thường hay ngẫu nhiên xuất hiện một cách… cố định ở cuối bài.
ZKP được dùng như 1 công cụ vô cùng hiệu quả như trên. Nhưng đôi khi nó cũng có thể gây phiền toái và biết đâu loại bỏ nó lại hay hơn. Và đây là một ví dụ: bầu cử.
Trong các hệ thống bầu cử, khi nhận phiếu bầu từ cử tri, sẽ có các hệ thống tráo phiếu bầu để đảm bảo tính privacy: những phiếu cuối cùng được kiểm là hoán vị những phiếu gốc nhưng mất sợi dây liên lạc để không biết ai bầu cho ai. Để đảm bảo tính đúng đắn thì việc tráo phiếu thực chất là một chứng minh ZKP: các phiếu đầu ra được ngẫu nhiên hoá nhưng nội dung chính là hoán vị của các phiếu đầu vào. Khác với trường hợp ảnh phía trên, đầu vào N phiếu thì đầu ra cũng N phiếu chứ không thể rút gọn như ảnh to - ảnh nhỏ. Ấy thế là ZKP phải rất cồng kềnh: là hoán vị của hàng triệu chục triệu phiếu bầu. Shuffling trong tất cả các hệ bầu cử Mix-Net đều phải như vậy.
Năm 2020, mình cùng cô học trò Chloé và ông thầy David đã challenge ý tưởng này: hay dẹp bỏ béng ZKP đi cho rồi, chứ chứng minh trên cả mấy triệu phiếu thì quá không thực tế. Và từ đó đưa ra ý tưởng sử dụng chữ ký đẳng cấu tuyến tính (Linear Homomorphic Signature) để bên cạnh ngẫu nhiên hoá mã phiếu bầu (không thay đổi nội dung phiếu, tất nhiên) và đồng thời ngẫu nhiên hoá luôn sự chứng thực hợp lệ của phiếu bầu. Khi đó chỉ cần làm trên từng phiếu đơn lẻ mà vẫn chứng minh được phiếu đầu ra hợp lệ khi và chỉ khi phiếu đầu vào hợp lệ. Bài báo đó ở đây cho các bạn quan tâm.
Và điều rất thú vị nhưng chưa thể chia sẻ kỹ hơn là, theo mình được biết, một start-up cực xịn sẽ được ra đời vào tháng 6 này để xây dựng một hệ bầu cử mới với kỹ thuật lõi chính là kỹ thuật trong bài báo trên của bọn mình, mà một số cải tiến của nó đã được đăng ký xong bằng sáng chế. Mục tiêu của start-up là chinh phục chính phủ Pháp sử dụng các hệ bầu cử mới tiên tiến này cho các cuộc bầu cử năm 2026 (hệ bầu cử trong Bộ giáo dục Pháp đã sử dụng một hệ cũ với ZKP của ENS)! Để đây và hẹn 2026 nhìn lại.
Chú thích và tài liệu đọc thêm
- Hệ thống chứng thực C2PA: c2pa.org
- Bài báo 2016 về việc dùng ZKP cho xử lý chứng thực ảnh: photoproof-oakland16.pdf
- Blog post của Trisha Datta và Dan Boneh - "Using ZK Proofs to Fight Disinformation": medium.com