Let’s say I have a problem that can only be solved with a trapdoor, but regardless of whether the trapdoor is right or wrong, you can’t check if you have found the solution to the problem. To what class of complexity theory does such a problem belong? And more importantly, can a quantum computer solve such a problem?
11
-
$\begingroup$ Can you give an example of such a problem? I don't find it conceivable. $\endgroup$– Mateus AraújoFeb 9, 2022 at 9:25
-
$\begingroup$ Well that would be the hard part, but I wanna know if that’ll be uncrackable by a quantum computer. That way I’ll know I’m using my time right by finding such a problem $\endgroup$– Shahid KhanFeb 9, 2022 at 9:27
-
2$\begingroup$ I think you're wasting your time. $\endgroup$– Mateus AraújoFeb 9, 2022 at 10:21
-
2$\begingroup$ Can you give a clear mathematical definition of the properties you want? I'm struggling to understand how it's not a contradictory definition. $\endgroup$– DaftWullieFeb 9, 2022 at 10:56
-
3$\begingroup$ @ShahidKhan That's not what he meant. How do the receiver knows they have the correct trapdoor/they correctly deciphered the message? What you describe is exactly a One-Time Pad: even if you test the correct trapdoor (key), you can't know whether that was indeed the message that was intended, because all messages have the same probability in that case. And even in this case, there has to be a criteria the receiver can use to determine whether they have the correct key $\endgroup$– Tristan NemozFeb 9, 2022 at 16:56
|
Show 6 more comments
1 Answer
$\begingroup$
$\endgroup$
5
Ok, now I understand what you mean. You want something like the one-time pad, where for any message of the correct length there is an encryption key that gives you that message. It is not possible to check which of the messages is the correct decryption, you need to have the correct encryption key.
It is not possible to solve this problem at all, with a quantum computer or anything. This is proven rigorously in information theory: the encrypted text has zero mutual information with the source text.
As for the complexity class, it doesn't have one. Complexity theory deals with problems where all the necessary information is available.
-
$\begingroup$ So can we use such a system as a security measure against quantum computers? $\endgroup$ Feb 10, 2022 at 11:12
-
1$\begingroup$ Yes, the one-time pad is secure against quantum computers. $\endgroup$ Feb 10, 2022 at 13:11
-
$\begingroup$ But do bear in mind the "problems" mentioned in Mateus's link, especially the unavoidable difficulty of securely distributing the one-time pad to everyone who should have it and no one who should not! Even for personal use, a one-time pad is only as secure as the lockbox you keep it in. $\endgroup$– jecadoFeb 10, 2022 at 15:03
-
$\begingroup$ Yeah what if we could somehow convert this otp to a public key protocol? Wouldn’t that fix the distribution problem? That is, create an unsolvable protocol like this, except it’s a public key protocol like RSA $\endgroup$ Feb 10, 2022 at 15:14
-
$\begingroup$ @ShahidKhan This question has an answer on Crypto SE. Basically, in a public-key protocol, any adversary can encrypt arbitrary messages using the public key and check whether it matches the ciphertext. This is true for any public-key system. Note also that there is no collision: two messages can't have the same ciphertext otherwise it wouldn't be possible to decrypt it. Thus, there is a criteria an adversary can use to decrypt any ciphertext, so there's no perfect secrecy here. $\endgroup$ Feb 11, 2022 at 8:23