Các giả định về độ khó tính toán

Các giả định về độ khó tính toán là những phỏng đoán chưa được chứng minh nhưng đã được nghiên cứu kỹ lưỡng — chẳng hạn như độ khó của việc phân tích thừa số nguyên tố, logarit rời rạc và các bài toán mạng tinh thể — mà trên đó tính bảo mật của các lược đồ mật mã cuối cùng được xây dựng.

Definition

Một giả định về độ khó tính toán là một phỏng đoán rằng một bài toán tính toán cụ thể không thể được giải quyết một cách hiệu quả (trong thời gian đa thức) bởi bất kỳ đối thủ thực tế nào, đóng vai trò là nền tảng mà trên đó tính bảo mật có thể chứng minh được xây dựng.

Scope

Chủ đề này bao gồm các giả định mà mật mã học dựa vào: sự tồn tại của các hàm một chiều, các bài toán lý thuyết số (phân tích thừa số nguyên tố, RSA, logarit rời rạc), và các bài toán mạng tinh thể và mã hóa được sử dụng trong mật mã hậu lượng tử. Nó đề cập đến hệ thống phân cấp giữa các giả định, sự khác biệt giữa độ khó trường hợp xấu nhất và trường hợp trung bình, và cách các giả định được kiểm định. Nó không bao gồm các cơ chế quy giản kết nối các giả định với các lược đồ và các định nghĩa bảo mật, được xử lý trong các chủ đề liên quan.

Core questions

• Tại sao tính bảo mật mật mã phải dựa trên các giả định độ khó chưa được chứng minh?
• Các giả định chính (hàm một chiều, phân tích thừa số nguyên tố, logarit rời rạc, mạng tinh thể) là gì?
• Các giả định liên quan đến nhau về độ mạnh như thế nào?
• Sự khác biệt giữa độ khó trường hợp xấu nhất và trường hợp trung bình là gì?
• Các bài toán khó tiềm năng được kiểm định như thế nào, và điều gì xảy ra khi một bài toán bị phá vỡ?

Key concepts

• hàm một chiều
• hàm cửa sập
• giả định phân tích thừa số nguyên tố
• giả định logarit rời rạc
• các giả định RSA và Diffie-Hellman
• học với lỗi (LWE)
• độ khó trường hợp xấu nhất so với trường hợp trung bình
• P so với NP
• hệ thống phân cấp giả định

Key theories

Hàm một chiều như một giả định tối thiểu

Sự tồn tại của các hàm một chiều — dễ tính toán, khó đảo ngược — là cần thiết và đủ cho phần lớn mật mã đối xứng và là giả định cơ bản nhất; gần như tất cả mật mã đều giả định ít nhất điều này.

Các giả định lý thuyết số và mạng tinh thể

Mật mã khóa công khai dựa trên các bài toán có cấu trúc — phân tích thừa số nguyên tố, bài toán RSA và logarit rời rạc (cổ điển), và các bài toán học với lỗi và vector ngắn nhất trong mạng tinh thể (hậu lượng tử) — mỗi bài toán được hỗ trợ bởi hàng thập kỷ kiểm tra phân tích mật mã.

Mechanisms

Mật mã học cần các bài toán khó trung bình (trên các trường hợp ngẫu nhiên), chứ không chỉ trong trường hợp xấu nhất, vì các khóa được chọn ngẫu nhiên. Các giả định được tổ chức thành một hệ thống phân cấp tương đối: việc phá vỡ một giả định yếu hơn (ví dụ: phân tích thừa số nguyên tố) thường phá vỡ các lược đồ được xây dựng trên đó, trong khi các quy giản liên hệ các giả định với nhau. Các giả định về mạng tinh thể đáng chú ý vì các quy giản từ trường hợp xấu nhất sang trường hợp trung bình, mang lại sự tin cậy mạnh mẽ hơn. Sự tin cậy vào bất kỳ giả định nào đến từ nỗ lực phân tích mật mã không thành công kéo dài chứ không phải từ bằng chứng.

Clinical relevance

Các giả định về độ khó xác định những gì an toàn và không an toàn để triển khai. Việc phát hiện ra rằng máy tính lượng tử sẽ phá vỡ việc phân tích thừa số nguyên tố và logarit rời rạc (thông qua thuật toán Shor) đã làm mất hiệu lực các giả định đằng sau mật mã RSA và đường cong elliptic chống lại các đối thủ lượng tử, trực tiếp thúc đẩy việc chuyển sang các tiêu chuẩn hậu lượng tử dựa trên mạng tinh thể. Việc lựa chọn các lược đồ được xây dựng trên các giả định đã được nghiên cứu kỹ lưỡng và theo dõi trạng thái của chúng là điều cần thiết cho an ninh lâu dài.

Evidence & guidelines

Các cơ quan tiêu chuẩn ủng hộ các giả định có lịch sử phân tích mật mã lâu dài; quy trình hậu lượng tử của NIST đã đánh giá rõ ràng sự trưởng thành và độ tin cậy của các giả định về mạng tinh thể, mã hóa và hàm băm cơ bản. Thực hành tốt nhất là tránh các giả định kỳ lạ hoặc mới được đề xuất cho các hệ thống có độ bảo mật cao và ưu tiên các bài toán thận trọng, đã được kiểm định kỹ lưỡng, với kích thước khóa được đặt chống lại các cuộc tấn công tốt nhất đã biết.

History

Sự phụ thuộc vào độ khó xuất hiện cùng với mật mã khóa công khai vào năm 1976, khi Diffie và Hellman gắn tính bảo mật với logarit rời rạc, và RSA với việc phân tích thừa số nguyên tố. Những năm 1980 đã chính thức hóa các hàm một chiều và sự khác biệt giữa trường hợp xấu nhất/trường hợp trung bình. Các quy giản từ trường hợp xấu nhất sang trường hợp trung bình của Ajtai (1996) và bài toán học với lỗi của Regev (2005) đã thiết lập các giả định về mạng tinh thể, vốn đã trở nên nổi bật như những nền tảng chống lượng tử và là cơ sở cho các tiêu chuẩn hậu lượng tử mới.

Key figures

• Whitfield Diffie
• Martin Hellman
• Oded Goldreich
• Oded Regev
• Andrew Yao

Seminal works

• diffie1976
• goldreich2001
• katz2020

Frequently asked questions

Tại sao chúng ta không thể chỉ chứng minh rằng những bài toán này là khó?

Việc chứng minh một bài toán đòi hỏi thời gian siêu đa thức sẽ giải quyết các câu hỏi mở sâu sắc trong lý thuyết độ phức tạp (đáng chú ý nhất là P so với NP), những câu hỏi này vẫn chưa được giải quyết. Vì vậy, mật mã dựa vào các giả định mà tính hợp lý của chúng đến từ hàng thập kỷ nỗ lực không thành công để giải quyết chúng một cách hiệu quả.

Điều gì xảy ra nếu một giả định độ khó bị phá vỡ?

Mọi lược đồ mà tính bảo mật của nó quy giản về giả định đó đều có khả năng trở nên không an toàn và phải được thay thế. Đây là lý do tại sao mối đe dọa lượng tử đối với việc phân tích thừa số nguyên tố và logarit rời rạc đã thúc đẩy một cuộc di cư toàn cầu sang các lược đồ dựa trên các giả định khác, chống lượng tử.