Nguyên thủy mật mã $Q$ mạnh hơn một mật mã nguyên thủy khác $P$ nếu $Q$ ngụ ý $P$ nhưng điều ngược lại là không đúng sự thật. Để cụ thể, hãy nghĩ về $P$ dưới dạng hàm một chiều và $Q$ như mã hóa khóa công khai.
Cách thông thường để chỉ ra rằng $Q$ ngụ ý $P$ là thông qua một giảm hộp đen của $P$ đến $Q$: I E.,
- đầu tiên cho thấy một hiệu quả xây dựng $C^{(\cdot)}$ điều đó, được cấp quyền truy cập hộp đen cho mọi trường hợp (không nhất thiết phải hiệu quả) $\mathsf{Q}$ của $Q$, mang lại một ví dụ $\mathsf{P}=C^{\mathsf{Q}}$ của $P$; và
- sau đó hiển thị một hiệu quả giảm an ninh $\mathsf{R}^{(\cdot)}$ điều đó, được cấp quyền truy cập hộp đen cho mọi đối thủ (không nhất thiết phải hiệu quả) $\mathsf{A}_P$ mà phá vỡ $\mathsf{P}$, mang lại một kẻ thù $\mathsf{A}_Q$ mà phá vỡ $\mathsf{Q}$.
Để thấy rằng mã hóa khóa công khai $(\mathsf{G},\mathsf{E},\mathsf{D})$ ngụ ý các hàm một chiều, (ví dụ) đặt thuật toán tạo khóa của nó thành hàm một chiều, nghĩa là, $\mathsf{F}(1^n,r):=pk$, ở đâu $(pk,sk):=\mathsf{G}(1^n;r)$.
Mặt khác, để chứng tỏ rằng $P$ không làm bao hàm, ngụ ý $Q$ người ta phải loại trừ tất cả các giảm của $Q$ đến $P$, tức là, hiển thị một tách biệt. Ví dụ, để chỉ ra rằng $P$ Không ngụ ý $Q$ thông qua việc thu nhỏ hộp đen, nó đủ để mô tả một lời tiên tri $\mathcal{O}$ sao cho nguyên thủy $P$ tồn tại so với $\mathcal{O}$, nhưng tất cả các Trường hợp của $Q$ bị hỏng. Kể từ khi giảm hộp đen tương đối hóa, giảm như vậy không thể tồn tại. Nó đã được chỉ ra trong [IR] rằng các chức năng một chiều không ngụ ý mã hóa khóa công khai thông qua việc rút gọn hộp đen (điều này rất không tầm thường).
Bạn có thể đọc thêm về các cách giảm và tách khác nhau trong [RTV].
[IR]: Impagliazzo và Rudich, Giới hạn về các hệ quả có thể chứng minh được của các hoán vị một chiều, STOC'89.
[RTV]: Reingold, Trevisan và Vadhan, Các khái niệm về khả năng rút gọn giữa các bản gốc mật mã, TCC'04.
