Năm 1994, nhà khoa học máy tính Peter Shor phát hiện rằng nếu máy tính lượng tử được phát minh, chúng sẽ phá hủy phần lớn cơ sở hạ tầng được sử dụng để bảo vệ thông tin được chia sẻ trực tuyến. Khả năng đáng sợ đó đã khiến các nhà nghiên cứu tranh nhau tạo ra các sơ đồ mã hóa “hậu lượng tử” mới, để lưu càng nhiều thông tin càng tốt khỏi rơi vào tay tin tặc lượng tử.

Đầu năm nay, Viện Tiêu chuẩn và Công nghệ Quốc gia tiết lộ bốn người lọt vào vòng chung kết trong cuộc tìm kiếm tiêu chuẩn mật mã hậu lượng tử. Ba trong số chúng sử dụng “mật mã mạng” — một sơ đồ lấy cảm hứng từ mạng, sự sắp xếp thông thường của các dấu chấm trong không gian.

Mật mã mạng và các khả năng hậu lượng tử khác khác với các tiêu chuẩn hiện tại theo những cách quan trọng. Nhưng tất cả chúng đều dựa trên sự bất đối xứng toán học. Tính bảo mật của nhiều hệ thống mật mã hiện tại dựa trên phép nhân và phân tích: Bất kỳ máy tính nào cũng có thể nhanh chóng nhân hai số, nhưng có thể mất hàng thế kỷ để phân tích một số lớn về mặt mật mã thành các thành phần chính của nó. Sự bất đối xứng đó làm cho bí mật dễ mã hóa nhưng khó giải mã.

Điều mà Shor đã tiết lộ trong thuật toán năm 1994 của mình là một sai sót nhỏ của phép tính bao thanh toán khiến nó dễ bị máy tính lượng tử tấn công. “Đó là một điều rất cụ thể, đặc biệt mà máy tính lượng tử có thể làm được,” ông nói Katherine Stange, một nhà toán học tại Đại học Colorado, Boulder. Vì vậy, sau Shor, các nhà mật mã học có một công việc mới: Tìm một tập hợp mới các phép toán dễ thực hiện nhưng gần như không thể hoàn tác.

Mật mã lưới là một trong những nỗ lực thành công nhất cho đến nay. Được phát triển lần đầu vào những năm 1990, nó dựa vào độ khó của tổng điểm kỹ thuật đảo ngược.

Đây là một cách để mô tả mật mã mạng: Hãy tưởng tượng bạn của bạn có một mạng, chỉ là một loạt các điểm theo một mô hình lặp lại thông thường trên khắp mặt phẳng. Bạn của bạn muốn bạn đặt tên cho 10 trong số những điểm này. Nhưng anh ấy đang gặp khó khăn, và anh ấy sẽ không vẽ toàn bộ lưới. Thay vào đó, anh ấy chỉ liệt kê hai điểm - điểm đầu tiên có x-giá trị của 101 và a y-giá trị 19, giá trị còn lại có tọa độ [235, 44].

May mắn thay, thật dễ dàng để tìm các điểm mới trên một mạng, bởi vì khi bạn cộng và trừ hai điểm bất kỳ trên một mạng, bạn sẽ có được điểm thứ ba trong cùng một mạng. Vì vậy, tất cả những gì bạn phải làm là cộng số điểm mà bạn của bạn đã cho bạn, hoặc nhân chúng với số nguyên rồi cộng lại, hoặc kết hợp cả hai. Thực hiện tám cách khác nhau này và bạn sẽ có thể trả lời câu hỏi của bạn mình.

Nhưng bạn của bạn vẫn chưa hài lòng. Anh ấy đưa cho bạn hai điểm bắt đầu giống nhau, sau đó hỏi bạn liệu bạn có thể tìm thấy một điểm gần [0, 0] trên cùng một mạng hay không. Để trả lời chính xác câu hỏi này, bạn phải tìm tổ hợp của [101, 19] và [235, 44] đưa bạn đến gần [0, 0]. Vấn đề này khó hơn nhiều so với vấn đề đầu tiên và có thể cuối cùng bạn sẽ chỉ đoán và kiểm tra để có câu trả lời. Sự bất đối xứng đó là nền tảng của mật mã mạng.

Nếu bạn thực sự muốn sử dụng mật mã mạng để chia sẻ thông tin, bạn sẽ làm như sau. Hãy tưởng tượng rằng một người bạn (một người tốt hơn!) muốn gửi cho bạn một tin nhắn bảo mật. Bạn bắt đầu với một ô vuông các số. Giả sử nó có hai hàng và hai cột và trông như thế này:

Bây giờ bạn nghĩ ra một “chìa khóa” riêng tư mà chỉ bạn biết. Trong ví dụ này, giả sử khóa riêng của bạn chỉ là hai số bí mật: 3 và −2. Bạn nhân các số trong cột đầu tiên với 3 và các số trong cột thứ hai với −2. Cộng các kết quả trong mỗi hàng để có cột thứ ba với hai mục nhập.

Dán cột mới vào cuối lưới của bạn. Lưới ba cột mới này là khóa chung của bạn. Chia sẻ nó một cách tự do!

(Kịch bản trong thế giới thực sẽ phức tạp hơn một chút. Để ngăn tin tặc giải mã khóa riêng của bạn, bạn phải thêm một chút nhiễu ngẫu nhiên vào cột cuối cùng của mình. Nhưng ở đây chúng ta sẽ bỏ qua bước đó vì mục đích đơn giản. )

Bây giờ bạn của bạn sẽ sử dụng khóa chung để gửi tin nhắn cho bạn. Cô ấy nghĩ ra hai con số bí mật của riêng mình: 2 và 0. Cô ấy nhân các số ở hàng đầu tiên với 2 và nhân các số ở hàng thứ hai với 0. Sau đó, cô ấy cộng các kết quả ở mỗi cột để được hàng thứ ba.

Bây giờ, cô ấy gắn hàng mới vào dưới cùng của lưới và gửi lại cho bạn. (Một lần nữa, trong một hệ thống thực, cô ấy cần thêm một số tiếng ồn vào hàng của mình.)

Bây giờ bạn sẽ đọc tin nhắn. Để làm điều này, bạn kiểm tra xem hàng cuối cùng của bạn mình có đúng không. Áp dụng khóa riêng của bạn cho hai mục đầu tiên trong hàng của cô ấy. Kết quả phải khớp với mục cuối cùng.

Bạn của bạn cũng có thể chọn gửi cho bạn một hàng có số sai ở cột cuối cùng. Cô ấy biết rằng con số này sẽ không khớp với tính toán của bạn.

Nếu bạn của bạn gửi một hàng có số cuối cùng là chính xác, bạn sẽ hiểu đây là 0. Nếu cô ấy gửi một hàng có số không chính xác, bạn sẽ hiểu nó là 1. Do đó, hàng này sẽ mã hóa một bit: 0 hoặc 1.

Lưu ý rằng kẻ tấn công bên ngoài sẽ không có quyền truy cập vào khóa cá nhân của bạn hoặc của bạn bè bạn. Nếu không có những thứ đó, kẻ tấn công sẽ không biết liệu con số cuối cùng có chính xác hay không.

Trong thực tế, bạn muốn gửi tin nhắn dài hơn một chút. Vì vậy, những người muốn nhận, chẳng hạn, một tin nhắn 100 bit sẽ tạo ra 100 cột mới thay vì chỉ một. Sau đó, người gửi tin nhắn sẽ tạo một hàng mới, sửa đổi 100 mục cuối cùng để mã hóa 0 hoặc 1 cho mỗi mục.

Nếu mật mã mạng thực sự được triển khai, nó sẽ có vô số sắc thái không được đề cập trong kịch bản này. Chẳng hạn, nếu bạn muốn tin nhắn thực sự an toàn trước những con mắt tò mò, ma trận cần phải có số lượng mục nhập không thể tưởng tượng được, khiến toàn bộ nội dung trở nên khó sử dụng đến mức không đáng sử dụng. Để giải quyết vấn đề này, các nhà nghiên cứu sử dụng ma trận với các đối xứng hữu ích có thể cắt giảm số lượng tham số. Ngoài ra, có cả một bộ chỉnh sửa có thể được áp dụng cho chính vấn đề đó, cho cách kết hợp các lỗi, v.v.

Tất nhiên, luôn có khả năng ai đó sẽ tìm thấy một lỗ hổng chết người trong mật mã mạng, giống như Shor đã làm đối với bao thanh toán. Không có gì đảm bảo rằng một sơ đồ mật mã cụ thể sẽ hoạt động khi đối mặt với bất kỳ cuộc tấn công nào có thể xảy ra. Mật mã hoạt động cho đến khi nó bị bẻ khóa. Thật vậy, đầu mùa hè này một sơ đồ mật mã hậu lượng tử đầy hứa hẹn đã bị bẻ khóa không phải sử dụng máy tính lượng tử mà là máy tính xách tay thông thường. Đối với Stange, toàn bộ dự án tạo ra một nghịch lý khó chịu: “Điều tôi thấy rất tuyệt vời về mật mã là chúng tôi đã xây dựng cơ sở hạ tầng này cho loài người dựa trên niềm tin vững chắc rằng khả năng con người của chúng ta là có hạn,” cô nói. “Thật lạc hậu.”

Điều chỉnh: Tháng Mười Một 9, 2022
Phiên bản gốc của bài viết này nói rằng vấn đề khó giải quyết trong mật mã mạng là tìm một điểm cho trước trên mạng gần gốc. Trong thực tế, việc tìm kiếm một điểm cụ thể là tương đối đơn giản. Bài toán khó là tìm một điểm chưa biết nào đó nằm gần gốc tọa độ. Bài viết đã được thay đổi để phản ánh thực tế này.