Mã hóa khóa công khai ra đời cách đây 35 năm, đánh dấu bởi công trình
khoa học của Whitfield Diffie và Martin Hellman. Đó thực sự là một bước
ngoặt đưa mật mã từ một nghệ thuật thành một ngành khoa học. Trong quá
trình 35 năm phát triển, những phát kiến trong mật mã hầu hết rất phản
trực quan, và do đó càng bất ngờ thú vị, đã có ảnh hưởng lớn đến nhiều
ngành khoa học khác: áp dụng những kết quả trừu tượng trong lý thuyết số
vào thực tế; thúc đẩy sự phát triển của các thuật toán xác suất; đưa ra
những khái niệm quan trọng trong lý thuyết tính toán mà điển hình là
khái niệm chứng minh tương tác; tạo cầu nối giữa lý thuyết số và khoa
học máy tính thông qua lý thuyết số tính toán… Trong bài này, chúng tôi
sẽ điểm sơ qua sự phát triển của mật mã trong mối liên hệ với các ngành
khoa học khác, và thảo luận về những hướng phát triển của mật mã trong
những năm tới.
Thay đổi trong cách tiếp cận tính an toàn.
Từ ngàn xưa con người ta đã có nhu cầu trao đổi bí mật: từ những mệnh
lệnh trong các cuộc chiến tranh cho đến những hẹn hò thường nhật. Ta
tìm thấy vết tích của mật mã từ thời Ai cập cổ đại, cho tới hệ mã nổi
tiếng mà Ceasar dùng trong thời La mã, cho tới bức thư tình mà
George Sand gửi cho Alfred de Musset…
Ở thời kỳ sơ khai, mật mã có thể coi như nghệ thuật che giấu thông tin
mà độ an toàn đạt được là nhờ có sự thống nhất một qui ước bí mật chung.
Như vậy, thuật toán lập mã và giải mã là bí mật. Nhưng khi tầm ứng dụng
càng rộng thì yêu cầu bí mật cơ chế mã lại càng không hợp lý vì nhiều
người sử dụng nên tất yếu sẽ rất dễ bị lộ. Cuối thế kỷ 19, Kerckhoffs đề
nghị một nguyên tắc xem xét độ an toàn chỉ dựa trên khóa bí mật còn
thuật toán lập mã/giải mã không cần phải giữ kín. Qui tắc này đến nay
vẫn còn là rất cơ bản. Xuyên suốt thế kỷ vừa qua, người ta đã xây dựng
được rất nhiều các cơ chế mã tốt, với độ an toàn dựa trên sự bảo mật của
khóa chung giữa người gửi và người nhận. Tuy vậy, sự cần thiết chia sẻ
khóa bí mật là một điểm bất thuận lợi, nó là rào cản lớn cho việc trao
đổi thông tin trên diện rộng: ví dụ để thiết lập kênh bí mật đôi mội
giữa một nghìn người thì cần tới cả nửa triệu khóa bí mật.
Mật mã khóa công khai đã vượt qua rào cản đó và đưa đến một bước
ngoặt trong sự phát triển ngành mật mã. Ý tưởng chính của nó khá giản
đơn: lập mã và giải mã là hai quá trình có bản chất khác nhau, nếu như
giải mã nhất thiết phải dùng khóa bí mật (nếu không ai cũng giải được)
thì lập mã lại không nhất thiết như vậy, và thậm chí sẽ càng tốt hơn khi
ai cũng có thể lập mã. Do vậy, nếu ta có thể sinh ra một khóa bí mật
cho giải mã và một khóa công khai tương ứng cho lập mã thì quá trình lập
mã không còn cần bất kỳ bí mật nào. Tuy có vẻ tự nhiên nhưng việc mã
hóa sử dụng khóa công khai làm thay đổi hoàn toàn yêu cầu về sự an toàn:
khóa bí mật không cần chia sẻ nữa, mỗi người có khóa bí mật của riêng
mình và chỉ cần giữ kín nó, không cần thiết phải chia sẻ nó với bất kỳ
ai khác. Sự đảm bảo an toàn không còn cần dựa trên sự tin tưởng lẫn nhau
giữa người gửi và người nhận.
Mật mã khóa công khai còn làm thay đổi hoàn toàn phạm vi ứng dụng,
cho phép mật mã được sử dụng rộng rãi trong thực tế: việc thiết lập kênh
bí mật giữa một nghìn hay một triệu người thì cũng chỉ yêu cầu mỗi
người cần giữ một khóa bí mật và công bố một khóa công khai, không cần
phải thống nhất khóa chung nào. Áp dụng vào thực tế, một cửa hàng trực
tuyến có thể thu hút hàng triệu khách hàng mà chỉ cần công khai duy nhất
một khóa để ai mua hàng cũng chỉ cần dùng khóa công khai đó để gửi
thông tin bảo mật về thẻ thanh toán.
Mật mã với lý thuyết độ phức tạp tính toán
Bên cạnh những ưu điểm mang tính bước ngoặt, mã hóa khóa công khai ẩn
chứa một điều đáng lo ngại về tính an toàn: khi công bố khóa công khai
tương ứng với khóa bí mật sẽ có thể dẫn tới việc khóa bí mật không còn …
hoàn toàn bí mật! Điều lo ngại đó hoàn toàn có cơ sở bởi một kẻ tấn
công có thể thử hết các trường hợp có thể để tìm ra khóa bí mật tương
ứng với khóa công khai. Do đó, về nguyên tắc, kẻ tấn công có thể phá
được sơ đồ mã hóa, tìm ra khóa bí mật mà không cần quan sát bất kể bản
mã nào! Chính vì thế mà độ an toàn của mật mã khóa công khai sẽ không
thể chỉ dựa trên sự giữ bí mật khóa nữa. Muốn đảm bảo sự an toàn, ta
phải chứng tỏ làm sao, dù về nguyên tắc, kẻ tấn công có thể tìm ra khóa
bí mật, nhưng thời gian để đạt được mục đích đó phải là rất lớn, cỡ hàng
triệu năm trên một máy tính nhanh nhất chẳng hạn. Hay nói cách khác, độ
phức tạp mà kẻ tấn công có thể tìm lại khóa bí mật là lớn phi thực tế.
Một cách rất tự nhiên, nghiên cứu độ an toàn của mật mã khóa công khai đã nằm gọn trong lý thuyết độ phức tạp tính toán (
Computational Complexity).
Trong lý thuyết độ phức tạp, ta không chỉ quan tâm xem một bài toán có
thể giải được hay không, mà điều quan trọng nhất là nghiên cứu xem để
giải bài toán đó thì độ khó khăn lớn đến đâu. Độ phức tạp được phân cấp
theo các lớp, trong đó hai lớp quan trọng nhất là lớp P và lớp NP. Lớp P
bao gồm những bài toán giải được trong thời gian đa thức, và nó được
coi là lớp các bài toán có thể giải được trong thực tế. Chẳng hạn các
bài toán sắp xếp dữ liệu theo một thứ tự định sẵn, tìm đường đi ngắn
nhất giữa hai thành phố, biến đổi Fourrier rời rạc (đều có thể thực hiện
được với cỡ
nlog(n) bước cho
n đối tượng, tức là bị chặn bên bởi một đa thức
)
là những bài toán trong P. Lớp NP là lớp các bài toán có thể kiểm tra
được lời giải đúng hay sai trong thời gian đa thức. Chẳng hạn trò chơi
Sudoku thuộc lớp NP vì để giải nó có thể rất khó (thậm chí nó được chứng
minh là một trong những bài toán thuộc
lớp khó giải nhất trong NP)
nhưng để kiểm tra một phương án có là lời giải không thì có lẽ chỉ cần
đến một cậu bé biết phân biệt các con số với nhau và duyệt qua tất cả
các ô. Rõ ràng chỉ khi lời giải có thể kiểm tra được trong thực tế thì
bài toán mới được quan tâm, do vậy mà lớp NP có vai trò quan trọng. Câu
hỏi trọng tâm của lý thuyết độ phức tạp là liệu các bài toán trong NP có
thể có lời giải thực tế (tức trong thời gian đa thức) hay không, tức
liệu P có bằng NP? Nếu P=NP thì điều đó đem lại một sự bất ngờ cho nhận
thức của chúng ta: việc tìm ra lời giải cũng chỉ khó như việc kiểm tra
lời giải. Điều khó tin đó làm người ta thường giả thuyết rằng P khác NP.
Sự quan trọng của câu hỏi “P chọi NP?” là lý do để nó được viện Clay
xếp vào một trong bảy bài toán thiên niên kỷ.
Quay trở lại với lý thuyết mật mã và xem xét nó dưới góc nhìn của lý
thuyết độ phức tạp. Giờ đây ta có thể định nghĩa hệ mã bị phá nếu như có
thuật toán phá mã (tìm lại khóa bí mật từ khóa công khai, hay đơn giản
hơn, tìm lại bản rõ từ bản mã) trong thời gian đa thức. Vậy độ phức tạp
của thuật toán phá mã liệu có thể đánh giá trong trường hợp chung? Câu
trả lời là có và với mọi sơ đồ mã hóa khóa công khai đều có thuật toán
phá mã thuộc lớp NP: do điều kiện cần của hệ mã là khi giải mã ta phải
tìm lại đúng bản rõ, bài toán kiểm tra xem 1 khóa bí mật có tương ứng
với 1 khóa công khai hay không là dễ dàng (chỉ cần chọn 1 bản rõ, mã nó
dùng khóa công khai rồi giải mã nó với khóa bí mật xem có thu lại được
đúng bản rõ hay không). Bài toán “P chọi NP” trở nên có tầm quan trọng
sống còn tới lý thuyết mật mã: nếu hai lớp này tương đương thì toàn bộ
lý thuyết nghiên cứu mật mã dưới góc nhìn độ phức tạp sẽ hoàn toàn sụp
đổ vì việc phá mã, vốn thuộc NP, khi đó sẽ có thể thực hiện được trong
thời gian đa thức. Và cũng do vậy, nghiên cứu độ phức tạp trong mật mã
cần phải dựa trên giả thuyết “P khác NP”.
Hàm cửa lật một chiều và sự phát triển của lý thuyết số tính toán
Khi tính an toàn chia tay với nghệ thuật che giấu bí mật để chuyển
sang dựa trên lý thuyết độ phức tạp thì cũng là lúc mật mã bất ngờ tìm
đến và làm những nghiên cứu trừu tượng trong lý thuyết số bỗng có những
áp dụng đầy ý nghĩa trong thực tế. Nó cũng đưa lý thuyết số tính toán (
computational number theory) trở thành một nhánh nghiên cứu quan trọng, nằm giữa vùng giao thoa của toán học và tin học.
Tựu chung yêu cầu để xây dựng mật mã khóa công khai là: hàm lập mã
thì dễ (với khóa công khai), nhưng hàm giải mã thì khó khi không có khóa
bí mật. Đó là các hàm cửa lật một chiều (
trapdoor oneway functions):
tính xuôi thì dễ, tính ngược lại phải khó, nhưng với cửa lật là khóa bí
mật thì tính ngược, tức giải mã, cũng phải dễ. Yêu cầu trông có vẻ đơn
giản đó nhưng thực tế là sau rất nhiều năm tìm kiếm vẫn chỉ có rất ít
hàm có thể thỏa mãn. Các bài toán trong lớp NP-đầy đủ (là lớp các bài
khó nhất trong NP, trò chơi Sudoku là một trong số đó; ta chỉ cần giải
được 1 bài trong lớp NP-đầy đủ trong thời gian đa thức là đủ để chứng tỏ
P=NP) rõ ràng là những ứng cử viên tiềm năng để xây dựng hàm cửa lật
một chiều. Nhưng thực tế không hề dễ như ban đầu người ta hình dung, vì
hai lý do: thứ nhất là bởi các bài toán NP chỉ quan tâm đến độ khó trong
trường hợp xấu nhất, trong khi mã hóa cần mã an toàn cho mọi bản rõ nên
cần ít nhất độ khó trong trường hợp trung bình; thứ hai là bởi tính
chất cửa lật, bài toán cần khó nhưng với một số thông tin thì nó lại
phải trở nên dễ giải, và chính yêu cầu về tính chất cửa lật đó đã khiến
nhiều hệ mã dựa trên bài toán NP-đầy đủ (như hệ mã Chor-Rivest dựa trên
bài toán xếp ba lô) bị phá vỡ.
Những hàm cửa lật thông dụng trong mật mã đã đến từ những bài toán
rất cổ điển của lý thuyết số! Đó là bài toán phân tích số (cho một số
N = pq là tích của hai số nguyên tố, phân tích nó ra thừa số nguyên tố
p,q) và bài toán logarit rời rạc trong trường hữu hạn (cho một phần tử sinh
g của một nhóm con của một trường hữu hạn, và một phần tử nhóm
u=ga, bài toán là phải tìm lại
a).
Cả hai bài toán này, tuy về mặt toán học là giải được, nhưng cho đến
nay không thể giải được trong thời gian đa thức. Bài toán phân tích số
là nền tảng cho độ an toàn của hệ mã nổi tiếng RSA, và bài toán logarit
rời rạc là cơ sở cho hệ mã Elgamal. Chính vì tính phổ dụng của hai hệ mã
này mà một cách tất nhiên, bài toán phân tích số và bài toán logarit
rời rạc trở thành đối tượng nghiên cứu rất được quan tâm. Việc nghiên
cứu tính phức tạp của việc tìm ra lời giải cho các bài toán lý thuyết số
đã đưa tới sự phát triển sâu rộng của lý thuyết số tính toán.
Sau nhiều công trình nghiên cứu quan trọng thì các bài toán bài toán
phân tích số và bài toán logarit rời rạc tuy chưa giải được trong thời
gian đa thức nhưng cũng không cần đến thời gian hàm mũ để giải nó, mà đã
có các thuật toán dưới mũ (
sub-exponention) như thuật toán dùng tính chỉ số (
index calculus) và thuật toán dùng
đường cong elliptic
của Lenstra, được giới thiệu năm 1985. Dù cho những công trình này
không làm các hệ mã sụp đổ, nhưng nó buộc phép xây dựng các hệ mã phải
giảm hiệu quả vì phải dùng các khóa dài hơn để đảm bảo an toàn. Công
trình của Lenstra cũng đánh dấu lần đầu tiên lý thuyết các đường cong
elliptic được sử dụng vào mật mã, ở đây có vai trò như phá mã. Điều thú
vị là ngay sau đó thì lý thuyết các đường cong elliptic đã được sử dụng
cho việc lập mã. Koblitz và Miller cùng độc lập đề nghị thay thế việc sử
dụng nhóm trong trường hữu hạn bằng nhóm các điểm trên đường cong
elliptic vì ở đó, các thuật toán dưới mũ đã biết để giải quyết bài toán
logarit rời rạc có vẻ như không thể áp dụng được. Từ đó việc sử dụng
đường cong elliptic dẫn tới dẫn đến những hệ mã hiệu quả hơn (do không
cần phải chọn khóa quá dài để chống lại các thuật toán dưới mũ).
Các kết quả lý thuyết sâu sắc trong lý thuyết số tiếp tục được áp
dụng vào mật mã. Việc sử dụng đường cong elliptic dẫn tới yêu cầu cần
phải lựa chọn những đường cong phù hợp. Tấn công MOV (đưa ra bởi
Menezes, Okamoto, và Vanstone) chỉ ra không phải loại đường cong
elliptic nào cũng có thể được sử dụng, bằng cách đưa việc giải quyết bài
toán logarit rời rạc trên đường cong elliptic trở lại bài toán logarit
rời rạc trên một trường hữu hạn mở rộng với độ mở rộng tùy thuộc vào
loại đường cong. Do đó, các đường cong siêu lạ (
supersingular)
rất được ưa dùng ở giai đoạn đầu lại trở nên rất yếu vì ở đó độ mở rộng
chỉ cao nhất là 6. Nét đặc biệt trong tấn công MOV là việc sử dụng phép
ghép cặp (
pairings) trên các đường cong elliptic, với những kết
quả khá mới mẻ trong lý thuyết số. Không chỉ phục vụ cho việc phá mã,
việc sử dụng phép ghép cặp sau đó đã trở nên cực kỳ hữu hiệu trong việc
xây dựng mã. Khởi đầu là Joux đã dùng phép ghép cặp để xây dựng sơ đồ
trao đổi khóa 3 bên, nhưng sự kiện nổi bật là việc dùng phép ghép cặp để
giải quyết vấn đề mở về xây dựng mã hóa dựa trên danh tính-
Identity based Encryption.
Một cách giản đơn, mã hóa dựa trên danh tính cho phép ta sử dụng một
khóa công khai duy nhất cho tất cả mọi người (từ đó giải quyết được vấn
đề quản lý khóa của mã hóa khóa công khai, tuy vậy nhược điểm của nó là
lại cần có thêm người quản trị đáng tin cậy để sinh ra khóa công khai
chung và khóa bí mật cho từng người) và hàm lập mã dựa trên khóa công
khai chung và danh tính của người nhận như địa chỉ email. Sau khi
Sakai-Ohgishi-Kasahara và Boneh-Franklin đưa ra lời giải cho bài toán mã
hóa dựa trên danh tính vào những năm 2000, phép ghép cặp đã được sử
dụng hầu khắp trong mọi lĩnh vực của mật mã (mã hóa, chứa ký điện tử, sơ
đồ định danh…) để nâng cao tính an toàn và hiệu quả và đôi khi là giải
quyết những bài toán mở đã bế tắc trong thời gian dài (chẳng hạn như
trong việc xây dựng chữ ký nhóm). Đến cách đây vài năm người ta đã tổ
chức hẳn một hội nghị (Pairing-based Cryptograhy) dành cho các nghiên
cứu liên quan đến các thuật toán xây dựng và phân tích các phép ghép cặp
trên các đường cong elliptic hay hyperelliptic và các phương pháp mã và
tấn công mã dựa trên phép ghép cặp.
Nhìn lại các phát triển của lý thuyết số tính toán, ta nhận thấy các
phương pháp mới thường được đề nghị đầu tiên cho phá mã, nhưng rồi sau
đó lại được sử dụng rất hiệu quả cho việc lập mã. Điều đó cũng phần nào
chứng tỏ vai trò tương hỗ giữa cộng đồng những người thám mã và lập mã:
trong rất nhiều trường hợp, chính những người say mê tìm cách phá tính
an toàn của các hệ thống mật mã, sẽ là những người đem tới những phát
kiến mới mẻ để xây dựng những hệ mã an toàn hơn.
Đảm bảo tính an toàn và sự phát triển của lý thuyết các thuật toán xác suất
Để có thể cài đặt được hệ mã RSA, một phần tất yếu là sự cần thiết
phải tìm được những số nguyên tố lớn để có thể đảm bảo yêu cầu an toàn
tối thiểu (khóa công khai chứa tích của hai số nguyên tố, và nếu một
trong hai số nguyên tố là nhỏ thì bài toán phân tích số sẽ là dễ). Từ đó
mà yêu cầu tìm các số nguyên tố lớn trở nên rất cần thiết.
Cho tới nay, các phương pháp tìm số nguyên tố lớn đều theo nguyên tắc
hai bước: bước 1 là chọn một số tự nhiên đủ lớn và bước 2 là kiểm tra
xem số được chọn có là số nguyên tố hay không. Do các số nguyên tố có
cấu trúc rất bí hiểm và ta chưa hiểu được quy luật tường minh của chúng
nên bước 1 chưa có cách nào khác là chọn một số ngẫu nhiên. Bước thứ 2
là bước kiểm tra tính nguyên tố. Chính những thuật toán kiểm tra tính
nguyên tố, mà điển hình là những thuật toán được sử dụng rộng rãi của
của Rabin và Solovay, Strassen, đã khởi đầu cho việc dùng xác suất để
thiết kế các thuật toán (chú ý rằng trước đó khá lâu phương pháp xác
suất đã được Erd ̋os sử dụng trong việc chỉ ra
sự tồn tại của
các đối tượng tổ hợp). Các thuật toán xác suất cho ta lời giải không
hoàn toàn chính xác, nhưng độ không chính xác có thể làm nhỏ tới bao
nhiêu cũng được, với điều kiện đầu vào của thuật toán có một nguồn ngẫu
nhiên đủ lớn.
Việc phát triển các thuật toán xác suất dẫn tới sự cần thiết tìm
nguồn ngẫu nhiên đủ lớn. Điều đó dẫn tới việc nghiên cứu những bài toán
sau đó đã trở nên rất có ý nghĩa trong khoa học máy tính như bài toán
trích nguồn ngẫu nhiên (
randomness extractor, nhằm từ một nguồn
không hoàn toàn ngẫu nhiên ta phải trích ra từ đó một lượng tin có độ
ngẫu nhiên cao) và bài toán sinh dãy giả ngẫu nhiên (
pseudo-random generator
– từ một nguồn ngẫu nhiên nhỏ làm sao sinh ra một nguồn gần như ngẫu
nhiên lớn hơn rất nhiều, nó không hoàn toàn ngẫu nhiên nhưng không có
thuật toán nào trong thời gian đa thức có thể chỉ ra tính không ngẫu
nhiên của nó)
Sau nhiều phát triển quan trọng của lý thuyết thuật toán xác suất,
người ta quay lại hoài nghi “liệu độ ngẫu nhiên có thực sự mang tới sự
hiệu quả?”. Bài toán “BPP chọi P” (ở đó BPP là lớp các bài toán giải
được theo nghĩa xác suất) là một bài toán mở trọng tâm của lý thuyết độ
phức tạp. Cũng như bài toán “P vs. NP”, nếu câu trả lời là hai lớp tương
đương thì nó sẽ dẫn tới một khẳng định bất ngờ: mọi thuật toán xác suât
đều có thể có thuật toán tất định tương đương. Bên cạnh câu hỏi tổng
quan này, các nhà nghiên cứu quay lại với bài toán tìm số nguyên tố nhằm
đưa ra một lời giải tất định cho nó. Công trình lý thuyết đột phá của
Agrawal–Kayal–Saxena đưa ra năm 2000, đã chỉ ra một thuật toán tất định
để kiểm thử tính nguyên tố trong thời gian đa thức, giải quyết trọng vẹn
bước thứ 2 một cách tất định. Sự hấp dẫn của một lời giải hoàn chỉnh
cho bài toán tất định tìm số nguyên tố chính là nguồn cảm hứng chung rất
lớn của các nhà toán-tin học và nó được chọn là bài toán khởi đầu cho
một kế hoạch đầy tham vọng nhằm thay đổi tư duy trong hợp tác nghiên cứu
khoa học: hợp tác mở thông qua đóng góp, trao đổi mở trên mạng. Với sự
nhiệt tình của Timothy Gower, Terence Tao (cả hai đều đạt giải thưởng
Fields), đã có rất nhiều nhà khoa học tham gia vào dự án mở Polymath để
cùng trao đổi nhằm tìm kiếm lời giải cho bài toán này. Tuy chưa thể đưa
ra lời giải toàn phần, họ đã có một số kết quả dẫn tới một
bài báo khoa học
dưới tên tác giả Polymath. Rất có thể đây sẽ là một hình thức cộng tác
khoa học xuyên biên giới có sức mạnh tổng hợp lớn trong tương lai.
Chứng minh tương tác không để lộ tri thức
Trong mật mã, mọi trao đổi thông tin đều giả thiết có sự hiện diện
của kẻ xấu. Mục đích của ta là vừa có thể thuyết phục người đối thoại về
tính đúng đắn của một mệnh đề nào đó, lại vừa không cần tin tưởng anh
ta, và không muốn sau khi trao đổi anh ta cũng có khả năng chứng minh
mệnh đề đó với người khác. Chẳng hạn, một thành viên của một câu lạc bộ
bí mật muốn chứng minh danh tính của mình cho người gác cổng, nhưng lại
không muốn nói mật khẩu của mình vì sợ chính người gác cổng sẽ bán nó
cho kẻ khác. Trong ngữ cảnh đó, một trong những khái niệm thú vị nhất
của khoa học máy tính đã được đề nghị: chứng minh tương tác (
interactive proofs).
Khái niệm này được đưa ra bởi Goldwasser, Micali và Rackof vào đầu
những năm 80 và nhờ đó họ đã được trao giải Godel đầu tiên trong lịch sử
(giải thưởng hàng năm cho công trình lý thuyết xuất sắc nhất trong khoa
học máy tính).
Dưới góc độ toán học, ta thường quan niệm chứng minh là một dãy các
lập luận lô gíc có thể trình bày tường minh trên giấy. Liệu chăng yếu tố
đối thoại, tương tác giữa người chứng minh và người kiểm tra có mang
đến điều mới mẻ? Để trả lời câu hỏi đó, trước hết khái niệm về một chứng
minh sẽ phải thay đổi. Goldreich thường trích lời thầy giáo Simon của
mình khi giảng về các chứng minh tương tác:
“chứng minh là bất kể cách gì có thể thuyết phục được tôi” (“ A proof is whatever convinces me”).
Theo nghĩa đó, một chứng minh tương tác là một chuỗi các chất vấn,
cho tới khi người hỏi bị thuyết phục hoàn toàn bởi người chứng minh. Một
câu chuyện vui kể rằng, rằng, một cậu bé cho rằng mình có câu thần chú
để mở vách ngăn giữa hai nhánh của một hang động. Tất nhiên cậu ta không
muốn lộ câu thần chú của mình, nhưng lại muốn chứng minh khả năng đó.
Trò chơi đuổi bắt có thể là một chứng minh tương tác hiệu quả: chú bé
chạy vào 1 trong hai ngã, một người đuổi chon một hướng nhằm dồn chú vào
ngách ngăn nhưng cuối cùng không lần nào bắt được chú. Nếu đuổi một lần
ta có thể cho là chú đã chọn ngã khác, nhưng lặp đi lặp lại trò chơi
tới 100 lần mà không lần nào đuổi được thì có lẽ ta bị thuyết phục là
chú đúng là có câu thần chú (ví dụ lấy từ
Wikipedia). Các chứng minh tương tác hầu hết dựa trên một tinh thần như thế.
Có những bài toán mà người ta chưa biết cách nào chứng minh trong
thời gian đa thức, nhưng lại chứng minh được thông qua tương tác, chẳng
hạn bài toán chứng minh hai đồ thị không đồng cấu với nhau. Hơn thế
nữa, trong nhiều bài toán, người chứng minh có thể không cần để lộ ra
bất kể tri thức nào anh ta có về cái chứng minh đó (
zero-knowledge proofs).
Kết quả rất đẹp của Goldreich, Micali và Wigderson cho ta kết quả bất
ngờ: dựa trên giả thuyết tồn tại các hàm một chiều, tất cả những gì ta
có thể chứng minh trong thực tế (theo nghĩa trong thời gian đa thức),
đều có thể chứng minh mà không để lộ tri thức! Bài toán chứng minh danh
tính phía trên là một trong số đó.
Các chứng minh không để lộ tri thức đặc biệt quan trọng trong mật mã,
là thành phần cơ bản trong việc xây dựng các sơ đồ mã hóa, chữ ký điện
tử. Chứng minh không để lộ tri thức cũng là thành phần không thể thiếu
trong một sơ đồ bầu cử điện tử, cho phép mỗi cử tri kiểm tra được lá
phiếu của mình đã được tính đến mà việc kiểm phiếu lại không cần phải
công bố nội dung từng lá phiếu, đảm bảo quyền lựa chọn bí mật của cử
tri.
Ở một khía cạnh khác, chứng minh tương tác cũng là phần hồn của nhánh khoa học «chứng minh tính bảo mật » (
provable security),
nơi ta cố gắng chứng minh tính an toàn của hệ thống trong một thế giới
tương tác rất phức tạp (với sự hiện diện của kẻ tấn công luôn muốn lừa
hệ thống thông qua quan sát, nghe trộm, đóng giả người tốt để tương tác
với hệ thống) dựa trên những giả thuyết tĩnh, giản đơn của toán học.
Một số hướng đi tương lai của mật mã
Bảo mật trong điện toán đám mây (cloud computing)
Điện toán đám mây cho phép ta lưu trữ những khối lượng thông tin
khổng lồ trên mạng và thực hiện các thao tác trên nó một cách dễ dàng.
Nó có thể giúp ta giải quyết những bài toán lớn mà trước đây khó có thể
giải quyết trên một mạng lưới các máy tính mang tính chất cục bộ. Tuy
nhiên, điều đó mang tới một thách thức vô cùng lớn về tính bảo mật. Có
hai điều có vẻ như mâu thuẫn nhau: lưu trữ dữ liệu lớn trên các hệ thống
xa lạ rõ ràng rất dễ bị đánh cắp thông tin, nhưng nếu ta mã hóa toàn bộ
dữ liệu thì sẽ khó có thể tận dụng sức mạnh của tính toán đám mây để
thao tác dữ liệu đó.
Nhưng gần đây, vấn đề tưởng khó có thể giải quyết này đã có chút tia
hy vọng, với công trình của Gentry năm 2009 về mật mã đẳng cấu theo cả
phép nhân và phép cộng (
fully homomorphic encryption). Hệ mã này cho phép, từ hai bản mã của hai bản rõ
m và
m’, ta có thể tính được bản mã nhân của
mm’ và bản mã cộng của
m+m’.
Vấn đề với bề ngoài đơn giản nhưng chứa đựng không ít nghịch lý trong
đó: hệ mã vừa phải đảm bảo an toàn cho dữ liệu (không thể biết thông tin
về bản rõ
m, m’), mà lại vẫn thao tác được trên dữ liệu đó. Và
cũng với bề ngoài giản đơn như vậy, nó lại mang đến một ý nghĩa rất bao
quát: do mọi tính toán đều có thể qui về các phép toán cơ bản là cộng
và nhân, một hệ mã như thế sẽ cho ta khả năng làm mọi tính toán trên dự
liệu được mã hóa! Điều đó có nghĩa ta có thể để tất cả dữ liệu bảo mật
trên những máy mạng không an toàn mà vẫn có thể tận dụng được sức tính
toán lớn của điện toán đám mây để thao tác trên dữ liệu được mã hóa. Tuy
nhiên, hiện tại, hệ mã Gentry và một số hệ mã cải tiến còn có hiệu quả
vô cùng thấp, hầu như chỉ mang tính lý thuyết. Một hệ mã hiệu quả sẽ là
lời giải tuyệt vời cho bài toán an toàn thông tin trong điện toán đám
mây.
Mở rộng mô hình mã hóa: cho đối tượng nhóm và cho việc giải mã bộ phận
Mã hóa thường cho ta thiết lập kênh trao đổi thông tin giữa một người
với một người. Tuy nhiên, những ứng dụng thực tế đòi hỏi khả năng ta mã
một lần sao cho nhiều người cùng có thể giải mã. Một ví dụ điển hình là
việc phát chương trình truyền hình mã hóa sao cho hàng triệu thuê bao
đều giải được mã. Nhưng một ứng dụng như vậy sẽ đặt ra hai vấn đề: mã
một lần cho nhiều người (
broadcast encryption) và ngăn chặn một người hay một nhóm người thuê bao cấu kết nhau để làm một bộ giải mã giả (
tracing traitor).
Hiện tại các thuật toán được sử dụng trong truyền hình thuê bao hầu hết
đang còn ở thời nguyên thủy: độ an toàn buộc phải dựa trên tính bí mật
của thuật toán. Nhưng cũng bởi vậy nên khi một nhóm phá mã có thể phá
được nguyên lý bằng kỹ nghệ đảo ngược (
reverse engineering) thì thị trường chợ đen có thể bán tràn lan các bộ giải mã giả mà không có cách gì truy lại được ai là thủ phạm.
Hai năm trở lại đây, một hướng nghiên cứu khá mới là về một kiểu mã
tổng quát có thể bao quát hết các khái niệm về mã hóa công khai, mã hóa
dựa trên danh tính, hay mã hóa một lần cho nhiều người. Đó là loại mã
hàm (
functional encryption) ở đó nó cho phép người lập mã định nghĩa một cơ chế giải mã
để
đối với mỗi người nhận, tùy vào thuộc tính được gán có mà có thể truy
cập sâu vào bản rõ tới đâu. Cho tới nay, đối với những cơ chế mã với các
cấu trúc tương đối phức tạp, các phương án lập mã còn rất hạn chế về
hiệu quả. Những kết quả trong tương lai chắc chắn sẽ mang tới những ứng
dụng rất hiệu quả, đặc biệt là cho việc truy cập các cơ sở dữ liệu mã
hóa lớn.
An toàn trước các tấn công vật lý
Mật mã thường phân tích tính an toàn dựa trên giả thuyết là khóa bí
mật được bảo vệ tốt. Tuy nhiên, những tấn công vật lý đôi khi lại có thể
tìm ra những thông tin về khóa (chẳng hạn bằng cách đo năng lượng tiêu
thụ của máy giải mã trên các bản mã khác nhau). Do vậy, một trong các
mục đích của mật mã là tìm cách hình thức hóa các khái niệm tấn công vật
lý và tiếp sau đó là thiết kế các sơ đồ mã hóa mà tính an toàn có thể
đảm bảo chỉ duy nhất dựa trên các giả thiết toán học. Hướng nghiên cứu
an toàn trong mô hình khóa bị lộ (
key leakage resilient cryptography) đang khá được quan tâm trong cộng đồng mật mã.
An toàn trước sự tấn công của máy tính lượng tử
Cuối cùng, chúng ta không thể bỏ qua sự hiện diện tiềm tàng của máy
tính lượng tử, dù rằng cho tới nay các máy tính lượng tử mới chỉ phân
tích được số 21 ra thừa số nguyên tố. Nhưng về mặt lý thuyết, nó có tiềm
năng to lớn không thể không kể tới. Công trình của Shor năm 94 đã chỉ
ra rằng bài toán phân tích số có thể giải được trong thời gian đa thức
bởi máy tính lượng tử. Bài toán logarít rời rạc trong trường hữu hạn
hay trên đường cong elliptic cũng có thể giải được trong thời gian đa
thức bởi máy tính lượng tử. Điều đó có nghĩa là các hệ mã thông dụng
hiện nay sẽ bị phá vỡ một khi máy tính lượng tử được thiết kế chạy được
trên dữ liệu lớn. Để phòng ngừa trước điều đó (dù khả năng sớm xảy ra
được đánh giá là rất nhỏ), nhiều nghiên cứu nhằm xây dựng các hệ mã có
thể an toàn trước máy tính lượng tử được đề nghị. Hai hướng chính đang
được quan tâm là các hệ mã dựa trên mã sửa sai (
error correcting codes) và dựa trên lý thuyết lưới Euclid (
lattice based cryptography), nơi sự hiện diện của máy tính lượng tử có vẻ như không đem lại hiệu quả đặc biệt.
