# Semantically Secure Symmetric Encryption with Error Correction for Distributed Storage

Authors: Juha Partala
Journal: Security and Communication Networks
 (2017)

---

## Abstract

A distributed storage system (DSS) is a fundamental building block in many distributed applications. It applies linear network coding to achieve an optimal tradeoff between storage and repair bandwidth when node failures occur. Additively homomorphic encryption is compatible with linear network coding. The homomorphic property ensures that a linear combination of ciphertext messages decrypts to the same linear combination of the corresponding plaintext messages. In this paper, we construct a linearly homomorphic symmetric encryption scheme that is designed for a DSS. Our proposal provides simultaneous encryption and error correction by applying linear error correcting codes. We show its IND-CPA security for a limited number of messages based on binary Goppa codes and the following assumption: when dividing a scrambled generator matrixG^ into two parts G1^ and G2^, it is infeasible to distinguish G2^ from random and to find a statistical connection between G1^ and G2^. Our infeasibility assumptions are closely related to those underlying the McEliece public key cryptosystem but are considerably weaker. We believe that the proposed problem has independent cryptographic interest.


---

## Body

## 1. Introduction

The world’s ability to generate, process, and store information is growing at an exponential rate [1]. The Internet of Things (IoT) has enabled objects to collect and share a vast amount of data enabling new applications and improving efficiency. In distributed IoT, intelligence is pushed to the very edge of the networks. Such decentralized approach has created challenges regarding the security and privacy of the collected data [2]. A distributed storage system (DSS) is a widely used technology for storing data in a reliable way. It is one of the essential building blocks for distributed applications. Such a system consists of a collection of n storage nodes that may be individually unreliable but apply redundancy to make the system reliable as a whole. Coding schemes are applied to ensure its reliability and to reduce the bandwidth required for repair. In particular, linear network coding has turned out to offer good performance both in theory and in practice.Complications arise if we cannot be certain that the storage nodes are well-behaved. Encryption needs to be applied to ensure the confidentiality of the data. However, traditional cryptographic primitives are ill-suited for network coding which requires that data packets from different nodes can be combined according to the coding scheme. Secure network coding [3–6] has been applied to ensure confidentiality in the information-theoretic security model. However, secure network coding incurs a cost on the storage capacity of the system. It decreases exponentially with the number of compromised nodes [7]. Furthermore, in many cases the storage nodes are provided by a third party storage service provider leading to systems with zero secrecy capacity [8].In this paper, we consider the confidentiality of network coding and, in particular, distributed storage systems in a setting where the adversary has complete control of the nodes but is computationally bounded. We devise a linear error correcting code based symmetric additively homomorphic encryption scheme that is compatible with linear network coding. There are several advantages of our scheme compared to ordinary encryption:(1)
Linear network coding can be applied as if working directly with the plaintext messages. Linear operations on the ciphertext space transfer to the plaintext space upon decryption.(2)
The encrypted parts of the file do not disclose which part is which. The part information can be kept in the plaintext domain. It makes it impossible for the storage nodes or the adversary to eavesdrop on which subsets of the data the user requests.(3)
The plaintext data can be first authenticated and then encrypted. For storage systems, this ordering is often desirable to ensure plaintext integrity. Our scheme can support this functionality with an additively homomorphic message authentication code such as [9] meaning that all linear combinations of the plaintext messages are authenticated.(4)
Our scheme provides simultaneous encryption and error correction.There are encryption schemes possessing additively homomorphic properties such as the Goldwasser-Micali scheme [9] and the Paillier cryptosystem [10]. However, to apply coding schemes for distributed storage we need flexibility in choosing the ciphertext space field which, for efficiency reasons, is often an extension field of the binary field F2 when working with big data [11]. The required flexibility is not provided by existing proposals.We construct a symmetric encryption schemeAddHomSE that is homomorphic from (Fqn,+) to (Fqk,+), where k<n and Fq is a finite field. In particular, our security proofs are shown in the case where Fq=F2 the binary field resulting in a scheme that is homomorphic from the additive group (F2n,⊕) to (F2k,⊕). We also show that our construction is semantically (IND-CPA) secure in the standard model (on F2) for a fixed number of messages showing that itprovides indistinguishability for each individual part of the file. We apply problems that are closely related to the McEliece cryptosystem [12]. In particular, we formulate an assumption that is related to the pseudorandomness of the McEliece generator matrix. However, our assumption is much weaker. We believe that the corresponding problem has cryptographic interest in its own right.The paper is organized as follows. In Section2 we present work that is related to ours. Section 3 describes the preliminaries for the rest of the paper. We formulate AddHomSE in Section 4. We show that the scheme is IND-CPA secure for a limited number of messages in Sections 5 and 6. In Section 7 we consider the infeasibility of the applied problems and discuss how the scheme can be applied in practice with compact keys. Finally, Section 8 provides the conclusion.


## 2. Related Work

The theory of confidentiality of distributed storage is related to that of network coding. Cai and Yeung were the first to consider secure network coding [3, 4]. In their security model, a passive wiretapper is able to eavesdrop on a subset of the links between nodes. The adversary is computationally unbounded and privacy is considered information-theoretically. A similar model was considered in [13–16]. The security model of eavesdropping nodes, which is more natural for distributed storage, was suggested by Pawar et al. [8]. In their model, a computationally unbounded eavesdropper can access data on her selection of the nodes. The maximum file size that can be stored with information-theoretic security in the DSS using an optimal bandwidth MDS code (with exact repair) is called thesecrecy capacity of the DSS. Regenerating codes achieving the secrecy capacity were suggested by Shah et al. [5]. Regenerating codes and locally repairable secure codes that achieve minimum storage requirements for a DSS were suggested by Rawat et al. [6]. Multiple simultaneous node failures, cooperative regenerating codes, and their secrecy capacity were considered in [17]. Kosut et al. considered networks where a node behaves traitorously [18]. Multiple nodes containing adversarial errors were considered by Dikaliotis et al. [19]. Pawar et al. considered an active omniscient adversary that has complete knowledge of the data on all nodes and can corrupt b nodes, where 2b<k [20].The concept of homomorphic encryption was introduced by Rivest et al. [21]. While fully homomorphic encryption enables arbitrary computations on ciphertexts, many proposed schemes have homomorphic properties over specific operations. For example, RSA [22] is homomorphic over multiplication. Additively homomorphic schemes enable the computation of linear combinations of the ciphertexts. For the Goldwasser-Micali scheme [9] and the Paillier cryptosystem [10] multiplication in the ciphertext space corresponds to addition in the plaintext space. The scheme proposed by Lyubashevsky et al. is additively homomorphic with a polynomial ring as the ciphertext space [23]. Other asymmetric schemes with additively homomorphic properties can be found, for example, from [24–29]. The functionality of public key encryption incurs a computational burden that is not needed in certain situations. For many applications, symmetric encryption suffices. Few symmetric schemes with the additive homomorphic property have been proposed. Some constructions, mostly concentrating on realizing fully homomorphic encryption, can be found from [30–33]. In addition, the ciphertext and plaintext spaces in these schemes cannot be easily applied with linear network coding where we want to work with extension fields of the binary field F2 for efficiency reasons.


## 3. Preliminaries

### 3.1. Notation

Standard notation will be used for probabilistic algorithms [34]. We denote by y←A(x;r) the result of running a probabilistic algorithm A on input x with randomness r and setting y to be equal to the output. We denote the uniform probability distribution on a set X by U(X). If A is a random variable and F is a distribution, we denote A~F when A is distributed according to F. A probability ensemble X={Xk}k∈N is a collection of random variables indexed by the integers. The problem of computationally distinguishing between two probability ensembles A and B is denoted by D(A,B).Whenever we refer to indistinguishability of probability ensembles, we mean computational indistinguishability unless stated otherwise. Security proofs are considered in the standard model. That is, all algorithms are considered to be probabilistic polynomial time (PPT) and time complexity is considered in the average case. The success probability (called theadvantage) of an adversary A on a problem P is considered asymptotically as a function of a security parameter s and is denoted by AdvAP(s). A function ϵ:N→R is negligible if for every n∈N there is k′∈N such that ϵ(k)≤1/kn for every k≥k′. A problem P is considered infeasible if for all PPT algorithms A the advantage AdvAP(s) is negligible.


### 3.2. Dynamic Distributed Storage

LetF be a file consisting of M elements from a finite field Fq. A dynamic distributed storage system (DSS) consists of n live nodes each storing α symbols over Fq. These nodes can be individually unreliable but the system is designed to apply redundancy in a clever way to achieve robust and efficient data recovery against failures. The file F=(F1,F2,…,FM)∈FqM is encoded into a codeword x consisting of n blocks x=(x1,x2,…,xn)∈(Fqα)n. Given such a codeword x, the part xi is stored into node i. During operation, some of the nodes of the DSS may fail. If node i fails, a new node is added to the network. It contacts d live nodes and downloads β symbols from each. The total amount of downloaded data, γ=βd, is called the repair bandwidth. The new node processes these symbols to reconstruct xi. The repair process is conducted so that data stored at k<n nodes allows F to be completely constructed (the “k out of n property”). A DSS satisfying such a property is often referred to as a (n,k)-DSS.There is a tradeoff between the repair bandwidthγ and the amount of data that can be stored in each node [35]. Dimakis et al. suggested network coding [36, 37] for distributed data storage in order to reduce the bandwidth of node repair [35]. They introduced regenerating codes that achieve the optimal tradeoff between storage and repair bandwidth. This tradeoff can be achieved with linear network coding [20]. See Figure 1 for an example of a DSS and the repair process after node failure.Figure 1
An example of a distributed storage system with linear coding. A fileF=(F1,F2,F3,F4) is distributed to n=4 nodes each storing a vector of two parts of the file (α=2). The file is safe if one node fails. If Node 1 fails, it can be replaced by communicating only three blocks (F4,F2⊕F4,F1⊕F2⊕F4) instead of all four.


### 3.3. Mutual Information

Mutual information of two random variablesX and Y is(1)IX;Y=∑y∈Y∑x∈Xpx,ylog2⁡px,ypx·py,where p(x,y) is the joint probability distribution function of X and Y, p(x) is the marginal probability distribution function of X, and p(y) is the marginal probability distribution function of Y. We say that X and Y aredependent if(2)IX;Y>0.Generalizing this to probability ensembles X={Xs:s∈N} and Y={Ys:s∈N} we say that X and Y aredependent if(3)IXs;Ys>0for every s∈N.


### 3.4. McEliece Cryptosystem and Related Problems

The McEliece schemeMcEliece=Gen,Enc,Dec applies binary Goppa codes [38] to enable asymmetric encryption. The key generation algorithm Gen outputs a private/public key pair such that the private key consists of three matrices (S,G,P) with entries in F2, where P is an n×n permutation matrix, S is a nonsingular k×k matrix, and G is the generator matrix for a binary Goppa code that is able to correct up to t errors. The public key is the k×n composition matrix SGP. A message m∈F2k is encrypted by Enc by computing c=mSGP+e, where e is a randomly chosen error vector of Hamming weight t. For the decryption, Dec first computes cP-1=mSG+eP-1 and then decodes the corresponding Goppa codeword to obtain mS. Since S is nonsingular, the message m is computed by multiplying with S-1 from the right. A semantically secure version of the scheme can be found in [39]. Here, semantic security refers to indistinguishability of ciphertexts under chosen plaintext attack. For details on semantic security, see, for example, [40].The security ofMcEliece is based on a certain assumption on the generator matrix SGP. Let Mcs denote the random variable determined by the probability distribution of sampling a generator matrix SGP according to Gen(1s), where s is a security parameter. Let the probability ensemble Mc={Mcs:s∈N}. Let McU denote the probability ensemble of random matrices with the same size as Mc. The following hardness assumption was first formulated in [41].Assumption 1 (pseudorandomness of McEliece generator matrix).
There exists a negligible functionϵM such that(4)AdvDMc,McUs≤ϵMs for every s≥1.In addition to this pseudorandomness assumption,McEliece relies on the hardness of thelearning parity with noise problem. However, we do not need to apply it in our scheme.


## 3.1. Notation

Standard notation will be used for probabilistic algorithms [34]. We denote by y←A(x;r) the result of running a probabilistic algorithm A on input x with randomness r and setting y to be equal to the output. We denote the uniform probability distribution on a set X by U(X). If A is a random variable and F is a distribution, we denote A~F when A is distributed according to F. A probability ensemble X={Xk}k∈N is a collection of random variables indexed by the integers. The problem of computationally distinguishing between two probability ensembles A and B is denoted by D(A,B).Whenever we refer to indistinguishability of probability ensembles, we mean computational indistinguishability unless stated otherwise. Security proofs are considered in the standard model. That is, all algorithms are considered to be probabilistic polynomial time (PPT) and time complexity is considered in the average case. The success probability (called theadvantage) of an adversary A on a problem P is considered asymptotically as a function of a security parameter s and is denoted by AdvAP(s). A function ϵ:N→R is negligible if for every n∈N there is k′∈N such that ϵ(k)≤1/kn for every k≥k′. A problem P is considered infeasible if for all PPT algorithms A the advantage AdvAP(s) is negligible.


## 3.2. Dynamic Distributed Storage

LetF be a file consisting of M elements from a finite field Fq. A dynamic distributed storage system (DSS) consists of n live nodes each storing α symbols over Fq. These nodes can be individually unreliable but the system is designed to apply redundancy in a clever way to achieve robust and efficient data recovery against failures. The file F=(F1,F2,…,FM)∈FqM is encoded into a codeword x consisting of n blocks x=(x1,x2,…,xn)∈(Fqα)n. Given such a codeword x, the part xi is stored into node i. During operation, some of the nodes of the DSS may fail. If node i fails, a new node is added to the network. It contacts d live nodes and downloads β symbols from each. The total amount of downloaded data, γ=βd, is called the repair bandwidth. The new node processes these symbols to reconstruct xi. The repair process is conducted so that data stored at k<n nodes allows F to be completely constructed (the “k out of n property”). A DSS satisfying such a property is often referred to as a (n,k)-DSS.There is a tradeoff between the repair bandwidthγ and the amount of data that can be stored in each node [35]. Dimakis et al. suggested network coding [36, 37] for distributed data storage in order to reduce the bandwidth of node repair [35]. They introduced regenerating codes that achieve the optimal tradeoff between storage and repair bandwidth. This tradeoff can be achieved with linear network coding [20]. See Figure 1 for an example of a DSS and the repair process after node failure.Figure 1
An example of a distributed storage system with linear coding. A fileF=(F1,F2,F3,F4) is distributed to n=4 nodes each storing a vector of two parts of the file (α=2). The file is safe if one node fails. If Node 1 fails, it can be replaced by communicating only three blocks (F4,F2⊕F4,F1⊕F2⊕F4) instead of all four.


## 3.3. Mutual Information

Mutual information of two random variablesX and Y is(1)IX;Y=∑y∈Y∑x∈Xpx,ylog2⁡px,ypx·py,where p(x,y) is the joint probability distribution function of X and Y, p(x) is the marginal probability distribution function of X, and p(y) is the marginal probability distribution function of Y. We say that X and Y aredependent if(2)IX;Y>0.Generalizing this to probability ensembles X={Xs:s∈N} and Y={Ys:s∈N} we say that X and Y aredependent if(3)IXs;Ys>0for every s∈N.


## 3.4. McEliece Cryptosystem and Related Problems

The McEliece schemeMcEliece=Gen,Enc,Dec applies binary Goppa codes [38] to enable asymmetric encryption. The key generation algorithm Gen outputs a private/public key pair such that the private key consists of three matrices (S,G,P) with entries in F2, where P is an n×n permutation matrix, S is a nonsingular k×k matrix, and G is the generator matrix for a binary Goppa code that is able to correct up to t errors. The public key is the k×n composition matrix SGP. A message m∈F2k is encrypted by Enc by computing c=mSGP+e, where e is a randomly chosen error vector of Hamming weight t. For the decryption, Dec first computes cP-1=mSG+eP-1 and then decodes the corresponding Goppa codeword to obtain mS. Since S is nonsingular, the message m is computed by multiplying with S-1 from the right. A semantically secure version of the scheme can be found in [39]. Here, semantic security refers to indistinguishability of ciphertexts under chosen plaintext attack. For details on semantic security, see, for example, [40].The security ofMcEliece is based on a certain assumption on the generator matrix SGP. Let Mcs denote the random variable determined by the probability distribution of sampling a generator matrix SGP according to Gen(1s), where s is a security parameter. Let the probability ensemble Mc={Mcs:s∈N}. Let McU denote the probability ensemble of random matrices with the same size as Mc. The following hardness assumption was first formulated in [41].Assumption 1 (pseudorandomness of McEliece generator matrix).
There exists a negligible functionϵM such that(4)AdvDMc,McUs≤ϵMs for every s≥1.In addition to this pseudorandomness assumption,McEliece relies on the hardness of thelearning parity with noise problem. However, we do not need to apply it in our scheme.


## 4. Additively Homomorphic Symmetric Encryption Scheme

In this section, we give a construction of a symmetric encryption scheme that is homomorphic from the additive group(F2n,⊕) to (F2k,⊕), where k,n∈N and k<n. Due to linearity, it will be compatible with linear network coding. Our construction is inspired by the symmetric scheme suggested in [42], the homomorphic scheme suggested in [43] and the McEliece public key encryption scheme [12], and, especially, its IND-CPA variant [39]. Similarly to the McEliece scheme, our scheme is based on binary Goppa error correcting codes [38]. However, contrary to the McEliece scheme, we do not disclose the scrambled generator matrix. We also do not add any errors while encrypting which means that the full error correction capacity of the code can be utilized in applications. It would also be easy to adapt our proposal to apply other codes on an arbitrary finite field Fq. However, binary fields and their extensions are useful for many applications since they enable efficient data combination due to efficiency of addition modulo 2 [11].In general, the scheme operates as follows. Suppose that our file is divided intor parts constituting r plaintext messages m1,m2,…,mr. Each of these messages are padded with a random suffix z and encrypted by encoding with a scrambled generator matrix G^ of a linear error correcting code: ci=(mi,z)G^. Note that the resulting ciphertexts can be linearly combined and the corresponding combination translates back to the plaintext space upon decoding due to linearity of the code. Furthermore, since the generator matrix is scrambled, an adversary is not able to determine the applied code and thus not able to decrypt the ciphertexts. In the following, we rigorously formulate this construction and the related computational assumptions. Based on computational indistinguishability, we then proceed to show its semantic security.Definition 2 (AddHomSE).
The symmetric encryption scheme(5)AddHomSE=Gen,Enc,Decconsists of a three-tuple of algorithms given in the following: (1)
Gen(1s): based on the security parameter 1s, Gen chooses a randomization length r, a linear [n,k∗,d]-error correcting Goppa code over F2 with a generator matrix G such that k∗>r. It also samples a random nonsingular k∗×k∗ matrix S and a random n×n permutation matrix P. It then sets the cleartext length to be k such that k∗=k+r, where k≤r-1 and sets n,k as public parameters and outputs (S,G,P) as the secret key.(2)
Enc((S,G,P),m): the input consists of a key (S,G,P), a plaintext m∈F2k. It then samples a random(6)z⟵UF2rand encodes the concatenation(m,z)∈Fk∗ using SGP to obtain a ciphertext message(7)c=m,zSGP∈Fn.(3)
Dec((S,G,P),c): the input consists of a key (S,G,P) and a ciphertext c∈F2n. The plaintext message m∈F2k is obtained by decoding cP-1 using the Goppa code, mapping the decoded message by S-1 and discarding the last r bits.The key generation, encryption, and decryption processes are depicted in Algorithms1, 2, and 3, respectively.Algorithm 1:
AddHomSE key generation.
Gen:1s
↓
Determine randomization lengthr∈N
↓
Generate
random non-singular matrixS∈F2k∗×k∗
Goppa generator matrixG∈F2n×k∗
random permutation matrixP∈F2n×n
↓
Set cleartext lengthk=k∗-r
↓
Output public parametersn,k
Output secret keyS,G,PAlgorithm 2:
AddHomSE encryption.
Enc:m∈F2k
Generate a random↓
suffixz∈F2r
↓
Add suffixm,z∈F2k∗
↓
S
G
P
Encodec∈F2nAlgorithm 3:
AddHomSE decryption.
Dec:c∈F2n
Permute↓P-1
c
P
-
1
∈
F
2
n
Decode↓G
z
∈
F
2
k
∗
Demix↓S-1
m
,
z
∈
F
2
k
∗
Discard suffix↓
m
∈
F
2
kNote that contrary to the McEliece cryptosystem, the matrixSGP is not public. Instead, it is kept as a secret key. In addition, no error vectors are added in the encryption process.We shall now proceed to show the IND-CPA security of our construction. Our plan is the following. We first show thatAddHomSE can be divided into two parts, Enc1 and Enc2, such that the output of Enc is the sum of the outputs of these two algorithms. We then proceed to show that Enc2 produces a probability ensemble that is indistinguishable from random under a certain (reasonable) assumption. We then consider the sum of the outputs of these two algorithms and proceed to show that (under another reasonable assumption) the complete encryption algorithm produces ciphertexts that are indistinguishable from random.We start by showing thatEnc can be expressed as a sum of two algorithms. Let the scrambled generator matrix G^=SGP be partitioned into k∗×n and r×n submatrices G1^ and G2^ such that SGPT=(G1^T,G2^T), where T denotes transpose. Then we have(8)EncS,G,P,m;r′=mG1^︸Enc1S,G,P,m⊕zG2^︸Enc2S,G,P;r′,where Enc1 is deterministic PT, Enc2 is PPT, and r′ is the internal randomness used by Enc.Now,Enc2 adds a different element zG2^∈F2n to the output of Enc1 determined by the randomness r′. Suppose that we are encrypting q messages and that the output of Enc2 is a truly random U(h)~U(F2n) for every h≤q. Then for every h≤q and every plaintext message mh the output of Enc would be characterized by(9)Enc1S,G,P,mh⊕Uh~UF2nand AddHomSE would satisfy perfect secrecy for q encryptions. In reality, the output of Enc2 is not truly random. However, in the following we show that it is indistinguishable from random under a certain assumption. Then we consider the connection between Enc1 and Enc2 and, finally, the indistinguishability of encryptions from random. For easier reference, variables used in the description of the scheme, as well as in the following proofs, have been collected into Table 1. Similarly, the used random variables have been collected into Table 2.Table 1
The variables used inAddHomSE and in its proof of security and their descriptions.
Variable
Description
1
s
The security parameter
r
,
r
s
A randomization length; determines the maximum number of file parts
m
,
m
h
A plaintext message
c
,
c
h
A ciphertext message
z
,
z
h
A random binary suffix of lengthr
n
,
n
s
The length of the used Goppa code
k
∗
,
k
s
∗
The dimension of the used Goppa code
d
The distance of the used Goppa code
G
The generator matrix of the Goppa code
S
A random non-singular binaryk∗×k∗ matrix
P
A randomn×n permutation matrix
k
,
k
s
The cleartext length such thatk∗=k+r and k≤r-1
G
^
The scrambled generator matrixG^=SGP
G
1
^
k
∗
×
n submatrix of G^; (G^)T=(G1^T,G2^T)
G
2
^
r
×
n submatrix of G^; (G^)T=(G1^T,G2^T)
r
′
The internal randomness used byEnc
q
The total number of encrypted messages
Z
A uniformly randomq×rs matrix
G
′
A uniformly randomrs×ns matrix
M
A message matrixM=m0T,m1T,…,mq-1TTTable 2
The used random variables and their descriptions.
Random variable
Description
U(h)
Distributed uniformly onF2n for every h≤q
E
s
2
,
(
h
)
Induced byEnc2S,G,P=zhG2^ for h≤q
E
s
2
,
q
Aq-tuple of random variables Es2,0,Es2,1,…,Es2,q-1
M
c
s
Corresponds to the choice ofG^
M
c
s
1
Corresponds to the choice ofG1^
M
c
s
2
Corresponds to the choice ofG2^
M
c
U
s
2
Distributed uniformly onF2rs×ns
V
s
q
Determined byZG′
U
s
q
Distributed uniformly onF2rs×ns
K
s
Determined by key generation;Ks=Gen(1s)
E
s
(
h
)
Determined by encryption ofmh; Es(h)=Enc(Ks,mh)
E
s
q
Determined by encryption ofq messages; Esq=Es0,Es1,…,Esq-1


## 5. The Probability Ensemble Induced byEnc2

In the following, we consider the probability ensembleE2,q=Es2,qs∈N induced by Enc2 for q encryptions. That is, we have a q-tuple(10)Es2,q=Es2,0,Es2,1,…,Es2,q-1such that Es2,(h)=Enc2S,G,P=zhG2^ for every h∈0,1,…,q-1, where (S,G,P)←Gen(1s) and zh←U(F2r). Note that n,k∗,k, and r depend on the security parameter s. In the following, we have made the dependence explicit. We can consider E2,q as a random variable over F2q×ns by setting E2,q=ZG2^, where Z is a q×rs matrix chosen uniformly at random. For convenience, we assume that E2,q is written in such a matrix form.


### 5.1. Indistinguishability ofG2^ from Random

Our plan is to show the indistinguishability ofE2,q from random for all q≤rs. In order to do that we want G2^ to be also indistinguishable from random. We could apply the McEliece assumption (Assumption 1) that states that the complete generator matrix SGP satisfies this property. However, such an assumption is too strong in our case. We derive a weaker assumption that relates only to G2^.Definition 3.
LetMc={Mcs}s∈N denote a probability ensemble of McEliece generator matrices (chosen according to some schema) such that Mcs is distributed over matrices of size ks∗×ns∗ for every s∈N. Let Mc1={Mcs1}s∈N and Mc2={Mcs2}s∈N denote the probability ensembles such that McsT=((Mcs1)T,(Mcs2)T) for every s∈N, where Mc1 is distributed over matrices of size ks×ns and Mc2 is distributed over matrices of size rs×ns, where ks+rs=ks∗ and ks and rs are chosen according to Gen(1s).Assumption 4 (G2^ indistinguishable from random).
LetMcU2=McUs2s∈N denote the uniform probability ensemble such that McUs2~UF2rs×ns for every s∈N. For every PPT algorithm A, there is a negligible function ϵ such that(11)AdvADMc2,McU2s≤ϵsfor every s≥1.If the generator matrix satisfies the formulated assumption, thenG2^ cannot be distinguished from random. Suppose that G2^ is exchanged with truly random matrix. Let Vq=Vsqs∈N be a probability ensemble such that Vsq=ZG′, where Z←U(F2q×rs) and G′←UF2rs×ns. Let Uq={Usq}s∈N denote the uniform probability ensemble such that Usq~UF2q×ns, where ns is determined by Gen1s. Clearly, the statistical distance(12)ΔVsq,Usq=0for every s∈N and q≤rs since all of the elements of ZG′ are uniformly random.We shall now provide a connection between Assumption4 and the indistinguishability of E2,q from Vq for q≤rs.Proposition 5.
For every PPT algorithmA there is a PPT algorithm B such that(13)AdvBDMc2,McU2s≥AdvADE2,q,Vqsfor every q≤rs and s∈N.Proof.
The reduction is straightforward. Lets∈N be given and let A be a PPT algorithm considered as a distinguisher for E2,q and Vq. Let us define the distinguisher B for Mc2 and McU2 that is shown in Algorithm 4.
IfX←Mcs2, then B is invoked with rs rows of a McEliece generator matrix. By the description of B, A is queried with a matrix sampled according to Es2,q. Let now X←McUs2. Then A is invoked with an element sampled according to Vsq and since B outputs the same bit as A, we have(14)AdvBDMc2,McU2s=AdvADE2,q,Vqs.Algorithm 4
(1)procedureB1s,X▹X is a rs×ns matrix
(2)Z←U(F2q×rs)
(3)b←A(1s,ZX)
(4)return  b
(5)end procedureA direct consequence of Proposition5 is the result we aimed for: indistinguishability of E2,q from random under Assumption 4.Proposition 6.
For every PPT algorithmA and q≤r,(15)AdvADE2,q,Uqs=AdvADE2,q,Vqs≤AdvDMc2,McU2sfor every s∈N.


## 5.1. Indistinguishability ofG2^ from Random

Our plan is to show the indistinguishability ofE2,q from random for all q≤rs. In order to do that we want G2^ to be also indistinguishable from random. We could apply the McEliece assumption (Assumption 1) that states that the complete generator matrix SGP satisfies this property. However, such an assumption is too strong in our case. We derive a weaker assumption that relates only to G2^.Definition 3.
LetMc={Mcs}s∈N denote a probability ensemble of McEliece generator matrices (chosen according to some schema) such that Mcs is distributed over matrices of size ks∗×ns∗ for every s∈N. Let Mc1={Mcs1}s∈N and Mc2={Mcs2}s∈N denote the probability ensembles such that McsT=((Mcs1)T,(Mcs2)T) for every s∈N, where Mc1 is distributed over matrices of size ks×ns and Mc2 is distributed over matrices of size rs×ns, where ks+rs=ks∗ and ks and rs are chosen according to Gen(1s).Assumption 4 (G2^ indistinguishable from random).
LetMcU2=McUs2s∈N denote the uniform probability ensemble such that McUs2~UF2rs×ns for every s∈N. For every PPT algorithm A, there is a negligible function ϵ such that(11)AdvADMc2,McU2s≤ϵsfor every s≥1.If the generator matrix satisfies the formulated assumption, thenG2^ cannot be distinguished from random. Suppose that G2^ is exchanged with truly random matrix. Let Vq=Vsqs∈N be a probability ensemble such that Vsq=ZG′, where Z←U(F2q×rs) and G′←UF2rs×ns. Let Uq={Usq}s∈N denote the uniform probability ensemble such that Usq~UF2q×ns, where ns is determined by Gen1s. Clearly, the statistical distance(12)ΔVsq,Usq=0for every s∈N and q≤rs since all of the elements of ZG′ are uniformly random.We shall now provide a connection between Assumption4 and the indistinguishability of E2,q from Vq for q≤rs.Proposition 5.
For every PPT algorithmA there is a PPT algorithm B such that(13)AdvBDMc2,McU2s≥AdvADE2,q,Vqsfor every q≤rs and s∈N.Proof.
The reduction is straightforward. Lets∈N be given and let A be a PPT algorithm considered as a distinguisher for E2,q and Vq. Let us define the distinguisher B for Mc2 and McU2 that is shown in Algorithm 4.
IfX←Mcs2, then B is invoked with rs rows of a McEliece generator matrix. By the description of B, A is queried with a matrix sampled according to Es2,q. Let now X←McUs2. Then A is invoked with an element sampled according to Vsq and since B outputs the same bit as A, we have(14)AdvBDMc2,McU2s=AdvADE2,q,Vqs.Algorithm 4
(1)procedureB1s,X▹X is a rs×ns matrix
(2)Z←U(F2q×rs)
(3)b←A(1s,ZX)
(4)return  b
(5)end procedureA direct consequence of Proposition5 is the result we aimed for: indistinguishability of E2,q from random under Assumption 4.Proposition 6.
For every PPT algorithmA and q≤r,(15)AdvADE2,q,Uqs=AdvADE2,q,Vqs≤AdvDMc2,McU2sfor every s∈N.


## 6. Semantic Security forr Messages

Let us now turn to the probability ensemble induced by the complete encryption algorithmEnc. We establish the semantic security of AddHomSE by proving that it satisfies ciphertext indistinguishability for up to rs messages under two assumptions: Assumption 4 and a new one regarding independence of G1^ and G2^. Let m0,m1,…,mq-1∈F2k be any plaintext messages. Let Eq=Esqs∈N such that Esq=Es0,Es1,…,Esq-1, where Es(h)=Enc(Ks,mh) and Ks=Gen(1s). As before, let us consider Esq in the matrix form. Set also M=m0T,m1T,…,mq-1TT. That is, the rows of M consist of the plaintext messages. We call M themessage matrix of m0,m1,…,mq-1∈F2k.


### 6.1. Computational Independence

Assumption4 concerns the last part G2^ of the generator matrix G. However, we need to also make an assumption regarding G1^. For example, suppose that it was possible that G1^=G2^. Then Eq would be easily distinguishable with high probability by choosing M=I, the identity matrix. To foil such attempts, we want G1^ and G2^ to be sufficiently independent of each other. We shall formulate an assumption concerning the mutual information of Mcs1 and Mcs2.Let us define the following experiment in which we attempt to determine whether two probability ensembles are dependent. Suppose that we have three probability ensemblesA,B, and X. Suppose also that B is indistinguishable from X. Furthermore, suppose that I(As;Bs)>0 while I(As;Xs)=0 for every s∈N. We define the experiment that is shown in Algorithm 5.Algorithm 5
(1)procedureDepExpA,A,B,Xs▹Dependability experiment
(2)b←U0,1
(3)if  b=1  then
(4)b′←A1s,As,Bs
(5)else
(6)b′←A1s,As,Xs
(7)end if
(8)ifb=b′  then
(9)output 1
(10)else
(11)output 0
(12)end if
(13)end procedureIn the experiment,A is either given an element from Bs such that I(As;Bs)>0 or an element from Xs that is indistinguishable from Bs such that I(As;Xs)=0. Since B and X are indistinguishable, A succeeds in this experiment with nonnegligible probability only if it is able to find the dependability of Bs from As.Definition 7.
LetA={As:s∈N},B={Bs:s∈N} be probability ensembles. We say that A and B arecomputationally independent if for every PPT algorithm A and every probability ensemble X={Xs:s∈N} such that X is computationally indistinguishable from B and I(Bs;Xs)=0 for every s∈N there is a negligible function ϵ such that(16)AdvADepA,B,Xs=2·PrDepExpA,A,B,X=1-1≤ϵsfor every s∈N. If this does not hold, then we say that A and B arenoticeably dependent.Note that it follows from the definition ofDep(A,B,X) that(17)AdvDepA,B,Xs≥AdvDB,Xsfor every s∈N. We formulate the following assumption concerning the relationship between G1^ and G2^.Assumption 8 (G1^ and G2^ computationally independent).
For every probability ensembleX indistinguishable and independent from Mc2 and every PPT algorithm A there is a negligible function ϵ such that(18)AdvADepMc1,Mc2,Xs≤ϵsfor every s≥1.The assumption states that it is not feasible to find any information that linksG1^ and G2^. The assumption is still weaker than the McEliece assumption that states that the whole G^=SGP is indistinguishable from random. (If they are, then necessarily G1^ and G2^ are computationally independent.) However, Assumption 8 does not require G1^ to be indistinguishable from random. In fact, our proofs do not depend at all on the structure of G1^ as long as G1^ and G2^ are computationally independent. To make the scheme faster, we could, for instance, omit S and P from affecting the first k rows of the generator matrix G.We are now ready to show the semantic security ofAddHomSE by showing the indistinguishability of Eq from random.Proposition 9.
A
d
d
H
o
m
S
E has indistinguishable encryptions for rs messages under Assumptions 4 and 8.Proof.
Suppose that Assumption4 holds. We establish the claim by showing that for every set of q≤rs plaintext messages m0,m1,…,mq-1∈F2ks and every PPT algorithm A there is a PPT algorithm B such that(19)AdvADEq,Uqs≤AdvBDepMc1,Mc2,McU2sfor s∈N, where Eq is induced by m0,m1,…,mq-1. Then, under Assumption 8, the advantage of A is negligible.
SinceMcU2 is truly random, we have IMc2;McU2=0. In addition, by Assumption 4, Mc2 is computationally indistinguishable from McU2 and therefore DepMc1,Mc2,McU2 is well defined. Let the security parameter s be fixed and let m0,m1,…,mq-1∈F2k be any messages. Let M be the message matrix of m0,m1,…,mq-1. Written in the matrix form, we have Esq=MMcs1⊕Es2,q and the elements are of the form(20)MG1^⊕ZG2^,where G=(G1^T,G2^T)T←Mcs and Z←UF2q×rs.
LetA be any PPT algorithm considered as a distinguisher for D(Eq,Uq). Using A, we construct an algorithm B that determines the dependability of Mc1 and Mc2 (see Algorithm 6).
Suppose that the inputX is random matrix. Then(21)Y=MG1^⊕ZX︸←UF2q×nsis a truly random matrix. Therefore, A was invoked with a matrix sampled according to Usq. Suppose now that X=G2^. Then(22)Y=MG1^⊕ZG2^︸←Es2,qand Y was sampled according to Esq. Since B outputs the same bit as A, we have(23)AdvBDepMc1,Mc2,McU2s≥AdvADEq,Uqs.Algorithm 6
(1)procedure  B1s,G1^,X▹X is either G2^ or a random matrix
(2)Z←U(F2q×rs)
(3)Y←MG1^⊕ZX
(4)b←A(1s,Y)
(5)output  b
(6)end procedureA
d
H
o
m
S
E is IND-CPA secure under Assumptions 4 and 8 whenever the adversary is restricted to at most rs queries to the encryption oracle (the test query included). Considering a DSS, whenever the dataset is divided into at most rs parts, each of those parts remains secret even under a chosen ciphertext attack where the adversary is able to choose each of those parts separately and adaptively.


## 6.1. Computational Independence

Assumption4 concerns the last part G2^ of the generator matrix G. However, we need to also make an assumption regarding G1^. For example, suppose that it was possible that G1^=G2^. Then Eq would be easily distinguishable with high probability by choosing M=I, the identity matrix. To foil such attempts, we want G1^ and G2^ to be sufficiently independent of each other. We shall formulate an assumption concerning the mutual information of Mcs1 and Mcs2.Let us define the following experiment in which we attempt to determine whether two probability ensembles are dependent. Suppose that we have three probability ensemblesA,B, and X. Suppose also that B is indistinguishable from X. Furthermore, suppose that I(As;Bs)>0 while I(As;Xs)=0 for every s∈N. We define the experiment that is shown in Algorithm 5.Algorithm 5
(1)procedureDepExpA,A,B,Xs▹Dependability experiment
(2)b←U0,1
(3)if  b=1  then
(4)b′←A1s,As,Bs
(5)else
(6)b′←A1s,As,Xs
(7)end if
(8)ifb=b′  then
(9)output 1
(10)else
(11)output 0
(12)end if
(13)end procedureIn the experiment,A is either given an element from Bs such that I(As;Bs)>0 or an element from Xs that is indistinguishable from Bs such that I(As;Xs)=0. Since B and X are indistinguishable, A succeeds in this experiment with nonnegligible probability only if it is able to find the dependability of Bs from As.Definition 7.
LetA={As:s∈N},B={Bs:s∈N} be probability ensembles. We say that A and B arecomputationally independent if for every PPT algorithm A and every probability ensemble X={Xs:s∈N} such that X is computationally indistinguishable from B and I(Bs;Xs)=0 for every s∈N there is a negligible function ϵ such that(16)AdvADepA,B,Xs=2·PrDepExpA,A,B,X=1-1≤ϵsfor every s∈N. If this does not hold, then we say that A and B arenoticeably dependent.Note that it follows from the definition ofDep(A,B,X) that(17)AdvDepA,B,Xs≥AdvDB,Xsfor every s∈N. We formulate the following assumption concerning the relationship between G1^ and G2^.Assumption 8 (G1^ and G2^ computationally independent).
For every probability ensembleX indistinguishable and independent from Mc2 and every PPT algorithm A there is a negligible function ϵ such that(18)AdvADepMc1,Mc2,Xs≤ϵsfor every s≥1.The assumption states that it is not feasible to find any information that linksG1^ and G2^. The assumption is still weaker than the McEliece assumption that states that the whole G^=SGP is indistinguishable from random. (If they are, then necessarily G1^ and G2^ are computationally independent.) However, Assumption 8 does not require G1^ to be indistinguishable from random. In fact, our proofs do not depend at all on the structure of G1^ as long as G1^ and G2^ are computationally independent. To make the scheme faster, we could, for instance, omit S and P from affecting the first k rows of the generator matrix G.We are now ready to show the semantic security ofAddHomSE by showing the indistinguishability of Eq from random.Proposition 9.
A
d
d
H
o
m
S
E has indistinguishable encryptions for rs messages under Assumptions 4 and 8.Proof.
Suppose that Assumption4 holds. We establish the claim by showing that for every set of q≤rs plaintext messages m0,m1,…,mq-1∈F2ks and every PPT algorithm A there is a PPT algorithm B such that(19)AdvADEq,Uqs≤AdvBDepMc1,Mc2,McU2sfor s∈N, where Eq is induced by m0,m1,…,mq-1. Then, under Assumption 8, the advantage of A is negligible.
SinceMcU2 is truly random, we have IMc2;McU2=0. In addition, by Assumption 4, Mc2 is computationally indistinguishable from McU2 and therefore DepMc1,Mc2,McU2 is well defined. Let the security parameter s be fixed and let m0,m1,…,mq-1∈F2k be any messages. Let M be the message matrix of m0,m1,…,mq-1. Written in the matrix form, we have Esq=MMcs1⊕Es2,q and the elements are of the form(20)MG1^⊕ZG2^,where G=(G1^T,G2^T)T←Mcs and Z←UF2q×rs.
LetA be any PPT algorithm considered as a distinguisher for D(Eq,Uq). Using A, we construct an algorithm B that determines the dependability of Mc1 and Mc2 (see Algorithm 6).
Suppose that the inputX is random matrix. Then(21)Y=MG1^⊕ZX︸←UF2q×nsis a truly random matrix. Therefore, A was invoked with a matrix sampled according to Usq. Suppose now that X=G2^. Then(22)Y=MG1^⊕ZG2^︸←Es2,qand Y was sampled according to Esq. Since B outputs the same bit as A, we have(23)AdvBDepMc1,Mc2,McU2s≥AdvADEq,Uqs.Algorithm 6
(1)procedure  B1s,G1^,X▹X is either G2^ or a random matrix
(2)Z←U(F2q×rs)
(3)Y←MG1^⊕ZX
(4)b←A(1s,Y)
(5)output  b
(6)end procedureA
d
H
o
m
S
E is IND-CPA secure under Assumptions 4 and 8 whenever the adversary is restricted to at most rs queries to the encryption oracle (the test query included). Considering a DSS, whenever the dataset is divided into at most rs parts, each of those parts remains secret even under a chosen ciphertext attack where the adversary is able to choose each of those parts separately and adaptively.


## 7. Infeasibility, Key Size, and Error Correction Capacity

### 7.1. Infeasibility of the Problems

Let us briefly consider the infeasibility of the underlying problems related toAddHomSE. The IND-CPA security is based on assumptions that are weaker but closely related to the ones underlying the McEliece scheme. The selection of parameters for the McEliece scheme has been considered in [44] and the best performing attacks are based on information set decoding. In addition, due to algebraic attacks against Goppa codes [45, 46] the rate R∗=k∗/n cannot be close to one and the degree t of the Goppa polynomial has to satisfy t≥zmin, where zmin is the smallest integer satisfying αzαz-2β+1z+2β/2≥n-αz, where α=log2⁡n and β=log2⁡z+1 [47]. Choosing R∗≈0.8 maximizes the complexity of information set decoding attacks [44].ForAddHomSE, the attacker is not given the generator matrix. Instead, the attacker gets at most r scrambled messages under an adaptive chosen plaintext attack. Therefore, n can be drastically lower for AddHomSE. We suggest k=k∗/2-1 and r=n∗-k so that randomization length is slightly more than half of the input. The rate R∗ should be kept close to a constant. We suggest choosing a rate R∗ that is close to 0.8 due to information set decoding attacks [44].


### 7.2. Key Size

The key size ofAddHomSE is big if truly random matrices are used. In a practical setting, we want to use pseudorandom matrices for S and P. The key size is dramatically decreased by exchanging these matrices with a short seed c and generating S and P using a pseudorandom generator G. The generating matrix G of the Goppa code can be derived from the Goppa polynomial g(x) and pseudorandom elements generated by G. Therefore, in practice, the key can be compactly presented by the seed c and the polynomial g(x).Typically, in a distributed storage systems we want to encrypt files or file systems that are huge. If a large file is divided into few parts, we do not want to consider each part as a single plaintext message since such an approach would requirek∗ and n to be at least as large as the length of the file part. In such a case, we can further divide the part into smaller blocks and encrypt those block independently. Such an approach enables us to select small and efficient values for k∗ and n. Note that such a division does not affect the homomorphic property of the scheme provided that each of the file parts are processed similarly and encrypted with the same keys. It also does not have an effect on the key size since the keys of those individual blocks can be derived from the same seed c and the polynomial g(x).


### 7.3. Error Correction

Due to requirements of semantic security and error correction, ciphertexts contain overhead compared to plaintext messages. For example, withn,k∗,r=256,200,100, where the rate R∗≈0.78, plaintexts of length 100 will be encrypted into ciphertexts of length 256. The scheme can correct up to t errors, where t is the degree of the Goppa generator polynomial. With these parameters, we should choose t≥zmin=5 [47]. Choosing the smallest t, which results in the most efficient implementation, enables us to correct up to 5 errors in each 256 bits meaning that the plaintext messages are correctly decrypted with high probability whenever the error rate is less than 2%. If more error correction capacity is needed, then a higher degree Goppa generator polynomial needs to be selected and/or the rate R∗ should be lowered. As a final remark, we note that the binary Goppa code can be exchanged with another linear code on a finite field Fq. However, we have only shown the security of AddHomSE based on the indistinguishability of a scrambled Goppa generator matrices. The applied linear code has to satisfy a similar infeasibility result.


## 7.1. Infeasibility of the Problems

Let us briefly consider the infeasibility of the underlying problems related toAddHomSE. The IND-CPA security is based on assumptions that are weaker but closely related to the ones underlying the McEliece scheme. The selection of parameters for the McEliece scheme has been considered in [44] and the best performing attacks are based on information set decoding. In addition, due to algebraic attacks against Goppa codes [45, 46] the rate R∗=k∗/n cannot be close to one and the degree t of the Goppa polynomial has to satisfy t≥zmin, where zmin is the smallest integer satisfying αzαz-2β+1z+2β/2≥n-αz, where α=log2⁡n and β=log2⁡z+1 [47]. Choosing R∗≈0.8 maximizes the complexity of information set decoding attacks [44].ForAddHomSE, the attacker is not given the generator matrix. Instead, the attacker gets at most r scrambled messages under an adaptive chosen plaintext attack. Therefore, n can be drastically lower for AddHomSE. We suggest k=k∗/2-1 and r=n∗-k so that randomization length is slightly more than half of the input. The rate R∗ should be kept close to a constant. We suggest choosing a rate R∗ that is close to 0.8 due to information set decoding attacks [44].


## 7.2. Key Size

The key size ofAddHomSE is big if truly random matrices are used. In a practical setting, we want to use pseudorandom matrices for S and P. The key size is dramatically decreased by exchanging these matrices with a short seed c and generating S and P using a pseudorandom generator G. The generating matrix G of the Goppa code can be derived from the Goppa polynomial g(x) and pseudorandom elements generated by G. Therefore, in practice, the key can be compactly presented by the seed c and the polynomial g(x).Typically, in a distributed storage systems we want to encrypt files or file systems that are huge. If a large file is divided into few parts, we do not want to consider each part as a single plaintext message since such an approach would requirek∗ and n to be at least as large as the length of the file part. In such a case, we can further divide the part into smaller blocks and encrypt those block independently. Such an approach enables us to select small and efficient values for k∗ and n. Note that such a division does not affect the homomorphic property of the scheme provided that each of the file parts are processed similarly and encrypted with the same keys. It also does not have an effect on the key size since the keys of those individual blocks can be derived from the same seed c and the polynomial g(x).


## 7.3. Error Correction

Due to requirements of semantic security and error correction, ciphertexts contain overhead compared to plaintext messages. For example, withn,k∗,r=256,200,100, where the rate R∗≈0.78, plaintexts of length 100 will be encrypted into ciphertexts of length 256. The scheme can correct up to t errors, where t is the degree of the Goppa generator polynomial. With these parameters, we should choose t≥zmin=5 [47]. Choosing the smallest t, which results in the most efficient implementation, enables us to correct up to 5 errors in each 256 bits meaning that the plaintext messages are correctly decrypted with high probability whenever the error rate is less than 2%. If more error correction capacity is needed, then a higher degree Goppa generator polynomial needs to be selected and/or the rate R∗ should be lowered. As a final remark, we note that the binary Goppa code can be exchanged with another linear code on a finite field Fq. However, we have only shown the security of AddHomSE based on the indistinguishability of a scrambled Goppa generator matrices. The applied linear code has to satisfy a similar infeasibility result.


## 8. Conclusion

We propose an additively homomorphic symmetric encryption schemeAddHomSE that is compatible with linear network coding: a linear combination of ciphertext messages decrypts to the same linear combination of corresponding plaintext messages. The scheme can be used for the encryption of data stored in a distributed storage system (DSS), for example, in the distributed Internet of Things. We show that the scheme is semantically secure (IND-CPA) and provides computational indistinguishability for each individual part of the file stored in the DSS. In combination with an additively homomorphic MAC our scheme supports the authenticate- then-encrypt paradigm that ensures plaintext integrity. Finally, based on Goppa codes, our scheme offers simultaneous error correction. Our proofs are shown for the binary field F2 which is commonly used for the implementation of a DSS due to computational efficiency reasons. We also discuss the selection of secure parameters for the scheme and explain how it can be applied with compact keys.



---

*Source: 4321296-2017-06-22.xml*