Bảo mật có thể chứng minh và các phép quy giản

Bảo mật có thể chứng minh cho thấy rằng việc phá vỡ một lược đồ mật mã ít nhất cũng khó bằng việc giải quyết một vấn đề được cho là bất khả thi, bằng cách đưa ra một phép quy giản rõ ràng từ vấn đề được giả định là khó sang bất kỳ cuộc tấn công nào vào lược đồ.

Definition

Phép quy giản bảo mật là một bằng chứng biến đổi bất kỳ đối thủ hiệu quả nào phá vỡ một lược đồ mật mã thành một thuật toán hiệu quả giải quyết một vấn đề được giả định là khó, từ đó cho thấy lược đồ an toàn trừ khi vấn đề đó dễ dàng.

Scope

Chủ đề này bao gồm phương pháp luận dựa trên phép quy giản của các bằng chứng mật mã: cấu trúc của một phép quy giản bảo mật, độ chặt chẽ và bảo mật cụ thể, các kiểu bằng chứng dựa trên trò chơi và dựa trên mô phỏng, mô hình oracle ngẫu nhiên và mô hình tiêu chuẩn, cũng như các giới hạn và phê bình của phương pháp tiếp cận. Nó đề cập đến cách các đảm bảo bảo mật được trình bày và tranh luận. Nó không bao gồm các giả định độ khó cụ thể và các định nghĩa cũng như mô hình đối thủ, những điều này được xử lý trong các chủ đề liên quan.

Core questions

• Phép quy giản chuyển đổi một cuộc tấn công vào một lược đồ thành một giải pháp cho một vấn đề khó như thế nào?
• Sự khác biệt giữa bằng chứng dựa trên trò chơi và bằng chứng dựa trên mô phỏng là gì?
• Độ 'chặt chẽ' của một phép quy giản có ý nghĩa gì đối với các tham số bảo mật trong thế giới thực?
• Mô hình oracle ngẫu nhiên và mô hình tiêu chuẩn là gì, và tại sao mô hình trước đây lại gây tranh cãi?
• Những giới hạn và cạm bẫy phổ biến của các lập luận bảo mật có thể chứng minh là gì?

Key concepts

• phép quy giản bảo mật
• bằng chứng dựa trên trò chơi
• bằng chứng dựa trên mô phỏng
• phép quy giản chặt chẽ so với lỏng lẻo
• bảo mật cụ thể
• mô hình oracle ngẫu nhiên
• mô hình tiêu chuẩn
• lợi thế không đáng kể
• giả định độ khó

Key theories

Phương pháp luận bằng chứng quy giản

Để chứng minh một lược đồ an toàn, người ta giả định một đối thủ phá vỡ nó và xây dựng, sử dụng đối thủ đó làm một chương trình con, một thuật toán giải quyết vấn đề khó cơ bản — do đó, một cuộc tấn công thành công sẽ mâu thuẫn với giả định độ khó.

Mô hình oracle ngẫu nhiên

Nhiều lược đồ hiệu quả được chứng minh an toàn bằng cách lý tưởng hóa một hàm băm như một oracle thực sự ngẫu nhiên; mô hình này cho phép các bằng chứng cho các cấu trúc thực tế nhưng mang tính heuristic, vì không có hàm thực nào là một oracle ngẫu nhiên.

Mechanisms

Trong một phép quy giản, người chứng minh giả định một đối thủ giả định phá vỡ lược đồ với lợi thế không đáng kể và xây dựng một trình bao bọc nhúng một trường hợp của vấn đề khó vào tầm nhìn của đối thủ, chạy đối thủ và sử dụng đầu ra của nó để giải quyết vấn đề. Các bằng chứng dựa trên trò chơi tiến hành thông qua một chuỗi các trò chơi không thể phân biệt từ lược đồ thực tế đến một trò chơi mà đối thủ rõ ràng không thể thắng. Độ chặt chẽ của phép quy giản — lượng lợi thế và thời gian chạy bị mất — xác định kích thước khóa cần thiết cho một mức độ bảo mật mục tiêu.

Clinical relevance

Bảo mật có thể chứng minh là tiêu chuẩn mà các lược đồ mật mã đạt được sự tin cậy và tiêu chuẩn hóa: các quy trình AES, SHA-3 và hậu lượng tử của NIST đã xem xét kỹ lưỡng các bằng chứng bảo mật, và các giao thức như TLS 1.3 đã đi kèm với các phân tích quy giản và được kiểm tra bằng máy. Việc hiểu các phép quy giản cho phép các nhà thực hành đánh giá những gì một tuyên bố bảo mật đảm bảo và không đảm bảo, và chọn các tham số có tính đến độ chặt chẽ của phép quy giản.

Evidence & guidelines

Thực tiễn hiện đại ưu tiên các bằng chứng trong mô hình tiêu chuẩn khi khả thi và coi các bằng chứng oracle ngẫu nhiên là bằng chứng heuristic mạnh mẽ hơn là các đảm bảo tuyệt đối. Các khung công cụ hỗ trợ (EasyCrypt, CryptoVerif) cung cấp các bằng chứng được kiểm tra bằng máy. Phân tích bảo mật cụ thể (chính xác), định lượng lợi thế của đối thủ theo chức năng của tài nguyên, được ưu tiên hơn các tuyên bố tiệm cận thuần túy để thiết lập các tham số thực tế.

History

Phương pháp luận quy giản xuất hiện cùng với cuộc cách mạng định nghĩa vào đầu những năm 1980 và được hệ thống hóa trong suốt những năm 1990. Bellare và Rogaway đã giới thiệu mô hình oracle ngẫu nhiên (1993) để chứng minh các lược đồ thực tế an toàn, và sau đó là phân tích 'bảo mật cụ thể' để định lượng các đảm bảo. Kết quả năm 1998 của Canetti, Goldreich và Halevi cho thấy các lược đồ an toàn trong mô hình oracle ngẫu nhiên nhưng không an toàn khi được khởi tạo đã làm sắc nét cuộc tranh luận về các mô hình lý tưởng hóa.

Key figures

• Mihir Bellare
• Phillip Rogaway
• Oded Goldreich
• Shafi Goldwasser
• Silvio Micali

Seminal works

• bellare1993
• katz2020
• goldreich2001

Frequently asked questions

Liệu một bằng chứng bảo mật có nghĩa là một lược đồ không bao giờ có thể bị phá vỡ không?

Không. Một bằng chứng cho thấy rằng việc phá vỡ lược đồ ngụ ý giải quyết một vấn đề được giả định là khó trong một mô hình cụ thể. Nếu giả định thất bại, mô hình không thực tế, hoặc việc triển khai khác biệt so với lược đồ được phân tích, các cuộc tấn công vẫn có thể xảy ra. Các bằng chứng giảm thiểu, nhưng không loại bỏ, rủi ro.

Tại sao mô hình oracle ngẫu nhiên được coi là gây tranh cãi?

Nó mô hình hóa một hàm băm như một hàm ngẫu nhiên hoàn hảo, điều mà không có hàm cụ thể nào thực sự là như vậy. Các bằng chứng trong mô hình này là bằng chứng mạnh mẽ và cho phép các lược đồ hiệu quả, nhưng tồn tại các lược đồ (được tạo ra) an toàn trong mô hình nhưng không an toàn khi oracle được thay thế bằng bất kỳ hàm băm thực nào, vì vậy các bằng chứng như vậy mang tính heuristic.