Криптография на основе #P-полных задач

Существуют ли какие-либо примеры криптографической схемы, основанной на (форме среднего случая) #P-полной задачи?

Мы не знаем, как основывать криптографию даже на $\mathbf{НП}$- полнота, не говоря уже о $\#\mathbf{P}$-полнота. Более того, существуют известные препятствия для создания криптографии на основе $\mathbf{НП}$-полнота: [АГГМ,БТ], а также [Глава 7, Б].

Тем не менее, если кто-то готов сделать дополнительные предположения, то $\#\mathbf{P}$может быть полезна: например, в [CHK+] показано, что в модель случайного оракула, твердость $\#САТ$ (который является полным для $\#\mathbf{P}$) может дать жесткие распределения Нэша, проблема вычисления равновесие по Нэшу (скажем, игры на двоих).

[AGGM]: Акавиа, Гольдрайх, Гольдвассер и Мошковиц, О базировании односторонних функций на NP-трудности, СТОЦ 2006

[B]: Бржушка, Об основах обмена ключами, кандидатская диссертация, 2013 г.

[BT]: Богданов и Тревизан, О редукции от наихудшего случая к среднему для задач NP, ФОКС 2003

[CHK+]: Чоудхури и др., Найти равновесие Нэша не проще, чем сломать Fiat-Shamir, СТОЦ 2019

Обновление: следующий ответ не распространяется на исходный вопрос. Это результат путаницы p-полный с #p-полный.

Первый в истории криптографический алгоритм с открытым ключом был основан на задаче p-полных. Сегодня он известен как Головоломка Меркла. Грубо говоря, сложность обмена ключами для принимающей и отправляющей сторон составляет $\mathcal{О}(п)$ в то время как сложность успешной атаки $\mathcal{O}(n^2)$.

Хотя в современной криптографии она больше не считается безопасной, идея Меркла изменила все в криптографии.