Giải Turing 2023 - hành trình ngẫu nhiên
Hành trình của bác Avi Wigderson thật là romantic: ba năm trước mình viết bác Avi Wigderson đang được đánh giá sẽ có thể giành giải Turing (Nobel của Tin học) thì đạt giải Abel của Toán học, cùng bác László Lovász.
Đến năm nay thì bác Avi Wigderson được giải Turing bởi đã giúp chúng ta hiểu được vai trò của ngẫu nhiên trong tính toán (randomness in computation).
Những đóng góp của bác đã được nói rõ trong trang của ACM và mình cũng đã nói nhiều 3 năm trước, nên chỉ chia sẻ đôi suy nghĩ được lựa chọn ngẫu nhiên trong những điều thú vị.
Vai trò của ngẫu nhiên trong tính toán
Mình luôn cảm thấy sự ngẫu nhiên là một điều vô cùng đặc biệt, nó giúp giải các bài toán với tốc độ cực nhanh, tốc độ có thể tăng lên hàm mũ (exponential speed-up), đưa những cái tưởng như không thể thực hiện trong thế giới đơn định về có thể thực hiện rất nhanh trong thực tế.
Ấy đó là thời kỳ rực rỡ những năm 80s, còn sau này thì randomness lại đóng thêm một vai trò cực kỳ bất ngờ và quan trọng: xây dựng, đặc biệt là xây dựng các sơ đồ mật mã. Chúng ta có thể hình dung một cách trực quan thế này: tấn công là đoán định, đoán xem nội dung nào tương ứng với một bản mã. À, thế thì càng tất định thì càng dễ đoán, muốn khó đoán thì càng phải tăng tính ngẫu nhiên.
Và công trình năm 1984 của Goldwasser–Micali đã đưa ra điều kiện cần cho mật mã: muốn an toàn cần phải ngẫu nhiên, không có ngẫu nhiên thì không an toàn. Goldwasser–Micali cũng đoạt giải Turing năm 2012 và trong lời giới thiệu có đoạn:
"Goldwasser and Micali produced one of the most influential papers in computer science, 'Probabilistic Encryption.'"
Từ sau bài báo này, các cách xây dựng các sơ đồ mật mã khoá công khai đảm bảo chuẩn an toàn đều phải là mật mã xác suất. Về giải Turing 2012 mình đã viết tại đây.
Nhật ký bố mình và những kết nối
Một cách "ngẫu nhiên", đọc lại nhật ký của bố mình, hoá ra ngay từ năm 1981 ông đã thấy vai trò của ngẫu nhiên trong xây dựng và đã trình bày tại đại học Berkeley về "Ô tô mát xác suất" trước những cây cổ thụ Harrison, Paz, Blum. Trong đó Blum là người tiên phong trong xây dựng các hàm giả ngẫu nhiên, người sau này được giải Turing năm 1995 và là thầy của cả Goldwasser và Micali, và nhiều siêu sao khác (như Adleman - giải Turing, Sipser, Rudich, Vazirani, Naor…).
Mình có đề cập đến Goldwasser và Blum tại đây, nhân dịp năm ngoái mình cùng Goldwasser được mời là hai plenary speakers về crypto trong hội nghị an toàn thông tin tại Pháp.
Mình cũng có viết về nhật ký của bố mình ở đây.
Wigderson và ROMANTIC
Bác Avi Wigderson là một nghệ nhân đưa randomness vào xây dựng crypto, đặc biệt dùng nó để chứng minh mọi bài toán trong NP đều có chứng minh zero-knowledge, tạo mối quan hệ giữa tính ngẫu nhiên và tính khó giải "Hardness vs. Randomness", cách mạng hoá khái niệm tính toán v.v. Những đóng góp của bác các bạn có thể đọc trên trang ACM.
Cuối cùng, Romantic? Đó ngẫu nhiên cũng là project mình tham gia 12 năm trước, cũng là nhằm nghiên cứu tính ngẫu nhiên trong mật mã (ROMANTIC = Randomness in Mathematical Cryptography). Sau đó mình tham gia ALAMBIC và cuối cùng mới đây là sáng tạo ra Anamorphic, toàn là sử dụng randomness cho các việc có ích :)