# Cryptography based on #P-complete problems

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

• 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. Commented May 14, 2022 at 3:53
• Also, #P has a worst-case to average case reduction (so one may as well assume average-case hardness). Commented May 14, 2022 at 4:15

## 2 Answers

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

• 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. Commented May 15, 2022 at 18:44

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.

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