3
$\begingroup$

Looks like there is cryptography based on NP-hard problem, e.g. McEliece cryptosystem. The algorithm is an asymmetric encryption algorithm and is based on the hardness of decoding a general linear code (which is known to be NP-hard)

We are trying to strengthen this result.

Q1: Is strictly harder than NP-hard cryptography encryption or signature algorithm possible?

We don't allow One-Time Pads (OTP) and similar external secrets.

Conjecture J1: the answer is negative via generic attack of symbolic execution and then solve SAT with NP-oracle.

J1 implies that if a C language program implements some cryptographic algorithm and runs in time $X$ milliseconds, then the symbolic execution size of the CNF formula that breaks the algorithm is polynomial in $X$. XXX make this more rigorous.

It may be a good idea to unroll the loops by hand and ask about loopless programs.

Counterexample to J1 might be candidate for hard cryptography.

The main problem with J1 is that the resulting CNF might be of exponential size. We did some experiments with CBMC: Bounded Model Checker with factorization and the hash function SHA256 and the CNF were small enough.

Here is toy RSA example with zero knowledge of integer factorization:

 void main() {
 int nondetint();/* can be anything */
 int p,q,n;
 p=nondetint();
 q=nondetint();
 n=p*q;
 __CPROVER_assert(!(n==13*17 && 1 <p && p <n && 1 < q && q <n),"factor");
 }
 $cbmc --trace factor1.c

This approach might be used to mine bitcoins SAT solving - An alternative to brute force bitcoin mining.

Also this appears consistent with the fact that if P=NP all crypto will break.

Potential candidates are $\Sigma_2^p$-hard problems.

Improve this question
$\endgroup$
13
  • 4
    $\begingroup$ Is there existing NP-hard cryptography? $\endgroup$
    – Alex
    Commented Sep 19, 2020 at 16:04
  • 3
    $\begingroup$ McEliece's cryptosystem is based on the hardness of decoding a general linear code, which is NP-hard. It might not be the most efficient cryptosystem today, but it isn't "broken" in any sense. $\endgroup$
    – Ben Smith
    Commented Sep 20, 2020 at 13:41
  • 2
    $\begingroup$ Could you point to a definition of "NP-hard crypto" for the outsiders, please? Also, is there a way of making "we don't allow One Time Pads (OTP) and similar external secrets" less hand-wavy? $\endgroup$
    – Andrej Bauer
    Commented Sep 20, 2020 at 16:30
  • 1
    $\begingroup$ NP Hard is a lower bound on hardness, not an upper bound. "Harder" than NP Hard implies NP Hard $\endgroup$
    – wlad
    Commented Sep 20, 2020 at 19:21
  • 2
    $\begingroup$ I don't have an opinion on the conjecture, I'm not even sure it's well-posed (cf. @ogogmad 's comments). I'm a bit confused by the inclusion of OTP here, to be honest: with OTP you're looking at information-theoretic security, not algorithmic complexity. $\endgroup$
    – Ben Smith
    Commented Sep 21, 2020 at 15:16

1 Answer 1

Reset to default
9
$\begingroup$

I think I may not understand your model of cryptography. My model would be that encryption is a polynomial time computable, injective, function from plaintexts of length $m$ to cipher texts of length $n$, and decryption is inverting this function. In that case, such a problem will always be in NP.

Indeed, we must have $m \leq n$, since we require that encryption be injective. Given a coded message of length $n$, the plaintext is then a witness of length $m \leq n$ that shows that the decoding can be found. So an NP-oracle can always just guess the message, and then check in polynomial time that its guess is correct.

Which aspect of your model am I missing?

Improve this answer
$\endgroup$
5
  • $\begingroup$ Thanks. This makes sense, you are not missing anything. I though at very abstract level of breaking the underlying math: since there are harder than NP problems, can crypto benefit from this. $\endgroup$
    – joro
    Commented Sep 21, 2020 at 14:26
  • 1
    $\begingroup$ Since the discussion is concerned with asymmetric encryption, shouldn't "polynomial time" have a dependence on key length? $\endgroup$
    – S. Carnahan ♦
    Commented Sep 21, 2020 at 17:14
  • 2
    $\begingroup$ @S.Carnahan Yes, but the trouble is that now we get into modeling issues. Quite likely, the map (key, message) to cipher text is not invertible. Rather, as a code breaker, my goal is to find a preimage (key, message) where the message is plausible English text. I wanted to make the OP spell out their choices here instead of trying to guess. $\endgroup$
    – David E Speyer
    Commented Sep 21, 2020 at 21:59
  • 1
    $\begingroup$ For any model I can think of, decryption is in NP. $\endgroup$
    – David E Speyer
    Commented Sep 21, 2020 at 22:39
  • $\begingroup$ @David E Speyer what is your idea about keyless cryptography such as hash function? In this case the encrypted message is shorter than the message. $\endgroup$
    – Shahrooz
    Commented Sep 24, 2020 at 13:48

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .