4
$\begingroup$

A lot of cryptography is based on the assumption that ${\sf P} \neq {\sf NP}$.

Is it conceivable to construct a cryptography system based on a class of much harder problems than ${\sf NP}$-problems, namely undecidable problems such as the mortal matrix problem?

$\endgroup$
1
  • 4
    $\begingroup$ Would this Q/A resolve your question? $\endgroup$
    – Maarten Bodewes
    Commented Oct 14, 2023 at 22:18

4 Answers 4

11
$\begingroup$

Encryption, signatures, etc., can always be broken in NP.

  • You can break any encryption scheme if you can solve the following decision problem: "does there exist a secret key and encryption randomness that explains these ciphertexts as an encryption of these plaintexts?" This problem is in NP assuming the encryption algorithm runs in polynomial time.

  • You can break any signature scheme if you can solve the following decision problem: "does there exist a string starting with this prefix that makes the verification algorithm accept, using this public key?" Again, this is an NP problem if the signature verification algorithm runs in polynomial time.

Suppose you have a hard problem $X$, and an encryption scheme whose security reduces to $X$. Let's also suppose the security reduction is black box, meaning: given oracle access to an adversary who breaks the encryption scheme, you can efficiently break $X$. Since NP always contains a strategy to break the encryption scheme, there is always an algorithm to break $X$ in the complexity class $\text{P}^{\text{NP}}$. So you can't base cryptography on anything much "higher" than NP.

I suspect something similar can be said even if the reduction is not black-box, but I think the argument will be more tedious.

$\endgroup$
7
  • $\begingroup$ Do you mean to say that these can be broken by a polynomial-time algorithm? I'd have thought that would make them P, not NP – but I agree that they're NP. $\endgroup$
    – wizzwizz4
    Commented Oct 15, 2023 at 16:21
  • $\begingroup$ I mean that (1) those problems are clearly in NP by definition; (2) if there was a poly-time algorithm for these problems, then you could break the cryptographic schemes. But I think the way I wrote it was a little confusing. $\endgroup$
    – Mikero
    Commented Oct 15, 2023 at 17:30
  • $\begingroup$ Technically speaking, you could just embed an arbitrary Turing Machine into an encryption algorithm, then it's not necessarily in any particular complexity class. Of course, there's a difference between an arbitrary TM in the abstract and an actual TM that someone would be patient enough to embed in the process. $\endgroup$ Commented Oct 16, 2023 at 5:29
  • $\begingroup$ There is the one-time-pad which is not breakable in NP (because the answer to the first question is always "Yes", if ciphertext and plaintext have compatible length). $\endgroup$ Commented Oct 16, 2023 at 23:50
  • $\begingroup$ the problem with this accepted answer is that if I show you the ciphertext: "589" and tell you that the encryption algorithm used only a single message of 3 digits and a secret key of 3 digits and all I did was add them together, you would have absolutely no way of knowing whether I started with the message: "222" and the secret key "367", or if message was "123" and the key was "456", or any other possible combination. So clearly you can design an encryption scheme based on undecidable problems, since there's no algorithm that will ever be able to find the two components that went into a sum. $\endgroup$
    – mmm
    Commented Jan 3 at 20:20
12
$\begingroup$

It is impossible to build a cryptographic algorithm using uncomputable problems because you cannot compute them. It would be impossible to execute the encryption. In order to use a problem for encryption, you have to be able to answer it.

For example: you mention the mortal matrix problem, an undecidable problem. It has a "yes" or "no" answer, which is to say that it contains one bit of information. If you had a sufficiently large collection of sets of matrices for which the answer is undecidable, but somehow known to you, you could encrypt a message by exchanging every bit for some representation of a set of matrices with the corresponding answer (eg, "yes" = 1, "no" = 0).

However... it is no less impossible to generate these sets of matrices for you as it is for your 'enemy'. For cases where the answer is easy to work out (such as if all the matrices in a set are already the zero matrix), then you can use them, but you're no better off than using RSA where n = 6. In other words, if you know the answer, then the answer is not really undecidable – the problem may be undecidable in general, but your case is not one of the undecidable cases.

Basically, the way I specified the problem above — "if you had a sufficiently large collection..." — assumes the existence of an oracle – something that magically solves a problem for you. If that oracle really exists and only you and your interlocutor have it, then the whole system just reduces to a one-time pad (an encryption method already known to be unbreakable in theory) with extra steps. In the real world, though, you can't create that oracle because you can't solve the unsolvable problem.

$\endgroup$
1
$\begingroup$

It is certainly conceivable. The big issue is, most undecidable problems are of the form "create an algorithm which, for all possible inputs ...". Many of these problems are easy to solve for many inputs. We need to know that the problem is impractically hard for the inputs we actually used.

The attacker doesn't need to crack all possible messages under all possible keys. They only need to crack your message, under your key. That eliminates most undecidable problems from consideration.

Suppose, however, we have a problem that is undecidable for specific inputs we can use. Such that we can multiply two matrixes or whatever and know that, from the product, no attacker can determine if two such source matrices exist. That implies they can not calculate the matrixes we used. That is, the factorization is undecidable if we can't even decide whether such factors exist. We can easily see that would provide the important primitive for an equally unbreakable PRF - run the primitive repeatedly with output feedback.

Given an unbreakable PRF, we could use CTR mode to use it as an equally unbreakable cipher.

But the key here is knowing problem is unsolvable for specific inputs. As opposed to just saying there's not a solution that works for all inputs.

Also of course the encryption operation needs to be efficient for the user. Here we imagined a particular kind of matrix factorization is undecidable. That's useful only if the complementary multiplication is efficient.

$\endgroup$
0
$\begingroup$

assuming you have encryptionvthat has a pass phrase then you can go no higher, but what if there is no pass phrase and everything is operated on and evaluated WHILE it is in it's encrypted state? An encryption where it is not reversible, like time where it is for almost all practical purposes irreversable? not sure how you would construct it, but that's my thinking. Take it with a whole salt flat worth of salt though!

$\endgroup$
1
  • $\begingroup$ Encryption, by definition, is reversible. A hash function isn't, but the result is consistent, ie, the same input should always result in the same output. There is homomorphic encryption that allows computation without decryption, but it can still be decrypted, the idea is cloud servers can be utilized for their CPU without being privy to sensitive data. Anything else is either just writing to /dev/null and/or reading from /dev/random $\endgroup$
    – Martheen
    Commented Oct 17, 2023 at 1:57

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.