3 Selected Design and Analysis Techniques for Contemporary Symmetric Encryption
61
receiver obtains z = z(k) = y ⊕ v = C ECC (C H (a||u)) ⊕ x ⊕ v and starts by
decrypting y = (C ECC (C H (a||u)) ⊕ x ⊕ v) ⊕ x = C ECC (C H (a||u)) ⊕ v. He then
first decodes C H (a||u). In the case of a successful decoding, he computes a using
C
−1
H and informs the transmitter he could decode. Otherwise he asks the transmitter
for a retransmission. This assumes noiseless feedback between the receiver and the
transmitter.
3.4.3 Security Evaluation
Information-Theoretic Security In [452], the above model of randomized encryption schemes was studied from an information-theoretic point of view. The goal was
to analyze the security enhancement provided by the wiretap encoding, in terms of
secret key k equivocation, that is, the uncertainty that an adversary faces about the
secret key, given all the information he could collect during passive or active attacks.
This analysis demonstrated a gain in unconditional security, and thus confirmed
the security benefit of the additional wiretap encoder, through tight lower bounds
(Lemmas 1 and 2 in [452]) and asymptotic values (Theorems 1 and 2 in [452])
of the secret key equivocation. The cost of this enhanced security is only a slightto-moderate increase in the implementation complexity and the communications
overhead. However, it also revealed that if the same secret key is used for too
long, the adversary may gather large enough samples for offline cryptanalysis. The
uncertainty then decreases to zero. Then starts a regime in which a computational
security analysis is needed to estimate the resistance against secret key recovery,
which motivated the current paper.
Computational Complexity Security Mihaljevi´ c and Oggier [420] presents a security evaluation of the considered technique in a chosen plaintext attack scenario,
which shows that the computational complexity security is lower bounded by the
related LPN (Learning from Parity with Noise) complexity in both the average
and worst cases. This gives guidelines for constructing a dedicated homophonic
encoder which maximizes the complexity of the underlying LPN problem for a
given encoding overhead.
Note Recall that in a chosen plaintext attack (CPA) scenario, the claim that a
scheme is secure in an information-theoretic sense means that even an attacker
with unlimited resources for recovering the secret key, in the considered evaluation
scenario, faces complete uncertainty about the secret key employed for encryption,
i.e., a set of equally probable candidates for the true secret key will exist. On
the other hand, a claim that an encryption scheme is secure in a computationalcomplexity sense means the following: Although the secret-key could be recovered
in a CPA scenario, and so it is not possible to claim information-theoretic security,
the computational complexity of this recovery is as hard as solving a problem which
belongs to a class of proven hard problems, as the LPN problem is.
61
receiver obtains z = z(k) = y ⊕ v = C ECC (C H (a||u)) ⊕ x ⊕ v and starts by
decrypting y = (C ECC (C H (a||u)) ⊕ x ⊕ v) ⊕ x = C ECC (C H (a||u)) ⊕ v. He then
first decodes C H (a||u). In the case of a successful decoding, he computes a using
C
−1
H and informs the transmitter he could decode. Otherwise he asks the transmitter
for a retransmission. This assumes noiseless feedback between the receiver and the
transmitter.
3.4.3 Security Evaluation
Information-Theoretic Security In [452], the above model of randomized encryption schemes was studied from an information-theoretic point of view. The goal was
to analyze the security enhancement provided by the wiretap encoding, in terms of
secret key k equivocation, that is, the uncertainty that an adversary faces about the
secret key, given all the information he could collect during passive or active attacks.
This analysis demonstrated a gain in unconditional security, and thus confirmed
the security benefit of the additional wiretap encoder, through tight lower bounds
(Lemmas 1 and 2 in [452]) and asymptotic values (Theorems 1 and 2 in [452])
of the secret key equivocation. The cost of this enhanced security is only a slightto-moderate increase in the implementation complexity and the communications
overhead. However, it also revealed that if the same secret key is used for too
long, the adversary may gather large enough samples for offline cryptanalysis. The
uncertainty then decreases to zero. Then starts a regime in which a computational
security analysis is needed to estimate the resistance against secret key recovery,
which motivated the current paper.
Computational Complexity Security Mihaljevi´ c and Oggier [420] presents a security evaluation of the considered technique in a chosen plaintext attack scenario,
which shows that the computational complexity security is lower bounded by the
related LPN (Learning from Parity with Noise) complexity in both the average
and worst cases. This gives guidelines for constructing a dedicated homophonic
encoder which maximizes the complexity of the underlying LPN problem for a
given encoding overhead.
Note Recall that in a chosen plaintext attack (CPA) scenario, the claim that a
scheme is secure in an information-theoretic sense means that even an attacker
with unlimited resources for recovering the secret key, in the considered evaluation
scenario, faces complete uncertainty about the secret key employed for encryption,
i.e., a set of equally probable candidates for the true secret key will exist. On
the other hand, a claim that an encryption scheme is secure in a computationalcomplexity sense means the following: Although the secret-key could be recovered
in a CPA scenario, and so it is not possible to claim information-theoretic security,
the computational complexity of this recovery is as hard as solving a problem which
belongs to a class of proven hard problems, as the LPN problem is.