НП представляет собой набор проблем решения, которые эффективно проверяемый. Учитывая экземпляр $х$ проблемы решения есть короткое "доказательство" $w$ что, учитывая пару $(х, ш)$, можно эффективно проверить, что $х$ правда.
соНП представляет собой набор проблем решения, которые эффективно опровергаемый. Учитывая экземпляр $х$ проблемы решения есть короткое "опровержение" $w$ что, учитывая пару $(х, ш)$, можно эффективно проверить, что $х$ является ложным.
Практически для всех известных схем шифрования с открытым ключом открытые ключи образуют набор NP.
Что это значит?
Учитывая некоторый открытый ключ $пк$, есть дополнительная информация $ск$ (секретный ключ), чтобы можно было эффективно проверить, что $пк$ является открытым ключом по отношению к секретному ключу $ск$.
Например
для ЮАР, $N = pq$. Учитывая некоторые $N'$ который может принять или не принять эту форму, мы можем эффективно проверить это через свидетеля $(р, д)$.
для предположений типа DLOG, учитывая некоторые $(г, г^с)$, мы можем аналогичным образом эффективно проверить, что $g^s$ принимает эту форму через свидетеля $s$
для схем на основе решетки/кода, учитывая некоторые $(А, As + e)$, мы можем эффективно проверить, что $(Ас+е)$ принимает эту форму через свидетеля $(с, е)$.
Все это говорит о том, что, имея секретный ключ некоторого PKE, обычно довольно легко проверить правильность структуры открытого ключа (а не просто какой-то случайный элемент).
Теперь открытый ключ будет в наборе coNP, если, учитывая некоторые "$пк$" это нет открытый ключ (а вместо этого просто какой-то «случайный элемент»), можно эффективно проверить это.
Например, для RSA, если кто-то дает вам $N$ что не можем быть записано как $N = pq$, вы можете эффективно проверить это с помощью полной факторизации $N = \prod_i p_i^{e_i}$. $((p_1, e_1),\точки,(p_k,e_k))$ поэтому служит свидетелем $N$ нет являющийся открытым ключом RSA, и в этом смысле открытые ключи RSA являются как набором NP, так и набором coNP.
Утверждение этого раздела статьи состоит в том, что предварительное условие
шифрование является детерминированным, и набор открытых ключей образует набор coNP.
является ограничительным. Я лично рассматриваю первую часть этого как более ограничительную, чем вторая.
Например, мне кажется вероятным, что во всех трех приведенных выше примерах открытые ключи образуют набор coNP.
В первых двух примерах это очевидно, а в третьем я думаю, что достаточно сильная редукция базиса может/должна работать как свидетель, в частности, если $В$ достаточно короткая основа для дуального $\mathcal{L}(A)$, тогда $(BA + Be)$ будет необычно коротким вектором для «истинной выборки LWE», но будет равномерно случайным для случайной выборки, например. будет свидетелем СОНП.
