# A Posteriori Openable Public Key Encryption

Xavier Bultel, Pascal Lafourcade

► To cite this version:

Xavier Bultel, Pascal Lafourcade. A Posteriori Openable Public Key Encryption. 31st IFIP Information Security & Privacy Conference (IFIP SEC), May 2016, Ghent, Belgium. pp.17-31, 10.1007/978-3-319-33630-5_2. hal-01369535

HAL Id: hal-01369535

https://inria.hal.science/hal-01369535

Submitted on 21 Sep 2016

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
# A Posteriori Openable Public Key Encryption*

Xavier Bultel¹,² and Pascal Lafourcade¹,²

¹ CNRS, UMR 6158, LIMOS, F-63173 Aubière, France

² Université Clermont Auvergne, LIMOS, BP 10448, 63000 Clermont-Ferrand, France

**Abstract.** We present a public key encryption primitive called *A Posteriori Openable Public Key Encryption (APO-PKE)*. In addition to conventional properties of public key cryptosystems, our primitive allows each user, who has encrypted messages using different public keys, to create a special decryption key. A user can give this key to a judge to open all messages that have been encrypted in a chosen time interval with the public keys of the receivers. We provide a generic efficient construction, in the sense that the complexity of the special key generation algorithm and this key size are independent of the number of ciphertexts. We give security models for our primitive against chosen plaintext attack and analyze its security in the random oracle model.

**Keywords:** Public-Key Encryption, Openable Encryption, ROM, CPA.

## 1 Introduction

Since the emergence of the Internet, email communication is accessible to anyone. Email privacy is an important computer security topic. Without public key encryption schemes, plaintext messages are sent and stored by the mail server without any protection. Fortunately, there exist many straightforward to use softwares that allow everyone to encrypt and sign emails using public key cryptography, such as the well known GnuPG<fnref n="3" /> tool. Unfortunately, these softwares are rarely used [27], consequently encrypted emails may be considered as a suspect behavior. Hence as P. Zimmermann, the designer of PGP, said: "*If privacy is outlawed, only outlaws will have privacy*". We hope that in a near future everybody can privately exchange emails. Then our motivation is based on the following scenario, where Alice is implied in a court case. To find some clues, the judge needs to read emails that Alice has sent during a specified time period. The judge uses his power to obtain from Alice's email server all emails sent by Alice (including dates of dispatch and receiver identities). If the messages are not encrypted then the judge can read emails without relation to the investigation, which is a privacy violation. On the other hand, if messages are encrypted with

<footnote>* This research was conducted with the support of the “Digital Trust” Chair from the University of Auvergne Foundation.</footnote>

<footnote n="3">³ https://www.gnupg.org</footnote>
the receiver public key then the judge can suspect Alice to hide crucial information for the investigation. Moreover, without the receivers' private keys, Alice has no solution to prove her innocence and cannot reveal his correspondence to the judge.

To solve this problem, Alice needs a mechanism to give to the judge a possibility to open all messages sent during a specified time period. Using our solution Alice can construct such a special key called an *interval-key*. With this key, the judge can only read the encrypted messages sent during this specific interval of time, because this key does not allow him to open other encrypted messages stored on the email server. Nowadays, to the best of our knowledge, there is no efficient cryptographic solution that offers such functionality to the users. The goal of this paper is to propose a practical and efficient solution to this problem.

In many public key cryptosystems, when a ciphertext is generated, it is possible to create a special key that allows a person to decrypt it, without knowing the corresponding secret key. For example, in ElGamal [13], $C = (C_1, C_2) = (g^r, g^{x \cdot r} \cdot m)$ is the ciphertext of the message $m$ with the public key $g^x$ and a random element $r$ (for $g$ a generator of $G$ a group of prime order). Knowing the random element $r$, the public key of Bob $g^x$ and the ciphertext $C$ a third party can compute $C_2/(g^x)^r = m$ to recover the plaintext. Using this property it is possible to construct a naive solution by giving $n$ random elements to a third party to decrypt $n$ ciphertexts. However, this method presents an inherent limitation when the number $n$ is large and the user has to store all the random elements used to encrypt all the messages during an interval of time. The aim of this paper is to allow a user to construct an interval-key to decrypt several consecutive messages in a time interval where the size of the key, the stored information and the key generation complexity are constant and do not increase with the number of ciphertexts.

**Contributions:** We first present the notion of *Random Coin Decryptable Public Key Encryption (RCD-PKE)*. The idea of RCD-PKE is that one can open a ciphertext with the secret key and also use the random coin used during the encryption to open a cipher. We show that several existing schemes in the literature satisfy this notion, e.g. [1, 10, 14]. We use the RCD-PKE property to construct a scheme that allows a user to generate an interval-key for a judge to open all the messages he sent during a period of time. This scheme, called *A Posteriori Openable Public Key Encryption (APO-PKE)*, allows the judge to open all messages sent between two given dates. The number of ciphertexts is potentially infinite but the judge decryption capability is limited to the a posteriori chosen interval. It contains, like a standard public key encryption, a key generation function, an encryption function and a decryption function. It also has an extraction function that, given two ciphertexts and a secret value, generates an interval-key for the judge. Using this interval-key he can then open all messages encrypted by different public keys between the two ciphertexts for which the key has been created. Our scheme is generic since it only relies on any IND-CPA secure RCD-PKE and hash functions.
**Performances:** Our scheme has reasonable encryption and decryption execution time overhead comparing to the PKE we use, because the size of ciphertexts generated by our scheme is approximately the double of the size of the PKE encryption. Moreover the generation of the interval-key, its size and the stored information are also independent of the number of messages contained in the interval of time. Finally, there is no restriction neither about the total number of generated ciphertexts nor about the number of ciphertexts in a time interval.

**Security:** We provide the security models to prove the security of our schemes in the Random Oracle Model (ROM). We prove that the judge colluding with some users cannot learn more than the messages for which he received the interval-key. We also show that several users cannot collude in order to learn information about plaintexts contained in an interval of ciphertexts with the judge interval-key. We also demonstrate that the judge gets the same plaintext as the one received by the owners of the secret keys. This means that it is not possible to forge fake messages that the judge can open and not the owners of the secret keys, and vice-versa.

Our construction allows us to use the extraction algorithm only once per judge (or per set of encrypted mails). Our security model captures this situation. It is not going against our motivation as long as we consider that two judges having an interval key in two different court cases (for the same set of mails) do not collude. To avoid this drawback, we need to reinitialize the secret values stored by a user after the generation of an interval-key, in order to be able to produce new interval-key on the next encrypted data. We leave the construction of an APO-PKE with constant interval key generation complexity and constant interval key size allowing several interval key generations for the same judge and the same set of encrypted mails as an open problem.

**Related work:** Functional encryption [26] is a public-key encryption primitive that allows a user to evaluate a function on the plaintext message using a key and a ciphertext. This cryptographic primitive was formalized in [5]. It generalizes many well known cryptographic primitives such as identity based encryption [4] or attribute based encryption [26]. Moreover, some schemes that evaluate an arbitrary function have been proposed in [17,18]. A *posteriori* openable encryption can be seen as a functional encryption, where all ciphertexts (resp. plaintexts) that are encrypted by one user correspond to a unique large ciphertext (resp. plaintext). Then the interval-keys allow a user to find only some parts of the corresponding plaintext. Our proposal scheme is an efficient solution for this kind of functional encryption.

Deniable encryption [7, 22] is an encryption system that allows to encrypt two messages (original and hidden messages) in the same ciphertext. Using his secret key, the receiver can retrieve the original message. Using another shared secret key, the receiver can also decrypt the hidden message. It is not possible for the sender to prove that his encryption does not contain an hidden encrypted message. In our *a posteriori* openable encryption, the judge is only convinced that the plaintext that he decrypts is the same message that the plaintext decrypted by the secret key of the receiver. This notion differs from undeniability
since the judge is convinced that a message he decrypts using interval key has
actually been sent and received, but does not deal with message from another
channel that the given encryption system (including different way to encrypt or
decrypt a message in the same ciphertext).

Some cryptographic primitives deal with time in decryption mechanism or
rights delegation. *Timed-Release Encryption* (TRE), first proposed in [24], is
a public key encryption where encrypted messages cannot be opened before a
*release-time* chosen by the person who encrypted the messages. In this primitive,
it is generally a time server that allows the receiver to decrypt the message *in
the future* at a given date. Several TRE with diverse security properties have
been proposed [3,8,9]. More recently, an extension of TRE, called *Time-Specific
Encryption* (TSE), has been proposed in [25] and deals with time intervals.
Somehow these primitive are close to our because APO-PKE allows somebody
to give decryption capabilities *in the future*, after that encrypted messages has
been sent. However, TRE and TSE cannot be used to achieve APO-PKE, because
TRE ciphertext are intended to only one user and decryption capabilities cannot
be delegated to another party. Moreover, in TRE, time of decryption capability
must be chosen during the encryption phase, while in our primitive it can be
chosen at any time (*a posteriori*).

It is interesting to note that some TRE possess a pre-open mechanism [21]
that allows the sender to give decryption capabilities before the pre-specified
release-time. In this case, a security requirement (called *binding* property) en-
sures that the decrypted message from the pre-open mechanism is the message
decrypted by the receiver after the release-time [11]. For our primitive, we define
a similar property, called *integrity*, since we require that decrypted messages us-
ing an interval key must be equal to the messages decrypted by the legitimate
receivers.

Finally, *Key-Insulated Encryption* (KIE) [12,20,23] is a public key encryption
primitive where messages are encrypted from a tag corresponding to a time
period and a public key. At each time period corresponds a partial secret key
computed from a master key and the previous partial secret key. Moreover, the
public key is never changed. The motivation of this primitive is to provide secret
keys that can be stored in an untrusted device without compromising the master
key. Indeed, the leakage of a secret key compromises only messages received in a
specified time interval, and future encryptions remain secure. In the motivation
of [12], the authors give another interesting use of this primitive based on [16].
They provide a secure delegation of decryption rights in a time period. However,
this type of delegation allows them to delegate decryption rights only on pre-
defined time period. For example, if the time period corresponds to one month
then right delegation cannot be restricted to the last week of a month and the
first week of the following month without revealing all messages of these two
months. Moreover, delegator must give a different secret key to each time period,
so the decryption keys are proportional to the number of time periods contained
in the interval. Our goal is to propose decryption delegation capabilities to the
sender, while KIE only focuses on receiver decryption right delegation. Thus this primitive cannot solve our problem.

**Outline:** In the next section, we introduce some cryptographic tools and define the notion of RCD-PKE. In Section 3, we present a generic *A Posteriori Openable Public Key Encryption*. Then in Section 4, we provide security models and analyze the security of our scheme before concluding in the last section. All the proofs of our security results are given in the full version of this paper [6].

## 2 Random Coin Decryptable Public Key Encryption

We first recall the definition of probabilistic public key encryption.

**Definition 1 (Probabilistic Public Key Encryption (PKE)).** A probabilistic PKE is a triplet of polynomial time algorithms (Gen, Enc, Dec) such that Gen(1^k) returns a public/private key pair (pk, sk), Enc_{pk}(m; σ) returns a ciphertext c from the public key pk, the message m and the random coin σ, and Dec_{sk}(c) returns a plaintext m or a bottom symbol ⊥ from a secret key sk and a ciphertext c. Moreover the following equation holds: Dec_{sk}(Enc_{pk}(m; σ)) = m.

A PKE scheme $\Pi$ is said indistinguishable under chosen-plaintext attack (IND-CPA) [19] if for any polynomial time adversary $\mathcal{A}$, the difference between $\frac{1}{2}$ and the probability that $\mathcal{A}$ wins the IND-CPA experiment described in Fig. 1 is negligible.

We introduce the notion of *Random Coin Decryptable PKE (RCD-PKE)*. A public key encryption scheme is said RCD-PKE, if there exists a second way to decrypt the ciphertext with the random coin used to construct the

ciphertext. This primitive is a kind of PKE with *double decryption* mechanism (DD-PKE) which is defined in [15]. Actually RCD-PKE is a DD-PKE where the second secret key is the random coin and is used once.

$\mathbf{Exp}_{\Pi, \mathcal{A}}^{\text{IND-CPA}}(k):$
$b \stackrel{\$}{\leftarrow} \{0, 1\}$
$(\text{pk}, \text{sk}) \leftarrow \text{Gen}(1^k)$
$(m_0, m_1, \text{st}) \leftarrow \mathcal{A}_0(1^k, \text{pk})$
$c \leftarrow \text{Enc}_{\text{pk}}(m_b; \sigma)$
$b' \leftarrow \mathcal{A}_1(\text{st}, \text{pk}, c)$
return $(b = b')$

<caption>Fig. 1. IND-CPA experiment.</caption>

**Definition 2 (Random Coin Decryptable PKE (RCD-PKE)).** A probabilistic PKE is Random Coin Decryptable if there exists a polynomial time algorithm $\text{CDec}$ such that for any public key $pk$, any message $m$, and any coin $\sigma$, the following equation holds: $\text{CDec}_{\sigma}(\text{Enc}_{pk}(m; \sigma), pk) = m$.

For instance, ElGamal encryption scheme is RCD-PKE. It is possible, from a ciphertext $c = \text{Enc}_{pk}(m; \sigma) = (c_0, c_1) = (g^\sigma, pk^\sigma \cdot m)$ to use the algorithm $\text{CDec}_\sigma(c, pk)$ that computes $c_1/pk^\sigma$ to retrieve the plaintext message $m$. Many probabilistic encryption schemes in the literature are RCD-PKE, e.g. [1, 10, 14]. Algorithms $\text{CDec}$ of these two cryptosystems PKE are given in the full version of this paper [6]. We also introduce the concepts of valid key pair and of verifiable key PKE.
APOext<sup>st</sup><sub>pko</sub>(C<sub>i</sub>, C<sub>j</sub>): This algorithm generates an interval-key K<sup>pko</sup><sub>i&rarr;j</sub> that allows the owner O of the public key pko to decrypt all messages {C<sub>x</sub>}<sub>i&le;x&le;j</sub> using algorithm APOpen.

APOOpen<sub>sko</sub>(K<sup>pko</sup><sub>i&rarr;j</sub>, {C<sub>x</sub>}<sub>i&le;x&le;j</sub>, {pk<sub>x</sub>}<sub>i&le;x&le;j</sub>): Inputs of this algorithm contain a ciphertext set {C<sub>x</sub>}<sub>i&le;x&le;j</sub> and all the associated public keys {pk<sub>x</sub>}<sub>i&le;x&le;j</sub>. This algorithm allows a user to decrypt all encrypted messages sent during an interval using his secret key sk and the corresponding interval-key K<sup>pko</sup><sub>i&rarr;j</sub>. It returns a set of plaintexts {m<sub>x</sub>}<sub>i&le;x&le;j</sub> or &perp; in case of error.

In Scheme 1, we give a generic construction of APO-PKE based on an IND-CPA
secure RCD-PKE and three hash functions.

**Scheme 1 (Generic APO-PKE (G-APO))** Let $k$ be a security parameter, $\mathcal{E} =$
(Gen, Enc, Dec) be a RCD and VK PKE scheme, $\mathcal{R}$ be the set of possible random
coins of $\mathcal{E}$ and $\mathbf{F}: \{0,1\}^* \to \{0,1\}^k$, $\mathbf{G}: \{0,1\}^* \to \mathcal{R}$ and $\mathbf{H}: \{0,1\}^* \to
\{0,1\}^{2k}$ be three universal hash functions. Our generic APO-PKE is defined by
the following six algorithms where $\oplus$ denotes the exclusive-or, $|x|$ denotes the bit
size of message $x$ and $y||z$ the concatenation of $y$ with $z$:

APOgen(1^k): This algorithm generates (pk, sk) with Gen and returns it.

APOini(1^k): This algorithm picks three random values $\hat{\sigma} \stackrel{\$}{\leftarrow} \{0,1\}^k$, $\tilde{\sigma} \stackrel{\$}{\leftarrow} \{0,1\}^k$ and $K \stackrel{\$}{\leftarrow} \{0,1\}^k$ of the same size, and returns the state $\text{st} = (K || \hat{\sigma} || \tilde{\sigma})$.

APOenc<sub>pk</sub>(m): We note that $\text{st} = (K || \hat{\sigma}_N || \tilde{\sigma}_N)$. This algorithm picks a random $\hat{m}$ such that $|\hat{m}| = |m|$ and computes $\tilde{m} = \hat{m} \oplus m$. Let $\hat{\sigma} \stackrel{\$}{\leftarrow} \{0,1\}^k$ and $\tilde{\sigma} \stackrel{\$}{\leftarrow} \{0,1\}^k$ be two random values of size $|\hat{\sigma}_N|$. This algorithm computes $\hat{C} = \text{Enc}_{pk}(\hat{m} || (\hat{\sigma} \oplus \text{F}(\hat{\sigma}_N)); \text{G}(\hat{\sigma}_N))$ and $\tilde{C} = \text{Enc}_{pk}(\tilde{m} || (\tilde{\sigma}_N \oplus \text{F}(\tilde{\sigma})); \text{G}(\tilde{\sigma}))$. It also computes $D = (\hat{\sigma}_N || \tilde{\sigma}) \oplus \mathbf{H}(K || \hat{C} || \tilde{C})$. Finally it updates the state $\text{st}$ with $(K || \hat{\sigma} || \tilde{\sigma})$ and returns $C = (\hat{C} || \tilde{C} || D)$.

APOdec<sub>sk</sub>(C): The decryption algorithm computes the decryption of $\hat{m} || \hat{\sigma} =$ Dec<sub>sk</sub>(\hat{C}) and the decryption of $\tilde{m} || \tilde{\sigma} =$ Dec<sub>sk</sub>(\tilde{C}), where $C = (\hat{C} || \tilde{C} || D)$. It returns $m = \hat{m} \oplus \tilde{m}$.

APOext<sup>st</sup><sub>pko</sub>(C<sub>i</sub>, C<sub>j</sub>): Using the state st = (K || σ̂<sub>N</sub> || τ̂<sub>N</sub>), C<sub>i</sub> = (Ĉ<sub>i</sub> || Ĉ<sub>i</sub> || D<sub>i</sub>) and C<sub>j</sub> = (Ĉ<sub>j</sub> || Ĉ<sub>j</sub> || D<sub>j</sub>), this algorithm computes σ̂<sub>i-1</sub> || τ̂<sub>i</sub> = D<sub>i</sub> ⊕ H(K || Ĉ<sub>i</sub> || Ĉ<sub>i</sub>) and σ̂<sub>j-1</sub> || τ̂<sub>j</sub> = D<sub>j</sub> ⊕ H(K || Ĉ<sub>j</sub> || Ĉ<sub>j</sub>). It picks r ← R and returns K<sup>pko</sup><sub>i&rarr;j</sub> = Enc<sub>pko</sub>((σ̂<sub>i-1</sub> || τ̂<sub>j</sub>); r).

APOOpen<sub>sko</sub>(K<sup>pko</sup><sub>i&rarr;j</sub>, {(Ĉ<sub>x</sub> || Ĉ<sub>x</sub> || D<sub>x</sub>)}i&le;x&le;j, {pk<sub>x</sub>}i&le;x&le;j): This algorithm begins to recovering values σ̂<sub>i-1</sub> || τ̂<sub>j</sub> = Dec<sub>sko</sub>(K<sup>pko</sup><sub>i&rarr;j</sub>).

- For all $x$ in $\{i, i + 1, \dots, j\}$, it computes $\hat{R} = G(\hat{\sigma}_{x-1})$ and opens $\hat{C}_x$ as follows $\hat{m}_x || \hat{\sigma}_x^* = CDec_{\hat{R}}(\hat{C}_x, pk_x)$. It computes the next $\hat{\sigma}_x = \hat{\sigma}_x^* \oplus F(\hat{\sigma}_{x-1})$. If $Enc_{pk_x}((\hat{m}_x || \hat{\sigma}_x^*); G(\hat{\sigma}_{x-1})) \neq \hat{C}_x$ then it returns $\perp$.

- For all $x$ in $\{j, j - 1, \dots, i\}$, it computes $\tilde{R} = G(\tilde{\sigma}_x)$ and opens $\tilde{C}_x$ as follows $\tilde{m}_x || \tilde{\sigma}_{x-1}^* = CDec_{\tilde{R}}(\tilde{C}_x, pk_x)$. It computes the previous $\tilde{\sigma}_{x-1} = \tilde{\sigma}_{x-1}^* \oplus F(\tilde{\sigma}_x)$. If $Enc_{pk_x}((\tilde{m}_x || \tilde{\sigma}_{x-1}^*); G(\tilde{\sigma}_x)) \neq \tilde{C}_x$ then it returns $\perp$.

Finally, it returns {\hat{m}_x \oplus \tilde{m}_x}i \le x \le j.
The encryption algorithm APOenc separates the plaintext $m$ in two parts using xor operation such that $m = \hat{m} \oplus \tilde{m}$. We generate two random coins $\hat{\sigma}$ and $\tilde{\sigma}$. Using the two previous coins $\hat{\sigma}_N$ and $\tilde{\sigma}_N$ in the state st, we encrypt into two different ciphertexts $\hat{C}$ and $\tilde{C}$ the following two messages $\hat{m}||(\hat{\sigma} \oplus F(\hat{\sigma}_N))$ and $\tilde{m}||(\tilde{\sigma}_N \oplus F(\tilde{\sigma}))$. Finally we hide the usefull random elements with $H(K||\hat{C}||\tilde{C})$.

Knowing the secret key it is possible to recover $\hat{m}$ and $\tilde{m}$ and then to obtain the plaintext $m$ thanks to the algorithm APOdec.

An interval-key for the owner $O$ of a public key pko is constructed using the algorithm APOext. It is simply the encryption with pko of $\hat{\sigma}_N$ and $\tilde{\sigma}$. At each encryption, the values $\hat{\sigma}_{i-1}$ and $\tilde{\sigma}_i$ are masked by a "one time pad" with the digest $H(K||\hat{C}_i||\tilde{C}_i)$ in $D_i$. Then with the ciphertexts $C_i$, $C_j$ and the secret value $K$ we can construct an interval-key that contains these values $\hat{\sigma}_{i-1}$ and $\tilde{\sigma}_j$.

Using an interval-key $K_{i \to j}^{\text{pko}}$ it is possible to open all ciphertexts encrypted during an interval of time with the algorithm APOpen: thanks to the RCD property, someone who knows values $\hat{\sigma}_N$ and $\tilde{\sigma}$ for one ciphertext can open each part $\hat{C}$ and $\tilde{C}$ of it in order to recover $\hat{\sigma}$ and $\tilde{\sigma}_N$, and $\hat{m}$ and $\tilde{m}$, hence $m$. We also notice that with $\hat{\sigma}_i$ it is possible to decrypt all ciphertexts in $\{\hat{C}_x\}_{(i+1)\le x\le N}$. In the other hand, with $\tilde{\sigma}_j$ it is possible to decrypt all ciphertexts in $\{\tilde{C}_x\}_{1\le x\le j}$. Then it is possible to recover all messages between $C_i$ and $C_j$. Thus, it is possible to decrypt all messages between $C_i$ and $C_j$ with the knowledge of $\hat{\sigma}_{i-1}$ and $\tilde{\sigma}_j$.

If the interval always contains the first message, we give a more efficient algorithm. The idea is to only keep one part of the ciphertext, by consequence we do not need to split into two the message $m$. Hence the size of the ciphertext is smaller. Similarly if the algorithm always ends with the last encrypted message, we can also drop one half of the ciphertext and the tag value following the same idea. These simpler schemes are given in the full version of this paper [6].

# 4 Model and Security

We present the security properties of an APO-PKE scheme and we analyze the security of our G-APO scheme. The first security property corresponds to a chosen-plaintext attack scenario where the adversary has access to interval-keys on intervals that do not contain the challenge. We next introduce the notion of indistinguishability under chosen sequence of plaintext attack security (IND-CSPA) that corresponds to a chosen-plaintext attack scenario where the challenge is an interval of ciphertexts and the corresponding interval-key generated for a given judge public key. The last property is integrity, and captures the integrity of messages decrypted by APOpen algorithm. All security proofs are detailed in [6].

## 4.1 IND-CPA security

It concerns the resistance of an APO-PKE against a collusion of adversaries that have access to interval-keys in a chosen-plaintext attack scenario. For example, if
we consider a judge who receives an interval-key to open a sequence of ciphertexts and who colludes with ciphertext recipients; then it ensures that they cannot deduce any information about messages that are not in the sequence. Indeed, he cannot request an interval-key for an interval containing the challenge. We define the OT-IND-CPA security when only one interval-key can be asked during the experiment. Our scheme is proved secure in this model.

**Definition 5 (OT-IND-CPA experiment).** Let $\Pi$ be an APO-PKE, let $k$ be a security parameter, and let $\mathcal{A} = (\mathcal{A}_0, \mathcal{A}_1)$ be a pair of polynomial time algorithms. We define the one-time indistinguishability under interval opener chosen- plaintext attack (OT-IND-CPA) experiment as follows:

$\mathbf{Exp}_{\Pi, \mathcal{A}}^{\text{OT-IND-CPA}}(k):$

$$ 
\begin{aligned}
b & \leftarrow \{0, 1\} \\
(pk_*, sk_*) & \leftarrow \text{APOgen}(1^k) \\
st_* & \leftarrow \text{APOini}(1^k) \\
(m_0, m_1, \text{state}) & \leftarrow \mathcal{A}_0(1^k, pk_*) \\
C_* & \leftarrow \text{APOenc}_{pk_*}^{st_*}(m_b) \\
b' & \leftarrow \mathcal{A}_1(\text{state}, C_*) \\
\text{If } b = b' \text{ return } 1, \text{ else } 0
\end{aligned}
$$

The adversaries $\mathcal{A}_0$ and $\mathcal{A}_1$ have access to the following oracles:

$\mathcal{O}_{\text{enc}}^{\text{CPA}}$: On the first call to this oracle, it initializes the following values $l = 1$ and $n = 1$. This oracle takes as input a public key $pk$ and a message $m$. It returns $C_l = \text{APOenc}_{pk}^{st_l}(m)$. It increments the counter $l$. Only in the first phase, it increments the value $n$ that counts the number of calls to the encryption oracle before the generation of the challenge.

$\mathcal{O}_{\text{ext}}^{\text{CPA}}$: The adversary can ask this oracle only one time during the experiment. This oracle takes a public key $pk_o$ and two ciphertexts $C'_a$ and $C'_b$. In the second phase, if there exists $C_i = C'_a$ and $C_j = C'_b$ such that $i \le n \le j$ then the oracle rejects the query. Else, if $C'_a = C_n$ or $C'_b = C_n$, it rejects the query. Else it returns $\text{APOext}_{pk_o}^{st_o}(C'_a, C'_b)$.

We also define the IND-CPA experiment as the same as the OT-IND-CPA experiment except that the adversary can ask the oracle $\text{APOext}$ several times.

**Definition 6 (OT-IND-CPA advantage).** The advantage of the adversary $\mathcal{A}$ against OT-IND-CPA is defined by:

$$ \text{Adv}_{\Pi, \mathcal{A}}^{\text{OT-IND-CPA}}(k) = |\text{Pr}[\text{Exp}_{\Pi, \mathcal{A}}^{\text{OT-IND-CPA}}(k) = 1]| - \frac{1}{2} $$

We define the advantage on OT-IND-CPA experiment by:

$$ \text{Adv}_{\Pi}^{\text{OT-IND-CPA}}(k) = \max\{\text{Adv}_{\Pi, \mathcal{A}}^{\text{OT-IND-CPA}}(k)\} $$

for all $\mathcal{A} \in \text{POLY}(k)$. The advantages on IND-CPA experiment are similar to those of OT-IND-CPA. We say that a APO-PKE scheme $\Pi$ is OT-IND-CPA (resp. IND-CPA) secure when $\text{Adv}_{\Pi}^{\text{OT-IND-CPA}}(k)$ (resp. $\text{Adv}_{\Pi}^{\text{IND-CPA}}(k)$) is negligible.
Our construction is not IND-CPA since if a judge has two interval-keys for
two different intervals of time given by the same user and computed with the
same secret value then he can open all messages between the two extreme dates.

**Theorem 1.** Let $E$ be an IND-CPA secure RCD-PKE, then $G$-APO based on $E$ is OT-IND-CPA secure in the random oracle model.

*Proof idea:* To prove the OT-IND-CPA security, we show first that no polynomial adversary wins the experiment with non negligible probability using the oracle $O_{\text{ext}}^{\text{CPA}}$ in an interval of previous ciphertexts of the challenge. The interval-key allows to open the part $\tilde{C}_*$ of the challenge $C_*$, but since the PKE is IND-CPA then the interval-key gives no information about the part of the challenge encrypted in the part $\tilde{C}_*$. Similarly, we then prove that no adversary can win using the oracle in an interval of next ciphertexts of the challenge. Finally, using this two results, we show that our scheme is OT-IND-CPA in any case. $\square$

## 4.2 IND-CSPA security

A sequence of ciphertexts coupled with an interval-key can be seen as an unique ciphertext that encrypts a sequence of plaintexts because the open algorithm allows a judge to decrypt all the messages of the sequence with the knowledge of any secret key. Thus, we define a security model where the adversary must distinguish the sequence of plaintexts used to produce a challenge sequence of ciphertexts associated to an interval-key. The IND-CSPA security captures this security property. In this model, the adversary is a collusion of users that must distinguish the sequence of plaintexts used to produce a sequence of ciphertexts given the corresponding interval-key generated for the judge.

**Definition 7 (IND-CSPA<sub>φ</sub> experiment).** Let $\Pi$ be an APO-PKE, let $k$ be a security parameter, and let $\mathcal{A} = (\mathcal{A}_0, \mathcal{A}_1)$ be a pair of polynomial time algorithms. We define the indistinguishability under chosen sequence of plaintext attack (IND-CSPA<sub>φ</sub>) experiment as follows, where $n$ denotes the number of calls to the encryption oracle during the first phase and $\phi$ denotes the number of calls to the generation oracle:

$\mathbf{Exp}_{\Pi, \mathcal{A}}^{\text{IND-CSPA}_{\phi}}(k):$

$b, d \stackrel{s}{\leftarrow} \{0, 1\}$

$(pk_o, sk_o) \leftarrow \text{APOgen}(1^k)$

$st_* \leftarrow \text{APOini}(1^k)$

$(q, \{m_x^0\}_{n<x \le n+q}, \{m_x^1\}_{n<x \le n+q}, \{pk_x\}_{n<x \le n+q}, \text{state}) \leftarrow \mathcal{A}_0(1^k, pk_o)$

$\forall x \in \{n+1, n+2, \dots, n+q\}:$

if $pk_x$ comes from $O_{\text{gen}}^{\text{CSPA}}$ then $C_x^* = \text{APOenc}_{pk_x}^{st_*}(m_x^b)$

else, $C_x^* = \text{APOenc}_{pk_x}^{st_*}(m_x^d)$

$K_{(n+1) \rightarrow (n+q)}^{pk_o} \leftarrow \text{APOext}_{pk_o}^{st_*}(C_{n+1}, C_{n+q})$

$b' \leftarrow \mathcal{A}_1(\text{state}, \{C_x^*\}_{n<x \le n+q}, K_{(n+1) \rightarrow (n+q)}^{pk_o})$

If $b = b'$ return 1, else 0
The adversaries $\mathcal{A}_0$ and $\mathcal{A}_1$ have access to the following oracles:

$\mathcal{O}_{\text{gen}}^{\text{CSPA}}$: At the first call, the oracle creates a keys' list $K$ that contains $(\text{pko}_*, \text{sko}_*)$. At each call, it generates values $(\text{pk}, \text{sk})$ from $\text{APOgen}(1^k)$ and adds it to $K$. Then it returns $\text{pk}$. This oracle can be called only $\phi$ times.

$\mathcal{O}_{\text{enc}}^{\text{CSPA}}$: This oracle takes as inputs a public key $\text{pk}$ and a message $m$. Only in the first phase, it increments the value $n$ that counts the number of calls to the encryption oracle before the generation of the challenge. In the two phases, it returns $\text{APOenc}_{\text{pk}}^{\text{st}_*}(m)$.

$\mathcal{O}_{\text{ext}}^{\text{CSPA}}$: This oracle takes as input two ciphertexts $C_i$ and $C_j$. It returns the interval-key $K_{i \to j}^{\text{pko}_*} = \text{APOext}_{\text{pko}_*}^{\text{st}_*}(C_i, C_j)$.

In the first phase The challenger generates $(\text{pko}_*, \text{sko}_*)$ from $\text{APOgen}(1^k)$ and a state $\text{st}_*$ from $\text{APOini}(1^k)$. He sends the public key $\text{pko}_*$ to the adversary. The challenger initializes a counter $n$ that counts number of calls to the oracle $\mathcal{O}_{\text{enc}}^{\text{CSPA}}$ during this phase. Finally, the adversary sends to the challenger values $(q, \{m_x^0\}_{n<x\le(n+q)}, \{m_x^1\}_{n<x\le(n+q)}, \{\text{pk}_x\}_{n<x\le n+q}, \text{state})$.

In second phase, the challenger computes a sequence of ciphertexts from the adversary's output. He encrypts messages of one of the two sequences. The sequence of produced ciphertexts forms the challenge. More formally, the challenger picks two random bits $b$ and $d$. Then, $\forall x \in \{n+1, n+2, ..., n+q\}$, if $\text{pk}_x$ corresponds to an honest user (i.e. $\text{pk}_x$ comes from oracle $\mathcal{O}_{\text{gen}}^{\text{CSPA}}$) then he computes $C_x^* = \text{APOenc}_{\text{pk}_x}^{\text{st}_*}(m_x^b)$ else if $\text{pk}_x$ corresponds to a dishonest user (i.e. $\text{pk}_x$ comes from the adversary), he computes $C_x^* = \text{APOenc}_{\text{pk}_x}^{\text{st}_*}(m_x^d)$. Finally, he computes $K_{(n+1) \to (n+q)}^{\text{pko}_*} = \text{APOext}_{\text{pko}_*}^{\text{st}_*}(C_{n+1}, C_{n+q})$ and he sends $(\text{state}, \{C_x^*\}_{n<x\le(n+q)}, K_{(n+1) \to (n+q)}^{\text{pko}_*})$ to the adversary $\mathcal{A}_1$. During the guess phase, the adversary returns the bit $b'$. If $b' = b$ then $\mathcal{A}$ wins.

**Definition 8 (IND-CSPA advantage).** We define the advantage of $\mathcal{A}$ against IND-CSPA by:

$$ \text{Adv}_{\Pi, \mathcal{A}}^{\text{IND-CSPA}_{\phi}}(k) = |\text{Pr}[\text{Exp}_{\Pi, \mathcal{A}}^{\text{IND-CSPA}_{\phi}}(k) = 1] - \frac{1}{2}| $$

We define by:

$$ \text{Adv}_{\Pi}^{\text{IND-CSPA}_{\phi}}(k) = \max\{\text{Adv}_{\Pi, \mathcal{A}}^{\text{IND-CSPA}_{\phi}}(k)\} $$

for all $\mathcal{A} \in \text{POLY}(k)$ the advantage on IND-CSPA. We say that an APO-PKE scheme $\Pi$ is IND-CSPA secure when the advantage $\text{Adv}_{\Pi}^{\text{IND-CSPA}_{\phi}}(k)$ is negligible for any polynomial $\phi$.

**Theorem 2.** Let $E$ be a PKE that is RCD, then G-APO using $E$ is IND-CSPA secure in the random oracle model.
*Proof idea:* In [2] authors prove that any IND-CPA PKE is still secure in multi-user setting, i.e. where the adversary can ask several challenges for several different public keys. Without interval-key oracle, the IND-CSPA security of our scheme can be reduced to the IND-CPA of the PKE in multi-user setting since the challenge corresponds to ciphertexts of several messages from several public keys. Moreover, since the interval-keys from the oracle are encrypted, then the adversary must break the IND-CPA security of PKE to use it. It is possible to prove that no adversary can efficiently break the IND-CSPA of our scheme using these two arguments. □

## 4.3 Integrity

The last security property for APO-PKE is the *integrity*. This property is similar to *binding* property of TRE defined in [11]. The judge must be sure that the messages he decrypts with APOpen algorithm are the sent messages.

**Definition 9 (Integrity experiment).** Let $\Pi$ a APO-PKE, let $k$ be a security parameter, and let $\mathcal{A}$ a polynomial time algorithm. We define the integrity experiment as follows:

$$ \begin{array}{l} \text{Exp}^{\text{Integrity}}(k): \\ (\text{pko}_*, \text{sko}_*) \leftarrow \text{APOgen}(1^k) \\ (N, \{C_x\}_{1 \le x \le N}, \{pk_x\}_{1 \le x \le N}, l, \text{sk}_l, i, j, K_{i \to j}^{\text{pko}_*}) \leftarrow \mathcal{A}(1^k, pk_*) \\ \text{if } (pk_l, \text{sk}_l) \text{ is not a valid key pair then return } 0 \\ \{m_x\}_{i \le x \le j} \leftarrow \text{APOpen}_{\text{sko}_*}(K_{i \to j}^{\text{pko}_*}, \{C_x\}_{i \le x \le j}, \{pk_x\}_{i \le x \le j}) \\ \text{if } m_l \neq \text{APOdec}_{\text{sk}_l}(C_l) \text{ then return } 1, \text{ else } 0. \end{array} $$

The challenger generates $(\text{pko}_*, \text{sko}_*)$ from $\text{APOgen}(1^k)$ and sends the public key $\text{pko}_*$ to the adversary. The adversary $\mathcal{A}$ sends to the challenger an integer $N$, an ordered set of $N$ ciphertexts $\{C_x\}_{1 \le x \le N}$ and an ordered set of $N$ public keys $\{pk_x\}_{1 \le x \le N}$. The adversary then sends two integers $i$ and $j$ and the corresponding interval-key $K_{i \to j}^{\text{pko}_*}$. He finally sends the integer $l$ and the secret key $\text{sk}_l$ corresponding to $pk_l$. If $(pk_l, \text{sk}_l)$ is not a valid key pair then the challenger aborts and returns 0. The challenger then computes $\{m_x\}_{i \le x \le j} \leftarrow \text{APOpen}_{\text{sko}_*}(K_{i \to j}^{\text{pko}_*}, \{C_x\}_{i \le x \le j}, \{pk_x\}_{i \le x \le j})$. If $m_l \neq \text{APOdec}_{\text{sk}_l}(C_l)$ then the challenger returns 1, else he returns 0.

**Definition 10.** The advantage of $\mathcal{A}$ against integrity is defined by:

$$ \text{Adv}_{\Pi, \mathcal{A}}^{\text{Integrity}}(k) = \Pr[\text{Exp}_{\Pi, \mathcal{A}}^{\text{Integrity}}(k) = 1] $$

The advantage against integrity by:

$$ \text{Adv}_{\Pi}^{\text{Integrity}}(k) = \max\{\text{Adv}_{\Pi, \mathcal{A}}^{\text{Integrity}}(k)\} $$

for all $\mathcal{A} \in \text{POLY}(k)$. We say that a APO-PKE scheme $\Pi$ satisfies the integrity property $\text{Adv}_{\Pi}^{\text{Integrity}}(k)$ is negligible.

**Theorem 3.** Let $E$ be a RCD and VK PKE that is IND-CPA secure, then G-APO using this PKE satisfies the integrity property.
*Proof idea:* Since the judge has all the random coins and all the public keys used to encrypt all the opened messages, he can use them to re-encrypt these messages. Thus, if the ciphertexts that he opens correspond to the ciphertexts that he encrypts by himself, then he can conclude that the opened messages are the same as the messages decrypted by the recipient secret keys. □

## 5 Conclusion

We introduce the notion of RCD-PKE. Based on this notion, we propose an *a posteriori* openable PKE (APO-PKE) scheme. Our scheme allows a user to prove his innocence by showing to a judge the content of his encrypted communication with several PKE during a period of time. Our construction preserves the privacy of the others communications, meaning that the judge cannot learn any information concerning the other encrypted messages. Moreover the receivers of the encrypted messages cannot collude in order to learn more information that is contained in the received messages. Our construction is proven secure in the Random Oracle Model and is generic because it only requires RCD-PKE and hash functions.

In the future, we aim at proving that is not possible to have a secure construction that supports several generations of interval key with constant size interval-key and stored data (state). Another future work is to design a security model for chosen-ciphertext security of APO-PKE and to provide a generic construction that achieves this higher security. Finally, it may be interesting to design such a scheme in the standard model.

## References

1. M. Abdalla, M. Bellare, and P. Rogaway. DHIES: an encryption scheme based on the Diffie-Hellman problem. Contributions to IEEE P1363a, Sept. 1998.

2. M. Bellare, A. Boldyreva, and S. Micali. Public-key encryption in a multi-user setting: Security proofs and improvements. In B. Preneel, editor, *EUROCRYPT 2000*, volume 1807 of LNCS, pages 259–274. Springer, May 2000.

3. I. F. Blake and A. C.-F. Chan. Scalable, server-passive, user-anonymous timed release public key encryption from bilinear pairing. ICDS, IEEE Computer Society Press, 2005.

4. D. Boneh and M. K. Franklin. Identity-based encryption from the Weil pairing. In J. Kilian, editor, *CRYPTO 2001*, volume 2139 of LNCS, pages 213–229. Springer, 2001.

5. D. Boneh, A. Sahai, and B. Waters. Functional encryption: Definitions and challenges. In Y. Ishai, editor, *TCC 2011*, volume 6597 of LNCS, pages 253–273. Springer, Mar. 2011.

6. X. Bultel and P. Lafourcade. A posteriori openable public key encryption. Technical report, University Clermont Auvergne, LIMOS, 2015. http://sancy.univ-bpclermont.fr/~lafourcade/APOPKE.pdf.

7. R. Canetti, C. Dwork, M. Naor, and R. Ostrovsky. Deniable encryption. In *CRYPTO'97*, volume 1294 of LNCS, pages 90–104. Springer, 1997.
8. J. Cathalo, B. Libert, and J.-J. Quisquater. Efficient and non-interactive timed-release encryption. In *ICICS 05*, volume 3783 of LNCS, pages 291–303. Springer, 2005.

9. J. H. Cheon, N. Hopper, Y. Kim, and I. Osipkov. Timed-release and key-insulated public key encryption. In G. Di Crescenzo and A. Rubin, editors, *FC 2006*, volume 4107 of LNCS, pages 191–205. Springer, Feb. / Mar. 2006.

10. R. Cramer and V. Shoup. Design and analysis of practical public-key encryption schemes secure against adaptive chosen ciphertext attack. *SIAM Journal on Computing*, 33(1):167–226, 2003.

11. A. W. Dent and Q. Tang. Revisiting the security model for timed-release encryption with pre-open capability. In J. A. Garay, A. K. Lenstra, M. Mambo, and R. Peralta, editors, *ISC 2007*, volume 4779 of LNCS, pages 158–174. Springer, Oct. 2007.

12. Y. Dodis, J. Katz, S. Xu, and M. Yung. Key-insulated public key cryptosystems. In *EUROCRYPT 2002*, volume 2332 of LNCS, pages 65–82. Springer, 2002.

13. T. ElGamal. A public key cryptosystem and a signature scheme based on discrete logarithms. *IEEE Transactions on Information Theory*, 31:469–472, 1985.

14. E. Fujisaki and T. Okamoto. Secure integration of asymmetric and symmetric encryption schemes. *Journal of Cryptology*, 26(1):80–101, 2013.

15. D. Galindoa and J. Herranz. On the security of public key cryptosystems with a double decryption mechanism. *Information Processing Letters*, 108(5):279–283, Nov. 2008.

16. O. Goldreich, B. Pfitzmann, and R. L. Rivest. Self-delegation with controlled propagation - or - what if you lose your laptop. In H. Krawczyk, editor, *CRYPTO'98*, volume 1462 of LNCS, pages 153–168. Springer, Aug. 1998.

17. S. Goldwasser, Y. T. Kalai, R. A. Popa, V. Vaikuntanathan, and N. Zeldovich. How to run turing machines on encrypted data. In *CRYPTO 2013*, volume 8043 of LNCS, pages 536–553. Springer, 2013.

18. S. Goldwasser, Y. T. Kalai, R. A. Popa, V. Vaikuntanathan, and N. Zeldovich. Reusable garbled circuits and succinct functional encryption. In *45th ACM STOC*, pages 555–564. ACM Press, 2013.

19. S. Goldwasser and S. Micali. Probabilistic encryption. *Journal of Computer and System Sciences*, 28(2):270–299, 1984.

20. G. Hanaoka and J. Weng. Generic constructions of parallel key-insulated encryption. In *SCN'10*, volume 6280, pages 36–53, 2010.

21. Y. H. Hwang, D. H. Yum, and P. J. Lee. Timed-release encryption with pre-open capability and its application to certified e-mail system. In *ISC 2005*, volume 3650 of LNCS, pages 344–358. Springer, 2005.

22. M. Klonowski, P. Kubiak, and M. Kutyłowski. Practical deniable encryption. In *SOFSEM 2008: Theory and Practice of Computer Science*, volume 5805 of LNCS, pages 599–609. Springer, 2008.

23. B. Libert, J.-J. Quisquater, and M. Yung. Parallel key-insulated public key encryption without random oracles. In T. Okamoto and X. Wang, editors, *PKC 2007*, volume 4450 of LNCS, pages 298–314. Springer, Apr. 2007.

24. T. May. Time-release crypto. Manuscript, 1993.

25. K. G. Paterson and E. A. Quaglia. Time-specific encryption. In *SCN'10*, volume 6280, pages 1–16, 2010.

26. A. Sahai and B. R. Waters. Fuzzy identity-based encryption. In R. Cramer, editor, *EUROCRYPT 2005*, volume 3494 of LNCS, pages 457–473. Springer, May 2005.

27. A. Whitten and J. D. Tygar. Why johnny can't encrypt: A usability evaluation of pgp 5.0. In *Proceedings of the 8th Conference on USENIX Security Symposium - Volume 8*, SSYM'99, pages 14–14, Berkeley, CA, USA, 1999. USENIX Association.