A semantically secure encryption scheme can not preserve the length of an encrypted plaintext.
How to prove this? or are there some methods that can be used to obtain such information from a semantic secure ciphertext?
8
-
$\begingroup$ Consider adversary sends $m_1$ and $m_2$ with $len(m_1) \neq len(m_2)$. If the semantically secure encryption scheme preserves the length, is there a way for the adversary lose the game? $\endgroup$– kelalakaCommented Oct 15, 2023 at 6:12
-
1$\begingroup$ @kelalaka The definition I know of semantic security requires $|m_1| = |m_2|$, otherwise the length of the output can't be bounded by a polynomial (because if it was you could encrypt $0$ and a random long enough string and they could always be distinguished). $\endgroup$– Command MasterCommented Oct 16, 2023 at 10:15
-
$\begingroup$ @CommandMaster Yes, I know about that, the question is about if they relax the condition, I've already told that is there a way for the adversary to lose the game... $\endgroup$– kelalakaCommented Oct 16, 2023 at 10:22
-
1$\begingroup$ @kelalaka I don't see the question mentioning a relaxation of that condition... in fact, OTP preserves the length of the plaintext, so I don't think I understand the question correctly $\endgroup$– Command MasterCommented Oct 16, 2023 at 10:31
-
$\begingroup$ @kelalaka, I think the question refers to something else. For example: a block cipher would be a lenght preserving scheme. But the game still needs to enficrce that the queries of the adversaries have the same lengths. $\endgroup$– Marc IlungaCommented Oct 16, 2023 at 17:56
|
Show 3 more comments
1 Answer
$\begingroup$
$\endgroup$
1
Well, widely accepted definition of semantic security as LOR-distinguishing game prohibits queries with messages of different length.
Moreover, OPT is length-preserving. Obviously, OTP meets semantic security requirements. Hence, the statement in question is false.
You probably mean, that CPA-secure cipher cannot be length-preserving. This statement is proven in the following way: a length-preserving cipher is a deterministic cipher (otherwise its encryption function is not bijective for some key), a deterministic cipher is not CPA-secure. Hence, a length-preserving cipher is not CPA-secure.
-
1$\begingroup$ This is a great point on showing that length-preservation has to imply some kind of bijection. Sone nitpicks, however: AFAIK; SS security is a simulation-based notion and not really the LoR. Furthermore, SS security is equivalent to IND-CPA with is equivalent to the LoR formulation. So I am not sure about the first part of the answer. I think the OTP is a somewhat separate case, since the encryption oracle is queried "once". With such restrictions, even bare-bones block ciphers meet CPA security notions. $\endgroup$ Commented Oct 16, 2023 at 20:22