Fabrizio Biondi
email: fabrizio.biondi@inria.fr

Thomas Given-Wilson
email: thomas.given-wilson@inria.fr

Axel Legay
email: axel.legay@inria.fr

Axel Legay Attainable

Attainable Unconditional Security for Shared-Key Cryptosystems

Keywords: unconditional security, perfect secrecy, entropy, max-equivocation, private-key cryptography, symmetric encryption

Preserving the privacy of private communication is a fundamental concern of computing addressed by encryption. Information-theoretic reasoning models unconditional security where the strength of the results does not depend on computational hardness or unproven results. Usually the information leaked on the message by the ciphertext is used to measure the privacy of a communication, with perfect secrecy when the leakage is zero. However this is hard to achieve in practice. An alternative measure is the equivocation, intuitively the average number of message/key pairs that could have produced a given ciphertext. We show a theoretical bound on equivocation called max-equivocation and show that this generalizes perfect secrecy when achievable, and provides an alternative measure when perfect secrecy is not. We derive bounds for maxequivocation for symmetric encoder functions and show that max-equivocation is achievable when the entropy of the ciphertext is minimized. We show that max-equivocation easily accounts for key re-use scenarios, and that large keys relative to the message perform very poorly under equivocation. We study encoders under this new perspective, deriving results on their achievable maximal equivocation and showing that some popular approaches such as Latin squares are not optimal. We show how unicity attacks can be naturally modeled, and how breaking encoder symmetry improves equivocation. We present some algorithms for generating encryption functions that are practical and achieve 90 -95% of the theoretical best, improving with larger message spaces.

Introduction

Preserving privacy of private communication is a fundamental concern of computer science. Modern efforts can be divided into two categories: computational and unconditional security. Computational security of the privacy of a message depends on the assumed superpolynomial lower bound on complexity of some particular functions, e.g. factorization. Such lower-bound results are currently unproven, and may be weakened by technological progress in engineering, algorithmic theory, or quantum computing. Unconditional security is based on information-theoretic reasoning and proven independently of computational hardness. For this reason, unconditional security results are more general and solid than computational security results. However, the strict requirements to obtain unconditionally-secure cryptographic algorithms can make them generally impractical.

The first formal results on unconditional security were published by Shannon [START_REF] Shannon | Communication Theory of Secrecy Systems[END_REF] using results from the formal theory of communication that he had just invented [START_REF] Shannon | A mathematical theory of communication[END_REF]. Shannon considers the transmission of an encrypted message on a public channel between a sender A and a receiver B that share a cryptographic key. Shannon investigates how long the key has to be to transmit the message with perfect secrecy, meaning that an eavesdropper E intercepting the encrypted message obtains no information about the original message. Shannon proves that to achieve perfect secrecy the key must be as long as the message and can be used only once, and that the one-time pad algorithm achieves this under uniform key distribution. This means that, to transmit each n-bit long message, the sender and receiver have to have previously agreed on a fresh n-bit long key, which is often impractical. Perfect secrecy is proven to be unachievable with a shared key shorter than the message to be transmitted.

In this work we consider the same scenario in which a key with a different size to the message is shared between A and B, and an encoder function using the key is used to encrypt the message into a ciphertext that is transmitted by A to B on an unsecured channel. To ensure that the ciphertext is uniquely decipherable by B using the key, the encoder function must be injective when the key is fixed. We call this property semi-injectivity on the message. Such encoders are asymmetric in that they only require semi-injectivity on the message. However, many popular techniques and prior work consider symmetric encoders that also require semi-injectivity on the key.

We ask how many bits of message can be sent while respecting a suitable definition of unconditional security. However, we want to define a security condition that is also attainable when the key is smaller than the message, since this is the most common case in practice.

Since perfect secrecy cannot be achieved in this scenario, we define the maximum achievable security and how to attain it. Secrecy, as defined by Shannon, is a measure based on mutual information, and measures how much information is leaked by the communication, but not how hard it is for the attacker to decrypt the message given this leaked information. Instead of measuring secrecy, we measure the message equivocation of the encryption, measured as the con-ditional entropy of the message given the ciphertext. Equivocation, introduced by Shannon, measures how difficult it is for the attacker to decrypt the message after intercepting the ciphertext. Intuitively, equivocation measures the average number of message/key pairs that could have produced a given ciphertext.

We show a theoretical upper bound on equivocation, and we call this condition max-equivocation. We show that max-equivocation generalizes perfect secrecy, corresponding to perfect secrecy when the latter can be achieved and providing a characterization of maximum possible security when perfect secrecy cannot be achieved.

We derive upper and lower bounds to equivocation. For symmetric encoders we show that max-equivocation is achieved when the entropy of the ciphertext is minimized, contrarily to intuition. That is, the best theoretical encryption scheme is one that minimizes the entropy of the ciphertext.

We discuss key re-use through the perspective of max-equivocation and show that key re-use is easily accounted for. Further, that max-equivocation can be used in key re-use scenarios to consider when a key is reaching an unacceptable level of security and so should be changed.

We show that having much more entropy in the key than the message immediately loses this extra entropy the first time the key is used. This indicates that using excessively large keys is wasteful, and instead it is better to use parts of a large key as smaller keys to achieve better overall equivocation.

We then consider encryption functions under this new perspective and show that in general the theoretical best is not achievable. We present necessary and sufficient conditions on the probability distribution over the messages for max-equivocation to be achievable. Further, we show that popular approaches to encryption functions, such as Latin squares [START_REF] Bruen | Cryptography, Information Theory, and Error-Correction: A Handbook for the 21st Century[END_REF][START_REF] Mileva | Quasigroup representation of some Feistel and generalized Feistel ciphers[END_REF], are also not practically optimal.

One potential weakness of cryptosystems is the unicity problem [START_REF] Shannon | Communication Theory of Secrecy Systems[END_REF], i.e. the fact that the eavesdropper could use the redundancy in the language of the message to gain information. We show how the unicity problem can be addressed by considering a message space divided into valid messages with positive probability and invalid messages with probability 0. Further, we show that asymmetric encoders can better account for invalid messages.

We revisit the prior results on symmetric encoder functions for asymmetric encoder functions, and show that they can still be derived in a meaningful manner. However, finding the theoretical max-equivocation for a given message and key distribution is a more complex optimization problem.

We present some algorithms for generating symmetric encoder functions from the message and key information that are practical and achieve reasonably good results. In general these give solutions with a quality of 90 -95% of the theoretical best when the message space is less than 2 9 , and the quality improves as the message space increases in size.

We test different refinements to the best performing algorithm, achieving a few percentage points worse than the base algorithm for quality, in as little as approximately 55% of the runtime.

The structure of the paper is as follows. Section 2 recalls key concepts. Section 3 introduces max-equivocation and theoretic bounds. Section 4 explores key re-use and when the key has more entropy than the message. Section 5 presents results on when the theoretic bounds can and cannot be achieved. Section 6 addresses the unicity problem by considering messages with 0 probability. Section 7 considers allowing multiple keys to map the same message to the same ciphertext. Section 8 introduces and evaluates some heuristic algorithms for finding encryption functions in practice. Section 9 draws conclusions.

Related Work

This paper is an extended version of [START_REF] Biondi | Attainable unconditional security for shared-key cryptosystems[END_REF]. The content has been extended considering feedback received on the previous version. New material includes Sections 4, 5.4, 6, 7, and 8.5.

Other works have considered variations or alternatives to perfect secrecy in shared-key cryptosystems. Csiszár and Körner [START_REF] Csiszár | Broadcast channels with confidential messages[END_REF] introduce -secrecy as a relaxing of the requirement of perfect secrecy to I(M ; C) ≤ for a given . Ho et al. [START_REF] Ho | Error-free perfect-secrecy systems[END_REF] consider the bounds required for perfect secrecy in the sense of Shannon, while considering key reuse, and parameterise by the entropy of the message space. Russell and Wang [START_REF] Russell | How to fool an unbounded adversary with a short key[END_REF] consider entropic security as an alternative, that considers min-entropy bounded statistical security measures and smaller key spaces.

The design of encryption functions, or their components such as S-boxes, has been widely studied [START_REF] Wu | Dynamic and implicit latin square doubly stochastic s-boxes with reversibility[END_REF][START_REF] Mileva | Quasigroup representation of some Feistel and generalized Feistel ciphers[END_REF][START_REF] Wu | Design of image cipher using Latin squares[END_REF], particularly when designing optimal systems. The results here suggest that when the message space (or inputs to an S-box) are non-uniformly distributed then the result cannot ensure maxequivocation. Further, finding optimal functions should not be limited merely to Latin squares/rectangles, since higher max-equivocation can be achieved without such tight restrictions.

Background

This section recalls definitions and concepts from the literature pertinent to this paper. In particular we recall and define terminology in a manner useful for the results of this work.

We denote with |S| the size of set S. Given sets A and B we say that a function f :

A → B is injective if ∀a 1 , a 2 ∈ A it holds that f (a 1 ) = f (a 2 ) ⇒ a 1 = a 2 .
Further, we shall denote with a the sequence a 1 , . . . , a i .

Probability and Entropy

A probability distribution is used to model the (partial) knowledge of an agent about a fact, e.g. the content of a secret message being transmitted by another agent. Let X be a discrete random variable taking values from a sample space X . A probability distribution on X is a function ρ X : X → [0, 1] such that 1 = x∈X ρ(x). We will just write ρ(X) when the sample space is evident from the context. We write ρ(X, Y ) for the joint probability distribution on ρ(Y ) . Two random variables X and Y are said to be independent of for each x ∈ X, y ∈ Y it holds that ρ(x, y) = ρ(x)ρ(y).

Definition 1. Given two random variables X and Y with probability distributions ρ(X) and ρ(Y ) and joint probability distribution ρ(X, Y ) we define the following non-negative real-valued functions:

Entropy H(X) = -x∈X ρ(x) log 2 ρ(x) ; Joint entropy H(X, Y ) = -x∈X y∈Y ρ(x, y) log 2 ρ(x, y) ; Conditional entropy H(X|Y ) = -x∈X y∈Y ρ(x, y) log 2 ρ(x|y) = y∈Y H(X|Y = y) ; Mutual information I(X; Y ) = x∈X y∈Y ρ(x, y) log 2 rho(x,y) ρ(x)ρ(y)
The generalization to more than two variables is straightforward. Note that H(X, Y ) = H(X) + H(Y ) iff X and Y are independent.

Shared-Key Cryptosystems

A shared-key cryptosystem can be defined as follows.

Definition 2. A (shared-key) cryptosystem is a 3-tuple (M, K, enc) where:

• the message space M is a finite set of possible messages;

• the key space K is a finite set of possible keys;

• the encoder enc is a function M × K → C to some space C such that ∀k ∈ K. enc(•, k) is injective.
This definition is slightly weaker than that of Biondi et al. [START_REF] Biondi | Attainable unconditional security for shared-key cryptosystems[END_REF] where the additional condition for the enc function that "∀m ∈ M. enc(m, •) is injective" was also required. The additional condition can simplify some results, although we show that removing the additional condition can strengthen others. We highlight these differences when the results are presented later in the paper.

A shared-key cryptosystem induces the set of its possible ciphertexts and a decoder function. The existence and uniqueness of such a decoder function is ensured by the requirement that enc(•, k) is injective.

The channel model of a cryptosystem was introduced by Shannon [START_REF] Shannon | Communication Theory of Secrecy Systems[END_REF] as depicted in Figure 1. In this model, agent A wants to send a message m ∈ M to agent B on a public channel that is eavesdropped by agent E. Initially, A and B share a secret key k ∈ K.

A encodes the message m with key k using an appropriate encoder function enc, obtaining the ciphertext c. A sends c to B via a public channel, where c is also read by the eavesdropper E. Knowing the key k, B decodes the message m using the inverse of the encoding function, dec. Not knowing the key k, E tries to infer m from their knowledge of enc and c and using unlimited computational power.

Consider the information available to agent E. Agent E knows the encoder function enc, and ciphertext c, but not the message m or key k. We will use random variables to model E's knowledge about the communication before and after E intercepts the ciphertext c. Let M (resp. K, C) be a random variable on the support set M (resp. K, C) representing the a priori value of the message m (resp. key k, ciphertext c) according to E, i.e. the value before the ciphertext is intercepted.

Random variables M and K are assumed to be independent, so

H(M, K) = H(M ) + H(K) .
We call H(M ) the prior entropy of M , modeling the amount of uncertainty that E has on the message before observing the ciphertext. Similarly, we call H(M |C) the posterior entropy of M given C, modeling the uncertainty left on the message after observing the ciphertext. The prior entropy gives a measure of how hard it is for E to guess the message before observing the ciphertext, while the posterior entropy measures the same after observing the ciphertext.

Shannon defined perfect secrecy as the highest possible security condition attainable on a cryptosystem [START_REF] Shannon | Communication Theory of Secrecy Systems[END_REF]. Perfect secrecy is attained when the mutual information between the message and the ciphertext is zero; when knowledge of the ciphertext gives no information about the message. That is, the prior and posterior entropies coincide, meaning that observing the ciphertext did not reduce the uncertainty of E on the message in any way.

Definition 5 (Perfect Secrecy). A cryptosystem attains perfect secrecy iff

H(M ) = H(M |C)
It can be shown that

H(M ) = H(M |C) ⇔ I(M ; C) = 0
thus perfect secrecy is attained when the mutual information between the message and the ciphertext is 0.

Shannon also proved that for a cryptosystem to be perfectly secure it is necessary that the key space is at least as large as the message space, i.e.

|K| ≥ |M|

making perfect secrecy hard to achieve in practice. Indeed, Shannon proved that perfect secrecy can be achieved when |K| = |M | as long as the keys are uniformly distributed [START_REF] Shannon | Communication Theory of Secrecy Systems[END_REF]. Observe that such requirements induce the relation that

H(K) ≥ H(M ) .
However, this requires A and B to have exchanged such a key k before sending the message m, and k can be used only once.

Latin Squares and Rectangles

A Latin rectangle is a a × b matrix with elements in {1, . . . , b} such that all the elements in each row and each column are distinct. It is a Latin square iff a = b.

An encoder function enc can be represented as a Latin rectangle if |C| = max (|M |, |K|) and ∀m ∈ M. enc(m, •) is injective. This takes the form of a |K|×|M | matrix with elements in {c 1 , . . . , c |C| } [START_REF] Shannon | Communication Theory of Secrecy Systems[END_REF][START_REF] Bruen | Cryptography, Information Theory, and Error-Correction: A Handbook for the 21st Century[END_REF]. However, we will show in Section 5 that the optimal encoder function is in general not a Latin rectangle.

Different Entropy Measures

Recently it has been shown that Shannon entropy measures the effort for decrypting the ciphertext by asking arbitrary binary questions, which is not a general security scenario [START_REF] Köpf | Automatically deriving information-theoretic bounds for adaptive side-channel attacks[END_REF]. Other measures based on different entropies have been introduced. Smith's min-entropy [START_REF] Smith | On the foundations of quantitative information flow[END_REF] has been shown to measure the resistance of the cryptosystem against one-time attacks in which the attacker has a single chance to guess the message correctly. Other entropy measures include g-leakage, that parametrizes min-entropy with a given gain function [1], and guessing entropy, that quantifies the effort required to decrypt the ciphertext with equality tests [START_REF] Köpf | Automatically deriving information-theoretic bounds for adaptive side-channel attacks[END_REF]. In particular, the gain functions used in g-leakage computation can be used to model complex information about the message spaces, such as some messages being more valuable than others.

The results presented in this paper can be re-derived using any other entropy measure, generating alternate definitions of max-equivocation that consider different types of attackers. Modification of the heuristics to use a different type of entropy is straightforward. In general, different encoder functions can be optimal for different entropy measures.

Further discussion about the effect of choosing different measures of entropy is not in the scope of this paper.

Max-Equivocation

We want to provide a measure of the security of a shared-key cryptosystem that is meaningful whether or not the the key used is smaller than the message to be sent.

Consider the entropy H(M ) of the message m. It measures the lack of information that E has about the message, so a higher H(M ) corresponds to a greater difficulty for E to guess the message. In our scenario, A and B share a secret key k, and the lack of information that E has about k is measured by H(K). The amount of entropy left in the message after the attacker has intercepted the ciphertext is measured by the message equivocation H(M |C), so we focus upon this.

Shannon proved that H(K) ≥ H(M ) is a necessary but not sufficient condition to find an encoder function enc such that I(M ; C) = 0. Since I(M ; C) = H(M ) -H(M |C), this corresponds to H(M |C) = H(M ), thus the message equivocation is equivalent to the entropy of the message. Since H(K) ≥ H(M ), it is also true that H(M |C) ≤ min(H(M ), H(K)).

Consider the complementary case in which H(K) < H(M ). Since E knows every other detail of the communication except for k, we will show that it is not possible to encrypt m as a ciphertext c ∈ C in a way such that the message equivocation H(M |C) is greater than the entropy

H(K), i.e. H(M |C) ≤ H(K). Since H(K) < H(M ), this again corresponds to H(M |C) ≤ min(H(M ), H(K)).
We conclude that irrespective of the relative sizes of the entropies of the message space and key space, the theoretical maximum equivocation is always achieved when it corresponds to their minimum. We say that a cryptosystem respects max-equivocation when it achieves this upper bound. Definition 6. A cryptosystem achieves max-equivocation iff

H(M |C) = min(H(M ), H(K)) .
Key equivocation can similarly be defined as H(K|C), measuring the average number of keys that could have produced a given ciphertext.

We will now introduce semi-injectivity, the core property of an encoder function. We will show that as a consequence of the encoder function being semiinjective on both message and key, message equivocation and key equivocation actually coincide, so we can just call them equivocation.

Semi-Injectivity

We introduce the concept of semi-injectivity of a function, that will be used throughout the paper.

Definition 7. A function f : A × B → C is semi-injective on B iff it holds that ∀a ∈ A, ∀b i , b j ∈ B. f (a, b i ) = f (a, b j ) ⇔ b i = b j .
Observe that a function on a tuple can be semi-injective on any element of the tuple, and that a semi-injective function on a single argument is injective. Semi-injectivity is equivalent to the property that the function can be Curried and after being applied to one argument the remaining function is injective, i.e. f : Note that Lemma 2 can also be proved by concavity of H.

A × B → C is semi-injective on B when f : A → B → C and f (a) : B → C is injective. Lemma 1. Let a function f : A × B → C be semi-injective on A. The image f [A, B] of f in C has at least the size of A: |f [A, B]| ≥ |A| . Consequently, if f is semi-injective in both A and B then |f [A, B]| ≥ max(|A|, |B|) . Lemma 2. Let f : A × B → C be semi-injective on A, A be a random variable on A, ρ A (A) a

probability distribution on A, and H(A) the entropy of ρ

A (A). Similarly, let C be a random variable on f [A, B], ρ C (C) a probability distribution on C, and H(C) the entropy of ρ C (C). Then H(A) ≤ H(C) . Proof. Recall that |f [A, B]| ≥ |A| by Lemma 1. If |f [A, B]| = |A|
Definition 8. A function enc : M × K → N is an encoder function iff it is semi-injective on M. Definition 9. An encoder function enc : M × K → N is a symmetric encoder function iff it is semi-injective on M and K.
Definition 9 of a symmetric encoder function is the same as an "encoder function" of [START_REF] Biondi | Attainable unconditional security for shared-key cryptosystems[END_REF]. Definition 8 here is to generalise results and will be highlighted later in the paper. The rest of this section shall consider only symmetric encoder functions (Definition 9) since these simplify the results. Later in Section 7 this is relaxed to consider encoder functions in general (Definition 8).

Since the encoder function is semi-injective on M, then the message is uniquely determined by a given ciphertext c and key k, thus H(M |K, C) = 0. Analogous reasoning on a symmetric encoder being semi-injective on K shows that H(K|M, C) = 0. We use these results to show that message equivocation and key equivocation coincide for symmetric encoder functions.

Theorem 1. H(M |C) = H(K|C) .

Proof. The proof adapts the similar proof of Theorem 1 of [12, sec. 7.3]:

H(M |C) = H(M, C) -H(C) = H(M, K, C) -H(K|M, C) -H(C) = H(M, K, C) -H(M |K, C) -H(C) (since H(M |K, C) = H(K|M, C) = 0) = H(K, C) -H(C) = H(K|C) .
Since message equivocation and key equivocation coincide for symmetric encoders by Theorem 1, we will just refer to them as equivocation, denoted by H(M |C).

Bounds on Equivocation

This section is dedicated to studying upper and lower bounds for equivocation, and to find necessary and sufficient conditions for a cryptosystem to achieve max-equivocation.

Consider after agent E intercepts the ciphertext c, their a posteriori information about the message is measured by the equivocation H(M |C).

Lemma 3. The entropy of the ciphertext has: lower bound of the greater of the entropy of the message or the key; and upper bound of the entropy of the message plus the entropy of the key. That is,

max(H(M ), H(K)) ≤ H(C) ≤ H(M ) + H(K) .
Proof. By Definition 9 and Lemma 1.

Lemma 4. The entropy of the ciphertext given the message is that of the key. That is, H(C|M ) = H(K).

Proof. By Definition 9 of enc being symmetric and thus semi-injective on K and Lemma 2.

Theorem 2. Equivocation ranges from 0 to the minimum of the entropy of the message and the entropy of the key, i.e.

≤ H(M |C) ≤ min(H(M ), H(K)) .

Proof.

H(M |C) = H(C|M ) + H(M ) -H(C) = H(K) + H(M ) -H(C) (by Lemma 4)
with the lower bound being and upper bound

H(M |C) ≥ H(K) + H(M ) -(H(M ) + H(K)) (by Lemma 3) = 0
H(M |C) ≤ H(K) + H(M ) -(max(H(M ), H(K))) (by Lemma 3) = min(H(K) + H(M ) -H(M ), H(K) + H(M ) -H(K))) = min(H(K), H(M )) .
Corollary 1. A necessary and sufficient condition for max-equivocation is that the entropy of the ciphertext is equal to the maximum between the entropy of the key and the entropy of the message:

H(C) = max(H(K), H(M )) H(M |C) = min(H(K), H(M )) .
Proof. Recall that

H(M |C) = H(C|M ) + H(M ) -H(C) = H(K) + H(M ) -H(C) .
(by Lemma 4)

Since H(M ) and H(K) are constant and H(C) is negative in the equation, then

H(M |C) is maximal iff H(C) is minimal.
Since by Lemma 3 we know that H(C) ≥ max(H(K), H(M )), this means that max-equivocation is achieved when the entropy of the ciphertext is minimal. The relation between equivocation and entropy of the ciphertext is depicted in Figure 2.

Note that the idea that the entropy of the ciphertext has to be minimized is not intuitive, and claims of the opposite can be found e.g. in [12, p. 117]. In the next Sections we will study how to construct a symmetric encoder function minimizing the entropy of the ciphertext, and we will show that the theoretical minimum of H(C) = max(H(K), H(M )) cannot always be achieved.

Key Re-Use and Key Equivocation

This section considers key re-use, and how the results on equivocation can account for such scenarios. This also leads into considering the impact on key equivocation, and scenarios where the key has more entropy than the message.

Key Re-Use

The results so far have focused on when a single message is sent with a single key, however, the results can be generalized to account for scenarios where multiple messages are sent with the same key. This section shows how this can be easily accounted for, although the rest of the paper shall focus on the single message scenario for clarity.

Consider the sequential transmission of a vector of n independent messages m ∈ M n chosen according to the same prior distribution ρ such that ρ(M ) has entropy H(M ). Also consider a vector of keys k ∈ K n , not necessarily independent. Each transmission uses the same encoder enc. Transmission i encodes message m i with key k i producing ciphertext c i . The prior entropy of the messages is H( M ) = nH(M ) since the elements of m are independent. The equivocation of the repeated transmission is

H( M | C) = H( C| M ) + H( M ) -H( C) = H( C| M ) + nH(M ) -H( C) = H( K) + nH(M ) -H( C) .
(by Lemma 4) Observe that the entropy of H( K) is maximized to nH(K) when the keys are independent, and is minimized at H(K) when the same key is used to encode all messages. Similarly, the entropy of H( C) is between max(H( K), H( M )) and H( K) + H( M ) by Lemma 3, so it still holds that H( M | C) ≤ H( K). Note that the result holds whether we use n different independent keys, in which case H( K) = nH(K), or we re-use the same key n times, in which case H( K) = H(K), or we use keys with any other dependencies between them. This shows that given a fixed amount of entropy to be used as the key in a shared-key cryptosystem, there is no difference in the equivocation when transmitting independent messages sequentially using parts of the total shared key, or repeatedly using the whole shared key for each message. In the latter case, it can be considered that the first transmission encodes a message m 1 with the key k producing ciphertext c 1 and has a maximum equivocation of H(M 1 |C 1 ) = H(K|C 1 ) ≤ H(K) by Theorem 1. Then the second transmission encodes m 2 with k producing c 2 and the equivocation of both transmission becomes

H(M 1 , M 2 |C 1 , C 2 ) = H(K|C 1 , C 2 ) ≤ H(K|C 1 ) ≤ H(K)
, and so on.

Indeed, one could simply combine all the messages to be transmitted m into a single message as above and send this using all the shared key. Of course in practice it is far easier to do the reverse, and send parts of the message as blocks in some shared-key cipher such as AES, in which case the results here show the bounds on equivocation.

Since the entropy of the key decreases each time it is used, it is reasonable to continue using the same key until its entropy falls below some predetermined lower bound that is considered sufficient for the security of the transmission. When the entropy of the key becomes too low for the key to guarantee an acceptable equivocation, a fresh key is generated by the key exchange protocol used.

It could be thought that using a very large key could be beneficial for the key reuse scenario, since the key could be used many times before its entropy becomes too small. However, this is not necessarily the case. In fact, in the next section we will show that if a key with more entropy than the message is used, the excess entropy of the key is immediately lost. Therefore, there is no reason to use a key with more entropy than the message, even if the key is to be used multiple times.

Bounds on Key Equivocation

Consider the total information about the message and the key. We show that the amount of information leaked about the message and the key corresponds at least to the absolute difference of their entropies for symmetric encoder functions.

We start by showing that the key equivocation H(K|C) varies between 0 and the minimum of H(K) and H(M ), just like the message equivocation does:

Theorem 3. 0 ≤ H(K|C) ≤ min(H(M ), H(K)) .
Proof. Since K and M are independent and enc is semi-injective in both, we can just rewrite the proof of Theorem 2 by substituting M with K and vice versa.

We can now prove the main theorem of this subsection.

Theorem 4. I(M, K; C) ≥ |H(K) -H(M )| . Proof. I(M, K; C) = H(M, K) -H(M, K|C) = H(M ) + H(K) -H(M |C) -H(K|C)
(by independence of M and K)

≥ H(M ) + H(K) -2 min(H(M ), H(K)) (by Theorems 2 and 3)

= |H(K) -H(M )|
Theorem 4 proves that the information leakage about the message and key is minimal when they have the same size. Furthermore, this proves that having a key with more entropy than the message is unnecessary. In particular, we show that if H(K) > H(M ) and perfect secrecy holds, then H(M ) bits of the key are used to protect the message with perfect secrecy, and at least the remaining H(K) -H(M ) bits of the key are leaked to the attacker. Lemma 5. Assume H(K) > H(M ) and I(M ; C) = 0. Then

I(K; C) ≥ H(K) -H(M ) .
Proof.

I(K; C) = H(K) -H(K|C) ≥ H(K) -min(H(M ), H(K))
(by Theorem 3)

= H(K) -H(M ) (since H(K) > H(M ))
This proves that using a key with more entropy than the message is unnecessary, since for perfect secrecy it is sufficient that the entropies of the key and the message coincide, and any additional entropy of the key is leaked.

Uniform Key, Non-Uniform Message

This section considers some conditions for when max-equivocation can be achieved, and examples of when max-equivocation is not achievable. In general max-equivocation is not achievable and Latin squares prove to not even be optimal with respect to max-equivocation.

Achieving Max-Equivocation

From Corollary 1 and Lemma 3 we have that the max-equivocation is ensured when the entropy of the ciphertext is minimized. Unfortunately maxequivocation (and thus perfect secrecy) cannot be achieved in all scenarios. Max-equivocation can be achieved for any distribution over the message space when the key space is of equal size and the key distribution is uniform. The solution for max-equivocation in this case is any encryption function that can be represented as a Latin square.

Observe from Corollary 1 that H(C) = max(H(K), H(M )) and that since |K| = |M| and K has uniform distribution that H(K) ≥ H(M ). From this we require that H(C) = H(K) for max-equivocation.

The easiest way to achieve H(C) = H(K) is for |C| = |K| and for the distribution of C to be uniform. This is achieved when the encryption function corresponds to a Latin square.

Theorem 5. Given |K| = |M| and uniform distribution over K, any encryption function enc that can be represented as a Latin square achieves maxequivocation.

Proof. As enc can be represented as a Latin square it follows that every c ∈ C must appear in each row and each column exactly once. Since the key distribution is uniform, the probability for each c is

Unachievable Max-Equivocation

In general max-equivocation cannot be achieved. Indeed, there are small examples where H(C) cannot be made to match max(H(K), H(M )). For example, consider when there are three messages with probabilities ρ(m 1 ) = 0.2 and ρ(m 2 ) = 0.3 and ρ(m 3 ) = 0.5 and the key space is of size 2 with uniform distribution. It turns out that there is no encoder function such that H(C) = H(M ) 1.4854. The best possible is a Latin rectangle where the symbols must have the probabilities ρ(c 1 ) = 0.25 and ρ(c 2 ) = 0.35 and ρ(c 3 ) = 0.4 which yields H(C) 1.5588 (checked via brute forcing all possibilities). When the distribution on the larger side of the rectangle is uniform then any Latin rectangle achieves max-equivocation, as shown in Section 5.1.

Non-Optimality of Latin Rectangles

When the distribution on the larger side of the rectangle is not uniform, it is possible that the optimal encoder function is not a Latin rectangle. For instance, let M = {m 1 , m 2 , m 3 } with distribution ρ(M ) = {m 1 → 0.02, m 2 → 0.49, m 3 → 0.49} and let the key be uniform on K = {k 1 , k 2 }. The best Latin rectangle encoding shown in Table 1a has C = {c 1 , c 2 , c 3 } and H(C) 1.5097, while the optimal encoding shown in Table 1b has C = {c 1 , c 2 , c 3 , c 4 } and H(C) 1.1414. Note that neither reaches the theoretical lower bound of H(C) = H(M ) 1.1214.

Due to the inherent complexity of finding an encoder function that minimizes the entropy of the ciphertext, computing an optimal encoder function for a given key and message distribution is not trivial. We introduce different heuristics and compare them experimentally in Section 8.

Conditions for Achievability

Assume log(|K|) = H(K) < H(M ). Then the maximum achievable message equivocation depends on the probability distribution ρ(M ) on the message.

We introduce the set E c ⊆ M of the messages that can be decoded from a given ciphertext c using any key k ∈ K. Definition 10. Let enc be an encoder function and c ∈ C one of its ciphertextsymbols. Then the set E c is

Message

m 1 m 2 m 3 Key k 1 c 1 c 2 c 3 k 2 c 2 c 3 c 1 (a) Best Latin rectangle Message m 1 m 2 m 3 Key k 1 c 1 c 2 c 3 k 2 c 4 c 3 c 2 (b) Optimal encoder
E c = {m ∈ M | ∃k ∈ K. enc(m, k) = c} .
Note that |E c | ≤ |K|, with equality when the encoder is symmetric. Let E c be a random variable over E c with probability distribution

∀m ∈ E c . ρ Ec (m) = ρ M (m) m∈Ec ρ M (m)
.

The probability distribution ρ Ec represents the distribution over the messages according to the attacker after they have intercepted the ciphertext c, and its entropy is

H(E c ) = H(ρ Ec (E)).
Then we can compute the message equivocation of the encoder function enc as the expectation of the entropy of H(E c ) over all possible ciphertexts. Lemma 6.

H(M |C) = c∈C ρ C (c)H(E c ) . Proof. It is sufficient to prove that H(E c ) = H(M |C = c) for all c ∈ C. Note that for each c ∈ C it holds that ρ M (m / ∈ E c |C = c) = 0. Also, for each m ∈ M it holds that ρ M (m|C = c) = ρ M (m) m∈Ec ρ M (m) = ρ Ec (m)
and the result follows.

This shows that maximizing message equivocation means maximizing the entropy

E c of each set E c . Since |E c | ≤ |K| and H(K) = log(K) then H(E c ) ≤ H(K), thus to achieve H(M |C) = H(K)
we need every E c to have size equal to |K| and the distribution ρ Ec over it to be uniform. This justifies the following theorem. Theorem 6. An encoder function achieving H(M |C) = H(K) exists iff the message space M can be partitioned into subsets M 1 , . . . M n such that for each 1 ≤ i ≤ n it holds that:

1. |M i | ≥ |K|; and 2. messages in M i are equiprobable.

Proof. Forward direction

Assume by contradiction that an encoder function achieving H(M |C) = H(K) exists for a message space that cannot be partitioned into subsets respecting conditions 1) and 2).

Consider when there exists some partition M i that has size smaller than |K| and all partitions M j are such that m ∈ M j are equiprobable. Now consider one ciphertext symbol c such that ∃m ∈ M i where enc(m, k) = c. Now if E c has size smaller than |K| then it follows that H(M |C) < H(K). Therefore there must exist some m = dec(c, k) such that m ∈ M i . If ρ(m) = ρ(m ) then again it follows that H(M |C) < H(K). Lastly if ρ(m) = ρ(m ) then it follows that m can instead be partitioned into M i . To conclude; if |M i ∪ {m }| = |K| this violates the premise, otherwise there must be some other m's that eventually leads to |M i ∪ {m } ∪ {m } ∪ . . . | ≥ |K| and thus contradiction.

Consider when there exists some partition M i that contains m 1 and m 2 such that ρ(m 1 ) = ρ(m 2 ). Now if there exists some c and k 1 and k 2 such that enc(m 1 , k 1 ) = c = enc(m 2 , k 2 ) then it follows that H(M |C) < H(K). Therefore for H(M |C) = H(K) to hold there must be |K| -1 other m i 's with ρ(m i ) = ρ(m 1 ) and also m j 's with ρ(m j ) = ρ(m 2 ). It follows that M can be partitioned to have these sets of m's in different partitions achieving the conditions.

Reverse direction

We produce an encoder function achieving H(M |C) = H(K). Consider a single partition M i . Since the distribution over the messages in M i is uniform then any Latin rectangle encoder for M i achieves H(M i |C) = H(K) by Theorem 5. By producing a Latin encoder for each partition and concatenating them we obtain an encoder achieving H(M |C) = H(K).

Unicity

This section addresses the unicity problem for max-equivocation by considering the message space to contain both valid and invalid messages.

Motivation

In this section we will consider the messages as represented by sequences of symbols in some language, e.g. letters in the English language. In general not all sequences of symbols in the language represent a (valid) message that the sender may wish to transmit. For instance, the letter sequence "snfeigkpangrj" has no meaning in English, i.e. is not "valid" English.

Recall that having access to unlimited computational power, the eavesdropper E can list all possible messages that could have been encoded as a given ciphertext. However, many of these possible messages may be sequences of letters that have no meaning in English, and thus are not valid messages. Thus, a viable form of attack for E is to decrypt a ciphertext with all possible keys and keep the only possible valid messages. This can vastly reduce the equivocation of the message. The longer a sequence of letters is, the less likely it is to be a valid message in the given language. In particular, according to the language, there is a certain message length such that we expect only one of the messages decodable from the ciphertext to be valid. This is a common problem in languages that are highly structured where many sequences of symbols do not represent valid messages, e.g. English; this is referred to as redundancy of the language. This is the key to the unicity problem and unicity based attackers, for a thorough and formal treatment of this we refer to [START_REF] Shannon | Communication Theory of Secrecy Systems[END_REF][START_REF] Welsh | Codes and Cryptography[END_REF].

In this section we consider what happens of the message space, e.g. sequences of letters, is divided into valid and invalid messages, e.g. sequences that do and do not correspond to meaningful messages in the English language. We show that the results of this paper still apply by considering invalid messages as having probability 0 in the message distribution.

Valid and Invalid Messages

Consider a set M v of messages among which the sender chooses the one they want to transmit to the receiver: we will call these the valid messages.

Fix an alphabet Σ that will be used for the representation of the messages, also fix a length l such that |Σ l | ≥ |M v |. Now pick an injection from M v into Σ l and thus yield the sequences of Σ l that represent the valid messages. It follows that there are |Σ l | -|M v | sequences in Σ l that do not correspond to any valid message in M v ; we will call the set of these sequences the invalid messages M i . Since the message encoding can exploit compression or other techniques, we can assume that 0 ≤ |M i | < |M v | without loss of generality.

In Section 5 no assumption was made upon the alphabet of the messages, thus allowing log |Σ| |M v | ∈ N and consequently M i = ∅. In this section we consider vulnerabilities that can arise when the set of invalid messages is not empty.

Let M = M v ∪ M i be the set of all messages. The probability distribution ρ Mv (M v ) on random variable M v on set M v can be extended to a probability distribution ρ M (M ) on random variable M on set M as

ρ M (m) = ρ Mv (m) if m ∈ M v 0 otherwise
meaning that invalid messages are part of the message space but they have probability 0 of being chosen by the sender as the message to be sent. Note that

H(M ) = H(M v ).
Here we assume a symmetric encoder function enc : M × K → N with image C. By its semi-injectivity on M it holds that each ciphertext c ∈ C is the image of at most |K| messages in M. However, for some encoder functions (symmetric or otherwise) messages in the preimage of C are invalid messages, thus reducing the amount of different valid messages that can be decoded from some of the ciphertexts, and consequently reducing the message equivocation. This is illustrated by the following simple example. Let M v = {00, 01, 10}, M i = {11}, K = {00, 11}, and enc(m, k) m ⊕ k, where ⊕ represents the exclusive disjunction operator. Then enc is as depicted in Table 2a. Assuming uniform distribution on the key and valid message spaces, maxequivocation is achieved when H(M |C) = H(K) = 1 bit. We can compute the equivocation as H(M |C) = c∈C P (c)H(M |C = c). probability and posterior entropy of each ciphertext is depicted in Table 2b. The resulting message equivocation is 2 3 bits, which is inferior to the optimal value of 1. The reason for the sub-optimality of the encoding is that some of the ciphertexts, namely 00 and 11, can map back to invalid messages. If the attacker intercepts the ciphertext 00 they know that the message must be either 00 or 11, and since 11 is invalid this allows them to conclude that the message is necessarily 00. On the other hand, if they intercept the ciphertext 01 they have no way to decide whether the message was 01 or 10.

Message

This example shows that when the preimage of the ciphertext space includes invalid messages the security of the transmission is reduced, and this is captured by the fact that message equivocation decreases accordingly. Now consider the encoder function enc(m, k) mod((m + k), 3) when m is valid and enc(m, k) = 11 otherwise, where mod is the standard modulus function, on the same message spaces and K = {0, 1}, depicted in Table 3.

Message

Valid Invalid 00 01 10 11 Key 0 00 01 10 11 1 01 10 00 11 In this case each the only ciphertexts that can be produced are 00, 01 and 10; let's call them valid ciphertexts. Each valid ciphertext maps back to ex-actly 2 possible valid messages, so the message equivocation is 1 bit and maxequivocation is achieved. In fact, the symbols in the column of the invalid messages do not matter as long as the valid ciphertexts map to the right valid messages. Even substituting a constant for all the ciphertexts of the invalid messages would not change the equivocation of the system, even though it would violate the semi-injectivity on the key condition a symmetric encoder function.

In fact, in the next section we will consider encoder functions that are not symmetric, i.e. are not semi-injective on their keys, to show they can sometimes yield improved results over symmetric encoders and generally stronger encryption.

Relaxing Encoder Injectivity

The semi-injectivity conditions on the symmetric encoder functions imply that there exist at most one message that can produce each key-ciphertext pair and at most one key that can produce each message-ciphertext pair.

Relaxing the semi-injectivity on the message would mean that the receiver of the ciphertext, knowing the key, would not be able to uniquely determine which message the sender meant to send him. This would not be desirable.

However, if the messages are divided into valid and invalid messages as described in Section 6, it is sufficient for the key-ciphertext pair to map back to a single valid and any number of invalid messages for the receiver to be able to single out the valid message that the attacker sent. For this reason, we can relax the "semi-injectivity on M" condition on encoder functions to "semi-injectivity on M v ".

Similarly, we here exploit the weakening of the definition of a shared-key cryptosystem to exploit the lack of semi-injectivity on the key. This allows that there are ciphertexts that can be decoded as the same message by different keys. Since the receiver has the correct key this would not be a problem, and we can show that in general relaxing this condition can produce stronger encryption. Thus, in this section we will consider encoder functions from Definition 8 instead of symmetric encoder functions from Definition 9.

Example

To illustrate this, we recall the example in Table 1

. Let M = {m 1 , m 2 , m 3 } with distribution ρ(M ) = {m 1 → 0.02, m 2 → 0.49, m 3 → 0.49} and let the key be uniform on K = {k 1 , k 2 }.
The theoretical maximum to the message equivocation is achieved when the entropy of the ciphertext is minimal at H(C) = H(M ) ≈ 1.1214. The best Latin rectangle and best symmetric encoder function depicted in Table 4a and 4b respectively do not achieve this, having a ciphertext entropy of ≈ 1.5097 bits and ≈ 1.1414 respectively.

However, if we do not enforce semi-injectivity on the key, we can have the encoder function in Table 4c. Although this encoder function achieves the same Message

m 1 m 2 m 3 Key k 1 c 1 c 2 c 3 k 2 c 2 c 3 c 1 (a) Best Latin rectangle Message m 1 m 2 m 3 Key k 1 c 1 c 2 c 3 k 2 c 4 c 3 c 2 (b) Optimal symmetric encoder (with semi-injectivity on key) Message m 1 m 2 m 3 Key k 1 c 1 c 2 c 3 k 2 c 1 c 3 c 2
(c) Optimal asymmetric encoder (without semi-injectivity on key) message equivocation as the encoder in Table 4b, they differ in their key equivocation. This can have significant impact in scenarios where the key is re-used. Consider when the same key k ∈ {k 1 , k 2 } is used to transmit two messages α, β ∈ {m 1 , m 2 , m 3 }. If the encoder in Table 4b is used twice then the equivocation is H(M α , M β |C α , C β ) = 0.9604. However, if instead the encoder in Table 4c is used twice the equivocation is H(M α , M β |C α , C β ) = 0.9996. More generally, when using a single key, the encoder in Table 4b has equivocation H( M | C) = 0.98 n for transmitting n messages, this is due to any collection of messages containing m 1 completely leaking the key. By contrast, the encoder in Table 4c has equivocation H( M | C) = 1 -0.02 n for n messages, due to m 1 not leaking any information about the key.

Asymmetric encoders both generalise, and can achieve better equivocation than, symmetric encoders. Although this is demonstrated above on a key reuse scenario, asymmetric encoders perform better than symmetric encoders in non-trivial single transmission scenarios as well.

Differences in the Theory

Some of the results of Section 3 depend on the encoder function being symmetric and thus semi-injective on the key. We investigate the impact of using general encoder functions on the lemmata and theorems of Section 3.

Not having semi-injectivity on K means that the equation H(K|M, C) = 0 does not hold anymore. Consequently, Theorem 1 that was based on this result does not hold anymore, meaning that the equivocation of the message H(M |C) and the equivocation of the key H(K|C) can be different. Lemma 2 still holds, but the lower bound on Lemma 3 was based on using Lemma 1 on both M and K, so the lower bound of Lemma 3 becomes H(M ) ≤ H(C).

Lemma 4 does not hold, meaning that H(C|M ) is not necessarily H(K) but will depend on the particular encoder function producing C.

As a consequence, the upper and lower bounds for message equivocation in Theorem 2 change to

H(C|M ) -H(K) ≤ H(M |C) ≤ H(C|M ) .
Minimizing the entropy of the ciphertext is not sufficient to maximize message equivocation anymore, invalidating Corollary 1. Instead, message equivocation is maximized when the difference H(C|M )-H(C) approaches 0, posing a more complex optimization problem since both elements depend on the encoder function. In fact such difference is the negative of mutual information, since

H(C|M ) -H(C) = -(H(C) -H(M |C)) = -I(M ; C) .
This confirms that to maximize message equivocation we must minimize the mutual information between message and ciphertext, as we already noted in Section 3.

As for the results in Section 4.2, the upper bound of Theorem 3 becomes H(K|C) ≤ H(K), making the theorem uninteresting since 0 ≤ H(X|Y ) ≤ H(X) holds for any two random variables X, Y . Finally, Theorem 4 becomes

H(M ) -H(C|M ) ≤ I(M, K; C) ≤ H(M ) -H(C|M ) + 2H(K) .

Max-equivocation in Practice

In this section we discuss how an unconditionally secure communication system using the results of this paper can be constructed in practice, including the evaluation of heuristics for the generation of suitable encoder functions.

Scenario

As usual, A wants to send messages to B on an insecure channel in a way that E cannot understand even by collecting the ciphertexts. Recall that E can intercept the communications on the channel but not modify them.

First of all, A and B need to agree on an encoder function enc. The encoder function can be public, so A generates enc and sends it to B on the insecure channel, where E intercepts it. Now all three agents know the encoder function enc, and consequently the message space M and key space K. B and E reverse the encoder function obtaining the corresponding decoder dec. Note that the generation, transmission and reversal of the encoder function has to be performed only once.

Before starting the transmission of ciphertexts, A and B use a key distribution protocol to agree on a given key k 1 ∈ K. They know that the entropy of E over the key is H(K). Now, A can start sending messages to B. Whenever A wants to send a message m α to B, A encodes the message m α with the key k 1 and sends the corresponding ciphertext c α to B on the insecure channel, where c α is also intercepted by E.

Each subsequent transmission of messages with the same key k 1 reduces the entropy of k 1 and the equivocation of all messages transmitted with k 1 . For instance, if A sends to B three messages m α , m β and m γ encoded as ciphertexts c α , c β and c γ , the remaining entropy of k 1 is H(K|C α , C β , C γ ) and the equivocation of each of the three messages is H(M |C α , C β , C γ ). When this value becomes too low, A and B run the key distribution protocol again to agree on a new shared key k 2 , resetting the key entropy to H(K), and continue the transmission.

Since the generation of the encoder happens only once and potentially well before the transmission starts, A could spend significant time in the creation of an optimal encoder. However, finding the optimal encoder may be very expensive. Also, the quality of the encoder depends on the probability distribution of the messages that A will send, and A may have only an idea of such distribution, making perfect optimization pointless.

Therefore, instead of focusing on the optimal encoder for a given message distribution, we will consider more practical heuristic algorithms to produce a "good enough" encoder in a reasonable time, and we will experiment with the heuristics to find out which one can produce the best encoder in the least time.

Symmetric Encoder Generation Heuristics

We consider the generation of symmetric encoder functions via efficient heuristics. Our heuristics generate symmetric encoders by greedy sequential approximation. The quality of symmetric encoders is easier to compare than the quality of asymmetric encoders, since in the former case it is sufficient to choose the symmetric encoder that produces the ciphertext with the lowest entropy. While as explained in Section 7 symmetric encoders are non-optimal in general, according to our experiments the difference between equivocation achieved by symmetric encoders and the equivocation achieved by asymmetric encoders does not seem to be very large in practice.

We propose 4 different heuristic algorithms that produce a symmetric encoder function for a given message space M = {m 1 , m 2 , . . . , m |M| } with a given probability distribution ρ(M ) and a given key space K = {k 1 , k 2 , . . . , k |K| } with uniform distribution. We will assume that |K| < |M| and ρ(m

1 ) ≤ ρ(m 2 ) ≤ • • • ≤ ρ(m |M| ).
The algorithms we propose are similar as they all consider the symmetric encoder function as a |K| × |M| matrix C where the rows correspond to values of the key and the columns to the values of the message, as shown in the tables in this paper. The cell C i,j contains the ciphertext symbol produced when the key is k i and message is m j . For brevity we denote by H(C) the entropy of the ciphertext induced by the symmetric encoder function represented by C.

The algorithms initialize C by assigning to each value in the column m j the symbol c j , for 1 ≤ j ≤ |M|. The resulting ciphertext would have exactly H(C) = H(M ) and thus achieve max-equivocation, however it is not a valid symmetric encoder function since the same symbol is repeated more than once in each column. The algorithms then transform it into a valid symmetric encoder function while greedily trying to increase the entropy of the ciphertext by the smallest possible amount.

For C to be a symmetric encoder function, it must be that in each row and column of C each symbol appears at most once. We call a symbol c = C i,j a conflict if it violates this property, i.e. if c appears more than once in row i or column j.

The algorithms proceed by reducing the number of conflicts in C, and returning C when there are no conflicts left and consequently C represents a symmetric encoder function. A conflict can be replaced in two different ways: by swapping it with a symbol in a different position in C or by transforming it to another symbol.

Swapping c = C i,j and c = C i ,j means that we simultaneously set C i,j ← c and C i ,j ← c. A swap is considered valid only if c is not a conflict in position (i , j ) and c is not a conflict in position (i, j). The algorithms perform only valid swaps, so each swap strictly reduces the number of conflicts in C. The RandRow algorithm is equivalent to IncRow except that the columns are scanned in a random order. The pseudocode of RandRow is the same as the one described in Algorithm 1 except that the order of the columns of C is randomized after line 1.

7 if H(C[c ← c ν ]) < H(C[c ↔ c ]) then 8 Let candidateC ← C[c ← c ν ];
The Extensive algorithm considers all conflicts in C and for each one the best swap and the best transformation, and then it performs the swap or transformation operation that is the best among all possible conflict resolutions (ties in favor of swaps). It repeats this step until there are no conflicts left. The pseudocode of Extensive is described in Algorithm 2.

Lemma 7. Algorithms IncRow, DecRow, RandRow and Extensive terminate.

Proof. Since each iteration of the main cycle of each algorithm reduces the number of conflicts.

We now perform experiments on the proposed heuristics to determine which one is the most effective in producing a symmetric encoder function approaching max-equivocation.

Experimental Methodology

The experimental results are from two different phases to explore the behaviour and performance of different algorithms. The first phase considers a variety of small message spaces with two different message distribution generation algorithms (Split and Skew). The goal of this phase is to identify which algorithms perform comparatively well. The second phase iterates over increasing size of the message spaces with a single message distribution generation algorithm to test the performance of refined encoder generators. In both phases the key space size is randomly chosen to be between 2 and the maximum |K| such that H(K) < H(M ).

The Split algorithm splits the probability available x (initially 1) randomly into two parts x 1 and x 2 , and then recursively calls itself with these parts of the two halves of the message (sub-)space. This continues until the subspace is a single message that is assigned the whole probability.

The Skew algorithm splits the probability available into two parts, assigns the first part to the current message (initially the first), and then continues with the remaining probability and remaining messages. This tends to generate more skewed probability distributions than Split.

In both phases, once the size of the message space, message distribution, and size of the key space have been chosen, each algorithm is run in turn on the same initial state, with the data recorded after each symmetric encoder function has been created.

The code to perform these tests is written in Java 1.8 and run on Linux 3.13 64-bit kernel on an Intel Core i7-3720QM 2.60GHz CPU with 8GB of RAM. The code used to run these experiments is available upon request.

Comparing Algorithms

This phase generates tests with random small-sized message spaces, message distributions, and key sizes; determining the domain for an encryption function. The different algorithms for generating encryption functions are then all run on the same random examples and their outputs compared, in particular:

Win% The percentage of times each algorithm generates the lowest entropy (may sum to over 100% since more than one algorithm can generate the same lowest entropy).

∆ The average percentage of the message entropy that is lost; that is the average

(H(C)-H(M ))×100 H(M )
.

Runtime The average runtime for the algorithm in milliseconds.

The results for comparing IncRow, DecRow, RandRow, and Extensive over 450,000 tests (equally split across the two probability generation algorithms) are shown in Table 5. The results indicate that the DecRow algorithm performs the best in all categories, followed by RandRow, then IncRow and finally Extensive. In particular the results show that Extensive performs by far the worst, with much higher runtimes yielding the lowest win percentage and In the second phase, we consider refinements to the DecRow algorithm that improve the runtime with only small losses in ∆. There are three different approaches used: splitting the symmetric encoder function into subsections by Splitting into subsections by size is a simple approach that can yield reasonably large improvements. The most trivial algorithm is DualDec that splits the symmetric encoder function space in half and runs DecRow on each half. Another straightforward approach is to split into equal subsections of a given size. This was tested with subsections equal to the key space KSplit and subsections twice the size of the key space 2KSplit.

A further refinement of the splitting into subsections approach was to allow overlap between the subsections. This was implemented as the family of SplitXX algorithms that used different amounts of overlap between the subsections. The results here are detailed for the Split25 algorithm that extended 25% of the key space outside each subsection (or 3 messages for key sizes less than 12).

Rather than splitting the symmetric encoder function into sections with possible overlap, the aperture approach simply limits how far above and below the current message to consider swapping. Since the messages are ordered on probability, it was hypothesised that a swap would not be more than 3 times the key space below the current message, and only a few messages above (3). This is represented in the results by the Aperture3 algorithm.

Inspired by the necessary and sufficient conditions for max-equivocation in Theorem 6 an alternative approach was to try and find a drop point in the message distribution where the difference in probability between two messages is greater than a running average probability. This attempts to split the sym- metric encoder function into sections of least key space size with more uniform probabilities within each section. The drop point was taken to be a 25% different to the current average in the Drop25 algorithm.

2 5
The following results consider the DecRow, 2KSplit, Split25, Aper-ture3, and Drop25 algorithms run while comparing message sizes. (Other algorithms and variations were tested, but performed worse than those chosen and so have been omitted from detailed exploration here.) Tables 6 &7 shows the results for 100,000 tests with fixed message size (and random key space size such that 1 ≤ H(K) < H(M )). Message probability distributions are generated by the Split probability generation algorithm since Skew tends to be too skewed for larger message sizes. The deltas relative to DecRow are shown in Figure 4, while the runtimes relative to DecRow are shown in Figure 5.

The data shows that the Aperture3 algorithm consistently produces the symmetric encoder with the delta closer to DecRow.

The data shows that the Aperture3 algorithm consistently produces symmetric encoders with delta around 1% worse than DecRow, while doing so in less than 60% of the runtime. The Split25 algorithm performs worse for small message sizes but appears to improve as the message size increases, while having the best runtimes. 2KSplit appears to be increasingly worse with respect to delta although the runtime improvements increase with message size. Lastly, Drop25 was not graphed in Figure 4 due to performing significantly worse, and the runtime does not appear to be an improvement over other refinements.

Conclusions

We have presented max-equivocation, a generalization of Shannon's perfect secrecy condition that can also be established when the entropy of the key is smaller of the entropy of the message. Message equivocation measures the number of different messages that can be decrypted from the ciphertext, and max-equivocation holds when this number is maximized. Achievable maxequivocation is obtained when mutual information is minimized, and for symmetric encoder functions this corresponds to minimizing the entropy of the ciphertext.

We have shown that max-equivocation can be easily applied to scenarios with key re-use. Also that having keys with more entropy than the messages immediately loses the excess entropy, performing very poorly from a key re-use perspective.

We have explored the problem of finding an encoder function when the distribution over the message space is non-uniform and the distribution over the key space is uniform.

We have shown that having a ciphertext space larger than the message space can increase the effectiveness of encoder functions, proving the general nonoptimality of encoder functions that correspond to Latin rectangles. We have shown that in general it is impossible to give a symmetric encoder function that achieves max-equivocation: max-equivocation is achievable if and only if the message space can be divided in subspaces of size at least |K| each of which has uniform distribution.

We have addressed the unicity problem by considering messages that could be decoded from ciphertexts but have probability 0 of being chosen by the sender. We show that this can be resolved by either relaxing semi-injectivity on the key, or by distinguishing valid and invalid messages.

We considered the consequences of relaxing the semi-injectivity on the key encoder condition. The consequent lack of symmetry in the behavior of the encoder towards messages and keys complicates some of the results in Section 3. This allows us to produce more effective encoders, at significant complexity cost.

We have compared four heuristics to efficiently derive an effective encoder function. We established that the DecRow algorithm works better than the others under our experimental parameters, consistently providing encoder functions that are only a few percentage points worst than the theoretical optimum and in less time than the other heuristics.

We show that refinements to DecRow can yield algorithms that perform almost as well with respect to entropy, while doing so in almost half the runtime.

Finally, we show that using different entropy measures can impact the optimality of the encoders. This reflects the differences on what entropy measures quantify.

[1] Alvim, M. S., Chatzikokolakis, K., Palamidessi, C., Smith, G.,

Figure 1 :

 1 Figure 1: Shared-key cryptosystem model.

Definition 3 .Definition 4 .

 34 Let C = {c | ∃m ∈ M. ∃k ∈ K. c = enc(m, k)} be the ciphertext space, i.e. the set of possible ciphertexts c given M, K and enc. Let the decoder dec be the function C × K → M such that dec(enc(m, k), k) = m.

  then there must be one c ∈ f [A, B] that corresponds to each a ∈ A and thus H(A) ≤ H(C). If |f [A, B]| > |A| then there must be at least two c i and c j such that f (a, b x ) = c i and f (a, b y ) = c j . This increases the entropy, due to either H(B) (when b x = b y ), or via f itself otherwise. In either case, H(A) ≤ H(C).

Figure 2 :

 2 Figure 2: Graph showing equivocation H(M |C) as a function of the entropy of the ciphertext H(C). The gray area is unachievable, since H(C) ≥ max(H(M ), H(K)) by Lemma 3, thus the maximum possible equivocation is H(M |C) = min(H(M ), H(K)).

  m∈M ρ(m) = 1 it follows that ρ(c) = 1 |K| . Since in a Latin square |M| = |C| = |K| conclude via the uniform distribution over C that H(C) = H(K) and Corollary 1.

When

  |M| = |K|, each Latin rectangle of size |K|×|M| represents an encoder function with |C| = max(|M|, |K|). We can compute that the minimum and maximum entropy of the ciphertext space generated by such an encoder function are bounded by: max(H(M ), H(K)) ≤ H(C) ≤ log(max(|M|, |K|)) .

  Encoder function for a 2-bit message and a 1-bit key. P (c) H(M |C = c) Probability and posterior entropy for each ciphertext.

Figure 3 :

 3 Figure 3: Conflict resolution example for an encoder with message space M = {m 1 , m 2 , m 3 } with distribution ρ(M ) = {m 1 → 0.1, m 2 → 0.45, m 3 → 0.45} and key uniformly distributed on K = {k 1 , k 2 }. Ciphertext c 1 in the first column is in conflict (a). The possible options to resolve the conflict are considered: swapping c 1 with c 2 (b1), swapping c 1 with c 2 (b2), or transforming c 1 into a new ciphertext symbol c 4 (b3). The ciphertext entropy of each option is computed. The transformation is found to have the lowest ciphertext entropy (c), so it is chosen and applied.

4 foreach conflict c do 5 Find 6 Find

 456 We will denote the result of the swap with C[c ↔ c ]. A best swap operation C[c ↔ c ] for a Data: message space M = {m 1 , m 2 , . . . , m |M| }, probability distribution ρ(M ), key space K = {k 1 , k 2 , . . . , k |K| }. Result: matrix form C of a symmetric encoder enc. 1 Set C i,j = c j , ∀1 ≤ i ≤ |K|, 1 ≤ j ≤ |M|; 2 while C is not a symmetric encoder function do 3 Let minC ← C, minH ← ∞; the best swap C[c ↔ c ] with any element c ∈ C; the best transformation C[c ← c ν ];

9 else 10 Let

 910 candidateC ← C[c ↔ c ]; 11 end 12 if H(candidateC) < minH then 13 minC ← candidateC; 14 minH ← H(candidateC);

Figure 4 :

 4 Figure 4: Comparison of ∆'s for DecRow, 2KSplit, Split25, and Aperture3 versus message size

Figure 5 :

 5 Figure 5: Comparison of runtimes for DecRow, 2KSplit, Split25, Aperture3, and Drop25 versus message size

Table 1 :

 1 Encoder functions for message distribution ρ(M ) = {m 1 → 0.02, m 2 → 0.49, m 3 → 0.49} and uniform key distribution.

Table 2 :

 2 XOR encoding example.

Table 3 :

 3 Sum-modulo encoding for a 2-bit message and a 1-bit key

Table 4 :

 4 Encoder functions for message distribution ρ(M ) = {m 1 → 0.02, m 2 → 0.49, m 3 → 0.49} and uniform key distribution.

Table 5 :

 5 Comparison of IncRow, DecRow, RandRow, and Extensive only negligibly improved loss of message entropy over the next worse IncRow. Although IncRow is not significantly slower, the low win percentage and highest entropy loss suggest that despite greediness not being optimal, beginning with the smallest probabilities is worse than a random selection. Although De-cRow is not optimal, it does prove to be the most effective of the algorithms here and provides a good basis for further experiments.

		Algorithm Win%	∆ Runtime
		IncRow	9.3462 11.04	0.3978
		DecRow 80.5007	9.00	0.2909
		RandRow 21.5667 10.31	0.3608
		Extensive	8.4744 11.00	172.4039
	8.5. Refinement
	Message					∆
	size	DecRow 2KSplit Split25 Aperture3 Drop25
	2 5	.2423769	.2455512	.2460305	.2449590	.2923967
	2 6	.2827137	.2881369	.2902109	.2857851	.3233435
	2 7	.3221931	.3305574	.3321461	.3258651	.3550239
	2 8	.3588024	.3692356	.3695319	.3630879	.3856449
	2 9	.3971868	.4095588	.4081074	.4019161	.4198576

Table 6 :

 6 Comparison of ∆ of DecRow, 2KSplit, Split25, Aperture3, and Drop25 over different message sizes. Message size is in bits, smaller ∆ is better.

	Message			Runtime
	size	DecRow 2KSplit Split25 Aperture3 Drop25
	2 5	.46611	.32542	.23656	.26828	.26374
	2 6	3.6288	2.4475	1.8236	2.0277	2.1740
	2 7	30.589	19.768	16.501	17.228	19.903
	2 8	287.16	182.27	163.63	164.65	197.87
	2 9	3427.6	2086.6	1983.4	1981.3	2336.8

Table 7 :

 7 Comparison of runtime of DecRow, 2KSplit, Split25, Aperture3, and Drop25 over different message sizes. Message size is in bits, runtime in milliseconds, smaller runtime is better.

  2012. Measuring information leakage using generalized gain functions. In: Chong, S. (Ed.), 25th IEEE Computer Security Foundations Symposium, CSF 2012, Cambridge, MA, USA, June 25-27, 2012. IEEE, pp. 265-279.

Data: message space M = {m 1 , m 2 , . . . , m |M| }, probability distribution ρ(M ), key space K = {k 1 , k 2 , . . . , k |K| }. Result: matrix form C of a symmetric encoder enc.

Transforming c = C i,j means finding a symbol c ν that does not appear in row i nor in column j and setting C i,j ← c ν . A transformation reduces the number of conflicts by one. We will denote the result of the transformation with C[c ← c ν ]. Note that no symmetric encoder function has more than

In Figure 3 we show an example of conflict resolution for an encoder with message space M = {m 1 , m 2 , m 3 } with distribution ρ(M ) = {m 1 → 0.1, m 2 → 0.45, m 3 → 0.45} and key uniformly distributed on K = {k 1 , k 2 }.

All algorithms always terminate. We introduce them and explain how they differ.

The IncRow algorithm scans C's columns in increasing order of probability, and each column from top to bottom. When it finds a conflict c, it considers the best swap C[c ↔ c ] of c with elements on the same row and the best transformation of c with a different symbol

it performs the best transformation, otherwise the best swap. The pseudocode of IncRow is described in Algorithm 1.

The DecRow algorithm is equivalent to IncRow except that the columns are scanned in decreasing order of probability. The pseudocode of DecRow is the same as the one described in Algorithm 1 except that the order of the for on line 2 is j ← |M| to 1.