# Given the existence of provably-hard-to-solve problems, why do we routinely rely on conjectured-to-be-hard problems for encryption?

Let $$(X, Y, Z)$$ be a set of binary strings of length $$n$$. Let random $$X$$ be the private key for encoding (or decoding) message random $$Y$$ as $$Z$$. Let the encryption algorithm $$m$$ be a matching function, i.e., for $$m(X, Y) = Z$$, if $$x_i = y_i$$, $$z_i = 1$$, otherwise $$z_i = 0$$. Now, $$m$$ is clearly not a one-way function: given output $$Z$$, it is trivial to define some string pair such that $$m(X, Y) = Z$$. However, it is impossible to obtain the particular encoded message from the encrypted message without the private key.

Reusing the key repeatedly does not compromise it, given that $$Z$$ provides no information (entropy) about $$(X, Y)$$. To wit, suppose an eavesdropper collects a set of $$k<2^n$$ distinct encrypted messages $$Z$$, all encrypted using the same $$X$$. This tells the eavesdropper nothing about $$(X, Y)$$, and therefore nothing about $$Y$$, because it's just a random subset of all $$2^n$$ possible $$Z$$ of length $$n$$. Thus, if my reasoning is correct, the strength of the encryption is limited only by $$n$$.

Given the existence of such provably hard problems, why do we rely on supposedly one-way functions that might turn out to not be hard? Like, say, factoring the product of a pair of large primes? Or, is its equivalent used in some form I do not recognize?

Note: Corrected to clarify that the original message is random, and that breaking it is not impossible but provably hard.

• but you can collect relations about your mapping as different plaintext ciphertext pairs are accumulated--a basic use of kerchoff's principle states that known and chosen plaintext attacks are allowed. by definition, the more relations you collect the more information is leaked. Apr 10, 2023 at 19:39
• That encryption function $m$ is just bitwise complement of one-time pad. Apr 10, 2023 at 19:52
• @kodlu, are you saying that Kerckhoffs’s principle implies that the attacker will be able to obtain $Y$ even when only $Z$ is public? In this particular scenario, where both the private key and the unencrypted message are random strings, and therefore interchangeable, I don't see why old Kerckhoffs should allow me to keep one secret but not the other. Especially given that $Y$ changes over time but $X$ does not$-$seems easier to leak the value of a constant than to leak many values of a variable. Still, if that's the general interpretation, then this does become less secure with use. Apr 10, 2023 at 19:58
• If you assume that the message $X$ is random and unknown, DES encryption is provably secure - given a DES encrypted ciphertext, it is possible to compute the $2^{56}$ possible decryptions of the ciphertext, but you won't be able to tell which one is correct (because all the decryptions look random). Should we use this as an argument to use DES? Apr 10, 2023 at 20:18
• @poncho, you answer a sub-question in my question ("is its equivalent used in some form...?") since my algorithm is a block cipher with a key, like DES, with all the insecurities of such ciphers. Perhaps a larger question is: could you replace the factorization problem at the heart of a secure cryptosystem with a similar block cipher, or do you need a one-way function? I.e., could you use a function for which it is easy to obtain a workable preimage, but hard to obtain THE preimage? Could you use my strings $(X, Y)$ instead of primes $(p, q)$? Apr 10, 2023 at 20:41

Even if an eavesdropper collects an arbitrarily large set of (distinct) encrypted messages, all generated using the same $$X$$, there will still be infinitely many degrees of freedom for $$X$$ and $$Y$$ conditional on that set.... Thus, if my reasoning is correct, the encryption is unbreakable.

Hold your horses; this is known to be incorrect.

What you propose (for two different values of $$Y$$) is known as 'two-time pad'; that is known to be breakable.

If the attacker has $$m( X, Y )$$ and $$m( X, Y')$$, he can exclusive-or those two together; what that is happens to be the same as $$Y \oplus Y'$$, that is, the exclusive-or of the two plaintexts. Now, for completely random unknown plaintexts, that doesn't tell the attacker that much (although it is quite sufficient to break the CPA assumption); on the other hand, plaintexts are often not completely random, but instead have a lot of structure, and the attacker can use that structure to recover the plaintexts. For example, if $$Y, Y'$$ are ASCII English plaintexts, then simple crib-dragging will recover the plaintexts with not that much work...

It turns out to be informationally secure, to protect $$n$$ bytes of plaintext, you have to use at least $$n$$ bytes of key (which can't be used for anything else). Hence, the reason we don't use these techniques is that transporting the key is generally infeasible (and often no easier than the 'transporting the plaintext' problem we are originally trying to solve). One of the ways of looking at cryptography is 'turning a long secret into a short secret' (e.g. by encrypting a long message with a shorter key); this is not what these 'informationally secure' methods do.

• Good point: I corrected this passage specifically in the question (see note at bottom). The claim is now that, given a random $Y$, and assuming $X$ remains secret, an attacker with any number of observed, encrypted messages $Z$ gains no information about either $X$ or any $Y$ (past or future). Apr 10, 2023 at 19:10

The flaw in your argument is the assumption that the original plaintext messages are random. Any real message must have some structure, otherwise the intended recipient has no way to interpret it. (If it's a compressed image, for example, there must be a file header to allow decompression.) If your message has any such structure in it, then the eavesdropper can use codebreaking tricks (like the XOR that Poncho suggested) to extract information.

If you have some way to (reversibly) turn a meaningful message into one that is indistinguishable from random noise, then that in itself is already a valid encryption method, and no additional step is necessary.

• I think when we say "message" we don't literally mean syntactic content, we mean information. Information is a correspondence between two things, such that one may draw a (deterministic or probabilistic) inference from one to the other. So, my email password may literally be a random character string, but the correspondence between the password I input and the password on file is information about my identity. Apr 11, 2023 at 16:51
• This is a cryptography forum. When we say "message", we do literally mean a specific sequence of bits, not some ill-defined notion of abstract information. Apr 12, 2023 at 0:56
• Right, but "specific" and "random" are not antonyms. If I generate a random sequence and assign a (nominal) meaning to that sequence, its values remain random but the sequence now has a specific meaning. Again, that's how passwords work. As for "ill-defined," I admit my wording was crude, but I refer you to the eloquent and seminal work of Kolmogorov (1965) where he establishes a very crisp definition of conditional algorithmic information as the correspondence between a pair of strings. Apr 13, 2023 at 5:38

Your system cannot be more secure than a one-time pad (OTP) which has perfect secrecy. If analyzed [this is up to you to demonstrate security] it will most likely turn out to be less secure than an OTP. By the way, there are not infinitely many degrees of freedom for a system which is dependent on finite length strings, as you defined it.

There is one reason for not using a one-time pad, which has perfect secrecy, unlike yours, which is efficiency.

The transport of the key securely for a one time pad (key is as long as the message and the OTP is a symmetric cryptosystem) requires that a secure channel is already established and such a long key can be securely shared, which means the OTP is not needed.

In the normal setup, short symmetric keys (128 bits say) are shared using public key cryptography which are long term authenticated keys.

• Good points, I corrected the passage to say that the number of possible $(X, Y)$ does not change for any number of observed $Z$, not that there are infinitely many possible $(X, Y)$. However, I disagree that OTP is equally secure, if it can only be used once. See my revised rationale for why reusing it does not compromise it, given a random $Y$. Apr 10, 2023 at 19:15
• The necessity of establishing a secure channel is a good reason to prefer something like RSA. I wonder if one could, essentially, lift the factorization problem out of the general public-private key framework and replace it with a problem like this one, which (I argue) is provably hard. Apr 10, 2023 at 19:27