Score:0

generic method/process to construct a cryptosystem based on the Decisional Problem

us flag

Suppose I am given a Decision problem(DP) which is proven to be NP-hard. Is there a generic method/process to construct a cryptosystem based on the DP?

Thanks.

fgrieu avatar
ng flag
Have you looked at Katz and Wang's [_Efficiency Improvements for Signature Schemes with Tight Security Reductions_, section 3](https://www.cs.umd.edu/~jkatz/papers/CCCS03_sigs.pdf#page=4)?
Score:3
ng flag

No. Not only is there not a generic way to build a cryptosystem based on the decision problem, there isn't a single known decision problem that:

  1. is NP-Complete, and
  2. we can build cryptography from

"Any cryptography" may seem somewhat vague, but it can be made specific fairly easily --- most symmetric-key primitives (One-way Functions, Pseudorandom Functions/Generators, and Unpredictable functions) are known to be equivalent, in the sense that if you have one (say a OWF), you can easily build the others, and vice versa.

Why hasn't there been cryptography built from from this assumption? A basic reason is the "trivial theorem" that:

If there exists a secure (OWF/PRG/PRF/UF), then $P\neq NP$

This is because for any reasonable notion of "security", the problem of breaking an OWF/PRG/PRF/UF is:

  • Easily in NP ("guess" the secret key, then whatever the security notion is trivializes)
  • Not in P (otherwise an efficient adversary could break it, so it would not be "secure").

Beyond that, there is the (related) question of

How do I leverage knowledge of a specific hard problem to build cryptography?

The answer is somewhat complex. If you can build a standard cryptographic primitive (a PRG/PRF/OWF/UF, or a trapdoor OWF), then things become very easy very quickly. Beyond that, I would point out that if you can build "standard primitives" that are "homomorphic", things also become fairly straightforward. But the general story is still being worked out --- lattice-based encryption was first proposed perhaps 25 years ago, but it took until roughly a decade ago for lattice-based signatures to be developed. This is to say that knowing how to develop (public-key) encryption didn't lead to signatures "for free" (despite PKE being a "harder primitive to build" in a certain formal sense).

There has been some progress on understanding what generic constructions one gets from the construction of certain primitives (this is what the paper I linked does), but it is all fairly recent.

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.