Giải thưởng Turing 2012

Giải thưởng Turing (được ví như giải Nobel của ngành Khoa học máy tính) lần này sẽ được trao cho Shafi Goldwasser và Silvio Micali.

Hai đóng góp nổi bật của Goldwasser và Micali là về mật mã xác suất và chứng minh tương tác/chứng minh không để lộ tri thức.

Dưới đây mình sẽ bàn về bài báo Mật mã xác suất (Probabilistic Encryption). Bài báo này cùng lúc đưa vào : một cách nhìn mới về việc mã hoá ; những khái niệm nền tảng về an toàn ; và một phương pháp chứng minh tính an toàn của các hệ mã.

1. Mật mã xác suất

Xác suất thường được dùng nhằm để giúp tìm kiếm lời giải cho các bài toán một cách nhanh hơn là các thuật toán đơn định. Chẳng hạn, hiện nay tuy vẫn chưa có thuật toán tìm số nguyên tố một cách đơn định trong thời gian đa thức, nhưng đã có thuật toán xác suất rất hiệu quả với thời gian kỳ vọng là đa thức. Những thuật toán xác suất này được sử dụng trong thực tế để thiết lập các sơ đồ mã hoá.

Vậy nhưng Probabilistic Encryption lại mang đến một ý nghĩa khác cho việc sử dụng xác suất: giá trị ngẫu nhiên không phải được dùng để tìm kiếm nhanh hơn mà được sử dụng để xây dựng tốt hơn. Trước đó, hàm mã hóa được thiết lập duy nhất dựa trên khóa thì nay ta chủ động đưa thêm vào một giá trị ngẫu nhiên. Do vậy, tương ứng với một bản rõ là một không gian rất lớn các bản mã, nhưng tất nhiên mỗi bản mã vẫn luôn tương ứng duy nhất với một bản rõ.

Ta có thể đặt câu hỏi một cách tự nhiên: hà cớ gì phải phức tạp hoá vấn đề? Câu trả lời ngắn gọn là việc ngẫu nhiên hóa hàm mã giúp nâng lên rất cao độ an toàn cho hệ mã. Và ta sẽ thấy, tất cả các hệ mã muốn đạt được một mức độ an toàn chấp nhận được đều nhất thiết phải là mã hóa xác suất.

2. Khái niệm an toàn và nền móng cho các phương pháp chứng minh tính bảo mật

Goldwasser và Micali đưa ra những khái niệm an toàn làm nền tảng cho việc chứng minh tính bảo mật của các sơ đồ mã hóa.

Cách làm truyền thống là anh nào xây thì bảo hệ mã của tôi an toàn, đố ai phá được đấy. Lâu ngày không ai phá được thì dân làng tin là sơ đồ đó tốt. Nhưng cũng có khi đến lúc người ta tưởng là hệ mã an toàn thì lại có anh phá được, vậy là lại phải tìm tòi hệ mới. Xây xây phá phá xây xây tạo thành vòng luẩn quẩn khó thoát ra được. Goldwasser và Micali khởi đầu cho cách làm khoa học hơn: anh nào xây thì đồng thời phải chứng minh là hệ của mình an toàn!

Khi phá thì chỉ cần đưa ra một tấn công trong khi chứng minh an toàn thì phải loại bỏ được mọi cách tấn công. Nhưng trước khi nói tới việc loại bỏ tấn công thì phải hiểu tường minh thế nào là an toàn. Đóng góp lớn của Goldwasser và Micali là việc hình thức hóa chặt chẽ khái niệm an toàn, từ đó vạch đường cho các chứng minh: hình thức hóa khái niệm an toàn; mô hình hóa sức mạnh của kẻ tấn công ; và cuối cùng là chứng minh hệ của tôi đạt được mức độ an toàn yêu cầu trước tất cả những tấn công thực tế đã được mô hình hóa .

Khái niệm an toàn mà Goldwasser và Micali đưa ra rất mạnh: kẻ tấn công, từ bản mã, không thể tìm được dù chỉ một bít thông tin về bản rõ. Khái niệm này được gọi là an toàn ngữ nghĩa (semantic security), là một phiên bản của khái niệm an toàn tuyệt đối nhưng giới hạn cho kẻ tấn công là các giải thuật trong thời gian đa thức. Sau đó, Goldwasser và Micali chứng minh là an toàn ngữ nghĩa tương đương với tính không phân biệt được (IND-indistingishability) của hai bản mã: kẻ tấn công chọn hai bản rõ khác nhau m_0 và m_1 và nhận một bản mã c của một trong hai bản rõ này, nó không thể phân biệt được là bản mã c tương ứng với bản rõ m_0 hay m_1.

Nhìn từ yêu cầu đạt tính không phân biệt được, thật rất tự nhiên để thấy một hệ mã hóa khóa công khai bắt buộc phải là một hệ mã xác suất. Thật vậy, nếu hệ mã là đơn định, tương ứng với mỗi bản rõ chỉ có duy nhất một bản mã. Hơn nữa, nếu là hệ mã hóa khóa công khai, kẻ tấn công có thể tự mã hõa bản rõ với khóa công khai, và nó sẽ tự tính được bản mã của m_0 và m_1 và chỉ cần so sánh với c là phá được tính IND. Do vậy, một cách cần thiết, hệ mã phải là hệ mã xác suất mới mong đạt IND. Khi đó, tương ứng 1 bản rõ là một không gian rất lớn các bản mã và phép so sánh trên không còn hiệu quả.

Một cách nhìn khác, khái niệm IND ngầm định rằng hai phân bố ngẫu nhiên trên hai không gian bản mã của m_0 và m_1 là không phân biệt được đối với kẻ tấn công. Đứng trên quan điểm thông tin, do hai không gian này là rời nhau (nếu không sẽ có bản mã được giải ra các bản rõ khác nhau) nên khoảng cách thống kê (statistical distance) của hai phân bố là cực đại và tất nhiên chúng hoàn toàn phân biệt. Cái thú vị là khi giới hạn cho kẻ tấn công là một thuật toán thì ta có thể chuyển khoảng cách thống kê sang khoảng cách tính toán: computational distance định nghĩa khả năng phân biệt hai phân bố xác suất đối với các thuật toán. Tính IND yêu cầu computational distance của hai phân bố là vô cùng nhỏ đối với mọi thuật toán trong thời gian đa thức! Sau này, từ khái niệm computational distance sẽ dẫn tới khái niệm computational entropy được dùng phổ biến trong mật mã. Đối với mã hóa khóa công khai, cái hay là mọi thứ đều xác định vì khóa công khai xác định duy nhất khóa bí mật (do đó theo quan điểm thông tin, Shannon entropy bằng 0), nhưng lại rất khó tính-tức khó giải mã (và do vậy cần thiết rằng computational entropy là rất lớn). Shannon entropy = 0 nhưng đồng thời computational entropy phải lớn, đó là nguyên tắc cần đạt trong các hệ mã. Đây là cách nói đại khái, mình dự định sẽ có một bài bàn về khái niệm computational entropy một cách “nhiều Shannon entropy” hơn ^_^.

3. Sự khởi đầu cho các phương pháp chứng minh tính an toàn

Chúng ta biết rằng điều kiện tối thiểu để xây dựng các sơ đồ mật mã là sự tồn tại các hàm một chiều (các bạn có thể xem thảo luận thêm về vấn đề này tại bài này và bài này trên blog). Và khi P = NP thì cũng dẫn tới không tồn tại các hàm một chiều và các hệ mã sẽ đều bị phá vỡ. Do vậy khi bài toán P vs. NP còn chưa có lời kết, sự an toàn của các sơ đồ mật mã đều phải dựa trên một giả thuyết nào đó như giả thuyết về sự tồn tại các hàm một chiều (giả thiết tối thiểu với mã đỗi xứng) hay các hàm một chiều có cửa lật (giả thiết tối thiểu với mã hoá khoá công khai), hay các giả thuyết cụ thể về độ khó của các bài toán phân tích số hay lô ga rít rời rạc. Dù là giả thuyết kiểu gì thì đó cũng là một bài toán “tĩnh”, tức có đầu vào cụ thể và mục đích là giải bài toán đó.

Trong khi đó tính an toàn của một hệ mã lại liên quan đến bài toán tương tác (interactive problem) giữa kẻ tấn công và hệ thống. Trong lúc tấn công, kẻ phá mã có thể truy cập hệ thống và có thêm thông tin cho việc tấn công. Đối với hệ mã hoá khoá công khai, các kẻ tấn công được mô hình hoá theo nghĩa rất mạnh: kẻ tấn công có quyền truy cập máy giải mã (truy cập theo kiểu Oracle – hỏi đáp) trên mọi bản mã trừ duy nhất bản mã c nó cần giải mã. Khái niệm này được gọi là Chosen Ciphertext Security hay CCA security hay IND-CCA (IND against Chosen Ciphertext Attacks). Việc chứng minh tính an toàn của một hệ mã có thể nói ngắn gọn là việc qui dẫn một tấn công tương tác cho hệ mã về một tấn công tĩnh cho một bài toán được giả thiết là khó.

Khái niệm an toàn IND được Goldwasser và Micali hình thức hóa như trên là thông qua một trò chơi tương tác (Game) giữa kẻ tấn công và hệ thống (challenger) và nó đặt nền móng cho các phương pháp chứng minh tính an toàn sau này: khởi đầu là một Game theo định nghĩa, sau đó bản thân Game được “tiến hóa” dần dần sao cho kẻ tấn công có lợi thế “tương đương” giữa hai Games kế tiếp (“tương đương” theo nghĩa computational distance giữa phân bố đầu ra của hai Games là nhỏ không đáng kể). Trong mỗi Game sau, khả năng tương tác của kẻ tấn công bị triệt tiêu dần và cho đến Game cuối cùng là khi kẻ tấn công bị vô hiệu hoá khả năng tương tác và trở thành một kẻ tấn công tĩnh cho một bài toán được giả thuyết là khó. Mô hình chứng minh bằng các Games kế tiếp được sử dụng phổ biến trong các chứng minh tính an toàn của các hệ mã.

———————

Ngoài lề :

Công trình của Goldwasser và Micali là cảm hứng cho hàng nghìn nhà khoa học tiếp tục phát triển lý thuyết mật mã và hầu như người làm mật mã nào cũng có thể thích thú cảm thấy như những kết quả của mình liên quan ít nhiều đến nền móng được đặt ra bởi Goldwasser và Micali.

Với riêng mình, một số kết quả cùng David Pointcheval (thầy hướng dẫn PhD) cũng ít nhiều có liên hệ với công trình của Goldwasser và Micali, giải thích chút cho vui ^_^:

1. Một hệ mã muốn đạt CCA security cần phải là mã xác suất. Nhưng tất cả các cách xây dựng các hệ mã đạt CCA security lại cần phải đưa vào thêm tính dư thừa vào không gian bản mã: hầu hết các bản mã đều không tương ứng với một bản rõ nào. Đây là kỹ thuật để vô hiệu hoá việc truy cập máy giải mã: kẻ tấn công chỉ có thể hỏi những bản mã trong phần dư thừa, không tương ứng bản rõ nào, do vậy việc hỏi máy giải mã là vô nghĩa. Bọn mình nêu câu hỏi: liệu tính dư thừa có thực sự cần thiết? Trong mô hình giới hạn với Random Oracle (hiện hệ mã chuẩn được sử dụng nhiều nhất trong thực tế là RSA-OAEP cũng chỉ có chứng minh trong mô hình Random Oracle), bọn mình chứng minh tính xác suất là cần và đủ để đạt CCA security, và độ dư thừa là không cần thiết. Hai bài báo liên quan ở đây (chứng minh dựa trên sự tồn tại một hoán vị một chiều bộ phận có cửa lật) và ở đây (chứng minh dựa trên sự tồn tại một hàm một chiều có cửa lật).

Chú ý là đối với mô hình chứng minh không có Random Oracle, câu hỏi liệu tính chất xác suất có là đủ để đạt CCA security vẫn còn là câu hỏi mở. Tất cả các hệ mã hiện có đều cần tính dư thừa. Đây vẫn là một câu hỏi mà thỉnh thoảng mình lại trăn trở với nó. Qua trao đổi với nhiều người, một số cho rằng tính dư thừa là cần thiết, một số cho rằng không nhưng các lập luận đều còn cảm tính. Một chứng minh khẳng định theo chiều hướng nào cũng đều thú vị.

2. Đối với hệ mã hóa khóa công khai, để đạt IND nhất thiết cần là hệ mã xác suất. Câu hỏi tương tự nhưng xét cho hệ mã đối xứng thì sao? Bọn mình đặt mối liên quan giữa khái niệm IND và khái niệm giả ngẫu nhiên (khái niệm thông dụng cho mã đối xứng) và chứng minh là hệ mã đối xứng đơn định, không dư thừa có thể đạt IND. Và điều thú vị là trong khi tính adaptivity (truy cập oracle sau khi nhận thách thức) trong mã hoá khoá công khai đưa đến sức mạnh rõ rệt cho kẻ tấn công thì với mã đối xứng, tính adaptivity lại hầu như không có tác dụng. Bạn nào quan tâm có thể đọc bài này.

———————

Lan man:

Có những tác phẩm nổi trội mà được những người trong ngành và công chúng có cách nhìn khác nhau. Mình được kể rằng lúc đương thời, những bản nhạc của Robert Shumann được các nhạc sỹ đánh giá rất cao, trong khi công chúng lại ít để ý tới và mải say mê với các tác phẩm của Rossini. Tác phẩm “Mật mã xác suất” của Goldwasser và Micali được giới trong ngành đánh giá tuyệt đẹp, bản thân mình thấy hay hơn hệ mã RSA. Hệ mã RSA? ok, một công trình đỉnh, nhưng thực sự khoảng cách từ công trình của Diffie-Helmann đến RSA không phải là quá lớn. Với mình, khái niệm mật mã hoá khoá công khai mới thực sự bất ngờ và cách mạng. Từ đó đến hệ mã RSA có lẽ không sớm thì muộn cũng sẽ có. Nhưng công chúng thì ai ai cũng biết tới hệ mã RSA, mà chẳng mấy ai biết mã xác suất là gì. Ngay cả khi mình bắt đầu làm PhD về mật mã thì mới biết đến mã xác suất. Có thể do RSA được sử dụng hầu khắp? nhưng tất cả các hệ mã đang được sử dụng cũng đều là mã xác suất để có thể đạt độ an toàn chấp nhận được.

Có những tác phẩm mà khi ra đời chưa được đón nhận xứng đáng ngay cả từ giới chuyện môn, nhưng vẻ đẹp bí ẩn tiềm tàng của nó lại ngày càng được phát hiện theo thời gian, chẳng hạn như bức tranh Mona Lisa của Leonardo da Vinci. Và công trình nền tảng của Goldwasser-Micalli-Rackoff, nơi đưa vào khái niệm tuyệt vời về chứng minh tương tác và chứng minh không để lộ tri thức, cũng là một ví dụ như thế. Bài báo của họ liên tiếp bị từ chối tại FOCS ’83, STOC ’84, FOCS ’84 trước khi được nhận. Chứng minh tương tác và chứng minh không để lộ tri thức là những khái niệm rất đẹp và có ý nghĩa thực tế. Những kết quả sau này (IP=PSPACE và MIP=NEXP) cho thấy, nếu anh là một người có sức mạnh và quyền lực tuyệt đối, có những điều anh không thể chứng minh được tính đúng đắn qua những tuyên bố đơn phương và anh chỉ có thể chứng minh sự đúng đắn của mình qua đối thoại. Và chứng minh không để lộ tri thức đảm bảo rằng, dù phải dùng đối thoại để thuyết phục đối phương về một sự đúng đắn, anh sẽ không cần để lộ bất cứ bí mật nào. Do vậy, sự đối thoại là rất cần thiết.

Cuối cùng, cái sự lan man này của tớ chắc cũng còn mù mờ, hy vọng bạn nào hứng thú sẽ đọc và có thể trình bày rõ nét những kết quả như IP=PSPACE và MIP=NEXP như một sự cùng đối thoại trên blog.