Can a computationally unbounded adversary break any public-key encryption scheme?

Assume there is a public-key encryption scheme $(KeyGen, Enc, Dec)$ with perfect correctness (i.e., for all messages M and valid key-pairs (PK,SK), we have $Dec_{SK}(Enc_{PK}(M))=M$).

Will there always be a function $A$ such that for all messages M and valid public-keys PK, $A_{PK}(Enc_{PK}(M))=M$?

In other words, can a computationally unbounded adversary decrypt the message, having only the public key?

• I edited your question to look more like a question and less like a homework task. Feel free to edit it again to make it more clear. Sep 25, 2011 at 14:29
• Well, in light of the rewording of the question, I'd say yes it is possible for a computationally unbounded adversary to decrypt a message. Not sure why I was negative voted, as I have clearly demonstrated how this would be done using a simplified example. Nevertheless, if somebody were to answer the initial question, only to have it down-voted when the question changes, I prefer to retract my answer.
– user476
Sep 26, 2011 at 2:04
• @Bill Sorry, I did not intend to change the meaning of the question with my edit, I only intended to make it less "home-work-y" and more "question-y". Do you really feel the original question (or the question after huyichen's first edit) was in core other than it is now? Sep 26, 2011 at 10:31
• @PaŭloEbermann - No problem Paulo. I agree with your reasoning since we do not want to be providing solutions to assignment questions. That is why I have always been careful (in the past) of not providing too much detail in my answers. In this case, however, I may have gone a bit overboard.
– user476
Sep 26, 2011 at 10:38

Yes, a computationally unbounded attacker can break any public key system.

One easy way to see this is to consider the KeyGen algorithm, which takes takes as input a value R (which in normal use is the output of some random number generator), and outputs a public key PK and a private key SK.

Now, what a computationally unbounded adversary can do is consider all possible inputs R, and see which one produces the public key that he has been given. We know that there is at least one such input R (the one that was used when the public key was created); we can then use the corresponding private key to decrypt the message.

The obvious objection to this is "what if there are multiple such R's which generate the same public key, but different private keys?". Actually, it turns out that this is not a problem; because each such private key SK was generated correctly by the key generation function and corresponds to the public key under attack, it must still satisfy the formula:

$Dec_{SK}(Enc_{PK}(M)) = M$

Hence, it must correctly decrypt the message, even if it was not the exact private key that the legitimate user had.

I believe that the whole point of developing secure encryption schemes is to prevent such scenarios from occurring. With respect to the ElGamal encryption scheme, though, the above scenario is possible if the same random number (called the commitment) is used to encrypt two or more messages. The cryptanalyst can use this information to recover the private key.

To answer this question thoroughly, though, one needs to explain how set up and encrypt messages using the ElGamal coding scheme. Choosing the keys requires selecting a large prime number $p$. For security reasons, $p$ needs to be a number of at least 2000 bits, or 600 decimal digits.

First, select a primitive root $a \pmod{p}$. Note that finding a primitive root will be similar to finding a primitive element for cyclic groups. Also, select a number $b$ with $1 \leq b < p - 1$. This will be our private key. Calculate $c \equiv a^{b} \pmod{p}$ as a least residue modulo $p$. Note that $c \not\equiv 0, 1 \pmod{p}$. Publish $p$, $a$ and $c$ as the public key, and keep $b$ secret as the private key.

To encode a message, we must first translate the text into a numerical string using the ASCII collating sequence, or another agreed method (e.g. EBCDIC). Break this numerical string into blocks, each a number $x$ with $0 \leq x < p$. For each block $x$, choose a random number $r$ (called the commitment) with $1 \leq r < p - 1$. This number should be different for each block, for reasons that are explained below. Compute $y_{1}$ and $y_{2}$, with $0 < y_{1}$, $y_{2} < p$ by assigning $y_{1} \equiv a^{r} \pmod{p}$ and $y_{2} \equiv x \cdotp c^{r} \pmod{p}$. Finally, transmit $y_{1}$ and $y_{2}$, in that order.

To decode a message, we must first calculate $x$ with $0 \leq x < p$ by assigning $x \equiv y_{2}(y_{1}^{b})^{-1} \pmod{p}$, and then collect the decoded blocks into a numerical string which is translated to text by the agreed method.

As an example, to encode the message HELLO, we first translate the text into a numerical string using the ASCII collating sequence. This becomes the numerical string 72 69 76 76 79. For simplicity, we choose $p = 97$, $a = 10$ and $b = 2$, and calculate $c \equiv a^{b} \equiv 10^{2} \equiv 100 \equiv 3 \pmod{97}$. We then publish $p = 97$, $a = 10$ and $c = 3$, and keep $b = 2$ private.

Next, we split the numeric strings into blocks of two digits; that is, one letter in each block. For block $x = 72$, we choose $r = 2$, which results in $(y_{1}, y_{2}) = (3,66)$. Similarly, for block $x = 69$, we choose $r = 3$, which results in $(y_{1}, y_{2}) = (30,20)$. For blocks $x = 76$, we choose $r = 4$ and $r = 5$, respectively, and for block $x = 79$, we choose $r = 6$. Collectively, this results in the following message being transmitted:

(3,66), (30,20), (9,45), (90,38), (27,70)


If one were to use the same random number (or commitment), say $r = 2$, to encode different blocks, this would result in the following message being transmitted:

(3,66), (3,39), (3,5), (3,5), (3,32)


Notice that $y_{1}$ is repeated for each block, and that there is no entropy or dispersion of characters in the message that is encoded, meaning that if an intruder or cryptanalyst were to know (or guess) the message of the first (or any consecutive) block, he/she would be able to use it to find the multiplicative inverse of $(y_{1}^{b})^{-1}$, without the knowledge of the private key, and therefore use it to decode the rest of the message in the remaining blocks.

Remember, to decode a message, we use $x \equiv y_{2}(y_{1}^{b})^{-1} \pmod{p}$. So, if we were to know that $(3, 66)$ decodes to $72$, we can use this information to determine that $(y_{1}^{b})^{-1} = 54$, using the Euclidean algorithm for solving linear congruences. We can then use this to decode the message in the remaining blocks. Hence, $(3,39)$ translates to $69$, $(3,5)$ translates to $76$, and $(3,32)$ translates to $79$.

Note that this is a very simplistic example, and typically measures will be taken to prevent such a cryptanalysis of the message. Other methods of cryptanalysis typically involve dictionary attacks on the passphrase, or brute force attacks on the private key.

• Well, in light of the rewording of the question, I'd say yes it is possible for a computationally unbounded adversary to decrypt a message. Not sure why I was negative voted, as I have clearly demonstrated how this would be done using a simplified example. Nevertheless, if somebody were to answer the initial question, only to have it down-voted when the question changes, I prefer to retract my answer.
– user476
Sep 26, 2011 at 2:03
• I don't think this answered the original or revised question.The question is not asking about re-use of randomness. It's not asking whether there exists a public-key scheme that can be broken by an unbounded attacker; it's asking whether all public-key schemes can be broken by such an attacker (\forall vs \exists). In addition, your answer contains some inaccurate statements: e.g., "the whole point of developing secure encryption schemes is to prevent such scenarios from occurring" - this is not correct. I wonder if you might have misunderstood the question.
– D.W.
Sep 26, 2011 at 2:44
• @D.W. - Sorry to have to break it to you but, unless I misunderstood, the initial question posted was an existential one. Whether or not you agree with my opinion is your problem. And, in light of our recent exchange to this and other posts, it appears that you do have a problem with me specifically. Not that I want to insult your intelligence but, if you think you are so knowledgeable on the topic, why don't you post a solution to this question rather than criticizing and/or down-voting mine.
– user476
Sep 26, 2011 at 3:44
• I read the original question, and your characterization is not accurate. It says: "Show the following: [...] If there is a public-key encryption scheme [...] then there is a function A [that breaks the encryption scheme]". Moreover, as I already mentioned, reuse of randomness attacks are not in scope, so your attack does not actually solve the question as originally asked. This is not a matter of opinion; it is a matter of mathematics. I'm sorry that you are taking it personally, but I assure you that I do not have a problem with you -- my interest is in ensuring accuracy.
– D.W.
Sep 26, 2011 at 4:06
• Good morning everyone. So in the interests of not letting this get out of hand - here's what I think. I think it's hard to criticise constructively and not hurt feelings. That said, @D.W. I think the best course of action when you disagree with something is to use your vote (you're entitled to do that) - for minor issues (did you mean XYZ?) comments work, but otherwise propose an alternative solution. That way the better answer should be voted up more - comments have much less visibility in terms of being read.
– user46
Sep 26, 2011 at 8:15