Are there any examples of a cryptographic scheme based on (an average-case form of) a #P-complete problem?
$\begingroup$
$\endgroup$
2
-
$\begingroup$ We don't know how to base cryptography (e.g., one-way functions) even on NP-completeness (and there are known barriers to this) let alone #P completeness. $\endgroup$– ckamathMay 14, 2022 at 3:53
-
$\begingroup$ Also, #P has a worst-case to average case reduction (so one may as well assume average-case hardness). $\endgroup$– ckamathMay 14, 2022 at 4:15
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
1
We don't know how to base cryptography even on $\mathbf{NP}$-completeness let alone $\#\mathbf{P}$-completeness. Moreover, there are known barriers to basing cryptography on $\mathbf{NP}$-completeness: [AGGM,BT], and also [Chapter 7, B].
That said, it one is willing to make additional assumptions then $\#\mathbf{P}$-hardness can be useful: e.g., in [CHK+], it is shown that in the random-oracle model, hardness of $\#SAT$ (which is complete for $\#\mathbf{P}$) can yield hard distributions of Nash, the problem of computing Nash equilibrium (of, say, two-player games).
[AGGM]: Akavia, Goldreich, Goldwasser and Moshkovitz, On Basing One-Way Functions on NP-Hardness, STOC 2006
[B]: Brzuszka, On the Foundations of Key Exchange, PhD Thesis, 2013
[BT]: Bogdanov and Trevisan, On Worst-Case to Average-Case Reductions for NP Problems, FOCS 2003
[CHK+]: Choudhuri et al, Finding a Nash Equilibrium Is No Easier Than Breaking Fiat-Shamir, STOC 2019
-
$\begingroup$ Thanks - helpful answer! Particularly the second paragraph - I had in mind something like a #P-complete equivalent of e.g. this question crypto.stackexchange.com/questions/55724/…. The hardness of Nash is exactly the kind of example I was looking for. $\endgroup$– a196884May 15, 2022 at 18:44
$\begingroup$
$\endgroup$
2
Update: The following answer does not cover the original question. It is the result of confusing p-complete with #p-complete.
The first ever public key cryptographic algorithm was based on a p-complete problem. It is today known as Merkle Puzzle. Roughly speaking, the complexity of key exchange for the receiving and sending sides is $\mathcal{O}(n)$ while a successful attack complexity is $\mathcal{O}(n^2)$.
Although in modern cryptography, it is not considered secure anymore, Merkle's idea changed everything in cryptography.
