# Symmetric Blind Decryption with Perfect Secrecy

Authors: Juha Partala
Journal: Journal of Computer Networks and Communications
 (2017)

---

## Abstract

A blind decryption scheme enables a user to query decryptions from a decryption server without revealing information about the plain-text message. Such schemes are useful, for example, for the implementation of privacy-preserving encrypted file storages and payment systems. In terms of functionality, blind decryption is close to oblivious transfer. For noiseless channels, information-theoretically secure oblivious transfer is impossible. However, in this paper, we show that this is not the case for blind decryption. We formulate a definition of perfect secrecy of symmetric blind decryption for the following setting: at most one of the scheme participants is a passive adversary (honest-but-curious). We also devise a symmetric blind decryption scheme based on modular arithmetic on a ringZp2, where p is a prime, and show that it satisfies our notion of perfect secrecy.


---

## Body

## 1. Introduction

Over the past 15 years, data has moved from local storage to centralized data warehouses in the cloud. The accessibility of large amounts of personal data through a public network has given rise to many security and privacy issues [1]. Fortunately, such issues have generally been taken seriously. For example, in many countries, ethical and legal requirements have been imposed on guaranteeing the confidentiality of medical records [2, 3]. However, the implementation of privacy technologies is nontrivial, especially if the data storage has been outsourced to a cloud operator. Sensitive information can often be inferred from simple access patterns either by outsiders or by the operator of the storage. For example, being able to observe a medical doctor to access the medical record of a patient can leak sensitive information. Therefore, such access patterns should be kept hidden both from outsiders and from the party that is administering the records. Oblivious databases [4] and privacy-preserving encrypted file systems [5] are examples of technologies that can be used to hide the access information from the administrator. For such systems, the decryption of data is typically handled by a central decryption server. Such systems can be conveniently implemented usingblind decryption schemes [6]. Blind decryption is a versatile primitive. It can be used as a building block for many privacy-critical applications, such as privacy-preserving payment systems [7], key escrow systems, oblivious transfer protocols [8], privacy-preserving systems for digital rights management [9, 10], and private information retrieval [11]. A blind decryption scheme consists of an encryption scheme together with a blind decryption protocol intended to decrypt messages in a privacy-preserving fashion. The meaning of “blind decryption” can be easily described based on the following scenario depicted in Figure 1. Suppose that Alice has obtained several encrypted messages from an encryptor. Alice is entitled to choose and decrypt exactly one of those messages. Suppose that the decryption key k is stored on a decryption server and Alice wishes to have the server decrypt the message for her in such a way that neither the encryptor nor the decryptor learns the message chosen by Alice.Figure 1
Blind decryption. Alice has obtainedL ciphertexts from an encryptor and is entitled to choose exactly one of those for decryption. Alice interacts with a decryptor that shares a key k with the encryptor to transform the ciphertext message ci into a plain-text message mi. Neither the encryptor nor the decryptor learns the plain-text message chosen by Alice.There are suggestions for practical blind decryption based on public-key cryptography [5, 6, 12–14]. It is also possible to implement the blind decryption functionality with other protocols such as secure multiparty computation [15]. However, the resulting schemes would be computationally demanding. For many applications, symmetric primitives are sufficient and computationally more efficient. In addition, they can provide secrecy that is not based on computational assumptions. Oblivious transfer schemes [16, 17] deliver the same functionality directly between the sender and the receiver without the decryption server. However, for noiseless channels, information-theoretically secure oblivious transfer is impossible [18]. In addition, blind decryption schemes do not seem to exist, such that the privacy of the user is based on information-theoretic security. Our work aims to fill this shortage. In this paper, we give a meaningful definition of perfect secrecy for the blind decryption scenario. In particular, we formulate perfect secrecy of symmetric blind decryption in a setting in which at most one of the participants is an adversary but adhering to the protocol (at most one of the participants is honest-but-curious). We also propose a symmetric key blind decryption scheme SymmetricBlind which satisfies our definition. The scheme is based on modular arithmetic on a ring Zp2, where p is a prime. Our main contribution is theoretical. Perfect secrecy requires the key to be changed for each decryption. Therefore, many existing applications of blind decryption which are built on the public-key case in the computational security model are not directly applicable. However, for the first time, we are able to give a meaningful definition of perfect secrecy of blind decryption and to show that blind decryption is possible in the information-theoretic security model. Additional research is needed to show which applications are possible in this model.The paper is organized as follows. In Section2, we describe work that is related to ours. Section 3 discusses the fundamental definitions and the preliminaries for the rest of the paper. In Section 4, we formulate three perfect secrecy properties that the blind decryption scheme needs to satisfy. In Section 5, we give a description of a symmetric blind decryption scheme SymmetricBlind. In Section 6, we show that the devised scheme satisfies our definition of perfect secrecy. Finally, Section 7 considers future work and Section 8 provides the conclusion.


## 2. Related Work

Chaum was the first to consider blindness in the context of digital signatures and privacy-preserving payment systems [7]. He described the first public-key blind signature scheme [19] by utilizing the properties of RSA encryption [20]. The scheme can be also used for encryption and can be therefore considered as the first blind decryption scheme. In the early articles, blind decryption is referred to as “blind decoding.” Discrete logarithm based blind signature schemes were suggested in [21–24]. Sakurai and Yamane were the first to consider public-key blind decryption based on the discrete logarithm problem [6]. Their method was based on ElGamal Cryptosystem [25] and related to the blind signature of Camenisch et al. [24]. The method was later applied for the implementation of a key escrow system [12]. Mambo et al. were the first to consider blind decryption that is secure against chosen plain-text attacks by signing the ciphertext messages [26]. The resulting scheme is not capable of public-key encryption, since a secret signing key is required. Green described the first public-key blind decryption scheme [5] that is secure against adaptive chosen ciphertext attacks (IND-CCA2) using bilinear groups. The security of these constructions has been considered computationally either in the random oracle model [11] or using computational indistinguishability and infeasibility assumptions [5].Oblivious transfer protocols are symmetric primitives that offer functionality similar to blind decryption. For oblivious transfer, there are two participants: a sender and a receiver. For the original definition of oblivious transfer, the sender transmits a message which the receiver gets with probability 1/2. The sender remains oblivious as to whether the receiver actually got the message. This form of oblivious transfer was introduced by Rabin [16]. The concept was later extended by Even et al. [17]. For 21-oblivious transfer, the receiver can choose one from two messages without the sender knowing which of the messages was chosen. A related concept that can be considered as a further generalization isall-or-nothing disclosure of secrets [27] for which Alice is willing to disclose at most one secret from a set to Bob without Bob learning information about the rest of the secrets. Alice must not learn which secret Bob chose. Adaptive queries were considered by Naor and Pinkas [28]. They also considered active adversaries and provided security definitions related to the simulatability of the receivers. Camenisch, Neven, and Shelat extended the work of Naor and Pinkas by definingsimulatable oblivious transfer [29] and providing practical constructions for such a scheme. There are other suggestions for oblivious transfer based on problems in bilinear groups [30], groups of composite order [31], and the Diffie-Hellman problem [32–37]. These schemes are based on computational assumptions. It is impossible to achieve information-theoretic security for both of the parties using noiseless channels [18]. However, it is possible using noisy channels such as discrete memoryless channels [38] or a trusted initializer (shown by Rivest in 1999; see “unconditionally secure commitment and oblivious transfer schemes using private channels and a trusted initializer”). For the computational security setting, the functionality of oblivious transfer can be also implemented with public-key blind decryption using the method of Dodis et al. [39].Generalmultiparty computation protocols can be also applied to implement blind decryption capabilities. Secure multiparty computation was originally introduced by Yao [40] for the two-party case. The general case for n≥2 is due to Goldreich et al. [41]. However, secure multiparty computation protocols are computationally intensive in comparison to blind decryption and oblivious transfer.


## 3. Preliminaries

### 3.1. Notation

For the set of integers modulon, we denote Zn={[0],[1],…,[n-1]} and equate a congruence class with its least nonnegative representative. That is, we consider Zn={0,1,…,n-1}. By the notation xmod⁡n we mean the unique i∈{0,1,…,n-1} such that i≡x(mod⁡n). We denote the uniform distribution on a set X by U(X). If a random variable Z is uniformly distributed on a set X, we denote it by Z~U(X). When an element x is sampled from U(X), we denote it by x←U(X).


### 3.2. Symmetric Encryption

A symmetric encryption schemeSE=(Gen,Enc,Dec) with key space K, plain-text space M, and ciphertext space C consists of three algorithms:(1)
The key generation algorithmGen(s): on inputting a security parameter s, Gen outputs a key k∈K(2)
The encryption algorithmEnc(k,m): on inputting a key k∈K and a message m∈M, Enc outputs a ciphertext c∈C(3)
The decryption algorithmDec(k,m): on inputting a key k∈K and a ciphertext c∈C, Dec outputs a message m∈M such that m=Dec(k,Enc(k,m))


### 3.3. Blind Decryption

Blind decryption has been considered in the literature for the asymmetric case. However, in this paper, we are interested in the symmetric case that is easily adapted from the asymmetric one [5]. A symmetric blind decryption scheme BlindDecyption consists of a symmetric encryption scheme SE=(Gen,Enc,Dec) and a two-party protocol BlindDec. The protocol BlindDec is conducted between an honest user Alice and the decryption server which we shall call the decryptor. The protocol enables Alice, who is in possession of a ciphertext c, to finish the protocol with the correct decryption of c. As a result of running BlindDec, Alice on inputting a ciphertext c=Enc(k,m)∈C outputs either the message m∈M or an error message ⊥. The decryptor, on inputting the key k∈K, outputs nothing or an error message ⊥. To be secure, the exchanged messages must not leak information to malicious users (theleak-freeness property [8]). The property can be formalized based on computational indistinguishability. For every adversary, there has to be a simulator so that the following two games are well defined. For the first game, a probabilistic polynomial time (PPT) adversary A can choose any number L of ciphertexts ci for i∈{1,2,…,L}. It is then given the correct decryptions by executing BlindDec with the decryptor. Finally, A outputs the plain-text message and ciphertext pairs (mi,ci) for i∈{1,2,…,L}. For the second game, a simulator S chooses any number L of ciphertexts ci for i∈{1,2,…,L}. In this game, the plain-text messages are obtained by querying a trusted party. BlindDecyption isleak-free if for every PPT adversary A there is a simulator S such that for every PPT distinguisher D the probability of distinguishing between these two games is negligible [5].Another important property for secure blind decryption is theblindness property. It formalizes the idea that the decryptor must not learn anything about the actual plain-text message. This can be formalized by giving a PPT algorithm D the possibility to choose two ciphertexts c1,c2 and giving it oracle access to two instances of BlindDec based on these choices. If the probability of distinguishing these two instances is negligible for every PPT algorithm D, then BlindDecyption satisfiesciphertext blindness. For a formal and rigorous definition, see, for example, [5].


### 3.4. Perfect Secrecy

The notion of perfect secrecy is due to Shannon [42]. Let SE=(Gen,Enc,Dec) be an encryption scheme with key space K, plain-text space M, and ciphertext space C. Let K denote a random variable on the key space induced by Gen. SE satisfies perfect secrecy if, for every random variable M on the plain-text space, every plain-text m∈M, and every ciphertext c∈C,(1)Pr⁡M=m∣c=EncK,M=Pr⁡M=m.Equivalently, SE satisfies perfect secrecy if and only if, for every random variable M on the plain-text space, every plain-text messages m1,m2∈M, and every ciphertext c∈C,(2)Pr⁡c=EncK,M∣M=m1=Pr⁡c=EncK,M∣M=m2.


## 3.1. Notation

For the set of integers modulon, we denote Zn={[0],[1],…,[n-1]} and equate a congruence class with its least nonnegative representative. That is, we consider Zn={0,1,…,n-1}. By the notation xmod⁡n we mean the unique i∈{0,1,…,n-1} such that i≡x(mod⁡n). We denote the uniform distribution on a set X by U(X). If a random variable Z is uniformly distributed on a set X, we denote it by Z~U(X). When an element x is sampled from U(X), we denote it by x←U(X).


## 3.2. Symmetric Encryption

A symmetric encryption schemeSE=(Gen,Enc,Dec) with key space K, plain-text space M, and ciphertext space C consists of three algorithms:(1)
The key generation algorithmGen(s): on inputting a security parameter s, Gen outputs a key k∈K(2)
The encryption algorithmEnc(k,m): on inputting a key k∈K and a message m∈M, Enc outputs a ciphertext c∈C(3)
The decryption algorithmDec(k,m): on inputting a key k∈K and a ciphertext c∈C, Dec outputs a message m∈M such that m=Dec(k,Enc(k,m))


## 3.3. Blind Decryption

Blind decryption has been considered in the literature for the asymmetric case. However, in this paper, we are interested in the symmetric case that is easily adapted from the asymmetric one [5]. A symmetric blind decryption scheme BlindDecyption consists of a symmetric encryption scheme SE=(Gen,Enc,Dec) and a two-party protocol BlindDec. The protocol BlindDec is conducted between an honest user Alice and the decryption server which we shall call the decryptor. The protocol enables Alice, who is in possession of a ciphertext c, to finish the protocol with the correct decryption of c. As a result of running BlindDec, Alice on inputting a ciphertext c=Enc(k,m)∈C outputs either the message m∈M or an error message ⊥. The decryptor, on inputting the key k∈K, outputs nothing or an error message ⊥. To be secure, the exchanged messages must not leak information to malicious users (theleak-freeness property [8]). The property can be formalized based on computational indistinguishability. For every adversary, there has to be a simulator so that the following two games are well defined. For the first game, a probabilistic polynomial time (PPT) adversary A can choose any number L of ciphertexts ci for i∈{1,2,…,L}. It is then given the correct decryptions by executing BlindDec with the decryptor. Finally, A outputs the plain-text message and ciphertext pairs (mi,ci) for i∈{1,2,…,L}. For the second game, a simulator S chooses any number L of ciphertexts ci for i∈{1,2,…,L}. In this game, the plain-text messages are obtained by querying a trusted party. BlindDecyption isleak-free if for every PPT adversary A there is a simulator S such that for every PPT distinguisher D the probability of distinguishing between these two games is negligible [5].Another important property for secure blind decryption is theblindness property. It formalizes the idea that the decryptor must not learn anything about the actual plain-text message. This can be formalized by giving a PPT algorithm D the possibility to choose two ciphertexts c1,c2 and giving it oracle access to two instances of BlindDec based on these choices. If the probability of distinguishing these two instances is negligible for every PPT algorithm D, then BlindDecyption satisfiesciphertext blindness. For a formal and rigorous definition, see, for example, [5].


## 3.4. Perfect Secrecy

The notion of perfect secrecy is due to Shannon [42]. Let SE=(Gen,Enc,Dec) be an encryption scheme with key space K, plain-text space M, and ciphertext space C. Let K denote a random variable on the key space induced by Gen. SE satisfies perfect secrecy if, for every random variable M on the plain-text space, every plain-text m∈M, and every ciphertext c∈C,(1)Pr⁡M=m∣c=EncK,M=Pr⁡M=m.Equivalently, SE satisfies perfect secrecy if and only if, for every random variable M on the plain-text space, every plain-text messages m1,m2∈M, and every ciphertext c∈C,(2)Pr⁡c=EncK,M∣M=m1=Pr⁡c=EncK,M∣M=m2.


## 4. Perfect Secrecy for Symmetric Blind Decryption

In this section, we formulate a condition for the perfect secrecy of blind decryption. Instead of computational indistinguishability, we consider secrecy of symmetric blind decryption based on the information observed by the parties. In the following, letSE=(Gen,Enc,Dec) together with BlindDec be a symmetric blind decryption scheme with key space K, plain-text space M, and ciphertext space C.


### 4.1. The Scenario

For the sake of clarity, we do not consider active adversaries. We assume that the parties adhere to the blind decryption protocol and only observe the flow of messages (and possibly deduce information from those messages). Active adversaries could, for example, induce errors to the protocol messages. Such adversarial scenarios are left for future work. In addition, we do not consider the case where the decryptor is colluding with either Alice or the encryptor against the other. Such a case is equivalent to the oblivious transfer scenario and information-theoretic security is impossible for noiseless channels [18]. However, we note that such collusion scenarios are important for certain applications and need to be investigated in the future. We do consider the case where the adversary is impersonating one of the parties, which is a paramount requirement for many applications. For clarity, we also restrict ourselves to the case where Alice decrypts a single message m∈M. Similar to the one-time pad, we assume that a new key is derived after every decryption. However, in our case, there could be several ciphertexts c1,c2,…,cL encrypted under the same key. Nevertheless, once Alice has decrypted one of the messages, we consider that particular key used and a new key, and a new set of ciphertexts is generated.The scenario is the following. The encryptor chooses a set ofL plain-text messages mi for i∈{1,2,…,L}. He encrypts those messages under a key k to obtain ciphertext messages cj=Enc(k,mj) for j∈{1,2,…,L} that he transmits to Alice. Alice chooses one of those messages ci. To hide the actual ciphertext ci, we assume that there is a ciphertext transformation space C′⊆C so that Alice can derive a related ciphertext message ci′∈C′ that she transmits to the decryptor. The decryptor responds with its decryption mi′∈M which Alice transforms to the correct plain-text message mi. The general scenario has been depicted in Figure 2. The used variables have been collected into Notations for easier reference.Figure 2
The general blind decryption scenario. Alice chooses a ciphertextci and derives a related ciphertext ci′ that she transmits to the decryptor. The decryptor responds with the corresponding plain-text message mi′ from which Alice can recover mi.


### 4.2. Security Requirements

As described in Section3.2, the scheme has to satisfy the following property.


#### 4.2.1. Leak-Freeness

Outsiders must not learn information about the plain-text messages by observing the exchanges.The easiest way to provide leak-freeness against outsiders is to protect each exchange with an encryption scheme that satisfies perfect secrecy. However, leakage also needs to be addressed considering the protocol participants. Considering each individual party, we can divide leak-freeness as follows.(1) Leak-Freeness against the Encryptor. Honest-but-curious encryptor must not learn information about the plain-text message obtained by Alice at the end of the protocol by observing the blind decryption messages. The situation is depicted in Figure 3.Figure 3
Malicious encryptor. The adversary attempts to learn which message was chosen by Alice.(2) Leak-Freeness against Alice. This property ensures that, after obtaining mi, Alice does not learn information about the remaining L-1 plain texts mj for j≠i. The situation is depicted in Figure 4.Figure 4
Malicious Alice. The adversary attempts to decrypt additional messages.In contrast to computational security, we cannot define leak-freeness as a distinguishing problem. Instead, we shall consider the probability distributions regarding the exchanged elements. We also want to prevent decryptor from deducing information about the plain-text messagemi.


#### 4.2.2. Blindness against the Decryptor

This property ensures that an honest-but-curious decryption server does not learn the message Alice wants to decrypt. The situation is depicted in Figure5.Figure 5
Malicious decryptor. The adversary attempts to learn the plain-text message that Alice obtains.In the computational security setting, there can be multiple applications of the blind decryption protocol for a fixed key. In our case, we want a fresh key for every decryption to achieve perfect secrecy. Therefore, we formulate leak-freeness and blindness for a single decryption. However, as was described before, we want to be able to encrypt multiple messages with the same key. For example, in privacy-preserving payment systems, blind decryption is used to enable Alice to choose one (only one) item from a selection of items. This results in a scenario in which there areL plain-text and ciphertext pairs (mj,cj) for j∈{1,2,…,L} but there is only a single application of BlindDec.In the following section, we formulate these conditions based on information. Note that these conditions also provide secrecy against observers that are not participants of the scheme, since the information possessed by such observers is a proper subset of that of any of the participants. The following notation is used. LetK denote the random variable of blind decryption keys on the key space K induced by Gen. Let Mj for j∈{1,2,…,L} denote the random variables corresponding to the choice of mi for j∈{1,2,…,L} by the encryptor and let M denote the random variable corresponding to the plain-text m Alice obtains at the end of the scheme. Following the standard practice [43], we assume that K is independent of M and Mj for every j∈{1,2,…,L}. Let C′ denote the random variable on the ciphertext transformation space C′ for the ciphertext message c′ that Alice discloses to the decryptor. Finally, let M′ denote the random variable corresponding to the message m′ that the decryptor responds with. These variables have been collected into Notations.


### 4.3. Perfect Leak-Freeness against the Encryptor

We shall first formulate leak-freeness against the encryptor. The blind decryption protocol messagesc′ and m′ should not disclose any information about mi to the encryptor. Equivalently, the messages should not leak information about i that was chosen by Alice even if the encryptor knows the key k and the right plain-text messages mj for j∈{1,2,…,L}.Definition 1 (perfect leak-freeness against encryptor).
A symmetric blind decryption scheme isperfectly leak-free against the encryptor for a single decryption of a maximum of L messages if, for every random variable M,Mj for j∈{1,2,…,L} on the plain-text space and every m,m′,mj∈M for j∈{1,2,…,L} and every c′∈C′,(3)Pr⁡M=m∣C′=c′,M′=m′,M1=m1,…,ML=mL=Pr⁡M=m∣M1=m1,…,ML=mL.Our definition states that an honest-but-curious encryptor can equally easily guess the plain-text message Alice wanted to be decrypted with or without information provided by the blind decryption protocol messages c′ and m′. Note that, in the normal scenario, M=Mi for some i∈{1,2,…,L}. However, we do not want to restrict the definition to such a case. For example, there could be homomorphic blind decryption schemes for which certain operations could be permitted on the ciphertexts. Note also that the encryptor inherently possesses more information about m than an outsider, since m is dependent on m1,m2,…,mL.


### 4.4. Perfect Leak-Freeness against Alice

In order to be practical, the scheme needs to ensure that Alice is not able to decrypt messages. Therefore, we need to ensure that Alice obtains neither the decryption key nor any information about the decryptions ofc1,c2,…,cL without interacting with the decryptor. In addition, after a single application of BlindDec, Alice must not have any information about the remaining L-1 messages. To make the requirement precise, we require that the observation of a single plain-text and ciphertext pair (m1,c1) does not leak any information about the decryption of another ciphertext c2. The property is, in fact, a property of the encryption scheme.Definition 2 (perfect leak-freeness against Alice).
A symmetric encryption schemeSE satisfiesperfect leak-freeness against Alice for a single decryption if, for every random variable M1,M2 on the plain-text space, every m1,m2,m∈M, and every c1,c2∈C, such that c1≠c2,(4)Pr⁡c1=EncK,M1,c2=EncK,M2∣M1=m1,M2=m2=Pr⁡c1=EncK,M1,c2=EncK,M2∣M1=m1,M2=m.The condition states that the probability of obtaining the ciphertext pair (c1,c2) is the same whether we encrypt (m1,m2) or (m1,m). That is, observation of the ciphertexts c1,c2 does not yield information about the decryption of c2 even if we know the decryption of c1.


### 4.5. Perfect Blindness against the Decryptor

We still need to consider privacy against an honest-but-curious decryptor. It is reasonable to assume thatc1,c2,…,cL have been delivered to Alice using a private channel. If the decryptor can observe cj for j∈{1,2,…,L}, it means that he knows the corresponding plain-text messages, since he is in possession of the blind decryption key. Therefore, it is natural to require that the ciphertexts be protected by a separate secure channel between Alice and the encryptor. For the blindness property, we want the server to learn nothing of the actual message m that Alice derives at the end of the blind decryption scheme. In this case, the decryptor knows the correct key k as well as the messages c′ and m′ exchanged with Alice.Definition 3 (perfect ciphertext blindness against the decryptor).
A symmetric blind decryption scheme satisfiesperfect ciphertext blindness against the decryptor if, for every random variable M on the plain-text space, every m,m′∈M, and every c′∈C′(5)Pr⁡M=m∣C′=c′,M′=m′=Pr⁡M=m.The condition states that it is equally easy to guess the correct plain-text message with and without the information possessed by the decryptor. Note that we have assumed that c1,c1,…,cL have been delivered to Alice in perfect secrecy.


### 4.6. Perfect Secrecy for Symmetric Blind Decryption

Finally, we can state our definition of perfect secrecy based on the properties defined above.Definition 4 (perfect secrecy of blind decryption).
A symmetric blind decryption scheme consisting of a symmetric encryption schemeSE and a blind decryption protocol BlindDec satisfies perfect secrecy for symmetric blind decryption for a single decryption of a maximum of L messages against a single honest-but-curious party if the scheme is perfectly leak-free against the encryptor for a maximum of L messages, SE is leak-free against Alice, and the scheme satisfies perfect ciphertext blindness against the decryptor.


## 4.1. The Scenario

For the sake of clarity, we do not consider active adversaries. We assume that the parties adhere to the blind decryption protocol and only observe the flow of messages (and possibly deduce information from those messages). Active adversaries could, for example, induce errors to the protocol messages. Such adversarial scenarios are left for future work. In addition, we do not consider the case where the decryptor is colluding with either Alice or the encryptor against the other. Such a case is equivalent to the oblivious transfer scenario and information-theoretic security is impossible for noiseless channels [18]. However, we note that such collusion scenarios are important for certain applications and need to be investigated in the future. We do consider the case where the adversary is impersonating one of the parties, which is a paramount requirement for many applications. For clarity, we also restrict ourselves to the case where Alice decrypts a single message m∈M. Similar to the one-time pad, we assume that a new key is derived after every decryption. However, in our case, there could be several ciphertexts c1,c2,…,cL encrypted under the same key. Nevertheless, once Alice has decrypted one of the messages, we consider that particular key used and a new key, and a new set of ciphertexts is generated.The scenario is the following. The encryptor chooses a set ofL plain-text messages mi for i∈{1,2,…,L}. He encrypts those messages under a key k to obtain ciphertext messages cj=Enc(k,mj) for j∈{1,2,…,L} that he transmits to Alice. Alice chooses one of those messages ci. To hide the actual ciphertext ci, we assume that there is a ciphertext transformation space C′⊆C so that Alice can derive a related ciphertext message ci′∈C′ that she transmits to the decryptor. The decryptor responds with its decryption mi′∈M which Alice transforms to the correct plain-text message mi. The general scenario has been depicted in Figure 2. The used variables have been collected into Notations for easier reference.Figure 2
The general blind decryption scenario. Alice chooses a ciphertextci and derives a related ciphertext ci′ that she transmits to the decryptor. The decryptor responds with the corresponding plain-text message mi′ from which Alice can recover mi.


## 4.2. Security Requirements

As described in Section3.2, the scheme has to satisfy the following property.


### 4.2.1. Leak-Freeness

Outsiders must not learn information about the plain-text messages by observing the exchanges.The easiest way to provide leak-freeness against outsiders is to protect each exchange with an encryption scheme that satisfies perfect secrecy. However, leakage also needs to be addressed considering the protocol participants. Considering each individual party, we can divide leak-freeness as follows.(1) Leak-Freeness against the Encryptor. Honest-but-curious encryptor must not learn information about the plain-text message obtained by Alice at the end of the protocol by observing the blind decryption messages. The situation is depicted in Figure 3.Figure 3
Malicious encryptor. The adversary attempts to learn which message was chosen by Alice.(2) Leak-Freeness against Alice. This property ensures that, after obtaining mi, Alice does not learn information about the remaining L-1 plain texts mj for j≠i. The situation is depicted in Figure 4.Figure 4
Malicious Alice. The adversary attempts to decrypt additional messages.In contrast to computational security, we cannot define leak-freeness as a distinguishing problem. Instead, we shall consider the probability distributions regarding the exchanged elements. We also want to prevent decryptor from deducing information about the plain-text messagemi.


### 4.2.2. Blindness against the Decryptor

This property ensures that an honest-but-curious decryption server does not learn the message Alice wants to decrypt. The situation is depicted in Figure5.Figure 5
Malicious decryptor. The adversary attempts to learn the plain-text message that Alice obtains.In the computational security setting, there can be multiple applications of the blind decryption protocol for a fixed key. In our case, we want a fresh key for every decryption to achieve perfect secrecy. Therefore, we formulate leak-freeness and blindness for a single decryption. However, as was described before, we want to be able to encrypt multiple messages with the same key. For example, in privacy-preserving payment systems, blind decryption is used to enable Alice to choose one (only one) item from a selection of items. This results in a scenario in which there areL plain-text and ciphertext pairs (mj,cj) for j∈{1,2,…,L} but there is only a single application of BlindDec.In the following section, we formulate these conditions based on information. Note that these conditions also provide secrecy against observers that are not participants of the scheme, since the information possessed by such observers is a proper subset of that of any of the participants. The following notation is used. LetK denote the random variable of blind decryption keys on the key space K induced by Gen. Let Mj for j∈{1,2,…,L} denote the random variables corresponding to the choice of mi for j∈{1,2,…,L} by the encryptor and let M denote the random variable corresponding to the plain-text m Alice obtains at the end of the scheme. Following the standard practice [43], we assume that K is independent of M and Mj for every j∈{1,2,…,L}. Let C′ denote the random variable on the ciphertext transformation space C′ for the ciphertext message c′ that Alice discloses to the decryptor. Finally, let M′ denote the random variable corresponding to the message m′ that the decryptor responds with. These variables have been collected into Notations.


## 4.2.1. Leak-Freeness

Outsiders must not learn information about the plain-text messages by observing the exchanges.The easiest way to provide leak-freeness against outsiders is to protect each exchange with an encryption scheme that satisfies perfect secrecy. However, leakage also needs to be addressed considering the protocol participants. Considering each individual party, we can divide leak-freeness as follows.(1) Leak-Freeness against the Encryptor. Honest-but-curious encryptor must not learn information about the plain-text message obtained by Alice at the end of the protocol by observing the blind decryption messages. The situation is depicted in Figure 3.Figure 3
Malicious encryptor. The adversary attempts to learn which message was chosen by Alice.(2) Leak-Freeness against Alice. This property ensures that, after obtaining mi, Alice does not learn information about the remaining L-1 plain texts mj for j≠i. The situation is depicted in Figure 4.Figure 4
Malicious Alice. The adversary attempts to decrypt additional messages.In contrast to computational security, we cannot define leak-freeness as a distinguishing problem. Instead, we shall consider the probability distributions regarding the exchanged elements. We also want to prevent decryptor from deducing information about the plain-text messagemi.


## 4.2.2. Blindness against the Decryptor

This property ensures that an honest-but-curious decryption server does not learn the message Alice wants to decrypt. The situation is depicted in Figure5.Figure 5
Malicious decryptor. The adversary attempts to learn the plain-text message that Alice obtains.In the computational security setting, there can be multiple applications of the blind decryption protocol for a fixed key. In our case, we want a fresh key for every decryption to achieve perfect secrecy. Therefore, we formulate leak-freeness and blindness for a single decryption. However, as was described before, we want to be able to encrypt multiple messages with the same key. For example, in privacy-preserving payment systems, blind decryption is used to enable Alice to choose one (only one) item from a selection of items. This results in a scenario in which there areL plain-text and ciphertext pairs (mj,cj) for j∈{1,2,…,L} but there is only a single application of BlindDec.In the following section, we formulate these conditions based on information. Note that these conditions also provide secrecy against observers that are not participants of the scheme, since the information possessed by such observers is a proper subset of that of any of the participants. The following notation is used. LetK denote the random variable of blind decryption keys on the key space K induced by Gen. Let Mj for j∈{1,2,…,L} denote the random variables corresponding to the choice of mi for j∈{1,2,…,L} by the encryptor and let M denote the random variable corresponding to the plain-text m Alice obtains at the end of the scheme. Following the standard practice [43], we assume that K is independent of M and Mj for every j∈{1,2,…,L}. Let C′ denote the random variable on the ciphertext transformation space C′ for the ciphertext message c′ that Alice discloses to the decryptor. Finally, let M′ denote the random variable corresponding to the message m′ that the decryptor responds with. These variables have been collected into Notations.


## 4.3. Perfect Leak-Freeness against the Encryptor

We shall first formulate leak-freeness against the encryptor. The blind decryption protocol messagesc′ and m′ should not disclose any information about mi to the encryptor. Equivalently, the messages should not leak information about i that was chosen by Alice even if the encryptor knows the key k and the right plain-text messages mj for j∈{1,2,…,L}.Definition 1 (perfect leak-freeness against encryptor).
A symmetric blind decryption scheme isperfectly leak-free against the encryptor for a single decryption of a maximum of L messages if, for every random variable M,Mj for j∈{1,2,…,L} on the plain-text space and every m,m′,mj∈M for j∈{1,2,…,L} and every c′∈C′,(3)Pr⁡M=m∣C′=c′,M′=m′,M1=m1,…,ML=mL=Pr⁡M=m∣M1=m1,…,ML=mL.Our definition states that an honest-but-curious encryptor can equally easily guess the plain-text message Alice wanted to be decrypted with or without information provided by the blind decryption protocol messages c′ and m′. Note that, in the normal scenario, M=Mi for some i∈{1,2,…,L}. However, we do not want to restrict the definition to such a case. For example, there could be homomorphic blind decryption schemes for which certain operations could be permitted on the ciphertexts. Note also that the encryptor inherently possesses more information about m than an outsider, since m is dependent on m1,m2,…,mL.


## 4.4. Perfect Leak-Freeness against Alice

In order to be practical, the scheme needs to ensure that Alice is not able to decrypt messages. Therefore, we need to ensure that Alice obtains neither the decryption key nor any information about the decryptions ofc1,c2,…,cL without interacting with the decryptor. In addition, after a single application of BlindDec, Alice must not have any information about the remaining L-1 messages. To make the requirement precise, we require that the observation of a single plain-text and ciphertext pair (m1,c1) does not leak any information about the decryption of another ciphertext c2. The property is, in fact, a property of the encryption scheme.Definition 2 (perfect leak-freeness against Alice).
A symmetric encryption schemeSE satisfiesperfect leak-freeness against Alice for a single decryption if, for every random variable M1,M2 on the plain-text space, every m1,m2,m∈M, and every c1,c2∈C, such that c1≠c2,(4)Pr⁡c1=EncK,M1,c2=EncK,M2∣M1=m1,M2=m2=Pr⁡c1=EncK,M1,c2=EncK,M2∣M1=m1,M2=m.The condition states that the probability of obtaining the ciphertext pair (c1,c2) is the same whether we encrypt (m1,m2) or (m1,m). That is, observation of the ciphertexts c1,c2 does not yield information about the decryption of c2 even if we know the decryption of c1.


## 4.5. Perfect Blindness against the Decryptor

We still need to consider privacy against an honest-but-curious decryptor. It is reasonable to assume thatc1,c2,…,cL have been delivered to Alice using a private channel. If the decryptor can observe cj for j∈{1,2,…,L}, it means that he knows the corresponding plain-text messages, since he is in possession of the blind decryption key. Therefore, it is natural to require that the ciphertexts be protected by a separate secure channel between Alice and the encryptor. For the blindness property, we want the server to learn nothing of the actual message m that Alice derives at the end of the blind decryption scheme. In this case, the decryptor knows the correct key k as well as the messages c′ and m′ exchanged with Alice.Definition 3 (perfect ciphertext blindness against the decryptor).
A symmetric blind decryption scheme satisfiesperfect ciphertext blindness against the decryptor if, for every random variable M on the plain-text space, every m,m′∈M, and every c′∈C′(5)Pr⁡M=m∣C′=c′,M′=m′=Pr⁡M=m.The condition states that it is equally easy to guess the correct plain-text message with and without the information possessed by the decryptor. Note that we have assumed that c1,c1,…,cL have been delivered to Alice in perfect secrecy.


## 4.6. Perfect Secrecy for Symmetric Blind Decryption

Finally, we can state our definition of perfect secrecy based on the properties defined above.Definition 4 (perfect secrecy of blind decryption).
A symmetric blind decryption scheme consisting of a symmetric encryption schemeSE and a blind decryption protocol BlindDec satisfies perfect secrecy for symmetric blind decryption for a single decryption of a maximum of L messages against a single honest-but-curious party if the scheme is perfectly leak-free against the encryptor for a maximum of L messages, SE is leak-free against Alice, and the scheme satisfies perfect ciphertext blindness against the decryptor.


## 5. A Concrete Blind Decryption Scheme

We shall now devise a blind decryption schemeSymmetricBlind that satisfies Definition 4. We shall implement our scheme using two tiers of symmetric encryption. For the outer tier, we apply a scheme that satisfies ordinary perfect secrecy. Let that scheme be denoted by SE. The outer encryption scheme will hide information about c1,c2,…,cL from the decryptor and also provide secrecy for c′ and m′ against the encryptor. To achieve perfect blindness and leak-freeness against Alice, we design an inner tier encryption scheme called 2PAD that satisfies a useful transformation property which enables us to construct a blind decryption protocol BlindDec. To sum up, our final construction will consist of two tiers of encryption and a protocol for Alice to query a single decryption from the decryptor. The general overview of the scheme is depicted in Figure 6. It would be possible to implement some of the required privacy properties with multiple applications of the one-time pad. For example, if ci=mi⊕ki, Alice could hide the plain-text message from the decryptor by querying for the decryption of ci′=ci⊕k′, where k′ is only known to Alice. The correct plain-text message would be obtained from mi′=ci′⊕ki=ci⊕k′⊕ki by computing mi′⊕k′=ci⊕ki=mi. However, such a protocol would leak i to the decryptor, since i would be needed for decryption. In addition, for a single decryption, the decryptor would have to maintain a set of L keys which would quickly grow to an unmanageable size as L grows. In contrast, the optimal key size for single decryption would be 2mi, where mi is the bit length of mi, assuming that each plain-text message is of the same bit length. Therefore, simply applying the one-time pad is not sufficient.Figure 6
General overview ofSymmetricBlind. Two tiers of encryption are applied. The outer tier (SE) satisfies ordinary perfect secrecy. The inner tier (2PAD) provides perfect leak-freeness against Alice and has a transformation property enabling perfect blindness against the decryptor.In the following, we first describe our inner encryption scheme2PAD that will provide perfect leak-freeness against Alice, as well as the required message transformation property. Then, we proceed to the description of a blind decryption protocol utilizing this scheme. Finally, we combine the inner encryption scheme with an outer encryption scheme that satisfies ordinary perfect secrecy and describe the complete blind decryption scheme.


### 5.1. The Inner Encryption Scheme

We shall first construct an inner encryption scheme called2PAD with some useful properties. Our inner scheme is based on modular arithmetic on the ring Zp2, where p≥5 is a prime. Our plain-text space is Zp and every m∈Zp is mapped to the ciphertext space Zp2. To satisfy Definition 2, we want to add an amount of randomness that is at least twice the binary length of m in the encryption operation. Therefore, the keys of 2PAD will consist of pairs (xk,yk)∈Zp×Zp. Let b∈Zp2. Then,(6)b≡pz′+z′′mod⁡p2,where z′,z′′∈Zp. Therefore, we can essentially represent b with two elements of Zp. Using such a representation, we encrypt a single message m∈Zp by first sampling a random element z←U(Zp∖{0}) and setting b≔(pm+z)mod⁡p2. Then, we add the key (xk,yk) by computing(7)c≔pxkb2+pykb+bmod⁡p2=pxkz2+pykz+pm+zwhich is the ciphertext message. To enable blinding, Alice needs to be able to transform c into another ciphertext c′. The encryption operation entails such a transformation property that follows from the congruence(8)pxkb′2+pykb′+b′≡pxkb2+pykb+b′mod⁡p2for every xk,yk∈Zp and b,b′∈Zp2 such that b≡b′(mod⁡p). Let m1 be a plain text and let c1=pxkb2+pykb+b be its encryption with b=(pm1+z)mod⁡p2. Let c2 now be any ciphertext under the same key (xk,yk) such that c2≡c1≡z(mod⁡p) and let m2 be the corresponding plain text. Since c2≡c1≡z(mod⁡p), we have c2=pxkb′2+pykb′+b′, where b′=(pm2+z)mod⁡p2. Now, by (8),(9)c2≡pxkb′2+pykb′+b′≡pxkb2+pykb+b′≡c1-b+b′mod⁡p2,from which(10)c2≡c1-pm1+pm2mod⁡p2,which enables us to compute m2 using c2,m1,c1 without the key (xk,yk). Namely, if we know a plain text m1 and its encryption c1=pxkz2+pykz+pm1+z, we know the decryption m2 of c2 for every c2≡c1(mod⁡p). The plain text m2 can be computed by the transformation algorithm Map  in Algorithm 1.Algorithm 1
(
1
)  procedure  Mapc1,m1,c2
(
2
)    If c1≢c2(mod⁡p) output ⊥
(
3
)    m2≔((c2-c1+pm1)/p)mod⁡p
(
4
)    output  m2
(
5
)  end procedureLetz≡c1≡c2(mod⁡p). The algorithm works because(11)c2-c1+pm1p=pxkz2+pykz+pm2+z-pxkz2-pykz-pm1-z+pm1p=pm2p=m2.In order to query the decryptor, Alice can transform a ciphertext c into any c′ such that c′≡c(mod⁡p). The Map algorithm can transform the corresponding plain text m′ to the decryption m of c.Decryption is straightforward knowing the key(xk,yy). Its operation, as well as the complete encryption scheme, is described below.Definition 5 (2PAD).
The symmetric encryption scheme(12)2PAD=Gen2PAD,Enc2PAD,Dec2PADconsists of Algorithms 2, 3, and 4.Algorithm 2
(
1
)  procedure  Gen2PADs⊳s determines the size for the plaintext space
(
2
)    Choose a public prime p such that p≥5 and p≥2s
(
3
)    xk←U(Zp)
(
4
)    yk←U(Zp)
(
5
)    output  (xk,yk)
(
6
)  end procedureAlgorithm 3
(
1
)  procedure  Enc2PADxk,yk,m⊳ Input consists of a key (xk,yk) and a message m∈Zp
(
2
)    z←U(Zp∖{0})
(
3
)    b≔(pm+z)mod⁡p2
(
4
)    c≔(pxkb2+pykb+b)mod⁡p2
(
5
)    output  c
(
6
)  end procedureAlgorithm 4
(
1
)  procedure  Dec2PADxk,yk,c⊳ Input consists of a key (xk,yk) and a ciphertext c∈Zp2
(
2
)    z≔cmod⁡p
(
3
)    t≔(p(-xk)z2+p(-yk)z+c)mod⁡p2
(
4
)    m≔((t-z)/p)mod⁡p
(
5
)    output  m
(
6
)  end procedureThe plain-text and ciphertext spaces of2PAD depend on the chosen prime p; the plain-text space is Zp, while the ciphertext space is Zp2. Let us show the correctness of the scheme. That is,(13)Dec2PADxk,yk,Enc2PADxk,yk,m=mfor every key (xk,yk) and plain text m. Let c=Enc2PAD(xk,yk,m). Then one has(14)c=pxkb2+pykb+b≡pxkz2+pykz+pm+zmod⁡p2and cmod⁡p=z, where z∈Zp. Now,(15)Dec2PADxk,yk,c=t-zp=p-xkz2+p-ykz+pxkz2+pykz+pm+z-zp=pm+z-zp=m.We shall later show that, given a single plain-text and ciphertext pair (m1,c1) and a ciphertext c2 such that c2≢c1(modp), we still have information-theoretic security for c2. That is, 2PAD satisfies perfect leak-freeness against Alice whenever ci≢cj(modp) for i≠j. However, suppose that we have two plain-text and ciphertext pairs (m1,c1),(m2,c2) such that c1≢c2(modp). We can show that the key xk,yk can be completely determined from such two pairs.Proposition 6.
For every plain-text and ciphertext pair(m1,c1),(m2,c2) such that c1≢c2(modp), there is a unique key (xk,yk) such that(16)c1=Enc2PADxk,yk,m1,c2=Enc2PADxk,yk,m2.Proof.
Letz1,z2∈Zp such that z1≡c1(mod⁡p) and z2≡c2(mod⁡p). Let also v1=(c1-pm1-z1)/p and v2=(c2-pm2-z2)/p. Then, we have a system of two equations:(17)v1=xkz12+ykz1,v2=xkz22+ykz2,where v1,v2,z1,z2 are known. Now, let(18)Z=z12z22z1z2.Note that since z1,z2≢0(mod⁡p) and z1≢z2(mod⁡p), we have z12z2-z1z22≢0(mod⁡p) and Z is invertible modulo p. Therefore, the equation pair has a unique solution:(19)v1v2·Z-1=xkz12+ykz1xkz22+ykz2·Z-1=xkykz12z22z1z2·Z-1=xkyk.Due to the transformation algorithmMap, we require that if Bob sends L ciphertext messages c1,c2,…,cL to Alice, we have ci≢cj(mod⁡p) for every i≠j. Otherwise, it would be trivial for Alice to derive the decryptions of all of the ciphertexts from a single plain-text and ciphertext pair. Therefore, the maximum number of ciphertext messages under the same key is determined by L≤p-1.


### 5.2. Blind Decryption Protocol

Next, we give a description of a blind decryption protocol based on the transformation algorithmMap.Definition 7 (BlindDec).
Suppose that the encryptor and the decryptor share a key(xk,yk)=Gen2PAD(s) intended for a single decryption by Alice. Furthermore, let Alice have an encrypted message c=Enc2PAD(xk,yk,m) that is not known to the decryptor. Finally, suppose that the prime p is public knowledge. Let the protocol BlindDec be defined by the following exchange between Alice and the decryptor: (1)
Alice: computec′≔cmod⁡p and transmit it to the decryptor(2)
Decryptor: reply withm′=Dec2PAD(xk,yk,c′)(3)
Alice: compute the plain-text messagem=Map(c′,m′,c)Let us quickly check the correctness of BlindDec. Let z≡c′≡c(mod⁡p). Then, c=pxkz2+pykz+pm+z, where m is the plain-text message. The decryptor replies with(20)m′=p-xkz2+p-ykz+z-zp=-xkz2+-ykz.But now Alice can compute(21)Mapc′,m′,c=c-z+pm′p=pxkz2+pykz+pm+z-z+pm′p=pxkz2+pykz+pm-pxkz2-pykzp=pmp=m,which is the correct plain-text message.


### 5.3. The Complete Blind Decryption Scheme

As was mentioned earlier, the communication between Alice and the encryptor has to be protected in order to prevent the decryptor from obtaining the plain-text messages corresponding toc1,c2,…,cL. If the decryptor can observe these ciphertext messages, it can freely decrypt all of them, since it knows the correct key. Therefore, we need to apply an outer encryption scheme that hides the ciphertext messages. The same solution is the easiest way to provide perfect leak-freeness against the encryptor, since it enables us to simplify the secrecy conditions. In our case, we want to protect both of these exchanges with an outer tier of encryption which provides perfect secrecy. Let SEn=(Genn,Encn,Decn) be any symmetric encryption scheme that satisfies perfect secrecy such that the plain-text and ciphertext space is Zn. We will be applying SEn with both n=p2 and n=p together with 2PAD to provide the required leak-freeness and blindness properties. The outer tier is composed in the following way. Alice and the encryptor share a set of keys k1,k2,…,kL. The encryptor protects each ciphertext message by computing uj=Encp2(kj,cj) for j∈{1,2,…,L}. It sends u1,u2,…,uL to Alice. Similarly, Alice and the decryptor share a pair of keys kC,kP that are used to protect ci′ and mi′. Alice sends w=Encp(kC,c′) to the decryptor that responds with w′=Encp(kP,m′). The resulting scheme SymmetricBlind is defined as follows.Definition 8 (SymmetricBlind).
LetSEn=(Genn,Encn,Decn) be a symmetric encryption scheme such that the plain-text and ciphertext space is Zn and let SEn satisfy perfect secrecy. Let Alice and the encryptor share a set of keys k1,k2,…,kL. Let Alice and the decryptor share a pair of keys kC,kP intended for a single blind decryption by Alice. Also let the encryptor and the decryptor share a blind decryption key (xk,yk)=Gen2PAD(s), where 2s≥L+1, which is intended for single blind decryption by Alice. SymmetricBlind is determined by Box 1.Box 1
Alice
Encryptor
Choose m1,m2,…,mL
∀
j
:
c
j
=
E
n
c
2
P
A
D
(
x
k
,
y
k
,
m
j
)
such that
c
j
≢
c
j
′
(
mod
⁡
p
)
∀
j
≠
j
′
∀
j
:
u
j
=
E
n
c
p
2
(
k
j
,
c
j
)
u
1
,
u
2
,
…
,
u
L
⟵
u
1
,
u
2
,
…
,
u
L
∀
j
c
j
=
D
e
c
p
2
(
k
j
,
u
j
)
Picki
c
′
=
c
i
mod
⁡
p
w
=
E
n
c
p
(
k
C
,
c
′
)
Decryptor
w
⟶
w
c
′
=
D
e
c
p
(
k
C
,
w
)
m
′
=
D
e
c
2
P
A
D
(
x
k
,
y
k
,
c
′
)
w
′
=
E
n
c
p
(
k
P
,
m
′
)
w
′
⟵
w
′
m
′
=
D
e
c
p
(
k
P
,
w
′
)
m
i
=
M
a
p
(
c
′
,
m
′
,
c
i
)Note that we require that the parameters determining the size of the plain-text space satisfy 2s≥L+1 to ensure that the generated prime p satisfies L≤p-1 and the scheme supports at least the encryption of L messages.


## 5.1. The Inner Encryption Scheme

We shall first construct an inner encryption scheme called2PAD with some useful properties. Our inner scheme is based on modular arithmetic on the ring Zp2, where p≥5 is a prime. Our plain-text space is Zp and every m∈Zp is mapped to the ciphertext space Zp2. To satisfy Definition 2, we want to add an amount of randomness that is at least twice the binary length of m in the encryption operation. Therefore, the keys of 2PAD will consist of pairs (xk,yk)∈Zp×Zp. Let b∈Zp2. Then,(6)b≡pz′+z′′mod⁡p2,where z′,z′′∈Zp. Therefore, we can essentially represent b with two elements of Zp. Using such a representation, we encrypt a single message m∈Zp by first sampling a random element z←U(Zp∖{0}) and setting b≔(pm+z)mod⁡p2. Then, we add the key (xk,yk) by computing(7)c≔pxkb2+pykb+bmod⁡p2=pxkz2+pykz+pm+zwhich is the ciphertext message. To enable blinding, Alice needs to be able to transform c into another ciphertext c′. The encryption operation entails such a transformation property that follows from the congruence(8)pxkb′2+pykb′+b′≡pxkb2+pykb+b′mod⁡p2for every xk,yk∈Zp and b,b′∈Zp2 such that b≡b′(mod⁡p). Let m1 be a plain text and let c1=pxkb2+pykb+b be its encryption with b=(pm1+z)mod⁡p2. Let c2 now be any ciphertext under the same key (xk,yk) such that c2≡c1≡z(mod⁡p) and let m2 be the corresponding plain text. Since c2≡c1≡z(mod⁡p), we have c2=pxkb′2+pykb′+b′, where b′=(pm2+z)mod⁡p2. Now, by (8),(9)c2≡pxkb′2+pykb′+b′≡pxkb2+pykb+b′≡c1-b+b′mod⁡p2,from which(10)c2≡c1-pm1+pm2mod⁡p2,which enables us to compute m2 using c2,m1,c1 without the key (xk,yk). Namely, if we know a plain text m1 and its encryption c1=pxkz2+pykz+pm1+z, we know the decryption m2 of c2 for every c2≡c1(mod⁡p). The plain text m2 can be computed by the transformation algorithm Map  in Algorithm 1.Algorithm 1
(
1
)  procedure  Mapc1,m1,c2
(
2
)    If c1≢c2(mod⁡p) output ⊥
(
3
)    m2≔((c2-c1+pm1)/p)mod⁡p
(
4
)    output  m2
(
5
)  end procedureLetz≡c1≡c2(mod⁡p). The algorithm works because(11)c2-c1+pm1p=pxkz2+pykz+pm2+z-pxkz2-pykz-pm1-z+pm1p=pm2p=m2.In order to query the decryptor, Alice can transform a ciphertext c into any c′ such that c′≡c(mod⁡p). The Map algorithm can transform the corresponding plain text m′ to the decryption m of c.Decryption is straightforward knowing the key(xk,yy). Its operation, as well as the complete encryption scheme, is described below.Definition 5 (2PAD).
The symmetric encryption scheme(12)2PAD=Gen2PAD,Enc2PAD,Dec2PADconsists of Algorithms 2, 3, and 4.Algorithm 2
(
1
)  procedure  Gen2PADs⊳s determines the size for the plaintext space
(
2
)    Choose a public prime p such that p≥5 and p≥2s
(
3
)    xk←U(Zp)
(
4
)    yk←U(Zp)
(
5
)    output  (xk,yk)
(
6
)  end procedureAlgorithm 3
(
1
)  procedure  Enc2PADxk,yk,m⊳ Input consists of a key (xk,yk) and a message m∈Zp
(
2
)    z←U(Zp∖{0})
(
3
)    b≔(pm+z)mod⁡p2
(
4
)    c≔(pxkb2+pykb+b)mod⁡p2
(
5
)    output  c
(
6
)  end procedureAlgorithm 4
(
1
)  procedure  Dec2PADxk,yk,c⊳ Input consists of a key (xk,yk) and a ciphertext c∈Zp2
(
2
)    z≔cmod⁡p
(
3
)    t≔(p(-xk)z2+p(-yk)z+c)mod⁡p2
(
4
)    m≔((t-z)/p)mod⁡p
(
5
)    output  m
(
6
)  end procedureThe plain-text and ciphertext spaces of2PAD depend on the chosen prime p; the plain-text space is Zp, while the ciphertext space is Zp2. Let us show the correctness of the scheme. That is,(13)Dec2PADxk,yk,Enc2PADxk,yk,m=mfor every key (xk,yk) and plain text m. Let c=Enc2PAD(xk,yk,m). Then one has(14)c=pxkb2+pykb+b≡pxkz2+pykz+pm+zmod⁡p2and cmod⁡p=z, where z∈Zp. Now,(15)Dec2PADxk,yk,c=t-zp=p-xkz2+p-ykz+pxkz2+pykz+pm+z-zp=pm+z-zp=m.We shall later show that, given a single plain-text and ciphertext pair (m1,c1) and a ciphertext c2 such that c2≢c1(modp), we still have information-theoretic security for c2. That is, 2PAD satisfies perfect leak-freeness against Alice whenever ci≢cj(modp) for i≠j. However, suppose that we have two plain-text and ciphertext pairs (m1,c1),(m2,c2) such that c1≢c2(modp). We can show that the key xk,yk can be completely determined from such two pairs.Proposition 6.
For every plain-text and ciphertext pair(m1,c1),(m2,c2) such that c1≢c2(modp), there is a unique key (xk,yk) such that(16)c1=Enc2PADxk,yk,m1,c2=Enc2PADxk,yk,m2.Proof.
Letz1,z2∈Zp such that z1≡c1(mod⁡p) and z2≡c2(mod⁡p). Let also v1=(c1-pm1-z1)/p and v2=(c2-pm2-z2)/p. Then, we have a system of two equations:(17)v1=xkz12+ykz1,v2=xkz22+ykz2,where v1,v2,z1,z2 are known. Now, let(18)Z=z12z22z1z2.Note that since z1,z2≢0(mod⁡p) and z1≢z2(mod⁡p), we have z12z2-z1z22≢0(mod⁡p) and Z is invertible modulo p. Therefore, the equation pair has a unique solution:(19)v1v2·Z-1=xkz12+ykz1xkz22+ykz2·Z-1=xkykz12z22z1z2·Z-1=xkyk.Due to the transformation algorithmMap, we require that if Bob sends L ciphertext messages c1,c2,…,cL to Alice, we have ci≢cj(mod⁡p) for every i≠j. Otherwise, it would be trivial for Alice to derive the decryptions of all of the ciphertexts from a single plain-text and ciphertext pair. Therefore, the maximum number of ciphertext messages under the same key is determined by L≤p-1.


## 5.2. Blind Decryption Protocol

Next, we give a description of a blind decryption protocol based on the transformation algorithmMap.Definition 7 (BlindDec).
Suppose that the encryptor and the decryptor share a key(xk,yk)=Gen2PAD(s) intended for a single decryption by Alice. Furthermore, let Alice have an encrypted message c=Enc2PAD(xk,yk,m) that is not known to the decryptor. Finally, suppose that the prime p is public knowledge. Let the protocol BlindDec be defined by the following exchange between Alice and the decryptor: (1)
Alice: computec′≔cmod⁡p and transmit it to the decryptor(2)
Decryptor: reply withm′=Dec2PAD(xk,yk,c′)(3)
Alice: compute the plain-text messagem=Map(c′,m′,c)Let us quickly check the correctness of BlindDec. Let z≡c′≡c(mod⁡p). Then, c=pxkz2+pykz+pm+z, where m is the plain-text message. The decryptor replies with(20)m′=p-xkz2+p-ykz+z-zp=-xkz2+-ykz.But now Alice can compute(21)Mapc′,m′,c=c-z+pm′p=pxkz2+pykz+pm+z-z+pm′p=pxkz2+pykz+pm-pxkz2-pykzp=pmp=m,which is the correct plain-text message.


## 5.3. The Complete Blind Decryption Scheme

As was mentioned earlier, the communication between Alice and the encryptor has to be protected in order to prevent the decryptor from obtaining the plain-text messages corresponding toc1,c2,…,cL. If the decryptor can observe these ciphertext messages, it can freely decrypt all of them, since it knows the correct key. Therefore, we need to apply an outer encryption scheme that hides the ciphertext messages. The same solution is the easiest way to provide perfect leak-freeness against the encryptor, since it enables us to simplify the secrecy conditions. In our case, we want to protect both of these exchanges with an outer tier of encryption which provides perfect secrecy. Let SEn=(Genn,Encn,Decn) be any symmetric encryption scheme that satisfies perfect secrecy such that the plain-text and ciphertext space is Zn. We will be applying SEn with both n=p2 and n=p together with 2PAD to provide the required leak-freeness and blindness properties. The outer tier is composed in the following way. Alice and the encryptor share a set of keys k1,k2,…,kL. The encryptor protects each ciphertext message by computing uj=Encp2(kj,cj) for j∈{1,2,…,L}. It sends u1,u2,…,uL to Alice. Similarly, Alice and the decryptor share a pair of keys kC,kP that are used to protect ci′ and mi′. Alice sends w=Encp(kC,c′) to the decryptor that responds with w′=Encp(kP,m′). The resulting scheme SymmetricBlind is defined as follows.Definition 8 (SymmetricBlind).
LetSEn=(Genn,Encn,Decn) be a symmetric encryption scheme such that the plain-text and ciphertext space is Zn and let SEn satisfy perfect secrecy. Let Alice and the encryptor share a set of keys k1,k2,…,kL. Let Alice and the decryptor share a pair of keys kC,kP intended for a single blind decryption by Alice. Also let the encryptor and the decryptor share a blind decryption key (xk,yk)=Gen2PAD(s), where 2s≥L+1, which is intended for single blind decryption by Alice. SymmetricBlind is determined by Box 1.Box 1
Alice
Encryptor
Choose m1,m2,…,mL
∀
j
:
c
j
=
E
n
c
2
P
A
D
(
x
k
,
y
k
,
m
j
)
such that
c
j
≢
c
j
′
(
mod
⁡
p
)
∀
j
≠
j
′
∀
j
:
u
j
=
E
n
c
p
2
(
k
j
,
c
j
)
u
1
,
u
2
,
…
,
u
L
⟵
u
1
,
u
2
,
…
,
u
L
∀
j
c
j
=
D
e
c
p
2
(
k
j
,
u
j
)
Picki
c
′
=
c
i
mod
⁡
p
w
=
E
n
c
p
(
k
C
,
c
′
)
Decryptor
w
⟶
w
c
′
=
D
e
c
p
(
k
C
,
w
)
m
′
=
D
e
c
2
P
A
D
(
x
k
,
y
k
,
c
′
)
w
′
=
E
n
c
p
(
k
P
,
m
′
)
w
′
⟵
w
′
m
′
=
D
e
c
p
(
k
P
,
w
′
)
m
i
=
M
a
p
(
c
′
,
m
′
,
c
i
)Note that we require that the parameters determining the size of the plain-text space satisfy 2s≥L+1 to ensure that the generated prime p satisfies L≤p-1 and the scheme supports at least the encryption of L messages.


## 6. Security ofSymmetricBlind

We shall now consider the security ofSymmetricBlind. We proceed to show that the devised scheme satisfies the three conditions formulated in Section 4: perfect leak-freeness against the encryptor, perfect leak-freeness against Alice, and perfect blindness against the decryptor.


### 6.1. Perfect Leak-Freeness against the Encryptor

Proposition 9.
S
y
m
m
e
t
r
i
c
B
l
i
n
d satisfies perfect leak-freeness against the encryptor for a single decryption of a maximum of L≤p-1 messages, where p is determined by Gen2PAD(s).Proof.
The claim follows directly from the observation that the encryptor sees onlyw and w′. By the description of SymmetricBlind, c′ and m′ are protected by encryption satisfying perfect secrecy and thus do not leak information to the encryptor.It is easy to see that the outer tier of encryption is necessary. Suppose that the outer encryption scheme was not applied. Thenc′ would leak cimod⁡p which would betray i to the encryptor.


### 6.2. Perfect Blindness against Decryptor

We shall now prove that the decryptor does not get information about the plain-text message.Proposition 10.
S
y
m
m
e
t
r
i
c
B
l
i
n
d satisfies perfect blindness against the decryptor for a single blind decryption.Proof.
Sincec1,c2,…,cL are protected with perfect secrecy, we only need to show that(22)Pr⁡M=m∣C′=c′,M′=m′=Pr⁡M=m,where C′ and M′ are the random variables associated with the messages c′ and m′, respectively. Let X,Y denote the random variables corresponding to the key elements (xk,yk)←Gen(s), respectively. The reply m′ from the decryptor is completely determined by the key (xk,yk) and the element c′=cimod⁡p, since m′=(-xk)c′2+-ykc′. Therefore,(23)Pr⁡M=m∣C′=c′,M′=m′=Pr⁡M=m∣X=xk,Y=yk,C′=c′.Let us consider C′. By the description of the scheme, we have C′=Cimod⁡p, where i is the chosen index of Alice. But, for every i, we have, by the description of Enc2PAD, that Cimod⁡p~U(Zp∖{0}). Therefore, C′ is independent of X and Y and(24)Pr⁡M=m∣X=xk,Y=yk,C′=z=Pr⁡M=m∣X=xk,Y=yk,C′=z′for every z,z′∈Zp∖{0} and(25)Pr⁡M=m∣X=xk,Y=yk=∑z∈Zp∖0Pr⁡M=m∣X=xk,Y=yk,C′=z·Pr⁡C′=z∣X=xk,Y=yk=1p-1·∑z∈Zp∖0Pr⁡M=m∣X=xk,Y=yk,C′=z=Pr⁡M=m∣X=xk,Y=yk,C′=zfor any z∈Zp. By our assumption, M is independent of X and Y and therefore we have(26)Pr⁡M=m∣X=xk∩Y=yk=Pr⁡M=m,which shows our claim.The proof shows that the decryptor (with the knowledge of the key(xk,yk) and c′ and m′) does not gain any information about the plain-text message m assuming that cj for j∈{1,2,…,L} have been delivered to Alice in perfect secrecy. Considering the secrecy against the decryptor, it would suffice to send c′ without the additional level of encryption. However, the additional level is necessary to achieve leak-freeness against the encryptor.


### 6.3. Perfect Leak-Freeness against Alice

We shall now consider an honest-but-curious Alice and show that the observation of a single plain-text and ciphertext pair(m1,c1) does not yield information about the decryption of c2 for c2≢c1(mod⁡p).Proposition 11.
S
y
m
m
e
t
r
i
c
B
l
i
n
d satisfies perfect leak-freeness against Alice for a single decryption of a maximum of L≤p-1 ciphertexts.Proof.
By the description ofSymmetricBlind, the ciphertext messages c1,c2,…,cL are of different congruence class modulo p. Let M1,M2 be random variables over the plain-text space Zp. Let X,Y denote the random variables corresponding to the key elements (xk,yk)=Gen2PAD(s). We have to show that(27)Pr⁡c1=Enc2PADX,Y,M1,c2=Enc2PADX,Y,M2∣M1=m1,M2=m2,c1≢c2mod⁡p=Pr⁡c1=Enc2PADX,Y,M1,c2=Enc2PADX,Y,M2∣M1=m1,M2=m,c1≢c2mod⁡pfor every m1,m2,m∈{0,1,2,…,p-1} and c1,c2∈Zp2 such that c1≢c2(mod⁡p). Given a valid assignment for m1,c1 and c2, it suffices to show that(28)Pr⁡c1=Enc2PADX,Y,M1,c2=Enc2PADX,Y,M2∣M1=m,M2=m2,c1≢c2mod⁡p=1p2for every m∈Zp. By Proposition 6, for every plain-text and ciphertext pair (m1,c1),(m,c2) such that c1≢c2(mod⁡p), there is a unique key (xk,yk). Therefore,(29)Pr⁡c1=Enc2PADX,Y,M1,c2=Enc2PADX,Y,M2∣M1=m1,M2=m,c1≢c2mod⁡p=Pr⁡X=xk,Y=yk.By the definition of Gen2PAD, X and Y are independent and we have(30)Pr⁡X=xk,Y=yk=Pr⁡X=xk·Pr⁡Y=yk=1p2.We have now established the perfect secrecy ofSymmetricBlind according to Definition 4.


### 6.4. The Parameters

An optimal encryption scheme, with plain-text spaceM, that satisfies perfect leak-freeness against Alice for a single decryption needs 2log2⁡M bits of randomness for a key. 2PAD achieves exactly this bound, since the plain-text space is Zp and a single key (xk,yk) contains 2log2⁡p bits of randomness. Assuming that messages and keys are represented by binary strings, we need 2log2⁡p bits of key to encrypt messages of length log2⁡p. For a single decryption with SymmetricBlind, the decryptor needs to store the key elements xk,yk∈Zp, as well as the keys kC,kP. The keys kC,kP are used to encrypt messages of Zp. Therefore, log2⁡p bits for each of these keys suffice for perfect secrecy. In total, the decryptor needs to store key material of 4log2⁡p bits for a single decryption of a message of bit length log2⁡p. Since the ciphertext space is Zp2, the ciphertext’s length in bits is approximately twice the plain text’s length. Depending on the length of the plain-text messages and the needed maximum number of encryptions L≤p-1, we should therefore choose the smallest possible p, since its bit size has no effect on the security of the scheme. Table 1 lists some possible choices for p and the resulting key, plain text, and ciphertext lengths in bits. Note that for long plain-text messages the maximum number of messages L is practically unlimited.Table 1
Parameter examples forSymmetricBlind.
p
Decryptor key length [bits]
Plain text length [bits]
Ciphertext length [bits]
5
12
3
5
7
12
3
6
11
16
4
7
23
20
5
10
101
28
7
14
1009
40
10
20
5003
52
13
25
20011
60
15
29
2
31
-
1
124
31
62
2
61
-
1
244
61
122
2
127
-
1
508
127
254


## 6.1. Perfect Leak-Freeness against the Encryptor

Proposition 9.
S
y
m
m
e
t
r
i
c
B
l
i
n
d satisfies perfect leak-freeness against the encryptor for a single decryption of a maximum of L≤p-1 messages, where p is determined by Gen2PAD(s).Proof.
The claim follows directly from the observation that the encryptor sees onlyw and w′. By the description of SymmetricBlind, c′ and m′ are protected by encryption satisfying perfect secrecy and thus do not leak information to the encryptor.It is easy to see that the outer tier of encryption is necessary. Suppose that the outer encryption scheme was not applied. Thenc′ would leak cimod⁡p which would betray i to the encryptor.


## 6.2. Perfect Blindness against Decryptor

We shall now prove that the decryptor does not get information about the plain-text message.Proposition 10.
S
y
m
m
e
t
r
i
c
B
l
i
n
d satisfies perfect blindness against the decryptor for a single blind decryption.Proof.
Sincec1,c2,…,cL are protected with perfect secrecy, we only need to show that(22)Pr⁡M=m∣C′=c′,M′=m′=Pr⁡M=m,where C′ and M′ are the random variables associated with the messages c′ and m′, respectively. Let X,Y denote the random variables corresponding to the key elements (xk,yk)←Gen(s), respectively. The reply m′ from the decryptor is completely determined by the key (xk,yk) and the element c′=cimod⁡p, since m′=(-xk)c′2+-ykc′. Therefore,(23)Pr⁡M=m∣C′=c′,M′=m′=Pr⁡M=m∣X=xk,Y=yk,C′=c′.Let us consider C′. By the description of the scheme, we have C′=Cimod⁡p, where i is the chosen index of Alice. But, for every i, we have, by the description of Enc2PAD, that Cimod⁡p~U(Zp∖{0}). Therefore, C′ is independent of X and Y and(24)Pr⁡M=m∣X=xk,Y=yk,C′=z=Pr⁡M=m∣X=xk,Y=yk,C′=z′for every z,z′∈Zp∖{0} and(25)Pr⁡M=m∣X=xk,Y=yk=∑z∈Zp∖0Pr⁡M=m∣X=xk,Y=yk,C′=z·Pr⁡C′=z∣X=xk,Y=yk=1p-1·∑z∈Zp∖0Pr⁡M=m∣X=xk,Y=yk,C′=z=Pr⁡M=m∣X=xk,Y=yk,C′=zfor any z∈Zp. By our assumption, M is independent of X and Y and therefore we have(26)Pr⁡M=m∣X=xk∩Y=yk=Pr⁡M=m,which shows our claim.The proof shows that the decryptor (with the knowledge of the key(xk,yk) and c′ and m′) does not gain any information about the plain-text message m assuming that cj for j∈{1,2,…,L} have been delivered to Alice in perfect secrecy. Considering the secrecy against the decryptor, it would suffice to send c′ without the additional level of encryption. However, the additional level is necessary to achieve leak-freeness against the encryptor.


## 6.3. Perfect Leak-Freeness against Alice

We shall now consider an honest-but-curious Alice and show that the observation of a single plain-text and ciphertext pair(m1,c1) does not yield information about the decryption of c2 for c2≢c1(mod⁡p).Proposition 11.
S
y
m
m
e
t
r
i
c
B
l
i
n
d satisfies perfect leak-freeness against Alice for a single decryption of a maximum of L≤p-1 ciphertexts.Proof.
By the description ofSymmetricBlind, the ciphertext messages c1,c2,…,cL are of different congruence class modulo p. Let M1,M2 be random variables over the plain-text space Zp. Let X,Y denote the random variables corresponding to the key elements (xk,yk)=Gen2PAD(s). We have to show that(27)Pr⁡c1=Enc2PADX,Y,M1,c2=Enc2PADX,Y,M2∣M1=m1,M2=m2,c1≢c2mod⁡p=Pr⁡c1=Enc2PADX,Y,M1,c2=Enc2PADX,Y,M2∣M1=m1,M2=m,c1≢c2mod⁡pfor every m1,m2,m∈{0,1,2,…,p-1} and c1,c2∈Zp2 such that c1≢c2(mod⁡p). Given a valid assignment for m1,c1 and c2, it suffices to show that(28)Pr⁡c1=Enc2PADX,Y,M1,c2=Enc2PADX,Y,M2∣M1=m,M2=m2,c1≢c2mod⁡p=1p2for every m∈Zp. By Proposition 6, for every plain-text and ciphertext pair (m1,c1),(m,c2) such that c1≢c2(mod⁡p), there is a unique key (xk,yk). Therefore,(29)Pr⁡c1=Enc2PADX,Y,M1,c2=Enc2PADX,Y,M2∣M1=m1,M2=m,c1≢c2mod⁡p=Pr⁡X=xk,Y=yk.By the definition of Gen2PAD, X and Y are independent and we have(30)Pr⁡X=xk,Y=yk=Pr⁡X=xk·Pr⁡Y=yk=1p2.We have now established the perfect secrecy ofSymmetricBlind according to Definition 4.


## 6.4. The Parameters

An optimal encryption scheme, with plain-text spaceM, that satisfies perfect leak-freeness against Alice for a single decryption needs 2log2⁡M bits of randomness for a key. 2PAD achieves exactly this bound, since the plain-text space is Zp and a single key (xk,yk) contains 2log2⁡p bits of randomness. Assuming that messages and keys are represented by binary strings, we need 2log2⁡p bits of key to encrypt messages of length log2⁡p. For a single decryption with SymmetricBlind, the decryptor needs to store the key elements xk,yk∈Zp, as well as the keys kC,kP. The keys kC,kP are used to encrypt messages of Zp. Therefore, log2⁡p bits for each of these keys suffice for perfect secrecy. In total, the decryptor needs to store key material of 4log2⁡p bits for a single decryption of a message of bit length log2⁡p. Since the ciphertext space is Zp2, the ciphertext’s length in bits is approximately twice the plain text’s length. Depending on the length of the plain-text messages and the needed maximum number of encryptions L≤p-1, we should therefore choose the smallest possible p, since its bit size has no effect on the security of the scheme. Table 1 lists some possible choices for p and the resulting key, plain text, and ciphertext lengths in bits. Note that for long plain-text messages the maximum number of messages L is practically unlimited.Table 1
Parameter examples forSymmetricBlind.
p
Decryptor key length [bits]
Plain text length [bits]
Ciphertext length [bits]
5
12
3
5
7
12
3
6
11
16
4
7
23
20
5
10
101
28
7
14
1009
40
10
20
5003
52
13
25
20011
60
15
29
2
31
-
1
124
31
62
2
61
-
1
244
61
122
2
127
-
1
508
127
254


## 7. Future Work

There are two main drawbacks of the construction presented in this paper. First, we have not considered active adversaries. Similar to the one-time pad, we have only considered such adversaries that observe the flow of messages. For practical scenarios, we need to consider adversaries that actively induce errors into the protocol flow. However, such considerations are most naturally conducted in the computational infeasibility model which has been used, for instance, in [5]. In the active adversaries setting, it would also be natural to consider the security of the devised scheme in the framework of computational indistinguishability such that the truly random keys are exchanged with pseudorandom bit strings. In particular, the computationally hard version of our scheme yields efficient practical implementation. The computational security model is also more appealing considering applications due to the limitations induced by the information-theoretic model. For example, in the information-theoretic security model, private information retrieval requires an amount of communication that is at least the size of the database [44]. Similarly, in SymmetricBlind, a fresh key is needed for each decryption resulting in limitations regarding existing applications. For example, applications that require adaptive queries cannot be instantiated with SymmetricBlind, since a fresh key would be required for each query. We leave it for future research to consider SymmetricBlind and its possible generalizations and applications in the computational security model.The second drawback is that we have only considered the case of a single adversary. While it does not make sense to consider a scenario where Alice is colluding with the encryptor against the decryptor, the scenario where the encryptor and the decryptor are colluding is an important one. For many scenarios, Alice cannot be certain whether the encryptor and the decryptor are in fact separate entities. However, if they are a single entity, the scenario is identical to oblivious transfer. We cannot achieve information-theoretic security in such a case [18]. For example, it is easy to see that our construction fails for colluding encryptor and decryptor. If that is the case, we effectively remove the outer layer of encryption, which means that c′=cimod⁡p leaks i to the adversary. To provide security against colluding encryptor and decryptor, we would need to detect such collusion or to turn to computational assumptions. We leave the question as an open problem for future research. Another interesting question for future work is to consider the case where we do not apply the outer layer of encryption from the encryptor to Alice. Thus far, we have defined perfect blindness so that the decryptor has absolutely no information about the plain-text message. However, we could relax the requirement so that, similar to leak-freeness against the encryptor, the information is conditioned on the plain texts m1,m2,…,mL. In other words, we could relax the requirement so that the decryptor may observe the selection (and the corresponding plain-text messages) given to Alice. Such relaxation is natural in the oblivious transfer case where the encryptor and the decryptor are the same entity. We could then define blindness as a property requiring only that the selection i be hidden. It is again easy to see that our scheme without the outer layer of encryption fails such a property. If c1,c2,…,cL are not protected, then c′=cimod⁡p leaks i. Similarly, attempting to convert SymmetricBlind into an oblivious transfer scheme using the method of Dodis et al. is impossible, since SymmetricBlind requires that the parties be truly separate. The unification of encryptor and decryptor leaks i even in the computational security model [39]. We leave this consideration also for future work.


## 8. Conclusion

In this paper, we give a definition of perfect secrecy for symmetric blind decryption in the setting where one of the parties may be malicious but adhering to the protocol of the scheme. We consider neither active adversaries nor the setting where two of the participants are colluding against the third. We construct a symmetric blind decryption schemeSymmetricBlind and show that it satisfies our definition of perfect secrecy. The scheme is based on two layers of encryption, where the inner layer utilizes a novel encryption scheme 2PAD given in this paper. 2PAD is based on modular arithmetic with Zp2 as the ciphertext space, Zp as the plain-text space, and Zp×Zp as the key space, where p≥5 is a prime. The security of SymmetricBlind is shown information-theoretically and does not depend on the size of p. For a fixed blind decryption key, SymmetricBlind supports a single blind decryption from a selection of L≤p-1 messages. For a single decryption of a message of bit length log2⁡p, the decryption server needs to store key material of 4log2⁡p bits.



---

*Source: 6575907-2017-08-16.xml*