Nhà mật mã đảm bảo rằng chúng ta có thể tin tưởng vào máy tính của mình | Tạp chí lượng tử

Yael Tauman Kalai là một nhà khoa học máy tính lý thuyết tiên phong, người đã giành được những giải thưởng ấn tượng và đã thay đổi cách mọi người nghĩ về Internet. Nhưng khi còn bé, cô không hẳn là một học sinh gương mẫu.

“Tôi là một kẻ gây rối,” cô nói. “Về cơ bản, tôi - không hoàn toàn, nhưng về cơ bản - bị đuổi khỏi trường trung học.”

kalai sinh ra và lớn lên ở Tel Aviv, Israel, trong một gia đình khoa bảng. Cha cô, Yair Tauman, là một nhà kinh tế học và lý thuyết trò chơi. Các lớp học ở trường trung học của cô ấy khiến cô ấy chán nản - một học bạ ghi lại khoảng 150 lần nghỉ học, cô ấy nhớ lại, vì cô ấy thích dành thời gian trượt nước và giao lưu hơn. Nhưng kỹ năng phân tích của cô ấy luôn ở đó.

“Khi bố mẹ không cho tôi đi chơi, thường thì cách duy nhất khiến bố tôi đồng ý là nói với ông ấy, 'OK, cho bố một câu đố toán đi. Khó như bạn muốn, nhưng nếu tôi giải quyết được, tôi sẽ đi.'” Cô ấy thường đi.

Tình yêu toán học ngủ quên của cô cuối cùng cũng được đánh thức ở trường đại học, khi cô bắt đầu nhận ra vẻ đẹp của nó. Cuối cùng, cô ấy phát hiện ra rằng cô ấy có thể sử dụng toán học này với máy tính và đặc biệt là bảo mật thông tin. Giờ đây, công việc của cô ấy xoay quanh các lĩnh vực toán học và khoa học máy tính, và ý tưởng của cô ấy là nền tảng cho cách chúng tôi bảo vệ và xác minh tính toán trong thời đại kỹ thuật số. Trong hai thập kỷ qua, cô ấy đã làm việc để đảm bảo tính toàn vẹn của điện thoại thông minh, kết nối đám mây và thậm chí cả tiền điện tử của chúng tôi. Hiện là nhà nghiên cứu tại Microsoft và là giáo sư trợ giảng tại Viện Công nghệ Massachusetts, cô gần đây đã giành được Giải thưởng ACM danh giá của Hiệp hội Máy tính về Điện toán cho “những đột phá trong ủy quyền tính toán có thể kiểm chứng và những đóng góp cơ bản cho mật mã học”. Công việc mới nhất của cô ấy cũng hướng đến tương lai, khi cô ấy xem xét cách máy tính lượng tử có thể ảnh hưởng đến bối cảnh bảo mật.

Quanta đã nói chuyện với Kalai về những bí mật bị rò rỉ, xác minh đám mây và sự thú vị của điện toán lượng tử. Cuộc phỏng vấn đã được cô đọng và chỉnh sửa cho rõ ràng.

Làm thế nào bạn đi từ một kẻ gây rối trường trung học đến một học giả?

Tôi luôn biết mình yêu thích môn toán, nhưng môn toán ở trường trung học không hề thú vị chút nào. Sau đó, tôi bắt đầu học toán ở bậc đại học, và tôi đã rất ngạc nhiên. Đây là lần đầu tiên trong đời tôi ngồi học liên tục từ sáng đến tối. Tôi đã ở trong trạng thái hưng phấn. Và tôi phải nói rằng, tôi hơi buồn, vì tôi nghĩ, “Tôi không thể tin rằng mình có thể tận hưởng điều này khi còn trẻ hơn nhiều!”

Điều gì về toán học đã thu hút bạn?

Nó rất sạch sẽ, thanh lịch và trừu tượng. Và một số khái niệm trong toán học là phản trực giác; Tôi nhớ cảm giác rằng việc nghiên cứu nó đã thay đổi con người tôi. Bạn học cách khiêm tốn, bởi vì hết lần này đến lần khác bạn nhận ra rằng trực giác của mình là sai.

Nhưng khi tôi đang tìm kiếm một câu hỏi nghiên cứu hay, mọi thứ đều tăng lên. Vì vậy, tôi bắt đầu chuyển sang khoa học máy tính. Và mật mã học chính xác là thứ tôi còn thiếu, bởi vì nó giải quyết các vấn đề trong thế giới thực. Ngày nay, mật mã được sử dụng ở mọi nơi. Nó được sử dụng để đảm bảo rằng các tin nhắn chúng tôi gửi là bí mật và xác thực. Khi tôi nhắn tin với ai đó, làm thế nào để tôi biết tin nhắn tôi nhận được là tin nhắn đã được gửi đi? Làm cách nào để tôi biết rằng người tuyên bố đã gửi tin nhắn là người thực sự đã gửi tin nhắn đó? Biết điều đó nghĩa là gì? Các khái niệm rất triết học và cách chúng tôi lập mô hình toán học thực sự rất đẹp. Nó đánh đúng chỗ đối với tôi, cả về tính thuần túy của toán học và khả năng ứng dụng.

Những loại vấn đề mật mã bạn đã làm việc trên?

Luận án thạc sĩ của tôi có tiêu đề “Làm thế nào để rò rỉ một bí mật”. Đây là vấn đề: Chúng tôi biết cách ký điện tử — để nói, “Tôi là người đã viết tin nhắn này.” Nhưng nói rằng tôi muốn ký một cái gì đó với tư cách là giáo sư MIT, nhưng tôi không muốn mọi người biết đó là tôi? Bằng cách đó, bí mật sẽ giữ được ít nước vì bạn biết một giáo sư MIT đã ký nó, nhưng bạn không biết ai.

Chúng tôi đã giải quyết vấn đề này bằng một thứ mà chúng tôi gọi là chữ ký vòng, được lấy cảm hứng từ một khái niệm trong khoa học máy tính gọi là bằng chứng không thể phân biệt bằng chứng. Giả sử có một mệnh đề và hai cách chứng minh khác nhau. Chúng tôi nói rằng có hai "nhân chứng" cho tuyên bố là chính xác - mỗi bằng chứng. Một bằng chứng không thể phân biệt bằng nhân chứng trông giống nhau cho dù bạn sử dụng loại nào: Nó ẩn bạn đã bắt đầu với nhân chứng nào.

Chữ ký nhẫn cũng tương tự. Trong nhóm những người có khả năng tiết lộ bí mật, bạn có thể coi mỗi người đều có một khóa bí mật. Và chữ ký vòng về cơ bản chứng minh rằng thông điệp này đã được ký bởi ai đó bằng một trong các khóa bí mật, nhưng nó không tiết lộ khóa bí mật nào mà họ biết. Nó ẩn khóa bí mật của ai đã được sử dụng.

Liệu một tổ chức có bao giờ thực sự sử dụng hệ thống này?

Đó là điều đẹp đẽ và đáng sợ về nó - tôi có thể làm điều đó mà không có ai khác tham gia. Tôi có thể đăng nhập với tư cách là thành viên của nhóm mà không cần sự cho phép của nhóm. Không rõ đây là một tính năng hay một lỗi, nhưng rõ ràng đây là một khám phá khoa học. Chữ ký vòng đã được sử dụng — có một loại tiền điện tử gọi là monero cho biết họ sử dụng nó để bảo mật các giao dịch. Nhưng thẳng thắn mà nói, tôi thực sự không biết ai đang sử dụng tác phẩm của chúng tôi. Sự thật là tôi quá bận rộn để theo dõi nó.

Làm thế nào mà công việc của bạn phát triển thành việc phân tích tính bảo mật của các thiết bị của chúng tôi?

Vào đầu những năm 2000, tôi đã hoàn thành chương trình Tiến sĩ, làm việc với Shafi Goldwasser tại MIT. Mọi người mới bắt đầu nói về điện toán đám mây mà hiện nay chúng ta sử dụng hàng ngày. Trước đây, bạn có một máy tính để bàn khổng lồ, nơi mọi thứ được thực hiện. Với sự gia tăng trong việc thu thập dữ liệu lớn, việc tính toán trở nên tốn kém hơn và chúng bắt đầu được thực hiện từ xa. Ý tưởng là có một đám mây mạnh mẽ thực hiện các phép tính cho bạn. Nhưng bạn có thể không tin tưởng vào nền tảng đám mây, vậy làm thế nào để bạn biết rằng họ đang thực hiện phép tính một cách chính xác? Đôi khi có thể có động cơ gian lận vì việc tính toán có thể rất tốn kém. Và sau đó trong một số cài đặt, bạn có thể lo lắng về lỗi ngẫu nhiên. Vì vậy, bạn thực sự muốn một bằng chứng rằng tính toán này là chính xác.

Nhưng các bằng chứng thường rất dài và các thiết bị yếu không thể xác minh các bằng chứng dài. Ngay cả đối với các thiết bị có thể, nó rất tốn kém. Vì vậy, có cách nào chúng ta có thể thu nhỏ các bằng chứng? Thông tin-về mặt lý thuyết, không. Nhưng hóa ra là bằng cách sử dụng các công cụ mật mã, thay vào đó, chúng ta có thể tạo ra các chứng chỉ ngắn gọn rất khó làm giả. Chúng được gọi là các đối số không tương tác ngắn gọn hoặc SNARG. Nó không phải là một bằng chứng, thực sự. Nhưng miễn là bạn không thể giải quyết một số vấn đề mà các nhà mật mã học chúng tôi tin là rất khó, chẳng hạn như phân tích số lượng lớn, thì bạn không thể giả mạo các bằng chứng ngắn gọn.

Làm thế nào mà những bằng chứng này xảy ra?

Nó bắt đầu vào năm 1985 với Shafi Goldwasser, Silvio Micali và Charles Rackoff, những người đã cùng nhau đưa ra khái niệm về bằng chứng tương tác. Trước đây, khi mọi người nghĩ về bằng chứng, họ nghĩ đến việc viết các dòng dữ liệu và bạn có thể đọc và kiểm tra xem chúng có đúng hay không. Goldwasser, Micali và Rackoff đã giới thiệu một cách hoàn toàn khác để chứng minh điều gì đó: sử dụng tương tác. Có một người chứng minh và có một người xác minh, và họ trao đổi thông điệp qua lại. Sau đó, người xác minh quyết định xem họ có bị thuyết phục hay không.

Để tôi cho bạn một ví dụ về một thứ dễ thực hiện như một bằng chứng tương tác hơn là một bằng chứng cổ điển. Giả sử chúng ta đang chơi cờ vua. Bây giờ, giả sử tôi muốn chứng minh với bạn rằng tôi có một chiến lược chiến thắng. Cho dù bạn thực hiện bất kỳ động thái nào, tôi vẫn sẽ thắng. Làm thế nào để tôi chứng minh điều này với bạn?

Về mặt kinh điển, đó là một bằng chứng quan trọng, bởi vì tôi cần chứng minh chiến lược của mình hoạt động chống lại tất cả các kết hợp di chuyển có thể có. Nhưng, hóa ra, thông qua tương tác, tôi có thể làm điều đó rất ngắn gọn. Nếu bạn không tin rằng tôi có một chiến lược chiến thắng, hãy chơi thôi. Tôi sẽ cho bạn thấy rằng tôi sẽ thắng. Tất nhiên, chỉ điều đó thôi thì chưa thuyết phục — chỉ vì tôi có thể thắng bạn một lần không có nghĩa là tôi có thể thắng bất kỳ ai. Vì vậy, hãy cho tôi một đại tướng. Tôi sẽ thắng một đại kiện tướng. Điều đó bắt đầu chứng minh sức mạnh của sự tương tác.

Nhưng nhược điểm của bằng chứng tương tác là nó không thể chuyển nhượng được. Giả sử bạn đưa cho tôi một tờ 100 đô la và chứng minh, thông qua tương tác, rằng nó thực sự trị giá XNUMX đô la. Tôi muốn có thể vượt qua nó. Tôi muốn tặng cho người khác, ai tặng cho người khác. Nhưng nếu tôi chỉ có một bằng chứng tương tác, điều đó chẳng nghĩa lý gì; Tôi không thể đưa nó cho bất cứ ai khác. Vì vậy, điều thú vị về SNARG là bạn có thể tặng chúng cho người khác.

Giống như một giấy chứng nhận tính xác thực?

Chính xác. Chuỗi khối là nơi chính mà chúng được sử dụng ngày nay để xác minh các giao dịch. Khi blockchain ra đời, tôi đã nói với các sinh viên của mình rằng chúng ta nên gửi cho nhà phát triển bitcoin, Satoshi Nakamoto, hoa và sôcôla, bởi vì anh ấy thực sự đã làm cho công việc của chúng tôi trở nên phù hợp.

Vậy làm cách nào để loại bỏ tương tác để tạo các chứng chỉ có thể chuyển nhượng này?

Với mật mã. Hãy để tôi cố gắng cung cấp cho bạn một trực giác về cách thức hoạt động của nó. Trong các bằng chứng tương tác của chúng tôi, người xác minh thường chỉ gửi tính ngẫu nhiên đến người chứng minh — bạn có thể coi đây là người xác minh kiểm tra ngẫu nhiên tại chỗ bằng chứng. Sau đó, Amos Fiat và Adi Shamir nảy ra một ý tưởng: Tại sao bạn cần người xác minh này nếu tất cả những gì anh ta làm là gửi ngẫu nhiên? Có lẽ chúng ta có thể thay thế trình xác minh này bằng một hàm nào đó, chẳng hạn như một thứ gọi là hàm băm — đó là một hàm trông có vẻ ngẫu nhiên và là một khối xây dựng rất quan trọng trong mật mã học.

Và hóa ra là có, chúng ta có thể. Hôm nay, điều này được thực hiện tất cả các thời gian. Nếu bạn có iPhone hoặc Android, thì bạn đang sử dụng mô hình Fiat-Shamir khi điện thoại của bạn kết nối với máy chủ từ xa, điều này có thể xảy ra thường xuyên trong ngày. Và chính mô hình này mà chúng tôi sử dụng để xây dựng các bằng chứng ngắn gọn xác nhận rằng các tính toán từ xa là chính xác.

Bạn đã nói về việc máy móc cần được “an toàn hậu lượng tử”. Điều đó nghĩa là gì?

Máy tính lượng tử, nếu chúng thực sự tồn tại trên quy mô lớn, sẽ mạnh hơn nhiều so với máy tính cổ điển. Máy tính cổ điển hoạt động theo bit, có thể là 0 hoặc 1. Trong máy tính lượng tử, bạn có các bit lượng tử, nằm chồng chất giữa 0 và 1. Và các qubit này bị vướng víu, nghĩa là chúng ảnh hưởng lẫn nhau. Đó là thứ thực sự mang lại sức mạnh cho máy tính lượng tử.

Trong tương lai, có thể không phải ai cũng có máy tính để bàn lượng tử. Có thể có một vài thiết bị lượng tử đắt tiền thực hiện các phép tính từ xa cho bạn. Giả sử bạn muốn ủy quyền một tính toán đắt tiền cho một trong những thiết bị lượng tử này và bạn cần một số chứng chỉ xác minh đầu ra là chính xác — làm cách nào để bạn chứng nhận tính đúng đắn của máy tính lượng tử? Bây giờ chúng tôi muốn sử dụng bit lượng tử chứ không phải bit cổ điển, mọi thứ sẽ thay đổi, đặc biệt là khi tôi muốn trình xác minh là một máy tính cổ điển.

Năm 2018, có một bước đột phá kết quả bởi một sinh viên Berkeley, Urmila Mahadev. Cô ấy là người đầu tiên đưa ra một bằng chứng cổ điển, an toàn về mặt tính toán để xác minh các tính toán lượng tử.

Vì vậy, bạn có thể sử dụng một máy tính cổ điển để xác minh tính toán lượng tử? Điều đó nghe có vẻ không thể!

Đó không phải là tuyệt vời sao? Tôi đã ở trong ủy ban chương trình khi Urmila xuất bản bài báo của cô ấy, và tôi đã dành cả đêm để xem nó - lượng caffein tôi đã uống! Tôi đã bị choáng ngợp. Vào thời điểm đó, tôi hoàn toàn là một hình nộm lượng tử. Tôi hiểu phần tiền điện tử, nhưng tôi phải mất một thời gian để hiểu phần đó kết hợp với phần lượng tử như thế nào. Và nó thật đẹp.

Chuyển từ điện toán cổ điển sang điện toán lượng tử nghe giống như một đường cong học tập dốc.

Tôi biết. Tôi thực sự không biết gì về vật lý, và có rất nhiều trực giác vật lý lượng tử liên quan. Tôi không hiểu những khái niệm cơ bản nhất, như năng lượng và nhiệt độ. Đôi khi tôi làm việc với sinh viên và ngay khi chúng tôi nói về điện toán lượng tử, tôi trở thành sinh viên. Tôi đang bắt đầu có thêm một chút trực giác. Và tôi phải nói rằng, tôi rất thích ngồi đó với cuốn sách giáo khoa về thông tin lượng tử. Không có gì tốt hơn là một sinh viên.