Score:4

Cryptography based on #P-complete problems

cn flag

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

ckamath avatar
ag flag
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.
ckamath avatar
ag flag
Also, #P has a worst-case to average case reduction (so one may as well assume average-case hardness).
Score:2
ag flag

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

a196884 avatar
cn flag
Thanks - helpful answer! Particularly the second paragraph - I had in mind something like a #P-complete equivalent of e.g. this question https://crypto.stackexchange.com/questions/55724/hardness-of-sis-and-its-reduction-to-an-np-complete-problem. The hardness of Nash is exactly the kind of example I was looking for.
Score:0
es flag

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.

a196884 avatar
cn flag
Interesting! But I don't think that that example is in #P.
Habib avatar
es flag
This was definitely my mistake. Confusing p-complete and #p-complete.
mangohost

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.