Giải Abel 2021 liên quan đến bảo vệ Privacy
(Ghi chép nhanh về giải Abel vừa mới được công bố)
Toán học và Tin học ngày càng gần gũi. Bác Avi Wigderson đang được đánh giá sẽ có thể giành giải Turing cho Tin học thì năm nay được giải Abel, cùng bác László Lovász.
Bác Avi Wigderson được ghi nhận về những đóng góp cho lĩnh vực Tin học lý thuyết, tác động đặc biệt đến mật mã nên mình sẽ nói đôi chút về hai (trong số nhiều) lĩnh vực của bác mà mình rất mê là Zero-Knowledge Proof (ZKP) và Probabilistically Checkable Proof (PCP). Cả hai loại chứng minh này đều rất kỳ lạ. ZKP là chứng minh thông qua tương tác mà không để lộ tri thức nào: anh bị thuyết phục là tôi có chứng minh cho một mệnh đề mà sau khi bị thuyết phục thì anh không biết gì về chứng minh nữa, không tự chứng minh hay thuyết phục được ai khác. Còn PCP thì cũng rất lạ, tôi có một chứng minh rất dài nhưng anh kiểm tra tính đúng sai thì chỉ cần nhìn vào một số nhỏ các vị trí ngẫu nhiên trong cái chứng minh đó là đủ đánh giá chứng minh đó đúng hay sai.
Tưởng chừng ZKP và PCP chỉ mang tính lý thuyết đẹp, ấy thế mà nó đang được ứng dụng rộng khắp. ZKP đã được ứng dụng rất nhiều như xây dựng chữ ký số, xây dựng các sơ đồ bầu cử, hay gần đây đã ứng dụng vào blockchain để bảo vệ Privacy cho người dùng. Chẳng hạn bình thường một giao dịch bitcoin sẽ có số bitcoin được giao dịch, như vậy lộ mất quá nhiều thông tin về số lượng bitcoin gắn với 1 địa chỉ tài khoản. Thế nhưng nếu dùng ZKP có thể che số lượng giao dịch (có thể che cả địa chỉ), và gắn với nó một chứng minh là số lượng giao dịch của tôi nằm trong phạm vi số tiền tôi có, mà không lộ bất kể thông tin gì khác. Còn PCP tưởng càng lý thuyết hơn mà nay lại cũng ứng dụng rất lớn vào blockchain khi việc yêu cầu kiểm thử cần rất nhanh. Trở ngại là PCP thường có độ dài proof lớn nên người chứng minh có thể phải thao tác (commit - cam kết để không thể thay đổi) cả cái chứng minh dài thì cũng gay go, may quá nếu PCP có cấu trúc thì tiện cho Prover sẽ phải thao tác ít thôi, Linear PCP được đưa ra trong ngữ cảnh đó và được sử dụng rất hiệu quả cho cả Prover và Verifier, và do vậy chạy khá ngon trong thực tế. PCP cũng còn ứng dụng trong việc ủy quyền tính toán trên Cloud: chẳng hạn ta có 1 bài toán rất phức tạp nên phải nhờ Cloud tính hộ, Cloud tính xong rồi trả cho ta kết quả, làm sao để biết là Cloud tính đúng mà không bịa kết quả, muốn vậy Cloud phải có cách chứng minh hiệu quả để ta có thể kiểm tra tính đúng đắn cực nhanh, ấy là lúc PCP lại được sử dụng rất phù hợp.
Những nghiên cứu về các loại chứng minh mới này thực sự là miền giao thoa thú vị giữa Toán và Tin học, vừa có vẻ đẹp lý thuyết rất độc đáo, lại vừa có những ứng dụng thực tế đang được phát triển rất mạnh mẽ hiện nay. Có bác này viết về những vấn đề trên khá dễ đọc và cập nhật, bạn nào thích tìm hiểu có thể đọc: ProofsArgsAndZK.pdf
Bác László Lovász cũng rất nổi tiếng trong mật mã với thuật toán LLL cho ta cách tìm một hệ véc tơ cơ sở tương đối trực chuẩn và tương đối ngắn của một lattice. Việc tấn công nhiều hệ mã có thể được quy dẫn về bài toán này và do vậy có thể dùng thuật toán LLL để tấn công. Các bạn có thể đọc bài của bác Joux và bác Stern nếu muốn tìm hiểu kỹ hơn: ToolBox.pdf
Điều thú vị là hiện tại để chống lại các tấn công trên máy lượng tử thì các hệ mã dựa trên độ khó của các bài toán trên lattice lại là những hệ mã tốt nhất. Bạn nào muốn tìm hiểu hướng này có thể đọc eprint.iacr.org/2015/939.pdf
Mình không biết nhiều về các công trình khác của bác Lovász nên không dám nói hơn. Hình dưới đây là hình mình chụp khi dự hội nghị kỷ niệm 25 năm thuật toán LLL, lúc bác Lovász công bố bức thư thú vị gửi bác Lenstra, khởi nguồn cho việc hoàn thiện thuật toán sau này mang tên LLL.
