Vẻ đẹp bất định trong mật mã hiện đại

Câu thơ Tagore đó tôi thích từ thủa… biết xao xuyến, và khi học tới chứng minh không để lộ tri thức (zero-knowledge proof) thì cảm thấy như bỗng gặp điểm giao hòa giữa mã và thơ…

Chứng minh tương tác đã vượt ra ngoài mô hình những chứng minh cổ điển. Nếu như chứng minh cổ điển là một dãy tuần tự các lập luận logic đưa đến định lý cần chứng minh, thì chứng minh tương tác là một quá trình thuyết phục thông qua hỏi đáp để người đối diện hoàn toàn bị thuyết phục là một định lý là đúng. Và thuyết phục mà không để lộ tri thức là làm sao vừa bị thuyết phục là định lý đó đúng, mà người bị thuyết phục lại vẫn không biết gì về cách chứng minh nó!

Với tôi, Tagore mới chính là ông tổ của zero-knowledge proof ^_^

Làm sao tôi chứng minh cho anh là có thể phân biệt được hai loại rượu Bordeaux trong vườn nhà Vincent và David? Một chứng minh tường minh đưa ra cách cảm nhận hai loại rượu với những khác biệt tinh tế dài mấy chục trang chưa chắc đã thuyết phục được ai, nhưng chỉ cần anh thử tôi 100 lần với 100 cốc rượu từ vườn nhà Vincent hay David, và lần nào tôi cũng nói đúng là vừa nốc cốc rượu nào, thì hẳn là anh đã bị tôi hoàn toàn thuyết phục về khả năng phân biệt của mình.

Các chứng minh tương tác đều chỉ na ná cách thử rượu như thế. Và điều thật ngạc nhiên, định lý về sự tồn tại zero-knowledge proof cho các bài toán NP-complete đại ý nói rằng: bất kể bài toán nào mà việc kiểm tra chứng minh là có thể thực hiện được, thì đều có cách thuyết phục là tôi giải được bài toán đó mà không để lộ tí thông tin nào về cái chứng minh! ("đại ý" vì nó còn cần điều kiện tồn tại hàm một chiều, nhưng nếu không có hàm một chiều thì chẳng có mật mã, chẳng có gì là bí mật nên chẳng có chuyện gì để viết.)

Và điều đặc biệt nữa là, dù bạn có là một cô gái tóc vàng ngây thơ luôn đặt các câu hỏi hồn nhiên đến mức ngẫu nhiên, thì bạn vẫn bị thuyết phục bởi tôi. Nói xấu các cô gái tóc vàng như vậy (vì các cô đâu có ngây thơ ^_^), nhưng nó diễn tả một khẳng định quan trọng: các chứng minh không để lộ tri thức hoàn toàn có thể thực hiện dù người hỏi chỉ cần đặt những câu hỏi hoàn toàn ngẫu nhiên.

Chính những câu hỏi vu vơ mới lại càng có ý nghĩa thực tế. Chính sự không đòi hỏi những câu hỏi thông minh sắc xảo, mà nó cho phép bất kỳ ai cũng có thể kiểm thử được chứng minh. Và từ đó nó đem lại một ứng dụng đẹp của zero-knowledge proof vào thực tế: chữ ký điện tử.

Lan man nhiều, nay ta đi vào ví dụ cụ thể.

Ta chỉ cần một nhóm cyclic \(G\) với một phần tử sinh \(g\) và với bậc \(q\) đủ lớn sao cho bài toán logarit rời rạc là khó. Bài toán logarit rời rạc đơn giản chỉ là: cho \(g\) và \(y = g^x\), yêu cầu tìm \(x\). Bài toán này được giả thiết là rất khó khi \(q\) lớn. Tất nhiên nếu ta hì hục thử từng \(x = 1\) cho đến \(q\) thì cũng tìm được \(x\), nhưng khi \(q\) lớn thì việc làm này có thể mất hàng trăm năm cô đơn.

Tôi cho anh số \(y\) và tuyên bố là tôi biết bí mật \(x\). Cách đơn giản nhất là tôi đưa thẳng \(x\) cho anh để kiểm tra xem \(y\) có bằng \(g^x\) hay không. Cách này thuyết phục hoàn toàn là tôi biết bí mật, nhưng cái giá phải trả là lộ mất bí mật \(x\). Tôi không muốn anh biết \(x\) mà anh vẫn bị tôi thuyết phục là tôi biết \(x\).

Nếu làm được như vậy cũng là đã đủ để có một ứng dụng đẹp cho việc định danh. Ngày xưa, muốn vào được cổng của một câu lạc bộ Mafia thì cần nói cho tên gác cổng đầu trâu mặt ngựa một mật khẩu. Điều gì sẽ xảy ra khi có chú cảnh sát nào nấp ở cổng hoặc mua chuộc tên gác cổng để lấy mật khẩu? Với cách chứng minh không lộ tri thức, tên gác cổng hoàn toàn bị thuyết phục khi một thành viên chứng tỏ anh ta biết mật khẩu, vậy mà hắn ta vẫn không hề biết mật khẩu đó và cuộc đối thoại cũng không lộ thông tin gì về mật khẩu.

Việc chứng minh biết \(x\) mà không để lộ \(x\) rất đơn giản. Người chứng minh (prover, gọi là P) đưa ra \(y\) và tuyên bố là biết \(x\) sao cho \(y = g^x\). Người kiểm tra (verifier, gọi là V) cần bị thuyết phục là P biết \(x\) nhưng bản thân V sẽ vẫn không biết gì về \(x\) sau khi bị thuyết phục.

Nói tóm lại, nhiệm vụ của P là cần đưa ra một biểu diễn của \(u\) theo \(y\) và \(g\), trong đó số mũ của \(y\) trong biểu diễn đó là \(k\) được chọn bởi V.

Dĩ nhiên, nếu biết \(x\) thì nhiệm vụ của P vô cùng đơn giản, vì khi đó chỉ cần tính \(t = r - kx\) là sẽ có \(u = y^k \cdot g^t\).

Tại sao P buộc phải biết \(x\) mới trả lời được cho mọi lựa chọn \(k\)? Điều này là dễ thấy, vì chỉ cần P đưa ra được hai giá trị \(t_1, t_2\) cho hai lựa chọn khác nhau \(k_1, k_2\) thì có nghĩa là P phải biết \(x\). Hay nói cách khác, khi đó \(k_1 x + t_1 = k_2 x + t_2\) và \(x = (t_2 - t_1)/(k_1 - k_2)\) tính được - đây là ý tưởng của extractor trong zero-knowledge proof of knowledge. Do đó, việc với lựa chọn \(k\) ngẫu nhiên của V mà P trả lời đưa ra được \(t\) đã hoàn toàn thuyết phục được V là P phải biết \(x\).

Tại sao sau đối thoại V không biết gì về \(x\)? Điểm thú vị là P chỉ cần đưa ra câu trả lời cho một lựa chọn \(k\) mà thôi; nếu lặp lại chứng minh thì P đã chọn \(r\) khác rồi. Và với sự trả lời cho một \(k\) thì V chả nhận được thông tin gì về \(x\) cả. Lý do là sau khi đối thoại với P, tất cả những gì V có là \(u, k, t\) thỏa mãn phương trình \(u = y^k \cdot g^t\). Tuy nhiên, không cần đối thoại với P thì V cũng có được ngần ấy thông tin bằng cách chọn \(k, t\) ngẫu nhiên rồi tính \(u = y^k \cdot g^t\) (phân bố của các giá trị theo hai cách là như nhau). Nói cách khác, đối thoại với P hay không chẳng đem lại lợi lộc gì cho V nên V không biết thêm thông tin gì về bí mật \(x\), dù như trên đã chứng tỏ, V bị thuyết phục hoàn toàn rằng P biết \(x\).

Vậy là ta kết thúc được chứng minh không để lộ tri thức. Các bạn kiên nhẫn thêm một chút nữa thôi là ta có được sơ đồ chữ ký điện tử.

Làm sao ta ký trên một văn bản \(m\) để không ai ngụy tạo được chữ ký của ta, nhưng ai cũng kiểm tra được chữ ký đó là của ta?

Nghe đã hơi giống chứng minh không lộ tri thức, nhưng khác biệt cơ bản là chữ ký thì không qua tương tác, còn chứng minh trên kia nhất thiết phải qua tương tác. Nếu \(k\) lại do P chọn thì P có thể chọn \(k\) sau khi biết \(r\) để tạo chứng minh mà không cần biết \(x\), bằng cách chọn \(t\) ngẫu nhiên rồi lấy \(u = y^k \cdot g^t\). Điểm mấu chốt của chứng minh tương tác là P chỉ biết \(k\) sau khi đã chọn \(r\). Điều này đạt được dễ dàng qua tương tác, vì V chỉ đưa \(k\) cho P sau khi đã nhận được \(u\).

Đối với ngữ cảnh không có tương tác, làm sao để có thể đảm bảo là \(u\) được chọn trước \(k\)? Ý tưởng tự nhiên là tính \(k\) như một hàm của \(u\). Và điều này có thể đạt được trong chữ ký bằng cách ép buộc \(k = H(m, u)\), với hàm \(H\) tạm coi là ngẫu nhiên - tức là với bất kể đầu vào nào thì đầu ra là một giá trị ngẫu nhiên không thể đoán. Việc giá trị \(H\) phụ thuộc vào \(m\) đảm bảo thêm luôn là chứng minh đó được tạo ra trên văn bản \(m\) chứ không phải văn bản nào khác. Lấy lại nguyên si chứng minh tương tác phía trên và thay đối thoại giữa P và V bằng công việc của người ký, ta có sơ đồ chữ ký điện tử:

Nếu hàm \(H\) đủ độ ngẫu nhiên thì ta không thể chọn \(k\) trước \(u\), vì việc cho giá trị của hàm \(H\) trước rồi tìm \(u\) thỏa mãn \(k = H(m,u)\) là khó như tìm chiếc nhẫn rơi giữa đại dương. Việc giá trị của \(H\) phụ thuộc vào \(m\) đảm bảo rằng đó là chữ ký trên văn bản \(m\) chứ không phải trên văn bản nào khác.

Đây cũng là chữ ký Schnorr nổi tiếng và là cơ sở cho nhiều chuẩn chữ ký số được dùng trong thực tế (bao gồm cả DSA). Trong thực tế ta có thể dùng \(H\) bằng các hàm băm như SHA, MD5…, nhưng trong chứng minh, \(H\) buộc phải được mô hình hóa như một máy tư vấn ngẫu nhiên (random oracle) thì mới chứng minh được sơ đồ chữ ký như trên là an toàn.

Chữ ký điện tử như ở Pháp đã được công nhận là hợp pháp từ năm 2000, vì người ta coi rằng làm giả chữ ký điện tử còn khó hơn bội phần làm giả chữ ký tay.

Rong chơi từ cái mơ hồ (chứng minh không lộ tri thức) để rồi ta áp dụng làm được cái cụ thể (chữ ký điện tử) thật là lý thú. Những cái gì quá rõ ràng có lẽ chỉ có được giá trị hữu hạn, những gì bí hiểm lại có thể có những giá trị tiềm tàng không giới hạn, và đó là ảnh hưởng những vần thơ của Tagore với tôi…