Is there an encryption scheme where it's hard to guess a valid ciphertext without knowing the key and the scheme is CPA secure?
1
-
6$\begingroup$ What do you mean by "Guess a valid ciphertext"? For almost any non-authenticated encryption, almost any ciphertext will decrypt to something, even if it is meaningless garbage. $\endgroup$– Eugene StyerOct 13 at 22:29
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
From what I've found, it seems that GCM with a secure encryption algorithm (i.e. AES) is secure against ciphertext guesses and chosen plaintext.
GCM is an AEAD (Authenticated Encryption with Associated Data) cipher mode, meaning that each message has a MAC (Message Authentication Code) stored/transmitted alongside it. If the tag is invalid, then the algorithm stops before it can get any further (assuming it was implemented and used correctly). If an adversary manages to guess a tag (requiring $2^{96}$ or more tries), you have bigger problems.
From what I have gathered, as long as you use it properly (no IV reuse), it is chosen-plaintext secure. However, the security breaks down when an IV-key pair is reused, referred to as a many-time pad. This can lead to all sorts of bad things, like decryption of messages or even a total break. However, this security may lie in the algorithm (I'm not an expert).
In conclusion, AES-GCM should work for what was described. GCM authenticates the data and AES-GCM in general should be secure against chosen-plaintext attacks.
$\begingroup$
$\endgroup$
By definition, a secure authenticated encryption scheme is expected to guarantee what is essentially hard-to-guess ciphertext. More precisely, Bellare and Namprempre define the notion of integrity of ciphertexts or INT-CTXT, which guarantees that it should be hard for an adversary to create a new valid ciphertext even given access to an encryption oracle.
They then define AE security as:
$$\text{AE = IND-CPA + INT-CTXT}.$$
There are numerous constructions of secure AE(AD) schemes.
As a final note: "hard to guess" here does not make any statement on the distribution or randomness of the ciphertext. AE security does not need random ciphertexts at all. However, many modes used in practice have this property.
