Криптографический примитив $Q$ сильнее другого криптографического примитива $P$ если $Q$ подразумевает $P$ но обратное неверно. Для конкретности подумайте о $P$ как односторонние функции и $Q$ как шифрование с открытым ключом.
Традиционный способ показать, что $Q$ подразумевает $P$ через сокращение черного ящика из $P$ к $Q$: т. е.
- сначала показать эффективный строительство $C^{(\cdot)}$ что, учитывая доступ черного ящика к каждому экземпляру (не обязательно эффективный) $\mathsf{Q}$ из $Q$, дает экземпляр $\mathsf{P}=C^{\mathsf{Q}}$ из $P$; и
- затем покажите эффективное снижение безопасности $\mathsf{R}^{(\cdot)}$ что при доступе к каждому противнику через черный ящик (не обязательно эффективном) $\mathsf{A}_P$ что ломает $\mathsf{P}$, дает противнику $\mathsf{A}_Q$ что ломает $\mathsf{Q}$.
Чтобы увидеть, что шифрование с открытым ключом $(\mathsf{G},\mathsf{E},\mathsf{D})$ подразумевает односторонние функции, (например) устанавливает свой алгоритм генерации ключа как одностороннюю функцию, т. е. $\mathsf{F}(1^n,r):=pk$, куда $(pk,sk):=\mathsf{G}(1^n;r)$.
С другой стороны, чтобы показать, что $P$ не подразумевать $Q$ нужно исключить все сокращения $Q$ к $P$, т. е. показать разделение. Например, чтобы показать, что $P$ не подразумевает $Q$ с помощью сокращений черного ящика достаточно описать оракула $\mathcal{O}$ такой, что примитив $P$ существует относительно $\mathcal{O}$, но все случаи $Q$ сломаны. Поскольку сокращения черного ящика относительный, таких сокращений быть не может. В [IR] было показано, что односторонние функции не подразумевают шифрование с открытым ключом посредством редукций черного ящика (это весьма нетривиально).
Вы можете больше узнать о различных вариантах сокращений и разделений в [RTV].
[ИК]: Импальяццо и Рудич, Ограничения на доказуемые последствия односторонних перестановок, СТОЦ'89.
[RTV]: Рейнгольд, Тревизан и Вадхан, Понятия сводимости между криптографическими примитивами, ТСС'04.
