Nền tảng của An ninh
Nền tảng của an ninh cung cấp các cơ sở toán học chặt chẽ cho mật mã học: các định nghĩa chính xác về ý nghĩa của an ninh, các giả định về độ khó mà an ninh dựa vào, và các phép quy giản chứng minh các lược đồ là an toàn.
Definition
Nền tảng của an ninh bao gồm các khuôn khổ định nghĩa, các giả định tính toán và các kỹ thuật chứng minh được sử dụng để xác định chính xác các mục tiêu an ninh và để chứng minh một cách chặt chẽ rằng các cấu trúc mật mã đạt được chúng.
Scope
Lĩnh vực này bao gồm lý thuyết biến mật mã học thành một khoa học chứ không phải một nghệ thuật: các định nghĩa an ninh hình thức và mô hình đối thủ, các giả định độ khó tính toán, phương pháp luận dựa trên quy giản của an ninh có thể chứng minh được, và vai trò trung tâm của tính ngẫu nhiên và giả ngẫu nhiên. Nó đề cập đến cách 'an toàn' được định nghĩa và chứng minh. Nó không bao gồm các nguyên thủy và giao thức cụ thể hiện thực hóa các ý tưởng này, vốn được xử lý trong các lĩnh vực tập trung vào mật mã học.
Sub-topics
Core questions
- Về mặt hình thức, một lược đồ mật mã 'an toàn' có nghĩa là gì?
- Làm thế nào để nắm bắt được sức mạnh và mục tiêu của một đối thủ trong một mô hình chính xác?
- An ninh dựa trên những giả định độ khó nào chưa được chứng minh nhưng hợp lý?
- Làm thế nào một phép quy giản chứng minh rằng việc phá vỡ một lược đồ sẽ giải quyết một vấn đề khó?
- Tại sao tính ngẫu nhiên và giả ngẫu nhiên lại là nền tảng của mật mã học?
Key concepts
- định nghĩa an ninh
- mô hình đối thủ
- an ninh ngữ nghĩa và tính không phân biệt được
- các giả định độ khó tính toán
- các phép quy giản
- các hàm một chiều
- tính giả ngẫu nhiên
- xác suất không đáng kể
- an ninh tính toán so với an ninh lý thuyết thông tin
Key theories
- An ninh ngữ nghĩa và tính không phân biệt được
- Goldwasser và Micali đã định nghĩa an ninh mã hóa là an ninh ngữ nghĩa — một bản mã không tiết lộ bất cứ thông tin hữu ích nào về mặt tính toán về bản rõ — được chứng minh là tương đương với tính không phân biệt được của bản mã, thay thế các trực giác mơ hồ bằng một mục tiêu chính xác, có thể đạt được.
- An ninh có thể chứng minh được bằng quy giản
- Một lược đồ được chứng minh là an toàn bằng một phép quy giản cho thấy rằng bất kỳ đối thủ hiệu quả nào phá vỡ nó đều có thể được biến thành một thuật toán giải quyết một vấn đề được giả định là khó; do đó, an ninh là có điều kiện dựa trên giả định nhưng chặt chẽ.
Clinical relevance
Quan điểm nền tảng là lý do tại sao mật mã học hiện đại có thể được tin cậy: thay vì hy vọng một lược đồ chống lại được tấn công, các nhà thiết kế chứng minh rằng việc phá vỡ nó khó như một vấn đề đã được nghiên cứu kỹ lưỡng dưới một mô hình đối thủ được nêu rõ ràng. Phương pháp luận này làm nền tảng cho các tuyên bố an ninh của mọi nguyên thủy và giao thức được tiêu chuẩn hóa, hướng dẫn các lược đồ mà các cơ quan quản lý và tổ chức tiêu chuẩn phê duyệt, và giải thích tại sao các thiết kế tùy tiện, không được chứng minh lại bị phản đối.
Evidence & guidelines
Phân tích an ninh có thể chứng minh được hiện nay được mong đợi trong việc tiêu chuẩn hóa mật mã (các cuộc thi NIST cho AES, SHA-3 và các lược đồ hậu lượng tử đều xem xét các bằng chứng và quy giản an ninh). Các bằng chứng được kiểm tra bằng máy (EasyCrypt) và các mô hình tiêu chuẩn hóa (random-oracle, standard model) cung cấp sự chặt chẽ, mặc dù các cuộc tranh luận vẫn tồn tại về các giả định lý tưởng hóa. Các cấu trúc mà an ninh chỉ dựa vào các phương pháp heuristic thì không được khuyến khích.
History
Mật mã học trở thành một khoa học chặt chẽ vào đầu những năm 1980 khi Goldwasser và Micali giới thiệu mã hóa xác suất và an ninh ngữ nghĩa (1982-1984), đưa ra các định nghĩa và bằng chứng chính xác đầu tiên. Yao và Blum-Micali đã hình thức hóa tính giả ngẫu nhiên, và phương pháp luận dựa trên quy giản lan rộng trong những năm 1980 và 1990, được củng cố trong 'Foundations of Cryptography' của Goldreich. Cuộc cách mạng định nghĩa này phân biệt mật mã học hiện đại với việc tạo mã trước đây.
Key figures
- Shafi Goldwasser
- Silvio Micali
- Oded Goldreich
- Andrew Yao
- Manuel Blum
Related topics
Seminal works
- goldwasser1984
- goldreich2001
- katz2020
Frequently asked questions
- 'An toàn có thể chứng minh được' thực sự có nghĩa là gì?
- Nó có nghĩa là có một bằng chứng toán học rằng việc phá vỡ lược đồ ít nhất cũng khó như giải quyết một vấn đề được cho là không thể giải quyết được, dưới một mô hình đối thủ đã nêu. Đây không phải là một sự đảm bảo tuyệt đối: an ninh là có điều kiện dựa trên giả định độ khó và mô hình phù hợp với thực tế.
- Tại sao lại phải dựa vào các giả định độ khó chưa được chứng minh?
- Hầu hết mật mã hữu ích không thể được chứng minh là an toàn vô điều kiện — làm như vậy sẽ giải quyết các vấn đề mở lớn như P so với NP. Thay vào đó, an ninh được quy giản về một tập hợp nhỏ các vấn đề đã được nghiên cứu lâu dài (phân tích thừa số, logarit rời rạc, mạng lưới) mà độ khó của chúng được hỗ trợ bởi hàng thập kỷ tấn công thất bại.