A conceptually simple and generic construction of plaintext checkable encryption in the standard model

Abstract

Plaintext-checkable encryption (PCE) can support searches over ciphertext by directly using plaintext. The functionality of a search is modeled by a specific check algorithm that takes a pair of target plaintext and ciphertext as input and returns 1 if the correct decryption result of the ciphertext is identical to the target plaintext. A trivial solution is to use an existing scheme (e.g., deterministic RSA) to achieve this, but there is no security guarantee with this method. Previous rigorous works have either relied on some mathematical structures to build PCE that can proven in the standard model or can be generic, as in the random oracle model. Hence, in this work, we aim to construct PCE that can be proven in the standard model by using standard primitives in a modular way in two steps. The first step is to present a warm-up construction of PCE from hash garbling and hash functions whose security is only proven in the random oracle model. The second step is to provide a full-fledged construction based on the warm-up, with slight modifications for achieving security in the standard model. Finally, we show the feasibility of the proposed construction through experiments.

1 Introduction

Recently, big data analysis techniques have been introduced with cloud aid, as such an overwhelming cost cannot be absorbed by personal computers. Many information technologies and cloud service providers have developed cloud computing applications and platforms. Indeed, the analytics offered by cloud computing from users’ data may help predict their potential activities. However, it is expected to protect some sensitive data with privacy and security concerns, which implies two kinds of issues: privacy and confidentiality. Differential privacy (DP) [8] is a method for quantifying the individual’s privacy for queries on a dataset. However, unlike DP, cryptographic solutions aim for confidentiality (e.g., encryption) and usually handle computing over ciphertext.

Plaintext checkable encryption (PCE) can provide simple functionality between ciphertext and plaintext. The concept of PCE was first introduced by [3] and provides a special check algorithm (denoted by $\textsf {Check}$). This algorithm takes target plaintext, ciphertext, and a public key as input, and then outputs correct if the ciphertext is an encryption of the target plaintext with the same public key. In real-life applications, the following scenario can be reached by using PCE. Let us take semi-honest¹ cloud storage into account. A user can upload encrypted data associated with some ciphertexts of tags $\textsf {Enc}(t)$ to a server. A search request is a plain tag $t'$. Once the server receives $t'$, it can run $\textsf {Check}$ whether the underlying tag of $\textsf {Enc}(t)$ is identical to the request $t'$. Returns the corresponding encrypted data whose encrypted tag is $\textsf {Enc}(t)$ if $\textsf {Check}(\textsf {Enc}(t),t')$ returns 1 such that $t=t'$.

PCE was rooted by Canard et al. [3]. Its basic security model is called unlinkable CPA security. In a sense, PCE makes it impossible to meet general CPA security, as the adversary can always access the check algorithm. In unlinkable CPA security, two unlinked adversaries are decoupled to perform the typical CPA game. The follow-up work of Ma et al. [17] formalized the other security notion, s-priv1-cca security, independent of unlinkable CPA security. In addition, they also presented a generic construction of PCE, and applied smooth projective hash as the underlying assumptions. The follow-up works [15, 16] provides a generic construction based on pairing-friendly smooth projective hash functions. They also provide instantiations from k-MDDH and SXDH assumptions, respectively. In particular, [16] is the first scheme offering verifiably.

Das et al. [5] modified the framework of PCE for partially to achieve CPA security. Their framework only allows the designated checker (who has been delegated check power) to run $\textsf {Check}$. However, if the adversary is the designed checker, the security is at most unlinkable CPA. Recently, Chen [4] revisited the security notion of PCE and presented a few possible security models and improvements. However, Chen did not aim to construct a pure PCE scheme.

1.1 Contributions

Our motivation comes from underlying assumptions [17] that rely on some mathematical structures (smooth projective hash), while [3] only gave generic constructions in the random oracle model. In this paper, we use standard cryptographic primitives to build a PCE scheme that can be proven in the standard model. To achieve this, we use two phases: the first is building an intermediate notion called the hash garbling (HG) scheme, and the other is building generic constructions of PCE from HG and conventional public key encryption (PKE). The details of our design principles, challenges, and techniques are elaborated as follows.

1.1.1 Initial idea for constructing PCE

We want to provide a conceptually simple and generic manner to construct a PCE scheme. Our first attempt keeps the decryption correctness by applying the traditional PKE and then developing an extra, special component (in a ciphertext) that can be used to provide plaintext checkability. Suppose we have a program obfuscation $\mathcal {O}$ [1, 10, 11, 13] that can convert program P into ${\widetilde{P}}$. ${\widetilde{P}}$ preserves the functionality of P such that for an input $x, {\widetilde{P}}(x) = P(x)$ but does not reveal additional information about the code of P. We can prepare a program P that takes a test plaintext M as input and outputs 1 if M is identical to the underlying plaintext of the ciphertext. Our ciphertext is composed of $(\textsf {Enc}(M),{\widetilde{P}})$, where ${\widetilde{P}}$ is as above and $\textsf {Enc}$ is the encryption algorithm of PKE. Unfortunately, obfuscation has been referred to as a non-standard primitive until now, as there is no secure construction based on standard assumptions. This fact forces us to choose the other candidate to realize the special component.

Table 1 Comparisons

1.1.2 Candidate building block: hash garbling

Recently, hash garbling (HG) [12] has been proposed to provide some properties similar to those of obfuscation. HG is somewhat similar to garbled circuits (GCs). In general, HG consists of a few main algorithms $\textsf {Hash},\textsf {HObf},\textsf {HInp}$. $\textsf {Hash}$ is similar to the usual hash function, taking a long input x to return a short output y. $\textsf {HObf}$ is identical to GC, aiming to produce some state information and the GC ${\widetilde{P}}$ from P. In particular, $\textsf {HInp}$ takes the state and y to output ${\widetilde{y}}$. However, we need an evaluation that given $x,{\widetilde{y}}, {\widetilde{P}}$ returns P(x). Note that $\textsf {HInp}$ does not have any knowledge of the pre-image x, and the evaluation must know x. We present a construction of HG from hash encryption (HE) and GCs, and then prove its simulation security (a.k.a $\langle x,{\widetilde{P}}, {\widetilde{y}} \rangle$ $\approx \langle \textsf {Sim}(x, P(x)) \rangle$ informally).

1.1.3 Overview of our warm-up construction: techniques and challenges

Our final goal is to use HG (with PKE) to build the PCE construction. We follow our initial idea to replace obfuscation with HG. For a clear presentation, let us focus on producing the special component in the ciphertext. At first, it is necessary to prepare a program P that hardwires the plaintext m and returns 1 if its input is identical m. The PCE encryption will generate $\textsf {Enc}(m), {\widetilde{P}}$, and ${\widetilde{y}}$, whose condition on $y=\textsf {Hash}(m)$. The PCE decryption directly runs $\textsf {Dec}$ of PKE, and $\textsf {Check}$ of PCE relies on evaluation with $m', {\widetilde{P}}$, and ${\widetilde{y}}$ for some test plaintext $m'$. The above-mentioned construction provides checkability but faces a challenge in proving its security. By simulating the security of HG, we can obtain that $\langle \textsf {Enc}(m_\beta ), {\widetilde{P}}_{m_\beta }, \widetilde{y}_{m_\beta } \rangle$ is computationally indistinguishable from $\langle \textsf {Enc}(m_\beta ), {\widetilde{P}}_{\textsf {Sim},m_\beta }, \widetilde{y}_{\textsf {Sim},m_\beta } \rangle$, where ${\widetilde{P}}_{\textsf {Sim},m_\beta }, {\widetilde{y}}_{\textsf {Sim},m_\beta }$ are simulated. However, we cannot directly use the CPA-security of PKE to switch $\textsf {Enc}(m_0)$ to $\textsf {Enc}(m_1)$, as ${\widetilde{P}}_{\textsf {Sim},m_\beta }, \widetilde{y}_{\textsf {Sim},m_\beta }$ depend on $m_\beta$. To overcome this dependency, the encryption algorithm of PCE randomly chooses a number r and returns $({\widetilde{y}}', r)$ instead of ${\widetilde{y}}$, where ${\widetilde{y}}' = H(m||r)\oplus {\widetilde{y}}$ with the other hash function H. Let us go back the proof. According to the slight modification, it suffices to obtain $\langle \textsf {Enc}(m_\beta ), {\widetilde{P}}_{\textsf {Sim},m_\beta }, H(m||r)\oplus \widetilde{y}_{\textsf {Sim},m_\beta }, r \rangle \approx \langle \textsf {Enc}(m_\beta ), U_{|{\widetilde{P}}| + |{\widetilde{y}}| + |r|} \rangle$ in the random oracle model, where the uniform is denoted by U. The security proof can go through by PKE security to switch $\langle \textsf {Enc}(m_0), U_{|{\widetilde{P}} + {\widetilde{y}}|} \rangle$ to $\langle \textsf {Enc}(m_1), U_{|{\widetilde{P}} + {\widetilde{y}}|} \rangle$.

1.1.4 Construction in the standard model

The above solution is generic and modular but still in the random oracle model. In other words, it achieves the same security as the schemes of [3]. However, this suffices to slightly modify the warm-up construction to a full-fledged one that can be proven in the standard model. Before we show the modification, let us introduce another property of HG: so-called blindness [12]. In an HG scheme, blindness means $\langle {\widetilde{P}}_{\textsf {Sim}}, {\widetilde{y}}_{\textsf {Sim}} \rangle \approx \langle U_{|{\widetilde{P}} + {\widetilde{y}}|}\rangle$ when P(x) is uniform. This property inspires us to modify the circuit P in the warm-up, and then we avoid using the random oracle to remedy our proof. Our full-fledged construction includes two slight modifications. One is to set P as a pseudorandom generator [2] that can make P(x) close to uniform, and the other is to verify the evaluation of $(x, {\widetilde{P}}, {\widetilde{y}})$ in $\textsf {Check}$. Recall the security proof where $\langle \textsf {Enc}(m_\beta ), {\widetilde{P}}_{\textsf {Sim},m_\beta }, {\widetilde{y}}_{\textsf {Sim},m_\beta }\rangle \approx \langle \textsf {Enc}(m_\beta ), U_{|{\widetilde{P}}| + |{\widetilde{y}}|} \rangle$ can be directly achieved without the random oracle model. Finally, we need to emphasize that this solution involves the non-black-box use of one-way functions, as the HG must know the codes of pseudorandom generators. Questions of how to use the primitives on the black box will be the subject of our future work on PCE proven in the standard model.

To summarize the results, we briefly compare our schemes with the existing ones in Table 1. All of the schemes satisfy the syntax of PCE, which implies that they can be used to reach the same above-mentioned applications. We do not show any comparison on efficiency, as our schemes may be slower than previous ones (depending on the underlying primitives). The value of our proposal is related to the module construction and its security in the standard model. In practical implementations, the underlying HG may require more space and computation cost (proportional to the program complexity) than the use of a bilinear map. However, our construction is generic and offers flexibility for using the primitive; for example, it can be made up of post-quantum cryptographic building blocks against quantum computers.

1.2 Organization

The rest of this paper is organized as follows. In Sect. 2, we introduce cryptography tools and their definitions of security, which will be used throughout this paper. In Sect. 3, we first build a hash garbling scheme and then prove its security based on $\textsf {HE}$ and the GC. In Sect. 4, a warm-up and a non-black-box PCE construction are presented with their security analysis. In Sect. 5, we provide the experiments for implementing our constructions. Finally, Sect. 6 provides the conclusion of this paper.

2 Preliminaries

Prior to presenting the preliminaries, we must state a few notations used in this paper. Let n be the security parameter. We say that for a negligible function $\textsf {negl}$ for any polynomial function P(n) that satisfies an n that is sufficiently large, $\textsf {negl}(n)\le \frac{1}{P(n)}$ holds. For a probabilistic polynomial time algorithm $\mathcal {D}$ with security parameter n, we define $|Pr\left[ \mathcal {D}(X)=1 \right] -Pr\left[ \mathcal {D}(X')=1 \right] \le \textsf {negl}(n)$ such that X is indistinguishable from $X'$. This is also denoted by $\langle X \rangle \overset{c}{\approx }\ \langle X' \rangle$ as indistinguishability on distribution.

2.1 Public key encryption (PKE)

A PKE scheme consists of three polynomial time algorithms: $\textsf {PKE}=(\textsf {Gen},\textsf {Enc},\textsf {Dec})$.

• $\textsf {Gen}(1^{n})$: It takes as input the security parameter n and outputs a pair of keys (pk, sk).

• $\textsf {Enc}(pk,m)$: It takes as input a public key pk and a message m, and outputs a ciphertext c.

• $\textsf {Dec}(sk,c)$: It takes as input a secret key sk and a ciphertext c, and outputs a message or $\perp$.

Definition 1

(Security of PKE) If a $\textsf {PKE}$ scheme is a chosen plaintext attack (CPA) that is secure against any probabilistic polynomial-time (PPT) algorithm $\mathcal {A}$, then we use $Exp_{\mathcal {A},\textsf {PKE}}^{CPA}(n)$ security to quantify that for every PPT algorithm $\mathcal {A}$, for all n and any equal length of plaintext input, we have

$$\begin{aligned} Pr\left[ Exp_{\mathcal {A},\textsf {PKE}}^{CPA}(n)\right]= & {} \left| Pr\left[ \mathcal {A}(pk,m_0,m_1,{C}_{m_0})=1 \right] -Pr\left[ \mathcal {A}(pk,m_0,m_1,{C}_{m_1})=1 \right] \right| \\\le & {} \textsf {negl}(n), \end{aligned}$$

where $\{m_0,m_1\}\overset{\$}{\leftarrow }\mathcal {M},pk\leftarrow \textsf {Gen}(1^{n}),{C}_{m_b}\leftarrow \textsf {Enc}(pk,m_b)$. We define the advantage of any algorithm $\mathcal {A}$ as the difference of probabilities above. The above formulation is also identical to $\langle pk,m_0,m_1,{C}_{m_0} \rangle \overset{c}{\approx }\ \langle pk,m_0,m_1,{C}_{m_1} \rangle$.

2.2 Plaintext checkable encryption (PCE)

A plaintext checkable encryption (PCE) [3, 4] scheme, $\textsf {PCE}$, is composed of four polynomial time algorithms. Formally, let $\textsf {PCE}=(\textsf {Gen},\textsf {Enc},\textsf {Dec},\textsf {Check})$.

• $\textsf {Gen}(1^{n})$: Given the security parameter n, it returns a pair of keys (pk, sk).

• $\textsf {Enc}(pk,m)$: Given a public key pk and a message m, it returns a ciphertext c.

• $\textsf {Dec}(sk,c)$: Given a secret key sk and a ciphertext c, it returns a message or $\perp$.

• $\textsf {Check}(pk,m,c)$: Given the public key pk, a message m, and a ciphertext c, it returns 1 if c is an encryption of m, or returns 0 if not.

Definition 2

(Security of PCE) A $\textsf {PCE}$ scheme is unlinkable CPA secure against any probabilistic polynomial time adversaries $\mathcal {A}$, which was described by [3]. Here, we use $Exp_{\mathcal {A},\textsf {PCE}}^{unlink}(n)$ security to quantify that for every PPT algorithm $\mathcal {A}$ for all n and any equal length of plaintext input:

$$\begin{aligned} Pr\left[ Exp_{\mathcal {A},\textsf {PCE}}^{unlink}(n)\right]= & {} \left| Pr\left[ \mathcal {A}(pk,{C}_{m_0})=1 \right] -Pr\left[ \mathcal {A}(pk,{C}_{m_1})=1 \right] \right| \\\le & {} \textsf {negl}(n), \end{aligned}$$

where $\{m_0,m_1\}\overset{\$}{\leftarrow }\mathcal {M},pk \leftarrow \textsf {Gen}(1^{n}),{C}_{m_b}\leftarrow \textsf {Enc}(pk,m_b).$ Note that there is no input m in unlinkable CPA security. We define the advantage of any algorithm $\mathcal {A}$ as the difference of the probabilities above.

2.3 Garble circuit

A projective circuit garbling (GC) [14, 19] scheme consists of three polynomial time algorithms, where $\textsf {GC}=(\textsf {Garble},\textsf {GarbleInp},\textsf {Eval}).$

• $\textsf {Garble}(1^{n},C)$: This takes as input a security n and a circuit C, and then outputs a GC $\widetilde{C}$ and labels $e_C=\{ X_{ l ,0},X_{ l ,1}\}_{ l \in [k] }$, where k is the number of input wires of C.

• $\textsf {GarbleInp}(e_C,x)$: This encodes an $x\in \{0,1\}^{k}$ with the input labels $e_C=\{ X_{ l ,0},X_{ l ,1}\}_{ l \in [k] }$ and outputs $\widetilde{x}\leftarrow \{X_{ l ,X_{ l }}\}_{ l \in [k]}$.

• $\textsf {Eval}(\widetilde{C},$ $\widetilde{x})$: This takes as input a GC $\widetilde{C},$ and as a garbled input $\widetilde{x}$, and outputs $\delta$.

Definition 3

(Correctness of GC) For any circuit C and input $x\in \{0,1\}^{k}$, the correctness is implied by

$$\begin{aligned} Pr \left[ \textsf {Eval}(\widetilde{C},\widetilde{x})=C(x) \right] =1, \end{aligned}$$

where $(\widetilde{C},e_c=\{X_{ l ,0},X_{ l ,1}\})$ $\overset{\$}{\leftarrow }\textsf {Garble}(1^{n},C)$ and $\widetilde{x}$ $\leftarrow \textsf {GarbleInp}(e_C,x)$.

Definition 4

(Security of GC) There exists a PPT simulator $\textsf {Sim}$ such that for any circuit C and any input x, we have

$$\begin{aligned} \langle \widetilde{C},\widetilde{x}\rangle \overset{c}{\approx }\langle \textsf {Sim}(1^{n},C(x))\rangle , \end{aligned}$$

(1)

where $(\widetilde{C},e_c=\{X_{ l ,0},X_{ l ,1}\})$ $\overset{\$ }{\leftarrow }\textsf {Garble}(1^{n},C)$ and $\widetilde{x}\leftarrow \textsf {GarbleInp}(e_C,x)$.

More generally, we use $Exp_{\mathcal {A},\textsf {GC}}^{IND}(n)$ security to quantify that for every PPT algorithm $\mathcal {A}$, the Eq. (1) is computationally indistinguishable, so we have

$$\begin{aligned} Pr\left[ Exp_{\mathcal {A},\textsf {GC}}^{IND}(n)\right]= & {} \left| Pr\left[ \mathcal {A}(\widetilde{C},\widetilde{x})=1\right] -Pr\left[ \mathcal {A}(\textsf {Sim}(1^{n},C(x)))=1\right] \right| \\\le & {} \textsf {negl}(n). \end{aligned}$$

Definition 5

(Blindness) The blindness is

$$\begin{aligned} \langle \textsf {Sim}(1^{n},C(x)) \rangle \overset{c}{\approx }\ \langle U_{|C(x)|} \rangle . \end{aligned}$$

The output of the simulator on a completely uniform output is indistinguishable from a uniform bit string.

2.4 Hash encryption (HE)

An HE [7] scheme consists of four polynomial time algorithms: $\textsf {HE}=(\textsf {Gen},\textsf {Hash},\textsf {Enc},$ and $\textsf {Dec})$.

• $\textsf {Gen}(1^{n},m)$: This takes as input the security parameter n and an input length m, and outputs a key k.

• $\textsf {Hash}(k,x)$: This takes as input a key k and an input $x \in \{0, 1\}^{m}$, and outputs a hash value h of n bits.

• $\textsf {Enc}(k,(h,i,c),m)$: This takes as input a key k, a hash value h, an index $i\in \left[ m\right] , c\in \{0,1\}$ and a message $m, \in \{0,1\}^{*}$ and outputs a ciphertext ct. We generally assume that the index i and the bit c are included alongside.

• $\textsf {Dec}(k,x,ct)$: This takes as inputs a key k, an input x, and a ciphertext ct, and outputs a value $m\in \{0,1\}^{*}$ or $\perp$.

Definition 6

(Correctness of HE) For any input $x\in \{0,1\}^{m},$ index $i\in \left[ m\right]$, the correctness is implied by

$$\begin{aligned} Pr \left[ \textsf {Dec}(k,x,\textsf {Enc}(k,(\textsf {Hash}(k,x),i,x_i),m)) \right] \ge 1-\textsf {negl}(n), \end{aligned}$$

where $x_i$ denotes the ith bit of x, and the randomness is taken over $k\leftarrow \textsf {Gen}(1^{n},m)$.

Definition 7

(Security of HE) If an $\textsf {HE}$ is selectively indistinguishable secure against any probabilistic polynomial time algorithm $\mathcal {A}$, then we use $Exp_{\mathcal {A},\textsf {HE}}^{IND}(n)$ security to quantify that for every PPT algorithm $\mathcal {A}$, for all n, the length of m and any equal length of plaintext input, we have

$$\begin{aligned} Pr\left[ Exp_{\mathcal {A},\textsf {HE}}^{IND}(n)\right]= & {} \left| Pr\left[ \mathcal {A}(k,x,ct_{m_0})=1\right] -Pr\left[ \mathcal {A}(k,x,ct_{m_1})=1\right] \right| \\ {}\le & {} \textsf {negl}(n), \end{aligned}$$

where $\{m_0, m_1\} \overset{\$}{\leftarrow }\ \mathcal {M}, k \leftarrow \textsf {Gen}(1^n, m)$ and $ct_{m_b}\leftarrow \textsf {Enc}(k,(\textsf {Hash}(k,x),i,1-x_i),m_b)$. We define the advantage of any algorithm $\mathcal {A}$ as the difference of the probabilities above.

Definition 8

(Blindness) The blindness is

$$\begin{aligned} \langle k, x, \textsf {Enc}(k,(h,i,c)),m)\rangle \overset{c}{\approx } \langle k, x, U_{|ct|}\rangle , \end{aligned}$$

where m is a uniform bit string.

2.5 Hash garbling

An HG [12] scheme consists of five polynomial time algorithms, $\textsf {HG}=(\textsf {Gen},\textsf {Hash},\textsf {HObf},\textsf {HInp},$ and $\textsf {Eval})$.²

• $\textsf {Gen}(1^n,{k})$: This takes as input the security parameter n and an input length parameter k for $k\le poly(n)$, and outputs a hash key hk. ($\textsf {Gen}$ runs in poly(n) time.)

• $\textsf {Hash}(hk,x)$: This takes as input hk and $x\in \{0,1\}^{k},$ and outputs a value $y\in \{0,1\}^{n}$.

• $\textsf {HObf}(hk,C)$: This takes as input hk and a circuit C,  and outputs a secret state $st\in \{0,1\}^{n}$ and a circuit $\widetilde{C}$.

• $\textsf {HInp}(hk,y,st)$: This takes as input hk, y, st and outputs $\widetilde{y}$.

• $\textsf {Eval}(\widetilde{C},\widetilde{y},x)$: This takes as input a GC $\widetilde{C}$ and the value $\widetilde{y}$ and x, and outputs $\delta$.

Definition 9

(Correctness of HG) For all $n, k, hk \leftarrow \textsf {Gen}(1^{n}, k)$, circuit C, input $x \in \{0, 1\}^{k}, st \in \{0, 1\}^{n},$ $\widetilde{C} \leftarrow \textsf {HObf}(hk, C, st)$ and $\widetilde{y} \leftarrow \textsf {HInp}(hk, \textsf {Hash}(hk, x), st)$, we have

$$\begin{aligned} Pr \left[ \textsf {Eval}(\widetilde{C},\widetilde{y},x)= C(x) \right] =1. \end{aligned}$$

Definition 10

(Security of HG) There exists a PPT simulator $\textsf {Sim}$ such that for all n, k and PPT (in n) $\mathcal {A}$ we have

$$\begin{aligned} \langle hk,x,\widetilde{C},\widetilde{y} \rangle \overset{c}{\approx }\langle hk,x,\textsf {Sim}(hk,x,1^{\left| C \right| },C(x))\rangle , \end{aligned}$$

(2)

where $hk\leftarrow \textsf {Gen}(1^{n},k), (C,x)\leftarrow \mathcal {A}(hk),(\widetilde{C},st) \leftarrow \textsf {HObf}(hk,C), st\leftarrow \{0,1\}^{n}$ and $\widetilde{y}\leftarrow \textsf {HInp}(hk,\textsf {Hash}(hk,x),st)$.

More generally, we use $Exp_{\mathcal {A},\textsf {HG}}^{IND}(n)$ security to quantify that for every PPT algorithm $\mathcal {A}$, (2) is computationally indistinguishable, so we have

$$\begin{aligned} Pr\left[ Exp_{\mathcal {A},\textsf {HG}}^{IND}(n)\right]= & {} |Pr\left[ \mathcal {A}(hk,x,\widetilde{C},\widetilde{y})=1\right] -Pr\left[ \mathcal {A}(hk,x,\textsf {Sim}(hk,x,1^{\left| C \right| },C(x))=1\right] |\\\le & {} \textsf {negl}(n). \end{aligned}$$

Definition 11

(Weak security of HG) There exists a PPT simulator $\textsf {Sim}$ such that for all n, k and PPT (in n) $\mathcal {A}$, we have the following weak notion

$$\begin{aligned} \langle hk,\widetilde{C},\widetilde{y}\rangle \overset{c}{\approx }\langle hk,\textsf {Sim}(hk,x,1^{\left| C \right| },C(x))\rangle . \end{aligned}$$

Note that there is no input x in the weak security. If a scheme meets the security of HG, then it absolutely meets the weak security.

Definition 12

(Blindness) The blindness is

$$\begin{aligned} \langle hk, x, \textsf {Sim}(hk, x, 1^{|C|}, C(x))\rangle \overset{c}{\approx }\ \langle hk, x, U_{|{\widetilde{C}}|+|{\widetilde{y}}|}\rangle , \end{aligned}$$

(3)

where the output distribution of C(x) is uniform.

Definition 13

(Weak blindness) To undertake Definition 12, we have the following weak notion:

$$\begin{aligned} \langle hk,\textsf {Sim}(hk, x, 1^{|C|}, C(x))\rangle \overset{c}{\approx }\langle hk, U_{|{\widetilde{C}}|+|{\widetilde{y}}|}\rangle . \end{aligned}$$

Note that there is no input x in the weak blindness of HG.

Table 2 Labels $e_C$

3 The HG scheme

3.1 Construction

Let $\textsf {GC}=(\textsf {Garble},\textsf {GarbleInp},\textsf {Eval}')$ and $\textsf {HE}=(\textsf {Gen}'',\textsf {Hash}'',\textsf {Enc},\textsf {Dec})$ be the secure GC and HE. We present the construction of $\textsf {HG}$, which consists of the following algorithms $(\textsf {Gen}, \textsf {Hash}, \textsf {HObf}, \textsf {HInp}, \textsf {Eval})$.

• $\textsf {Gen}(1^{n},k)$: This takes as input the security parameter n and the number of input wires k of a circuit C and computes $hk \leftarrow \textsf {Gen}''(1^{n}, k)$. It outputs a hash key hk.

• $\textsf {Hash}(hk,x)$: This takes as input hk and $x\in \{0,1\}^{k}$ and computes as follows:

  $$\begin{aligned} y \leftarrow \textsf {Hash}''(hk,x). \end{aligned}$$

  It outputs a value $y\in \{0,1\}^{n}$.

• $\textsf {HObf}(hk,C)$: This takes as input hk and a circuit C and computes as follows:

  $$\begin{aligned} (\widetilde{C},e_C) \leftarrow \textsf {Garble}(hk,C). \end{aligned}$$

  This outputs a GC $\widetilde{C}$ and labels $e_C=\{X_{ l ,0},X_{ l ,1}\}_{{ l } \in [k]},$ where $X_{ l ,*} \in \{0,1\}^{n}.$

• $\textsf {HInp}(hk,y,e_C)$: This takes as input $hk, y, e_C$ and computes the following:

  $$\begin{aligned} \widetilde{y} \leftarrow \textsf {Enc}(hk,(y, i, c),e_C), \end{aligned}$$

  where i represents the serial number of $x, c\in \{0,1\}.$ Hence, it outputs the value of $\widetilde{y}=(c_{1,*},\ldots , c_{ l ,*}\ldots , c_{k,*})$.

  According to Table 2, each $c_{ l ,*}$ is calculated as follows:

  $$\begin{aligned} \begin{aligned}&c_{ l ,0} \leftarrow \textsf {Enc}(hk,(y, l , 0),X_{ l ,0}).\\&c_{ l ,1} \leftarrow \textsf {Enc}(hk,(y, l , 1),X_{ l ,1}). \end{aligned} \end{aligned}$$

• $\textsf {Eval}(\widetilde{C},\widetilde{y},x)$: This takes as input $\widetilde{C},\widetilde{y},x$ and computes as follows:

  $$\begin{aligned} \begin{aligned}&{e_C}'\leftarrow \textsf {Dec}(hk,x,\widetilde{y}).\\&\widetilde{x}\leftarrow \textsf {GarbleInp}({e_C}',x).\\&\delta \leftarrow \textsf {Eval}'(\widetilde{C},\widetilde{x}). \end{aligned} \end{aligned}$$

  From Definition 3, it is equivalent to output C(x).

Correctness: From Definition 6 and Table 2, we know that for

$$\begin{aligned} ct \leftarrow \textsf {Enc}(hk,(\textsf {Hash}''(hk,x),i,1-c),X_{i,c}), \end{aligned}$$

the adversary $\mathcal {A}$ cannot distinguish $X_{i,c}$. In other words, for the $\textsf {HInp}$ of $x\in \{0,1\}^{k}$’s i-bit $c, \textsf {Dec}$ can only get the corresponding label $X_{i,c}$. For example, if the value of $x=1011, \mathcal {A}$ is only able to get the labels $X_{1,1}, X_{2,0},X_{3,1},X_{4,1}$, but it has no information about other labels.

3.2 Security analysis

Theorem 1

The HG construction meets simulation security (Definition 10), assuming the underlying hash encryption and garbled circuit are secure.

Proof

To show that the $\textsf {HG}$ construct meets the security of Eq. (2), we need to prove that the output of a PPT simulator ($\textsf {Sim}_{\textsf {HG}}$), which represents the right side of (2), is indistinguishable from that of $\textsf {HG}$. Moreover, $\textsf {View}_{\textsf {HG}}$ represents the left side of the (2). To do this, we have to define a sequence of hybrids $(\textsf {Hyb}_0,\textsf {Hyb}_1,\textsf {Hyb}_2)$ and demonstrate that $\textsf {Sim}_{\textsf {HG}}$ is computationally indistinguishable from the output of $\textsf {View}_{\textsf {HG}}$ by proving the relationship between the following views:

$$\begin{aligned} \textsf {View}_{\textsf {HG}}\equiv \textsf {Hyb}_0 \approx \textsf {Hyb}_1 \approx \textsf {Hyb}_2 \equiv \textsf {Sim}_{\textsf {HG}}. \end{aligned}$$

Similar to our presentation of Construction 3.1, here, all views use the same security parameters $1^n$ and k, and the value of $x \in \{0, 1\}^{k}$ is fixed.

• $\textsf {Hyb}_0$ (encrypt in real game): We make the output of $\textsf {Hyb}_0$ the same as $\textsf {View}_{\textsf {HG}}$, and obviously, $\textsf {View}_{\textsf {HG}} \equiv \textsf {Hyb}_0$.

• $\textsf {Hyb}_1$: Based on $\textsf {Hyb}_0$, we modify the value of $\widetilde{y}$ for the bit corresponding to the x value at the $l$-th value, assuming that 1, ($1 =c\leftarrow x_{ l }$), and the generated ciphertext is $c_{ l ,1}$. We keep the following unchanged:

  $$\begin{aligned} c_{ l ,1} \leftarrow \textsf {Enc}(hk,(y, l ,1),X_{ l ,1}). \end{aligned}$$

  In contrast, for another label $X_{ l ,0}$, we set it to 0, namely:

  $$\begin{aligned} c_{ l ,0} \leftarrow \textsf {Enc}(hk,(y, l ,0),0). \end{aligned}$$

  We do the same encryption process according to the x in $\{0,1\}^{k}$ string corresponding to the label $X_{ l ,*}$ in $e_C$ Table 2. If we assume that the value of x is 1011, the corresponding $\widetilde{y}'$ value should be as follows:

  $$\begin{aligned} \widetilde{y}'=\begin{pmatrix} c_{1,0}' &{} c_{2,0}&{}c_{3,0}'&{}c_{4,0}' \\ c_{1,1}&{} c_{2,1}'&{}c_{3,1}&{}c_{4,1} \end{pmatrix}. \end{aligned}$$

• $\textsf {Hyb}_2$: Based on $\textsf {Hyb}_1$, we modify the value of $\widetilde{x}$ and $\widetilde{C}$, and for each $l \in [0,k]$, in the x path, we use the form of a simulator to generate $\widetilde{C}_{\textsf {Sim}}$ and $\widetilde{x}_{\textsf {Sim}}$ for the corresponding label $e_C$, namely:

  $$\begin{aligned} (\widetilde{C}_{\textsf {Sim}},\widetilde{x}_{\textsf {Sim}})\leftarrow \textsf {Sim}(1^{n},C(x)). \end{aligned}$$

  Note that for the composition of $\widetilde{x}_{\textsf {Sim}}$, for the bit corresponding to the x value at the $l$-th value, assuming that 1. We use the label ${X_{ l ,1}}_{\textsf {Sim}}$ to indicate. For example, if the value of x is 1011 (consistent with $\textsf {Hyb}_1$), the composition of $e_C$ should be as follows:

  $$\begin{aligned} e_c=\begin{pmatrix} X_{1,0}&{} X_{{2,0}_{\textsf {Sim}}} &{} X_{3,0}&{} X_{4,0}\\ X_{{1,1}_{\textsf {Sim}}} &{} X_{2,1} &{} X_{{3,1}_{\textsf {Sim}}}&{}X_{{4,1}_{\textsf {Sim}}} \end{pmatrix}. \end{aligned}$$

  The label $X_{{ l ,*}_{\textsf {Sim}}}$ is generated by the simulator $\textsf {Sim}$, and the rest is generated by the $\textsf {GarbleInp}$ algorithm (which is consistent with $\textsf {Hyb}_1$). Therefore, $\widetilde{x}_{\textsf {Sim}}$ is composed as follows:

  $$\begin{aligned} \widetilde{x}_{\textsf {Sim}}=\begin{pmatrix} \widetilde{x}_{1,0}&{} {\widetilde{x}}_{{2,0}_{\textsf {Sim}}} &{} \widetilde{x}_{3,0}&{} \widetilde{x}_{4,0}\\ {\widetilde{x}}_{{1,1}_{\textsf {Sim}}} &{} \widetilde{x}_{2,1} &{} {\widetilde{x}}_{{3,1}_{\textsf {Sim}}}&{}{\widetilde{x}}_{{4,1}_{\textsf {Sim}}} \end{pmatrix}. \end{aligned}$$

  Hence, the value of the corresponding $\widetilde{y}_{\textsf {Sim}}$ is expressed as follows:

  $$\begin{aligned} \widetilde{y}_{\textsf {Sim}}=\begin{pmatrix} c_{1,0}' &{} c_{{2,0}_{\textsf {Sim}}}&{}c_{3,0}'&{}c_{4,0}' \\ c_{{1,1}_{\textsf {Sim}}}&{} c_{2,1}'&{}c_{{3,1}_{\textsf {Sim}}}&{}c_{{4,1}_{\textsf {Sim}}} \end{pmatrix}. \end{aligned}$$

  Clearly, $\textsf {Hyb}_2\equiv \textsf {Sim}_{\textsf {HG}}$.

Lemma 1

Assuming that HE is selectively indistinguishable secure (Definition 7), hybrid views $\textsf {Hyb}_0$ and $\textsf {Hyb}_1$ are computationally indistinguishable.

Proof

To prove $\textsf {Hyb}_0\overset{c}{\approx }\textsf {Hyb}_1$, we use the output of $\textsf {Hyb}_0$ and $\textsf {Hyb}_1$ as follows:

$$\begin{aligned} \langle hk,x,\widetilde{C},\widetilde{y}\rangle \overset{c}{\approx } \langle hk,x,\widetilde{C},\widetilde{y}'\rangle . \end{aligned}$$

(4)

The difference between the two sides of the (4) is $\widetilde{y}$ and $\widetilde{y}'$. More specifically, the difference between the two sides of (4) should be information that is not encrypted in the x path ($1-x_{ l ,*}$), such as $c_{1,0}'$ and $c_{1,0}$, to determine whether the encrypted information is labeled $X_{ l ,0}$ or 0. In other words, a PPT algorithm $\mathcal {A}$ needs to distinguish the following equation:

$$\begin{aligned} ct \leftarrow \textsf {Enc}(hk,(y,i,1-x_{ l ,*}),m_b). \end{aligned}$$

(5)

Equation (5) translates to prove $Exp_{\mathcal {A},\textsf {HE}}^{IND}$ security. From Definition 7, we know that the advantage of $\mathcal {A}$ is $\textsf {negl}(n)$, and the proof is completed. $\square$

Lemma 2

Assuming that GC meets simulation security (Definition 4), hybrid views $\textsf {Hyb}_1$ and $\textsf {Hyb}_2$ are computationally indistinguishable.

Proof

To prove $\textsf {Hyb}_1\overset{c}{\approx }\textsf {Hyb}_2$, we use the output of $\textsf {Hyb}_1$ and $\textsf {Hyb}_2$ as follows:

$$\begin{aligned} \langle hk,x,\widetilde{C},\widetilde{y}'\rangle \overset{c}{\approx }\langle hk,x,\widetilde{C}_{\textsf {Sim}},\widetilde{y}_{\textsf {Sim}}\rangle . \end{aligned}$$

(6)

The difference between the two sides of (6) is ($\widetilde{C},\widetilde{y}'$) and ($\widetilde{C}_{\textsf {Sim}},$ $\widetilde{y}_{\textsf {Sim}}$). More specifically, the difference between the two sides of (6) is the difference in the way $\widetilde{x}$ is generated, that is, whether $\widetilde{x}$ is generated by $\textsf {GarbleInp}$ or generated by the simulator on the x path ($x_{ l ,*}$). In other words, a PPT algorithm $\mathcal {A}$ needs to distinguish the following equation:

$$\begin{aligned} \langle \widetilde{C},\widetilde{x} \rangle \overset{c}{\approx }\langle \widetilde{C}_{\textsf {Sim}},\widetilde{x}_{\textsf {Sim}}\rangle . \end{aligned}$$

(7)

Equation (7) translates to prove $Exp_{\mathcal {A},\textsf {GC}}^{IND}$ security. From Definition 4, we know that the advantage of $\mathcal {A}$ is $\textsf {negl}(n)$, and the proof is completed. $\square$

This proof is done by proving Lemmas 1 and 2. $\square$

Theorem 2

The HG construction meets blind security (Definition 12), assuming that the underlying HE and GC are blind security.

Proof

To show that the HG construction meets the security of (3), we use $\textsf {View}_{BHG}$ to represent the right side of the (3) and $\textsf {Sim}_{BHG}$ to represent the left side of (3). For the simulator $\textsf {Sim}$ described above, consider the distribution of $\textsf {Sim}(hk,x,1^{|C|},C(x))$ for a uniformly generated output. By the security of a blind GC (Definition 5), we know the GC simulator $\langle \textsf {Sim}(1^{n},C(x))\rangle \overset{c}{\approx }\langle U_{|C(x)|} \rangle$. Hence, for each $l \in [k], X_{ l ,*}$ $\overset{c}{\approx }\ U$. Thus, by the security of blind HE (Definition 8), $\widetilde{y} = \textsf {Enc}(hk,(h,i,c),X_{ l ,*})$, we have $\langle hk,x,\widetilde{y} \rangle \overset{c}{\approx }\langle hk,x, U_{|\widetilde{y}|} \rangle$. Hence, it follows that $\textsf {Sim}_{BHG} \overset{c}{\approx }\textsf {View}_{BHG}$. $\square$

4 The proposed PCE scheme

4.1 Warm-up construction

Let $\textsf {PKE}= (\textsf {Gen}', \textsf {Enc}', \textsf {Dec}')$ and $\textsf {HG}= (\textsf {Gen}'',\textsf {HObf},\textsf {Hash},\textsf {HInp},\textsf {Eval})$ be the secure public key encryption and HG. The proposed construction of PCE is composed of the following algorithms.

• $\textsf {Gen}(1^{\lambda })$: It takes as input the security parameter $\lambda$, which contains two parameters, $(1^{n}, k)$, and computes the following:

  $$\begin{aligned} \begin{aligned}&(pk',sk') \leftarrow \textsf {Gen}'(1^n).\\&hk \leftarrow \textsf {Gen}''(1^n,k). \end{aligned} \end{aligned}$$

  Finally, it outputs the public/private key pair (pk, sk), where $pk = (pk',hk), sk = sk'$.

• $\textsf {Enc}(pk,m)$: This takes as input pk and a message m $\in \{0, 1\}^{*}$, and computes the following:

  $$\begin{aligned} \begin{aligned}&\mathcal {C}\leftarrow \textsf {Enc}' (pk',m)\\&(\widetilde{P},e_C) \leftarrow \textsf {HObf}(hk,P)\\&y \leftarrow \textsf {Hash}(hk,m).\\&\widetilde{y_m} \leftarrow \textsf {HInp}(hk,y,e_C)\\&t = \widetilde{y_m} \oplus H(m||r)\\&\widetilde{y} = (t,r), \end{aligned} \end{aligned}$$

  where r is a random number, $H(\cdot )$ is a cryptographic hash function that supports input of any length, P is explained below, and the generation of a secret state $e_C \in \{0, 1\}^{n}$ can be seen in Construction 3.1.

  The program P is defined below:

  • ${\textbf {Hardwired}}$: m

  • ${\textbf {Input}}$: x

    • 1. if $x = m$, output 1.

    • 2. if $x \ne m$, output $\perp$.

  Finally, it outputs ciphertext $C = (\mathcal {C}, \widetilde{P}, \widetilde{y})$.

• $\textsf {Dec}(sk,C)$: It takes as input the secret key sk and $\mathcal {C}$, and computes the following:

  $$\begin{aligned} m = \textsf {Dec}'(sk',\mathcal {C}). \end{aligned}$$

• $\textsf {Check}(pk,C,m)$: In order to check the correctness of m, this is calculated as follows:

  $$\begin{aligned} \begin{aligned}&\widetilde{y_m} \leftarrow t \oplus H(m||r)\\&b \leftarrow \textsf {Eval}(\widetilde{P},\widetilde{y_m},m), \end{aligned} \end{aligned}$$

  where $b \in \{\bot , 1\}$ ($b = 1$ if C is an encryption of m, or $b=\bot$ if not).

4.1.1 Correctness

In $\textsf {Dec}$, it is held by $m = \textsf {Dec}'(sk',\textsf {Enc}'(pk',m))$, the correctness of the underlying decryption of PKE.

In $\textsf {Check}$, taking (t, r) from C and the message $m^*$ and computing $H(m^*||r)$, it is held $\widetilde{y_m^*} = t \oplus H(m^*||r)$. With the hash input encoding $\widetilde{y_m^*}$, we can obtain $\widetilde{y_m^*} \leftarrow \textsf {HInp}(hk,\textsf {Hash}(hk,m^*),e_C)$. If $\widetilde{P}$ with hardcoded m and $e_C$ are generated by $\textsf {HObf}(hk,P), \textsf {Eval}(\widetilde{P},\widetilde{y_m^*},m^*)$ will output 1 if and only if $m^*$ is the same with the hardcoded m in P.

4.1.2 Security proof

The security of the warm-up is stated with the following theorem.

Theorem 3

The above generic construction of $\textsf {PCE}$ satisfies unlinkable CPA security in the random oracle model if the underlying public key encryption is CPA secure and the security of $\textsf {HG}$ meets Definition  11.

Proof

At a high level, we assume that there is a PPT adversary $\mathcal {A}$, which breaks the $Exp_{\mathcal {A},\textsf {PCE}}^{unlink}(n)$ security, and then we can create the PPT algorithm $\mathcal {A}$, which also breaks $Exp_{\mathcal {A},\textsf {PKE}}^{CPA}(n)$ or $Exp_{\mathcal {A},\textsf {HG}}^{IND}(n)$ security. However, for completing the proof, we start by defining an event $\textsf {HIT}$ where the adversary $\mathcal {A}_2$ exactly accesses $m_0$ or $m_1$ to $\textsf {Check}$. This suffices to obtain the following result:

$$\begin{aligned} Pr \left[ Exp_{\mathcal {A},\textsf {PCE}}^{unlink}(n)=1 \right]= & {} Pr \left[ Exp_{\mathcal {A},\textsf {PCE}}^{unlink}(n)=1 \wedge \textsf {HIT}\right] \\{} & {} + Pr \left[ Exp_{\mathcal {A},\textsf {PCE}}^{unlink}(n)=1 \wedge \overline{\textsf {HIT}} \right] \\\le & {} Pr \left[ \textsf {HIT}\right] +Pr \left[ Exp_{\mathcal {A},\textsf {PCE}}^{unlink}(n)=1 \wedge \overline{\textsf {HIT}} \right] . \end{aligned}$$

We claim $Pr[\textsf {HIT}] = \frac{2}{2^{\ell (n)}} \le \textsf {negl}(n)$, as $m_0,m_1$ are $\ell (n)$-bit, where $\ell$ is some polynomial.

The rest of the proof focuses on $Exp_{\mathcal {A},\textsf {PCE}}^{unlink}(n)=1 \wedge \overline{\textsf {HIT}}$. We abuse the notation ${\widetilde{y}}_{(m_\beta )}$ as ${\widetilde{y}}$ with $t=\widetilde{y_{m_\beta }} \oplus H(m_\beta ||r)$. Our goal is to show that $\langle pk', \textsf {Enc}'(m_0), hk, {\widetilde{P}}_{m_0}, {\widetilde{y}}_{(m_0)} \rangle$ is indistinguishable to $\langle pk', \textsf {Enc}'(m_1), hk, \widetilde{P}_{m_1}, {\widetilde{y}}_{(m_1)} \rangle$, where $\widetilde{P}_{m_\beta }, {\widetilde{y}}_{m_\beta }$ denotes the underlying garbled encoding for plaintext $m_\beta$. For short, denote by $\langle \textsf {Enc}'(m_0), {\widetilde{P}}_{m_0}, {\widetilde{y}}_{(m_0)} \rangle \approx \langle \textsf {Enc}'(m_1), {\widetilde{P}}_{m_1}, {\widetilde{y}}_{(m_1)} \rangle$ with public pair of $(pk',hk)$. We apply the standard hybrid arguments to complete the proof. At the beginning, start by defining two top-level hybrids, $\textsf {Hyb}_0$ and $\textsf {Hyb}_1$,³.

• $\textsf {Hyb}_\beta$: This experiment is identical to $Exp_{\mathcal {A},\textsf {PCE}}^{unlink}(n)$, except the challenge ciphertext is $\langle \textsf {Enc}'(m_\beta ), {\widetilde{P}}_{m_\beta }, {\widetilde{y}}_{m_\beta } \rangle$.

Note that $\textsf {Hyb}_\beta$ is identical to $\langle pk', \textsf {Enc}'(m_\beta ), hk, {\widetilde{P}}_{m_\beta }, {\widetilde{y}}_{m_\beta } \rangle$. In addition, we further define a few hybrids $\textsf {Hyb}_{\beta ,0}, \textsf {Hyb}_{\beta ,1}$ as follows (with $\beta \in \{0,1\}$):

• $\textsf {Hyb}_{\beta ,1}$: This is similar to $\textsf {Hyb}_\beta$, except ${\widetilde{P}}_{m_\beta }, {\widetilde{y}}_{m_\beta }$ is replaced with $\textsf {Sim}(hk,m_\beta , 1^{|P_{m_\beta }|}, P_{m_\beta }(m_\beta ))$.

• $\textsf {Hyb}_{\beta ,2}$: This is similar to $\textsf {Hyb}_{\beta ,1}$, except the simulated part is replaced with $U_{|{\widetilde{P}}| + |{\widetilde{y}}|}$.

To achieve $\langle pk', \textsf {Enc}'(m_0), hk, {\widetilde{P}}_{m_0},$ ${\widetilde{y}}_{m_0}\rangle \overset{c}{\approx }\ \langle pk',$ $\textsf {Enc}'(m_1), hk, {\widetilde{P}}_{m_1}, \widetilde{y}_{m_1}\rangle$, a sequence of hybrids is denoted by

$$\begin{aligned} \textsf {Hyb}_0 \approx \textsf {Hyb}_{0,1} \approx \textsf {Hyb}_{0,2} \approx \textsf {Hyb}_{1,2} \approx \textsf {Hyb}_{1,1} \approx \textsf {Hyb}_1. \end{aligned}$$

For each neighboring hybrid, we can use an assumption of security to complete the reduction. We directly state the following lemmas, and refer to the missing proofs of Lemmas 3 and 5 in Appendix.

Lemma 3

If the underlying hash garbling scheme meets weak security (Definition 11), then no poly-time adversary can distinguish with non-negligible probability between $\textsf {Hyb}_0$ and $\textsf {Hyb}_{0,1}$.

Lemma 4

No poly-time adversary can distinguish with non-negligible probability between $\textsf {Hyb}_{0,1}$ and $\textsf {Hyb}_{0,2}$ in the random oracle model.

The distributions of $\textsf {Hyb}_{0,1}$ and $\textsf {Hyb}_{0,2}$ in the random oracle model are identical. Details are shown below. Trivially, we have $\langle \widetilde{P}, r, \widetilde{y_m}\oplus H(m||r) \equiv \langle \widetilde{P}, r, U_{|\widetilde{y_m}|} \rangle$ in the random oracle. It is easy to obtain $\langle \widetilde{P}, r, U_{|y_m|} \rangle \equiv \langle \widetilde{P}, U_{|{\widetilde{y}}|} \rangle$ with identical distribution. Finally, after cutting the correlation from $\widetilde{P}$ to $\widetilde{y_m}$, we conclude that $\widetilde{P}$ is not evaluable, and further obtain $\langle \widetilde{P}, U_{|{\widetilde{y}}|} \rangle \equiv \langle U_{|\widetilde{P} + \widetilde{y}|} \rangle$.

Lemma 5

If our public key encryption scheme is CPA-secure (Definition 1), then no poly-time adversary can distinguish with non-negligible probability between $\textsf {Hyb}_{0,2}$ and $\textsf {Hyb}_{1,2}$.

These lemmas can be used to show $\textsf {Hyb}_{1,2}\approx \textsf {Hyb}_{1,1} \approx \textsf {Hyb}_1$ with the same manner. Finally, we conclude that $Pr [Exp_{\mathcal {A},\textsf {PCE}}^{unlink}(n)=1 \wedge \overline{\textsf {HIT}}] \le \textsf {negl}(n)$, which implies $Pr[Exp_{\mathcal {A},\textsf {PCE}}^{unlink}(n)=1 ] \le \textsf {negl}(n)$, completing the proof.

Here, we sketch the idea of using the random oracle for Lemma 4. Let us focus on $\langle \widetilde{P}_{\textsf {Sim},m_\beta }, H(m_\beta ||r) \oplus \widetilde{y}_{\textsf {Sim},m_\beta }, r \rangle$; it cannot be flipped to uniform, as ${\widetilde{y}}_{\textsf {Sim},m_\beta }$ depends on $\widetilde{P}_{\textsf {Sim},m_\beta }$ and $H(m_\beta ||r)$ on r. The main technique is to model H as a random oracle for cutting such a relationship. In the random oracle model, we directly have $\langle \widetilde{P}_{\textsf {Sim},m_\beta }, U_{|{\widetilde{y}}|} \oplus \widetilde{y}_{\textsf {Sim},m_\beta }, r \rangle$, as for each input m||r, the random oracle H uniformly determines a random number. It is clear to obtain $\langle {\widetilde{P}}_{\textsf {Sim},m_\beta }, U_{|{\widetilde{y}}|}, r \rangle$. Finally, without existing ${\widetilde{y}}$, we can claim ${\widetilde{P}}_{\textsf {Sim},m_\beta }$ as uniform $U_{|{\widetilde{P}}|}$. The proof sketch is done with $|r| \ge |{\widetilde{y}}|$, which guarantees uniform r can span all possible values on $\widetilde{y}$.$\square$

4.2 Non-black-box PCE construction in the standard model

Let $\textsf {PKE}$ $=$ $(\textsf {Gen}',$ $\textsf {Enc}',$ $\textsf {Dec}')$ and $\textsf {HG}$ $=$ $(\textsf {Gen}'',$ $\textsf {HObf},$ $\textsf {Hash},$ $\textsf {HInp},$ $\textsf {Eval})$ be the secure PKE and HG. The final construction of PCE is almost identical to the warm-up. In the following, only the modifications are shown.

• $\textsf {Enc}(pk,m)$: It takes as input pk and a message m $\in$ $\{0,$ $1\}^{*}$, and computes the following:

  $$\begin{aligned} \begin{aligned}&\mathcal {C}\leftarrow \textsf {Enc}' (pk',m)\\&(\widetilde{P},e_C) \leftarrow \textsf {HObf}(hk,P)\\&y \leftarrow \textsf {Hash}(hk,m)\\&\widetilde{y} \leftarrow \textsf {HInp}(hk,y,e_C). \end{aligned} \end{aligned}$$

  The P is explained below, and the generation of a secret state $e_C$ $\in$ $\{0,$ $1\}^{n}$ can be seen in Construction 3.1.

  The program P is defined below:

  • ${\textbf {Hardwired}}$: m,  r

  • ${\textbf {Input}}$: x

    • 1. if x $=$ m, output $\textsf {PRG}(x)$.

    • 2. if x $\ne$ m, output $\textsf {PRG}(x \oplus r)$,

  where r is a random number, and $\textsf {PRG}$ is a pseudorandom generator [2]. Finally, it outputs ciphertext C $=$ $(\mathcal {C},$ $\widetilde{P},$ $\widetilde{y})$.

• $\textsf {Check}(pk,C,m)$: In order to check the correctness of m, it is calculated as follows:

  $$\begin{aligned} \textsf {PRG}(m) \overset{?}{=}\ \textsf {Eval}(\widetilde{P},\widetilde{y},m). \end{aligned}$$

  (8)

  If C is encrypted by m, (8) holds, and vice versa.

We say that the above modifications can lift the construction to be secure in the standard model. However, the algorithm $\textsf {HObf}$ must know the code of $\textsf {PRG}$ precisely, which implies the construction is of non-black-box use for one-way functions. In the following proof, we omit to repeat the steps of the proof of Theorem 3. Here, we briefly describe the security argument by stating a lemma that is different from Lemma 4.

Lemma 6

Assuming that HG meets week blindness (Definition 13), then no poly-time adversary can distinguish with non-negligible probability between $\textsf {Hyb}_{0,1}$ and $\textsf {Hyb}_{0,2}$.

Proof

In a nutshell, we need to prove $\langle pk',$ $\textsf {Enc}'(m_0),$ hk,  $\textsf {Sim}(hk,$ $m_0,$ $1^{|P_{m_0}|},$ $P_{m_0}(m_0))\rangle$ $\overset{c}{\approx }$ $\langle pk',$ $\textsf {Enc}'(m_0),$ hk,  $U_{|\widetilde{p}|+|\widetilde{y}|}\rangle$, from the proposed construction. Recall that the result of $P_{m_0}(x)$ is close to uniform, as the output of $\textsf {PRG}$ is close to uniform. Thus, $\textsf {Hyb}_{0,1}$ $\overset{c}{\approx }$ $\textsf {Hyb}_{0,2}$ can be easily achieved as long as the HG meets weak blindness security without any random oracle. $\square$

Fig. 1

Implementation result of performance of $\textsf {PCE}$ algorithms

5 Experiments

In this section, we present the experimental evaluation of our PCE construction, which mainly consists of two cryptographic primitives. The first one is PKE, so we use the ElGamal algorithm [9] based on the decision Diffie–Hellman assumption [18]. The second is HG, which consists of cryptographic tools such as HE and GC. We choose Chameleon Encryption [6] based on the computation Diffie-Hellman assumption as the HE, and use AES or SHA to implement the GC.

We implement experiments by using C++ programming under an Intel(R) Core(TM) i5-3427U CPU of 1.80 GHz and 4 GB of memory, running in Ubuntu$-$18.04.1. In addition, we rely on the OpenSSL library for the hash function, the PBC library for group operations, and point exponentiation calculations. Group elements for $\mathbb {G}$ are set with 1024-bit. As mentioned in Construction 4.1, it is clear that the main influencing factor of the performance of the PCE instance is the plaintext length. The fixed plaintext length is 4, 32, 64, 128, 256, 512, and 1024 bits. The main metrics of performance include the PCE and HG algorithms (see Figs. 1 and 2).

For the performance, in Fig. 1, with the exception of the $\textsf {Dec}$ algorithm, the remaining algorithms experience a climbing trend with the increase of the length of plaintext. Moreover, from Fig. 2, it can be seen that the HG algorithm occupies the main performance of PCE. In fact, for the length of the plaintext, the time of execution of the PKE algorithm is also constant, as can be seen by comparing Figs. 1 and 2.

Fig. 2

Implementation result of performance of $\textsf {HG}$ algorithms

6 Conclusions

In this paper, we have shown a construction of HG based on hash encryption and garbled circuits. Then, we have built a warm-up solution to realize the construction of plaintext checkable encryption from HG, but its security has been proven in the random oracle. With slight modifications from our warm-up, the full-fledged construction of PCE has proved to be secure in the standard model. Finally, the experiments for implementing our warm-up PCE have shown effectiveness for real-life applications.

Appendix A: Missing proofs

Proof of Lemma 3

Suppose $\mathcal {A}$ is the adversary with non-negligible probability to distinguish $\textsf {Hyb}_0$ and $\textsf {Hyb}_{0,1}$, then we can create another algorithm $\mathcal {B}$ which runs $\mathcal {A}$ as a subroutine to break the weak security of HG.

Following the hybrid, $\mathcal {A}$ receives a challenge as $(\textsf {Enc}' (pk',m_0),\widetilde{\textsf {P}},\widetilde{\textsf {y}})$. $\widetilde{\textsf {y}}$ can be parsed as (t, r) such that $\widetilde{\textsf {y}_{m_0}} = t \oplus H(m_0||r)$. The pair of $(\widetilde{\textsf {P}},\widetilde{\textsf {y}_{m_0}})$ is $(\widetilde{P}_{m_0},\widetilde{y}_{m_0})$ or $(\widetilde{P}_{\textsf {Sim}},\widetilde{y}_{\textsf {Sim}})$ where $\widetilde{P}_{\textsf {Sim}},\widetilde{y}_{\textsf {Sim}}$ is generated by $\textsf {Sim}(hk,m_0, 1^{|P_{m_0}|}, \bot )$. Note that $\bot$ by the previous argument for $\textsf {HIT}$. Accordingly, $\mathcal {A}$ can transform parts of the challenge into $\mathcal {B}$’s input. $\mathcal {A}$ directly sets $\widetilde{\textsf {P}},\widetilde{\textsf {y}_{m_0}}$ as the input of $\mathcal {B}$, and waits for the output of $\mathcal {B}$. Finally, $\mathcal {A}$’s output (one bit) is set to be identical to $\mathcal {B}$’s, and thus it implies that $\Pr [\mathcal {A}(\textsf {Enc}' (pk',m_0),\widetilde{\textsf {P}},\widetilde{\textsf {y}})=1] = \Pr [\mathcal {B}(\widetilde{\textsf {P}},\widetilde{\textsf {y}_{m_0}})]=1$. Weak security of HG offers $|\Pr [\mathcal {B}(\widetilde{P}_{m_0},\widetilde{y}_{m_0})=1] - \Pr [\mathcal {B}(\widetilde{P}_{\textsf {Sim}},\widetilde{y}_{\textsf {Sim}})=1]| \le \textsf {negl}(n)$, so we obtain

$$\begin{aligned}{} & {} |\Pr [\mathcal {A}(\textsf {Enc}' (pk',m_0),\widetilde{P}_{m_0},(\widetilde{y}_{m_0}\oplus H(m_0||r), r))=1]\\{} & {} - \Pr [\mathcal {A}(\textsf {Enc}' (pk',m_0),\widetilde{P}_{\textsf {Sim}},(\widetilde{y}_{\textsf {Sim}}\oplus H(m_0||r), r))=1]|\le \textsf {negl}(n) \end{aligned}$$

as well as $\textsf {Hyb}_0$ and $\textsf {Hyb}_{0,1}$ are computationally indistinguishable. The proof of this lemma is done. $\square$

Proof of Lemma 5

Before we prove the lemma, we quickly remark the proof intuition of the main theorem. Our final goal is from $\textsf {Hyb}_0$ to $\textsf {Hyb}_1$ to replace $\textsf {Enc}(pk',m_0)$ with $\textsf {Enc}(pk',m_1)$. However, it cannot be directly replaced, since $(\widetilde{\textsf {P}},\widetilde{\textsf {y}})$ in $\textsf {Hyb}_0$ includes the information of $m_0$. However, Lemma 3 is used to eliminate the underlying $m_0$ for $(\widetilde{P}_{m_0},\widetilde{y}_{m_0})$ by the power of the random oracle.

Let go back to this proof. Suppose $\mathcal {A}$ is the adversary with non-negligible probability to distinguish $\textsf {Hyb}_{0,2}$ and $\textsf {Hyb}_{1,2}$, then we can create another algorithm $\mathcal {B}$ that runs $\mathcal {A}$ as a subroutine to break the CPA security of public key encryption. Following $\textsf {Hyb}_{\beta ,2}, \mathcal {A}$ receives a challenge as $(\textsf {Enc}' (pk',m_\beta ),\widetilde{\textsf {P}},\widetilde{\textsf {y}})$ where $\widetilde{\textsf {P}},\widetilde{\textsf {y}} \leftarrow U_{|\widetilde{P}|+|\widetilde{y}|}$. Consequently, $\mathcal {A}$ can transform parts of the challenge into $\mathcal {B}$’s input. $\mathcal {A}$ directly sets $\textsf {Enc}' (pk',m_\beta )$ as the input of $\mathcal {B}$, and waits for the output of $\mathcal {B}$. Similarly to the proof of the above lemma, it implies that $\Pr [\mathcal {A}(\textsf {Enc}' (pk',m_\beta ),\widetilde{\textsf {P}},\widetilde{\textsf {y}})] = \Pr [\mathcal {B}(\textsf {Enc}' (pk',m_\beta ))]$. The CPA security says $|\Pr [\mathcal {B}(\textsf {Enc}' (pk',m_0))=1] - \Pr [\mathcal {B}(\textsf {Enc}' (pk',m_1))=1]| \le \textsf {negl}(n)$. We finally obtain

$$\begin{aligned} | \Pr [\mathcal {A}(\textsf {Enc}' (pk',m_0),\widetilde{\textsf {P}},\widetilde{\textsf {y}})=1] - \Pr [\mathcal {A}(\textsf {Enc}' (pk',m_1),\widetilde{\textsf {P}},\widetilde{\textsf {y}})=1] | \le \textsf {negl}(n) \end{aligned}$$

as well as $\textsf {Hyb}_{0,2}$ and $\textsf {Hyb}_{1,2}$ are computationally indistinguishable. The proof of this lemma is done. $\square$