Do there exist information theoretic secure public key crypto-systems? Are they useful in any way, or are they just mathematical curiosities?

  • 1
    $\begingroup$ I can think of only one way of making any information theoretic public key that is using an information theoretically hiding (perfect/statistically) commitment to private key as public key. Note that binding public key to private key will only just be computational. I don't see how it can be useful for encryption, however. The public key itself does not have significant (if any) information about the private key, and use of different private keys would likely result in different plaintext. $\endgroup$ Jul 9 at 5:37
  • 2
    $\begingroup$ I am fairly certain, this can not exist. But I can't recall a proof or reference for that. But it should not be too difficult to prove (the public key fixes the private key, randomness has to be removable by the decryption, and decryption must be unique). Just keep in mind, the attacker can try out every combination of message and randomness for encryption. $\endgroup$
    – tylo
    Jul 9 at 9:12

1 Answer 1


If the cryptanalyst has no information about the public key, then there is. Otherwise there is not, but there a a closely-related concept of semantic security.

Information theoretic security when the public key is unknown

An example here would be the El Gamal encryption scheme in a group of prime order. If the cryptanalyst is handed the ciphertext $(c_1,c_2)$ and now information about the public key and has a putative guess for there message $m$, then there is a consistent private key $k$ which is the solution to $c_1^k=c_2/m$. If private keys are chosen uniformly at random, then there is no additional evidence for any given message over another.

Impossibility if public key is known

If this were true then every cryptogram that were constructed by a sender would have to be able to be decrypt able as an arbitrary message under some private key. This would mean that there were multiple private keys associated to a single public key, but the sender would not be able to know which is possessed by the receiver and so cannot send a message with correctness.

Related concept

There is however the concept of semantic security which stipulates that it should be computationally infeasible to guess with advantage whether a particular plaintext corresponds to a given ciphertext. For deterministic public key encryption schemes, this is not possible as an adversary will simply encrypt the putative plaintext and compare it to the ciphertext. Therefore for semantic security there must be some inexhaustible level of randomisation. Again El Gamal is a good example when used in a group where the decisional Diffie-Hellman property holds. If the generator $g$ is used with public key $a$ then testing whether the ciphertext $(c_1,c_2)$ corresponds to the message $m$ is equivalent to solving $DDH_g(a,c_1,c_2/m)$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.