4
$\begingroup$

Are there any examples of a cryptographic scheme based on (an average-case form of) a #P-complete problem?

$\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$
    – ckamath
    Commented May 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$
    – ckamath
    Commented May 14, 2022 at 4:15

2 Answers 2

2
+100
$\begingroup$

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

$\endgroup$
1
  • $\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$
    – a196884
    Commented May 15, 2022 at 18:44
0
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ Interesting! But I don't think that that example is in #P. $\endgroup$
    – a196884
    Commented May 5, 2022 at 9:04
  • $\begingroup$ This was definitely my mistake. Confusing p-complete and #p-complete. $\endgroup$
    – Habib
    Commented May 5, 2022 at 21:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.