# New Construction of PVPKE Scheme and Its Application in Information Systems and Mobile Communication

Authors: Minqing Zhang; Xu An Wang; Xiaoyuan Yang; Weihua Li
Journal: Mobile Information Systems
 (2015)

---

## Abstract

In SCN12, Nieto et al. discussed an interesting property of public key encryption with chosen
ciphertext security, that is, ciphertexts with public verifiability. Independently, we introduced
a new cryptographic primitive, CCA-secure publicly verifiable public key encryption without pairings in the standard model (PVPKE), and discussed its application in proxy reencryption
(PRE) and threshold public key encryption (TPKE). In Crypto’09, Hofheiz and Kiltz introduced
the group of signed quadratic residues and discussed its application; the most interesting feature
of this group is its “gap” property, while the computational problem is as hard as factoring, and
the corresponding decisional problem is easy. In this paper, we give new constructions of PVPKE
scheme based on signed quadratic residues and analyze their security. We also discuss PVPKE’s
important application in modern information systems, such as achieving ciphertext checkable
in the cloud setting for the mobile laptop, reducing workload by the gateway between the open
internet and the trusted private network, and dropping invalid ciphertext by the routers for
helping the network to preserve its communication bandwidth.


---

## Body

## 1. Introduction

In modern information systems such as mobile wireless network, social network, open internet, and cloud computation, security is an important issue [1, 2]. Public key encryption [3] is among the most important basic tools to strengthen the whole system’s security. Along with the development of information system, the security notion for public key encryption has been strengthened. The first proposal on public key encryption, RSA, though a great breakthrough in cryptography, only achieves the security notion of one-way security [4]. In 1984, Goldwasser and Micali [5] proposed the notion of semantic security (also known as indistinguishable security (IND-CPA)). This security notion states that the challenge ciphertext needs to contain no more information than a randomly chosen ciphertext. Although it is a reasonable security notion, many applications using public key encryption as a basic tool need stronger security notion, that is, chosen ciphertext security (IND-CCA). Compared with the semantic security notion, this security notion considers that the adversary can get help from the decryption oracle (the adversary can query the decryption oracle with his chosen ciphertexts, except the challenge ciphertext which cannot be queried). Until now, many CCA-secure PKE schemes have been proposed [6–11].Active attackers play more and more important role in breaking the security of modern information systems [1, 2]; thus chosen ciphertext security of the encryption scheme is essential for these systems. However, if the validity can only be checked by the decrypter privately with his secret key, the whole system can easily suffer from ciphertext-malleable attack. The active attackers can easily modify the right ciphertext transferred in the network to get numerous malicious ciphertexts and thus cost the precious bandwidth greatly. Although these ciphertexts can be rejected by the decrypter at the last moment, they have already caused great problem in the systems. These problems can affect the users’ feeling on using the system. Even more seriously, they cause shutting down the whole system and bring damage to the service providing corporations. If the validity of these ciphertexts can be checked publicly, the problems can be easily solved, the routers or the access infrastructure can drop these maliciously created ciphertexts, and the bandwidth has been effectively preserved [12]. As a concrete example, can you imagine, when using mobile phone for secure instant-message talking like MSN, you always have to deal with nonsense invalid ciphertexts maliciously created by active attackers? But if the access infrastructure equipped withPVPKE can help you to filter these invalid ciphertexts, you certainly will feel better. In one word,PVPKE is an important tool for smoothly running modern information systems if these systems have employed public key encryption as a basic way to achieve security.However, researchers give little care to the property of public verifiability of the chosen ciphertext-secure ciphertexts. In bilinear map setting or by using the random oracle, public verifiability of ciphertexts coming from an IND-CCA-secure public key encryption can be easily achieved. Thus, in this paper, we care about how to construct publicly verifiable public key encryption without pairing in the standard model. Recently, in [13], we introduced an interesting cryptographic primitive:PVPKE, defined as publicly verifiable chosen ciphertext-secure public key encryption in the standard model without pairing.PVPKE is a very powerful building block to construct some other interesting cryptographic protocols and cloud computation [14, 15]. For example, it can be used to construct chosen ciphertext- (CCA-) secure threshold public key encryption (TPKE) [16–20]. InTPKE, chosen ciphertext security always requires that the distributed decryption server can check the ciphertext’s validity before decryption; otherwise some valuable information about decryption will be returned to the adversary and this will help the adversary to break the chosen ciphertext security. For another example,PVPKE can be a core block to construct chosen ciphertext-secure proxy reencryption (PRE) [21–26]. Chosen ciphertext attackers can query the delegator and delegatee’s decryption oracle arbitrarily; if invalid ciphertexts forwarded by the proxy to the delegatee have been decrypted by the delegatee, the attackers can get useful information to breakCCA security. Since the proxy without secret keys needs to check the validity of the ciphertext for the delegatee before reencryption, thus public verifiability of the ciphertext seems to be an essential requirement for achievingCCA security for proxy reencryption.In SCN12, Nieto et al. [27] discussed an interesting property of public key encryption with chosen ciphertext security, that is, ciphertexts with public verifiability. They also demonstrated an important application of this new primitive, that is, “nontrivial filtering” of an incoming IND-CCA-secure ciphertext to be an IND-CPA-secure ciphertext with reduced workload by a gateway. They formally defined (nontrivial) public variability of ciphertexts for general encryption schemes, key encapsulation mechanisms, and hybrid encryption schemes, encompassing public key, identity-based, and tag-based encryption and also gave several concrete constructions. But we also note that their constructions cannot simultaneously satisfy the four requirements on “PVPKE”: (1) chosen ciphertext-secure; (2) publicly verifiable; (3) in the standard model; (4) without pairing. Thus their work further exploresPVPKE’s application but does not give concrete construction ofPVPKE.In Crypto’09, Hofheinz and Kiltz [28] introduced the group of signed quadratic residues and discussed its application; the most interesting feature of this group is its “gap” property, while the computational problem is as hard as factoring, and the corresponding decisional problem is easy. Membership in QRN+ can be publicly and efficiently verified while it inherits some nice intractability properties of the quadratic residues. For example, computing square roots in QRN+ is also equivalent to factoring the modulus N. We therefore have a gap group, in which the corresponding decisional problem (i.e., deciding if an element is a signed square) is easy, whereas the computational problem (i.e., computing a square root) is as hard as factoring. We also can show that, in the group of signed quadratic residues, the Strong Diffie-Hellman problem is implied by the factoring assumption.


### 1.1. Our Contribution

In [13], based on the core idea of changing the prime modular field to the composite modular field and masking the verifying secret key with secret order of the composite group and making the resulting “pseudosecret key” public, we find it is relatively easy to constructPVPKE scheme based on the Cramer-Shoup encryption and the Hanaoka-KurosawaCCA-secure public key encryption.In this paper, we show that, in case of basing some of Nieto et al.’s schemes on signed quadratic residues, the resulting schemes can meet the requirements ofPVPKE. The core idea about this construction is that the DDH oracle can be publicly instantiated by bilinear pairing, while DDH oracle cannot be instantiated by discrete logarithm group or RSA group. But, in signed quadratic residues, the DDH oracle can be efficiently publicly instantiated. Based on this observation, we give new constructions ofPVPKE scheme based on signed quadratic residues and discuss their security.Furthermore, we discussPVPKE’s important application in modern information system, such as achieving ciphertext checkable in the cloud setting for the mobile laptop, reducing the workload by the gateway between the open internet and the trusted private network, and dropping the invalid ciphertext by the routers for helping the network to preserve its communication bandwidth effectively.


### 1.2. Related Works

#### 1.2.1. Chosen Ciphertext Security in the Standard Model

Naor and Yung [29] introduced the notion ofCCA security for public key encryption, and this notion was further extended by Rackoff and Simon [30], Dolev et al. [31], and Sahai [32].Noninteractive zero-knowledge (NIZK) proofs are core blocks of these constructions, which is a relatively inefficient paradigm and its efficient realization always relies on bilinear pairing or random orale. In 1993, Bellare and Rogaway [33] introduced a so-calledrandom oracle which idealizes the hash function as a perfect random function to devise efficientCCA-secure public key encryption with provable security. However, random oracle model has seen criticism by cryptographers for its unrealistic assumption [34]. More and more cryptographers show interest in constructing efficient CCA-securePKE in the standard model. Till now, there are at least four ways to construct efficient CCA-securePKE in the standard model. The first way is proposed by Cramer and Shoup [8], which was further extended by themselves and other cryptographers [35–37]. The second way to construct CCA-securePKE is the paradigm of IBE transformation, which allows transforming selective-ID CPA-secure identity-based encryption (IBE) into a CCA-securePKE [38–41]. The third way is based onverifiable broadcast encryption, which is proposed by Hanaoka and Kurosawa [9]. The fourth way is by relying on lossy trapdoor function introduced by Peikert and Waters [42] and further extended by Rosen and Segev [43] and many other works. Among the CCA-secure PKE schemes from these four ways, only the ones from theIBE transformation are publicly verifiable. However, most of existing practicalIBE are based on the time-consuming pairings.


#### 1.2.2. Without Pairings

The bilinear pairings enable the construction of first practical identity-based encryption by Boneh and Franklin [44]. Since then, many wonderful results can be achieved by using the bilinear pairings, such as fully collusion resistant broadcast encryption [45], efficient practical zero-knowledge proof [46], searchable public key encryption [47, 48], attribute based encryption [49], and predicate encryption [50].But we note that, on the one hand, bilinear pairing is a very powerful cryptographic tool; on the other hand, the implementation speed of bilinear pairing is still relatively slower. So recently many researchers show interest in construction of schemes without pairings, because, on the one hand, it can clarify to us which cryptographic task inherits the bilinear property of pairings and which does not; on the other hand, it gives us a new view on old cryptographic problems. For example, Baek et al. constructed the first certificateless public key encryption without pairing [51], while the concept of certificateless public key cryptography was first raised by using bilinear pairings [52]. Other examples include Deng et al. and Shao and Cao’sCCA-secure proxy reencryption without pairing [53, 54].


#### 1.2.3. Verifiable Public Key Encryption

Another related research area is (private) verifiable public key encryption, such as Camenisch and Shoup’s work [55]. However, their work was concerned with only the decryptor’s verifiability of the ciphertext instead ofpublic verifiability. Kiayias et al. extended their work by introducing some new concepts for constructing group encryption [56]. Owing to bilinear property of pairings,CCA-secure public key encryption with public verifiability can be easily achieved in the bilinear pairing setting. However, the situation is completely different in the “without pairing” setting; constructingPVPKE scheme remains as an open problem left for almost decades.


### 1.3. Organization

We organize our paper as follows: In Section2, we give some preliminaries. In Section 3, we give ourPVPKE’s construction based on signed quadratic residues and analyse its security. In Section 4, we discussPVPKE’s applications. In the last section, we give our conclusion.


## 1.1. Our Contribution

In [13], based on the core idea of changing the prime modular field to the composite modular field and masking the verifying secret key with secret order of the composite group and making the resulting “pseudosecret key” public, we find it is relatively easy to constructPVPKE scheme based on the Cramer-Shoup encryption and the Hanaoka-KurosawaCCA-secure public key encryption.In this paper, we show that, in case of basing some of Nieto et al.’s schemes on signed quadratic residues, the resulting schemes can meet the requirements ofPVPKE. The core idea about this construction is that the DDH oracle can be publicly instantiated by bilinear pairing, while DDH oracle cannot be instantiated by discrete logarithm group or RSA group. But, in signed quadratic residues, the DDH oracle can be efficiently publicly instantiated. Based on this observation, we give new constructions ofPVPKE scheme based on signed quadratic residues and discuss their security.Furthermore, we discussPVPKE’s important application in modern information system, such as achieving ciphertext checkable in the cloud setting for the mobile laptop, reducing the workload by the gateway between the open internet and the trusted private network, and dropping the invalid ciphertext by the routers for helping the network to preserve its communication bandwidth effectively.


## 1.2. Related Works

### 1.2.1. Chosen Ciphertext Security in the Standard Model

Naor and Yung [29] introduced the notion ofCCA security for public key encryption, and this notion was further extended by Rackoff and Simon [30], Dolev et al. [31], and Sahai [32].Noninteractive zero-knowledge (NIZK) proofs are core blocks of these constructions, which is a relatively inefficient paradigm and its efficient realization always relies on bilinear pairing or random orale. In 1993, Bellare and Rogaway [33] introduced a so-calledrandom oracle which idealizes the hash function as a perfect random function to devise efficientCCA-secure public key encryption with provable security. However, random oracle model has seen criticism by cryptographers for its unrealistic assumption [34]. More and more cryptographers show interest in constructing efficient CCA-securePKE in the standard model. Till now, there are at least four ways to construct efficient CCA-securePKE in the standard model. The first way is proposed by Cramer and Shoup [8], which was further extended by themselves and other cryptographers [35–37]. The second way to construct CCA-securePKE is the paradigm of IBE transformation, which allows transforming selective-ID CPA-secure identity-based encryption (IBE) into a CCA-securePKE [38–41]. The third way is based onverifiable broadcast encryption, which is proposed by Hanaoka and Kurosawa [9]. The fourth way is by relying on lossy trapdoor function introduced by Peikert and Waters [42] and further extended by Rosen and Segev [43] and many other works. Among the CCA-secure PKE schemes from these four ways, only the ones from theIBE transformation are publicly verifiable. However, most of existing practicalIBE are based on the time-consuming pairings.


### 1.2.2. Without Pairings

The bilinear pairings enable the construction of first practical identity-based encryption by Boneh and Franklin [44]. Since then, many wonderful results can be achieved by using the bilinear pairings, such as fully collusion resistant broadcast encryption [45], efficient practical zero-knowledge proof [46], searchable public key encryption [47, 48], attribute based encryption [49], and predicate encryption [50].But we note that, on the one hand, bilinear pairing is a very powerful cryptographic tool; on the other hand, the implementation speed of bilinear pairing is still relatively slower. So recently many researchers show interest in construction of schemes without pairings, because, on the one hand, it can clarify to us which cryptographic task inherits the bilinear property of pairings and which does not; on the other hand, it gives us a new view on old cryptographic problems. For example, Baek et al. constructed the first certificateless public key encryption without pairing [51], while the concept of certificateless public key cryptography was first raised by using bilinear pairings [52]. Other examples include Deng et al. and Shao and Cao’sCCA-secure proxy reencryption without pairing [53, 54].


### 1.2.3. Verifiable Public Key Encryption

Another related research area is (private) verifiable public key encryption, such as Camenisch and Shoup’s work [55]. However, their work was concerned with only the decryptor’s verifiability of the ciphertext instead ofpublic verifiability. Kiayias et al. extended their work by introducing some new concepts for constructing group encryption [56]. Owing to bilinear property of pairings,CCA-secure public key encryption with public verifiability can be easily achieved in the bilinear pairing setting. However, the situation is completely different in the “without pairing” setting; constructingPVPKE scheme remains as an open problem left for almost decades.


## 1.2.1. Chosen Ciphertext Security in the Standard Model

Naor and Yung [29] introduced the notion ofCCA security for public key encryption, and this notion was further extended by Rackoff and Simon [30], Dolev et al. [31], and Sahai [32].Noninteractive zero-knowledge (NIZK) proofs are core blocks of these constructions, which is a relatively inefficient paradigm and its efficient realization always relies on bilinear pairing or random orale. In 1993, Bellare and Rogaway [33] introduced a so-calledrandom oracle which idealizes the hash function as a perfect random function to devise efficientCCA-secure public key encryption with provable security. However, random oracle model has seen criticism by cryptographers for its unrealistic assumption [34]. More and more cryptographers show interest in constructing efficient CCA-securePKE in the standard model. Till now, there are at least four ways to construct efficient CCA-securePKE in the standard model. The first way is proposed by Cramer and Shoup [8], which was further extended by themselves and other cryptographers [35–37]. The second way to construct CCA-securePKE is the paradigm of IBE transformation, which allows transforming selective-ID CPA-secure identity-based encryption (IBE) into a CCA-securePKE [38–41]. The third way is based onverifiable broadcast encryption, which is proposed by Hanaoka and Kurosawa [9]. The fourth way is by relying on lossy trapdoor function introduced by Peikert and Waters [42] and further extended by Rosen and Segev [43] and many other works. Among the CCA-secure PKE schemes from these four ways, only the ones from theIBE transformation are publicly verifiable. However, most of existing practicalIBE are based on the time-consuming pairings.


## 1.2.2. Without Pairings

The bilinear pairings enable the construction of first practical identity-based encryption by Boneh and Franklin [44]. Since then, many wonderful results can be achieved by using the bilinear pairings, such as fully collusion resistant broadcast encryption [45], efficient practical zero-knowledge proof [46], searchable public key encryption [47, 48], attribute based encryption [49], and predicate encryption [50].But we note that, on the one hand, bilinear pairing is a very powerful cryptographic tool; on the other hand, the implementation speed of bilinear pairing is still relatively slower. So recently many researchers show interest in construction of schemes without pairings, because, on the one hand, it can clarify to us which cryptographic task inherits the bilinear property of pairings and which does not; on the other hand, it gives us a new view on old cryptographic problems. For example, Baek et al. constructed the first certificateless public key encryption without pairing [51], while the concept of certificateless public key cryptography was first raised by using bilinear pairings [52]. Other examples include Deng et al. and Shao and Cao’sCCA-secure proxy reencryption without pairing [53, 54].


## 1.2.3. Verifiable Public Key Encryption

Another related research area is (private) verifiable public key encryption, such as Camenisch and Shoup’s work [55]. However, their work was concerned with only the decryptor’s verifiability of the ciphertext instead ofpublic verifiability. Kiayias et al. extended their work by introducing some new concepts for constructing group encryption [56]. Owing to bilinear property of pairings,CCA-secure public key encryption with public verifiability can be easily achieved in the bilinear pairing setting. However, the situation is completely different in the “without pairing” setting; constructingPVPKE scheme remains as an open problem left for almost decades.


## 1.3. Organization

We organize our paper as follows: In Section2, we give some preliminaries. In Section 3, we give ourPVPKE’s construction based on signed quadratic residues and analyse its security. In Section 4, we discussPVPKE’s applications. In the last section, we give our conclusion.


## 2. Preliminaries

### 2.1. Publicly Verifiable Public Key Encryption

A publicly verifiable public key encryption system consists of the following algorithms.(i)
The randomized key generation algorithmGen takes as input a security parameter 1k and outputs a public key (PK) and a secret key (SK). We write (PK,SK)←Gen(1k).(ii)
The randomized encryption algorithmE takes as input a public key (PK) and a message m∈{0,1}∗ and outputs a ciphertext C. We write C←EPK(m).(iii)
The verification algorithmV takes as input a ciphertext C and a public key (PK). It returns valid or invalid to indicate whether the ciphertext is valid or not. Note that the validity of C can be verified publicly.(iv)
The decryption algorithmD takes as input a ciphertext C and a secret key (SK). It returns a message m∈{0.1}∗ or the distinguished symbol ⊥. We write m←DSK(C). We require that, for all (PK,SK) output byGen, all m∈{0,1}∗, and all C output by EPK(m), we have DSK=m.


### 2.2.  Chosen Ciphertext Security

We recall the standard definition of security against adaptive chosen ciphertext attack. A publicly verifiable public key encryption (PKE) scheme  is secure against adaptive chosen ciphertext attacks (i.e., “CCA-secure”) if the advantage of any PPT adversary A in the following game is negligible in the security parameter k.(1)
Gen(1k) outputs (PK, SK). Adversary A is given 1k and PK.(2)
The adversary may make many polynomial-many queries to a decryption oracleDSK(·).(3)
The adversary may make many polynomial-many queries to a verification oracleVPK(·).(4)
At some point,A outputs two messages m0, m1 with m0=m1. A bit b is randomly chosen and the adversary is given a “challenge ciphertext” C∗←EPK(mb).(5)
A may continue to query its decryption oracle DSK(·) except that it may not request the decryption of C∗.(6)
A may continue to make polynomial-many queries to a verification oracle VPK(·).(7)
Finally,A outputs a guess b′. We say that A succeeds if b′=b and denote the probability of this event by PrA,PKE[Succ]. The adversary’s advantage is defined as |PrA,PKE[Succ]-1/2|.


### 2.3.  The Group of Signed Quadratic Residues

#### 2.3.1. RSA Instance Generator

Let0≤δ≤1/2 be a constant and let n(k) be a function. LetRSAgen be an algorithm that generates elements (N,P,Q), such that N=PQ is an n-bit Blum integer (N=PQ (where  P=3mod4 and Q=3mod4)) and all prime factors of ϕ(N)/4 are pairwise distinct and at least δn-bit integers.


#### 2.3.2. Factoring Assumption

The factoring assumption is that computingP, Q from N (generated byRSAgen) is hard. We write (1)AdvA,RSAGenfacW=PrP,Q⟵RAN:N,P,Q⟵RRSAGen1k. The factoring assumption forRSAgen holds if AdvA,RSAGenfac is negligible for all efficient A.


#### 2.3.3. The Group of Signed Quadratic Residues

LetN be an integer. For x∈ZN we define x as the absolute value of x, where x is represented as a signed integer in the set {-(N-1)/2,…,(N-1)/2}. For a subgroup G of ZN∗, we define the signed group, G+, as the group (2)G+=x:x∈G with the following group operation. Namely, for g,h∈G+ and an integer x, we define (3)g∘h=g·hmodN,gx_=g∘g∘⋯∘g=gxmodN.More complicated expressions in the exponents are computed modulo the group order; for example, g1/2_=g2-1modord(G+)_. Note that taking the absolute value is a surjective homomorphism from G to G+ with trivial kernel if -1 does not belong to G and with kernel {-1,1} if -1∈G.LetN be a Blum integer such that -1 does not belong to QRN. We will mainly be interested in QRN+, which we callsigned quadratic residues (modulo N). QRN+ is a subgroup of ZN∗/±1, with absolute values as a convenient computational representation. The following basic facts hold.Theorem 1.
LetN be a Blum integer; then we have the following. (1)
(QRN+,∘) is a group of order ϕ(N)/4.(2)
QRN+=JN+. In particular, QRN+ is efficiently recognizable (given only N).(3)
IfQRN is cyclic, so is QRN+.


#### 2.3.4. Strong DH Assumption Reduced to Factoring Assumption

Hofheinz and Kiltz [28] also proved that the strong DH assumption can be reduced to factoring assumption. Here we review the theorem and its proof.Theorem 2.
If the factoring assumption holds then the strong DH assumption holds relative toRSAgen. In particular, for every strong DH adversary A, there exists a factoring adversary B (with roughly the same complexity as A) such that(4)AdvA,RSAgenSDHk≤AdvB,RSAgenfack+O2-δnk.Proof.
We constructB from given A. Concretely, B receives a challenge N=PQ, chooses uniformly u←R(ZN∗)+∖QRN+, and sets h=u2_. Note that, by definition of N, we have h=QRN+ except with probability O(2-δn(k)). Then B chooses a,b∈[N/4] and sets (5)g≔h2_,X≔h∘ga_,Y≔h∘gb_(here we omit modN operation, and hereafter we continue to omit modN for typical exponential modular operation). This implicitly defines(6)dloggX=a+12modordQRN+,dloggY=b+12modordQRN+,where the discrete logarithms are of course considered in (QRN+,∘). Again, by definition of N, the statistical distance between these (g,X,Y) and the input of A in the strong DH experiment is bounded by O(2-δn(k)). So B runs A on input (g,X,Y) and answers A’s oracle queries (Y^,Z^) as follows. First, we may assume that (Y^,Z^)∈QRN+ since QRN+=JN+ is efficiently recognizable. Next, since N is a Blum integer, the group order ord(QRN+)=(P-1)(Q-1)/4 is odd, and hence (7)Y^dloggX_=Z^⟺Y^2dloggX_=Z^2_⟺Y^2a+1=Z^2_.Thus, B can implement the strong DH oracle by checking whether Y^2a+1=Z^2_ hold.
Consequently, with probabilityAdvA,RSAgenSDH(k)-O(2-δn(k)), A will finally output (8)Z=gdloggXdloggY_=ga+1/2b+1/2_=h2ab+a+b+1/2_∈QRN+from which B can extract v:=h1/2_∈QRN+ (using its knowledge about a and b). Since u is not in QRN+ and v∈QRN+ are two nontrivially different square roots of h, B can factor N by computing gcd(u-v,N).


## 2.1. Publicly Verifiable Public Key Encryption

A publicly verifiable public key encryption system consists of the following algorithms.(i)
The randomized key generation algorithmGen takes as input a security parameter 1k and outputs a public key (PK) and a secret key (SK). We write (PK,SK)←Gen(1k).(ii)
The randomized encryption algorithmE takes as input a public key (PK) and a message m∈{0,1}∗ and outputs a ciphertext C. We write C←EPK(m).(iii)
The verification algorithmV takes as input a ciphertext C and a public key (PK). It returns valid or invalid to indicate whether the ciphertext is valid or not. Note that the validity of C can be verified publicly.(iv)
The decryption algorithmD takes as input a ciphertext C and a secret key (SK). It returns a message m∈{0.1}∗ or the distinguished symbol ⊥. We write m←DSK(C). We require that, for all (PK,SK) output byGen, all m∈{0,1}∗, and all C output by EPK(m), we have DSK=m.


## 2.2.  Chosen Ciphertext Security

We recall the standard definition of security against adaptive chosen ciphertext attack. A publicly verifiable public key encryption (PKE) scheme  is secure against adaptive chosen ciphertext attacks (i.e., “CCA-secure”) if the advantage of any PPT adversary A in the following game is negligible in the security parameter k.(1)
Gen(1k) outputs (PK, SK). Adversary A is given 1k and PK.(2)
The adversary may make many polynomial-many queries to a decryption oracleDSK(·).(3)
The adversary may make many polynomial-many queries to a verification oracleVPK(·).(4)
At some point,A outputs two messages m0, m1 with m0=m1. A bit b is randomly chosen and the adversary is given a “challenge ciphertext” C∗←EPK(mb).(5)
A may continue to query its decryption oracle DSK(·) except that it may not request the decryption of C∗.(6)
A may continue to make polynomial-many queries to a verification oracle VPK(·).(7)
Finally,A outputs a guess b′. We say that A succeeds if b′=b and denote the probability of this event by PrA,PKE[Succ]. The adversary’s advantage is defined as |PrA,PKE[Succ]-1/2|.


## 2.3.  The Group of Signed Quadratic Residues

### 2.3.1. RSA Instance Generator

Let0≤δ≤1/2 be a constant and let n(k) be a function. LetRSAgen be an algorithm that generates elements (N,P,Q), such that N=PQ is an n-bit Blum integer (N=PQ (where  P=3mod4 and Q=3mod4)) and all prime factors of ϕ(N)/4 are pairwise distinct and at least δn-bit integers.


### 2.3.2. Factoring Assumption

The factoring assumption is that computingP, Q from N (generated byRSAgen) is hard. We write (1)AdvA,RSAGenfacW=PrP,Q⟵RAN:N,P,Q⟵RRSAGen1k. The factoring assumption forRSAgen holds if AdvA,RSAGenfac is negligible for all efficient A.


### 2.3.3. The Group of Signed Quadratic Residues

LetN be an integer. For x∈ZN we define x as the absolute value of x, where x is represented as a signed integer in the set {-(N-1)/2,…,(N-1)/2}. For a subgroup G of ZN∗, we define the signed group, G+, as the group (2)G+=x:x∈G with the following group operation. Namely, for g,h∈G+ and an integer x, we define (3)g∘h=g·hmodN,gx_=g∘g∘⋯∘g=gxmodN.More complicated expressions in the exponents are computed modulo the group order; for example, g1/2_=g2-1modord(G+)_. Note that taking the absolute value is a surjective homomorphism from G to G+ with trivial kernel if -1 does not belong to G and with kernel {-1,1} if -1∈G.LetN be a Blum integer such that -1 does not belong to QRN. We will mainly be interested in QRN+, which we callsigned quadratic residues (modulo N). QRN+ is a subgroup of ZN∗/±1, with absolute values as a convenient computational representation. The following basic facts hold.Theorem 1.
LetN be a Blum integer; then we have the following. (1)
(QRN+,∘) is a group of order ϕ(N)/4.(2)
QRN+=JN+. In particular, QRN+ is efficiently recognizable (given only N).(3)
IfQRN is cyclic, so is QRN+.


### 2.3.4. Strong DH Assumption Reduced to Factoring Assumption

Hofheinz and Kiltz [28] also proved that the strong DH assumption can be reduced to factoring assumption. Here we review the theorem and its proof.Theorem 2.
If the factoring assumption holds then the strong DH assumption holds relative toRSAgen. In particular, for every strong DH adversary A, there exists a factoring adversary B (with roughly the same complexity as A) such that(4)AdvA,RSAgenSDHk≤AdvB,RSAgenfack+O2-δnk.Proof.
We constructB from given A. Concretely, B receives a challenge N=PQ, chooses uniformly u←R(ZN∗)+∖QRN+, and sets h=u2_. Note that, by definition of N, we have h=QRN+ except with probability O(2-δn(k)). Then B chooses a,b∈[N/4] and sets (5)g≔h2_,X≔h∘ga_,Y≔h∘gb_(here we omit modN operation, and hereafter we continue to omit modN for typical exponential modular operation). This implicitly defines(6)dloggX=a+12modordQRN+,dloggY=b+12modordQRN+,where the discrete logarithms are of course considered in (QRN+,∘). Again, by definition of N, the statistical distance between these (g,X,Y) and the input of A in the strong DH experiment is bounded by O(2-δn(k)). So B runs A on input (g,X,Y) and answers A’s oracle queries (Y^,Z^) as follows. First, we may assume that (Y^,Z^)∈QRN+ since QRN+=JN+ is efficiently recognizable. Next, since N is a Blum integer, the group order ord(QRN+)=(P-1)(Q-1)/4 is odd, and hence (7)Y^dloggX_=Z^⟺Y^2dloggX_=Z^2_⟺Y^2a+1=Z^2_.Thus, B can implement the strong DH oracle by checking whether Y^2a+1=Z^2_ hold.
Consequently, with probabilityAdvA,RSAgenSDH(k)-O(2-δn(k)), A will finally output (8)Z=gdloggXdloggY_=ga+1/2b+1/2_=h2ab+a+b+1/2_∈QRN+from which B can extract v:=h1/2_∈QRN+ (using its knowledge about a and b). Since u is not in QRN+ and v∈QRN+ are two nontrivially different square roots of h, B can factor N by computing gcd(u-v,N).


## 2.3.1. RSA Instance Generator

Let0≤δ≤1/2 be a constant and let n(k) be a function. LetRSAgen be an algorithm that generates elements (N,P,Q), such that N=PQ is an n-bit Blum integer (N=PQ (where  P=3mod4 and Q=3mod4)) and all prime factors of ϕ(N)/4 are pairwise distinct and at least δn-bit integers.


## 2.3.2. Factoring Assumption

The factoring assumption is that computingP, Q from N (generated byRSAgen) is hard. We write (1)AdvA,RSAGenfacW=PrP,Q⟵RAN:N,P,Q⟵RRSAGen1k. The factoring assumption forRSAgen holds if AdvA,RSAGenfac is negligible for all efficient A.


## 2.3.3. The Group of Signed Quadratic Residues

LetN be an integer. For x∈ZN we define x as the absolute value of x, where x is represented as a signed integer in the set {-(N-1)/2,…,(N-1)/2}. For a subgroup G of ZN∗, we define the signed group, G+, as the group (2)G+=x:x∈G with the following group operation. Namely, for g,h∈G+ and an integer x, we define (3)g∘h=g·hmodN,gx_=g∘g∘⋯∘g=gxmodN.More complicated expressions in the exponents are computed modulo the group order; for example, g1/2_=g2-1modord(G+)_. Note that taking the absolute value is a surjective homomorphism from G to G+ with trivial kernel if -1 does not belong to G and with kernel {-1,1} if -1∈G.LetN be a Blum integer such that -1 does not belong to QRN. We will mainly be interested in QRN+, which we callsigned quadratic residues (modulo N). QRN+ is a subgroup of ZN∗/±1, with absolute values as a convenient computational representation. The following basic facts hold.Theorem 1.
LetN be a Blum integer; then we have the following. (1)
(QRN+,∘) is a group of order ϕ(N)/4.(2)
QRN+=JN+. In particular, QRN+ is efficiently recognizable (given only N).(3)
IfQRN is cyclic, so is QRN+.


## 2.3.4. Strong DH Assumption Reduced to Factoring Assumption

Hofheinz and Kiltz [28] also proved that the strong DH assumption can be reduced to factoring assumption. Here we review the theorem and its proof.Theorem 2.
If the factoring assumption holds then the strong DH assumption holds relative toRSAgen. In particular, for every strong DH adversary A, there exists a factoring adversary B (with roughly the same complexity as A) such that(4)AdvA,RSAgenSDHk≤AdvB,RSAgenfack+O2-δnk.Proof.
We constructB from given A. Concretely, B receives a challenge N=PQ, chooses uniformly u←R(ZN∗)+∖QRN+, and sets h=u2_. Note that, by definition of N, we have h=QRN+ except with probability O(2-δn(k)). Then B chooses a,b∈[N/4] and sets (5)g≔h2_,X≔h∘ga_,Y≔h∘gb_(here we omit modN operation, and hereafter we continue to omit modN for typical exponential modular operation). This implicitly defines(6)dloggX=a+12modordQRN+,dloggY=b+12modordQRN+,where the discrete logarithms are of course considered in (QRN+,∘). Again, by definition of N, the statistical distance between these (g,X,Y) and the input of A in the strong DH experiment is bounded by O(2-δn(k)). So B runs A on input (g,X,Y) and answers A’s oracle queries (Y^,Z^) as follows. First, we may assume that (Y^,Z^)∈QRN+ since QRN+=JN+ is efficiently recognizable. Next, since N is a Blum integer, the group order ord(QRN+)=(P-1)(Q-1)/4 is odd, and hence (7)Y^dloggX_=Z^⟺Y^2dloggX_=Z^2_⟺Y^2a+1=Z^2_.Thus, B can implement the strong DH oracle by checking whether Y^2a+1=Z^2_ hold.
Consequently, with probabilityAdvA,RSAgenSDH(k)-O(2-δn(k)), A will finally output (8)Z=gdloggXdloggY_=ga+1/2b+1/2_=h2ab+a+b+1/2_∈QRN+from which B can extract v:=h1/2_∈QRN+ (using its knowledge about a and b). Since u is not in QRN+ and v∈QRN+ are two nontrivially different square roots of h, B can factor N by computing gcd(u-v,N).


## 3. CCA-Secure Publicly Verifiable Public Key Encryption in the Standard Model Based on Signed Quadratic Residues

### 3.1. Review of Nieto et al.’s Publicly Verifiable PKE Scheme

Their construction is inspired by the IND-CCA public key KEM of Kiltz [57]; thePG(ParamGen) algorithm is similar to [57] except that it uses gap groups: PG(1k) outputs public parameters par=(G,p,g,DDH,H), where G=g is a multiplicative cyclic group of prime order p, 2k≤p≤2k+1, DDH is an efficient algorithm such that DDH(ga,gb,gc)=1↔c=ab(p), and H:G→{0,1}l1(k) is a cryptographic hash function such that l1(k) is a polynomial in k. We also use a strong one-time signature scheme OTS=(KG,Sign,Vrfy) with verification key space {0,1}l2(k) such that l2(k) is a polynomial in k and a target collision resistant hash function TCR:G×{0,1}l2(k)→Zp. The message space is MsgSp={0,1}l1(k). The scheme works as follows.(i)
PKE.KG(par)(9)x⟵Zp∗u⟵gx,v⟵Gek⟵u,v,dk⟵xReturnek,dk(ii)
PKE.Enc(par,ek,M)(10)u,v⟵ekvk,sigk⟵OTS.KG1kr⟵RZp∗,c1⟵grt⟵TCRc1,vk,π⟵utvrK⟵Hur,c2⟵M⊕Kc⟵c1,c2,πδ⟵OTS.Signsigk,cReturnC=c,δ,vk(iii)
PKE.Ver(par,ek,C)(11)u,v⟵ekc,δ,vk⟵Cc1,c2,ϕ⟵ct⟵TCRc1,vkIfDDHc1,utv,π≠1OrOTS.Vrfyc,δ,vk=⊥,return⊥ReturnC′=c1,c2(iv)
PKE.Dec′(par,ek,dk,C′)(12)c1,c2⟵C′x⟵dkK⟵Hc1x,M⟵c2⊕KReturnM.


### 3.2. Our Proposed PVPKE Scheme Based on Signed Quadratic Residues

First we give the core idea behind our construction. We observe that Nieto et al.’s PKE scheme actually is a PVPKE scheme, but the only issue is that they use an abstract DDH oracle. They instantiate this oracle by bilinear pairings, but we require that PVPKE scheme cannot rely on bilinear pairings. We also observe that signed quadratic residues can also instantiate the abstract DDH oracle, so we modify Nieto et al.’s scheme to be based on signed quadratic residues group, which now give a natural new PVPKE scheme. Notation: we omit themodN operation and every modular exponentiation in signed quadratic residues such as the fact that h=u2_ is represented as h=u2, which implies all the modular exponentiation and other operations obey the rules defined in [28] instead of obeying the normal group rules. The following is the concrete scheme.(i)
PVPKE.PG(1k) is as follows.
(a)
Here we focus onQRN+ group; we first generate an RSA modulus N=PQ withRSAgen(1k) [28], then choose uniformly u←R(ZN∗)+∖QRN+, and set h=u2. Note that, by definition of N, we have G=h=QRN+ except with probability O(2-δn(k)).(b)
H:G→{0,1}l1(k) is a cryptographic hash function such that l1(k) is a polynomial in k.(c)
We also use a strong one-time signature schemeOTS=(KG,Sign,Vrfy) with verification key space {0,1}l2(k) such that l2(k) is a polynomial in k and a target collision resistant hash function TCR:G×{0,1}l2(k)→Zp. The message space is MsgSp={0,1}l1(k).(d)
DDH is an efficient algorithm such thatDDH(ga,gb,gc)=1↔c=abmodp. For the scheme relying on QRN+ group, we can easily decide the DDH tuple; concretely, we do the following.
(1)
Choosea,b∈[N/4] and m,n∈ord(QRN+) satisfying 2m(a+1/2)>n×ord(QRN+), 2m(b+1/2)>n×ord(QRN+), and m is not very little. Then set (13)g≔h2,X≔h∘ga,Y≔h∘gb.(2)
Publisha′=2m(a+1/2)modn×ord(QRN+), b′=2m(b+1/2)modn×ord(QRN+) as the parameters for public verifying.(3)
TheDDHParams = (g,X,Y,a′,b′,2m).(e)
PG(1k) outputs public parameters par=(G,N,DDHParams, H,OTS)=(G,N,g,X,Y,a′,b′,2m,H,OTS).(ii)
PVPKE.KG(par)(14)x⟵ZN∗u⟵gx,X=h∘ga,Y=h∘gbek⟵u,X,Y,dk⟵xReturnek,dk(iii)
PVPKE.Enc(par,ek,M)(15)u,X,Y⟵ekvk,sigk⟵OTS.KG1kr⟵RZN∗,c1⟵grt⟵TCRc1,vk,π⟵XtYrK⟵Hur,c2⟵M⊕Kc⟵c1,c2,πδ⟵OTS.Signsigk,cReturnC=c,δ,vk(iv)
PVPKE.Ver(par,ek,C)(16)u,X,Y⟵ekc,δ,vk⟵Cc1,c2,π⟵ct⟵TCRc1,vkIfc1a′t+b′≠π2mOrOTS.Vrfyc,δ,vk=⊥,return⊥ReturnC′=c1,c2(v)
PVPKE.Dec′(par,ek,dk,C′)(17)c1,c2⟵C′x⟵dkK⟵Hc1x,M⟵c2⊕KReturnM.


### 3.3. Security Analysis

Based on Nieto et al.’s security result and the property of signed quadratic residues, we can give the following theorem.Theorem 3.
Assume thatTCR is a target collision resistant hash function andOTS is a strongly unforgeable one-time signature scheme. Under a variant of hashed Diffie-Hellman assumption for G (signed quadratic residues group) and H, the factoring assumption ofRSAGen (which implies the strong Diffie-Hellman assumption in signed quadratic residues group proved in [28]), our PVPKE scheme based on signed quadratic residues is IND-CCA-secure.Proof.
In the following we give our scheme’s security proof roughly.(1)
We observe that, in Nieto et al.’s PKE scheme,u plays two roles: one used to be deriving the DEM message mask key and the other used to be as part of the DDH test. But many research results show that it is secure to split these two roles separately [8]; thus we introduce X as the role of part of the DDH test, while maintaining  u as the source of deriving DEM message mask key, which is the reason why we use (XtY) instead of (utv) in our scheme.(2)
In our scheme, we adopt Hofheinz and Kiltz’s technique of reducing SDH assumption to the factoring assumption; concretely, we setX, Y, g, h, a, and b the same as theirs, but we make a′=2m(a+1/2)modn×ord(QRN+) and b′=2mb+12modn×ord(QRN+) public, which is used for public verifying. The verifying equation (gr)a′t+b′=((XtY)r)2m can also be used for deciding the DDH relationship of (g,XtY,gr,(XtY)r), but an attacker cannot figure out π=(XtY)r through finding 1/2m root of (gr)a′t+b′, for we know finding square root in QRN is as hard as factoring and this also holds in QRN+.(3)
We require2m(a+1/2)>n×ord(QRN+), 2m(b+1/2)>n×ord(QRN+) for avoiding the trivial attack of computing a+1/2=a′/2m and b+1/2=b′/2m without any modular operation, and thus trivial computing π=(XtY)r=(gr)(a+1/2)t+(b+1/2). Obviously this attack can easily forge a valid π and thus a valid ciphertext and break the IND-CCA property. We also require that m is not too little to resist the brute force attack on finding a from a′.(4)
Generally speaking, our scheme is almost identical to Nieto et al.’s scheme; thus the security proof is almost the same as theirs. Below are the details.Let(c∗,δ∗,vk∗) be the challenge ciphertext. The proposed PKE without the CHK transform can be seen as a KEM/DEM combination, which is at least IND-CPA-secure due to Herranz et al. [58]. As for the KEM, a variant of the hashed Diffie-Hellman (HDH) assumption [48] can be used to prove the IND-CPA security of the resulting PKE. Note that the message does not depend on vk∗ and is just the signature on c∗. Therefore c∗ being an output of the IND-CPA-secure scheme hides the value of the chosen b from the adversary.Below we prove that the IND-CCA adversaryA may access decryption oracle and will gain no help in guessing the value of b. Suppose the adversary submits a ciphertext (c′,δ′,vk′)≠(c∗,δ∗,vk∗) to the decryption oracle. Now there are two cases.
(i)
Whenvk′=vk∗, the decryption oracle will output ⊥ as the adversary fails to break the underlying strongly unforgeable one-time signature scheme with respect to vk′.(ii)
Whenvk′≠vk, the attacker B against the variant of HDH problem can set the public keys as seen in the IND-CCA security proof for the KEM by Kiltz [57] such that (1) B can answer except for the challenge ciphertext all decryption queries from A even without the knowledge of the secret key and (2) B solves HDH if A wins. Note in Nieto et al.’s scheme u,v is the public key while in our scheme u,X,Y is the public key, but we observe v is randomly chosen from G, while in our scheme X,Y are set as h∘ga, h∘gb which are also random because a,b are random. Thus our scheme roughly shares the same security proof outline as in [57] except that our scheme is in signed quadratic residues.


## 3.1. Review of Nieto et al.’s Publicly Verifiable PKE Scheme

Their construction is inspired by the IND-CCA public key KEM of Kiltz [57]; thePG(ParamGen) algorithm is similar to [57] except that it uses gap groups: PG(1k) outputs public parameters par=(G,p,g,DDH,H), where G=g is a multiplicative cyclic group of prime order p, 2k≤p≤2k+1, DDH is an efficient algorithm such that DDH(ga,gb,gc)=1↔c=ab(p), and H:G→{0,1}l1(k) is a cryptographic hash function such that l1(k) is a polynomial in k. We also use a strong one-time signature scheme OTS=(KG,Sign,Vrfy) with verification key space {0,1}l2(k) such that l2(k) is a polynomial in k and a target collision resistant hash function TCR:G×{0,1}l2(k)→Zp. The message space is MsgSp={0,1}l1(k). The scheme works as follows.(i)
PKE.KG(par)(9)x⟵Zp∗u⟵gx,v⟵Gek⟵u,v,dk⟵xReturnek,dk(ii)
PKE.Enc(par,ek,M)(10)u,v⟵ekvk,sigk⟵OTS.KG1kr⟵RZp∗,c1⟵grt⟵TCRc1,vk,π⟵utvrK⟵Hur,c2⟵M⊕Kc⟵c1,c2,πδ⟵OTS.Signsigk,cReturnC=c,δ,vk(iii)
PKE.Ver(par,ek,C)(11)u,v⟵ekc,δ,vk⟵Cc1,c2,ϕ⟵ct⟵TCRc1,vkIfDDHc1,utv,π≠1OrOTS.Vrfyc,δ,vk=⊥,return⊥ReturnC′=c1,c2(iv)
PKE.Dec′(par,ek,dk,C′)(12)c1,c2⟵C′x⟵dkK⟵Hc1x,M⟵c2⊕KReturnM.


## 3.2. Our Proposed PVPKE Scheme Based on Signed Quadratic Residues

First we give the core idea behind our construction. We observe that Nieto et al.’s PKE scheme actually is a PVPKE scheme, but the only issue is that they use an abstract DDH oracle. They instantiate this oracle by bilinear pairings, but we require that PVPKE scheme cannot rely on bilinear pairings. We also observe that signed quadratic residues can also instantiate the abstract DDH oracle, so we modify Nieto et al.’s scheme to be based on signed quadratic residues group, which now give a natural new PVPKE scheme. Notation: we omit themodN operation and every modular exponentiation in signed quadratic residues such as the fact that h=u2_ is represented as h=u2, which implies all the modular exponentiation and other operations obey the rules defined in [28] instead of obeying the normal group rules. The following is the concrete scheme.(i)
PVPKE.PG(1k) is as follows.
(a)
Here we focus onQRN+ group; we first generate an RSA modulus N=PQ withRSAgen(1k) [28], then choose uniformly u←R(ZN∗)+∖QRN+, and set h=u2. Note that, by definition of N, we have G=h=QRN+ except with probability O(2-δn(k)).(b)
H:G→{0,1}l1(k) is a cryptographic hash function such that l1(k) is a polynomial in k.(c)
We also use a strong one-time signature schemeOTS=(KG,Sign,Vrfy) with verification key space {0,1}l2(k) such that l2(k) is a polynomial in k and a target collision resistant hash function TCR:G×{0,1}l2(k)→Zp. The message space is MsgSp={0,1}l1(k).(d)
DDH is an efficient algorithm such thatDDH(ga,gb,gc)=1↔c=abmodp. For the scheme relying on QRN+ group, we can easily decide the DDH tuple; concretely, we do the following.
(1)
Choosea,b∈[N/4] and m,n∈ord(QRN+) satisfying 2m(a+1/2)>n×ord(QRN+), 2m(b+1/2)>n×ord(QRN+), and m is not very little. Then set (13)g≔h2,X≔h∘ga,Y≔h∘gb.(2)
Publisha′=2m(a+1/2)modn×ord(QRN+), b′=2m(b+1/2)modn×ord(QRN+) as the parameters for public verifying.(3)
TheDDHParams = (g,X,Y,a′,b′,2m).(e)
PG(1k) outputs public parameters par=(G,N,DDHParams, H,OTS)=(G,N,g,X,Y,a′,b′,2m,H,OTS).(ii)
PVPKE.KG(par)(14)x⟵ZN∗u⟵gx,X=h∘ga,Y=h∘gbek⟵u,X,Y,dk⟵xReturnek,dk(iii)
PVPKE.Enc(par,ek,M)(15)u,X,Y⟵ekvk,sigk⟵OTS.KG1kr⟵RZN∗,c1⟵grt⟵TCRc1,vk,π⟵XtYrK⟵Hur,c2⟵M⊕Kc⟵c1,c2,πδ⟵OTS.Signsigk,cReturnC=c,δ,vk(iv)
PVPKE.Ver(par,ek,C)(16)u,X,Y⟵ekc,δ,vk⟵Cc1,c2,π⟵ct⟵TCRc1,vkIfc1a′t+b′≠π2mOrOTS.Vrfyc,δ,vk=⊥,return⊥ReturnC′=c1,c2(v)
PVPKE.Dec′(par,ek,dk,C′)(17)c1,c2⟵C′x⟵dkK⟵Hc1x,M⟵c2⊕KReturnM.


## 3.3. Security Analysis

Based on Nieto et al.’s security result and the property of signed quadratic residues, we can give the following theorem.Theorem 3.
Assume thatTCR is a target collision resistant hash function andOTS is a strongly unforgeable one-time signature scheme. Under a variant of hashed Diffie-Hellman assumption for G (signed quadratic residues group) and H, the factoring assumption ofRSAGen (which implies the strong Diffie-Hellman assumption in signed quadratic residues group proved in [28]), our PVPKE scheme based on signed quadratic residues is IND-CCA-secure.Proof.
In the following we give our scheme’s security proof roughly.(1)
We observe that, in Nieto et al.’s PKE scheme,u plays two roles: one used to be deriving the DEM message mask key and the other used to be as part of the DDH test. But many research results show that it is secure to split these two roles separately [8]; thus we introduce X as the role of part of the DDH test, while maintaining  u as the source of deriving DEM message mask key, which is the reason why we use (XtY) instead of (utv) in our scheme.(2)
In our scheme, we adopt Hofheinz and Kiltz’s technique of reducing SDH assumption to the factoring assumption; concretely, we setX, Y, g, h, a, and b the same as theirs, but we make a′=2m(a+1/2)modn×ord(QRN+) and b′=2mb+12modn×ord(QRN+) public, which is used for public verifying. The verifying equation (gr)a′t+b′=((XtY)r)2m can also be used for deciding the DDH relationship of (g,XtY,gr,(XtY)r), but an attacker cannot figure out π=(XtY)r through finding 1/2m root of (gr)a′t+b′, for we know finding square root in QRN is as hard as factoring and this also holds in QRN+.(3)
We require2m(a+1/2)>n×ord(QRN+), 2m(b+1/2)>n×ord(QRN+) for avoiding the trivial attack of computing a+1/2=a′/2m and b+1/2=b′/2m without any modular operation, and thus trivial computing π=(XtY)r=(gr)(a+1/2)t+(b+1/2). Obviously this attack can easily forge a valid π and thus a valid ciphertext and break the IND-CCA property. We also require that m is not too little to resist the brute force attack on finding a from a′.(4)
Generally speaking, our scheme is almost identical to Nieto et al.’s scheme; thus the security proof is almost the same as theirs. Below are the details.Let(c∗,δ∗,vk∗) be the challenge ciphertext. The proposed PKE without the CHK transform can be seen as a KEM/DEM combination, which is at least IND-CPA-secure due to Herranz et al. [58]. As for the KEM, a variant of the hashed Diffie-Hellman (HDH) assumption [48] can be used to prove the IND-CPA security of the resulting PKE. Note that the message does not depend on vk∗ and is just the signature on c∗. Therefore c∗ being an output of the IND-CPA-secure scheme hides the value of the chosen b from the adversary.Below we prove that the IND-CCA adversaryA may access decryption oracle and will gain no help in guessing the value of b. Suppose the adversary submits a ciphertext (c′,δ′,vk′)≠(c∗,δ∗,vk∗) to the decryption oracle. Now there are two cases.
(i)
Whenvk′=vk∗, the decryption oracle will output ⊥ as the adversary fails to break the underlying strongly unforgeable one-time signature scheme with respect to vk′.(ii)
Whenvk′≠vk, the attacker B against the variant of HDH problem can set the public keys as seen in the IND-CCA security proof for the KEM by Kiltz [57] such that (1) B can answer except for the challenge ciphertext all decryption queries from A even without the knowledge of the secret key and (2) B solves HDH if A wins. Note in Nieto et al.’s scheme u,v is the public key while in our scheme u,X,Y is the public key, but we observe v is randomly chosen from G, while in our scheme X,Y are set as h∘ga, h∘gb which are also random because a,b are random. Thus our scheme roughly shares the same security proof outline as in [57] except that our scheme is in signed quadratic residues.


## 4. Applications

### 4.1. Application 1: The Routers Drop the Invalid Ciphertexts via PVPKE

As shown in Figure1, PVPKE can be used in the open internet network to help the routers to filter the invalid ciphertexts, while traditional IND-CCA-secure public key encryption does not have this function. First a sender (encrypter) wants to encrypt his message to a receiver (decrypter) by using public key encryption, and the ciphertexts in many cases have to be sent through open networks, which are not equipped with security guards to resist malicious attack; thus the sender should better choose an IND-CCA-secure public key encryption to encrypt his message. When an error or a data loss occurs in the ciphertexts through the transferring, the PVPKE can help the routers drop invalid ciphertexts by using the algorithm of public verifying. Note here the routers need not any secret, which will greatly reduce the cost of resetup of the old system. Also, if there exists malicious attacker modifying the ciphertexts, the invalid ciphertexts will also be dropped. This will greatly help the network to preserve its communication band only to effective data blocks and help the routers and the receiver to reduce the workload for they now only need to do the necessary computation. However, PVPKE cannot resist the following case: an attacker generates a ciphertext following the right encryption algorithm and this ciphertext will certainly pass through the algorithm of public verifying. We think this time the attacker is indeed an encrypter, which will be a trivial case, and any verifying algorithm cannot avoid it.Figure 1
Routers drop the invalid ciphertexts via PVPKE.


### 4.2. Application 2: The Gateways Reduce the Workload via PVPKE

The following scenarios are always existing: ciphertexts need to be transferred from a public open network like internet to an internal network like the government’s network. As shown in Figure2, PVPKE can be used to help the gateways reduce the workload: transforming an IND-CCA ciphertext to be an IND-CPA ciphertext. When an IND-CCA ciphertext was captured by the gateway, the gateway first verifies its validity by using the publicly verifying algorithm. If it has passed, then the gateway can drop one part of the ciphertext: the part which is used to authenticate the ciphertext, like (δ,vk) in our PVPKE and Nieto et al.’s PKE scheme (here we do not claim that any PVPKE scheme has this separate authentication part, for there exist PVPKE schemes in which the authentication part has been integrated in the other parts of the ciphertext as a whole). Thus the remaining ciphertext will be IND-CPA-secure and will be shorter compared with the original ciphertext. Because the government’s network usually will be protected well with many security mechanisms, IND-CPA security is enough to assure the security of the ciphertext. This will also reduce the workload of the employees who work on the internal network of the government.Figure 2
Gateways reduce the workload via PVPKE.


### 4.3. Application 3: Achieving Ciphertext Checkable in the Clouds via PVPKE

Today more and more people prefer to upload their personal data contents to the clouds, but they do not want the cloud to know what the data contents are. Thus they need to encrypt the personal data contents before uploading them to the clouds. PVPKE can be used to achieve ciphertext checkable in this case, which can be seen in Figure3. When the data owner uploads the ciphertexts to the cloud, there may exist incident things, like data loss or malicious attacker modifying the ciphertexts; in these cases, a proxy can be used to check the ciphertext’s validity by using PVPKE. When the data owner or data user needs to retrieve the content, the clouds return the corresponding ciphertext to them. Also this time the proxy can be used to check the ciphertext’s validity by using PVPKE. Note here that the proxy needs only to be semitrusted; it can perform the check without any secret; this will greatly benefit reducing the system management. For example, the proxy can be the access infrastructure in the wireless network setting. Note here that we do not claim that every ciphertext needs to be checked, which will be too heavy. This check must be run probabilistically with randomly chosen ciphertext.Figure 3
Achieving ciphertext checkable in the clouds via PVPKE.


## 4.1. Application 1: The Routers Drop the Invalid Ciphertexts via PVPKE

As shown in Figure1, PVPKE can be used in the open internet network to help the routers to filter the invalid ciphertexts, while traditional IND-CCA-secure public key encryption does not have this function. First a sender (encrypter) wants to encrypt his message to a receiver (decrypter) by using public key encryption, and the ciphertexts in many cases have to be sent through open networks, which are not equipped with security guards to resist malicious attack; thus the sender should better choose an IND-CCA-secure public key encryption to encrypt his message. When an error or a data loss occurs in the ciphertexts through the transferring, the PVPKE can help the routers drop invalid ciphertexts by using the algorithm of public verifying. Note here the routers need not any secret, which will greatly reduce the cost of resetup of the old system. Also, if there exists malicious attacker modifying the ciphertexts, the invalid ciphertexts will also be dropped. This will greatly help the network to preserve its communication band only to effective data blocks and help the routers and the receiver to reduce the workload for they now only need to do the necessary computation. However, PVPKE cannot resist the following case: an attacker generates a ciphertext following the right encryption algorithm and this ciphertext will certainly pass through the algorithm of public verifying. We think this time the attacker is indeed an encrypter, which will be a trivial case, and any verifying algorithm cannot avoid it.Figure 1
Routers drop the invalid ciphertexts via PVPKE.


## 4.2. Application 2: The Gateways Reduce the Workload via PVPKE

The following scenarios are always existing: ciphertexts need to be transferred from a public open network like internet to an internal network like the government’s network. As shown in Figure2, PVPKE can be used to help the gateways reduce the workload: transforming an IND-CCA ciphertext to be an IND-CPA ciphertext. When an IND-CCA ciphertext was captured by the gateway, the gateway first verifies its validity by using the publicly verifying algorithm. If it has passed, then the gateway can drop one part of the ciphertext: the part which is used to authenticate the ciphertext, like (δ,vk) in our PVPKE and Nieto et al.’s PKE scheme (here we do not claim that any PVPKE scheme has this separate authentication part, for there exist PVPKE schemes in which the authentication part has been integrated in the other parts of the ciphertext as a whole). Thus the remaining ciphertext will be IND-CPA-secure and will be shorter compared with the original ciphertext. Because the government’s network usually will be protected well with many security mechanisms, IND-CPA security is enough to assure the security of the ciphertext. This will also reduce the workload of the employees who work on the internal network of the government.Figure 2
Gateways reduce the workload via PVPKE.


## 4.3. Application 3: Achieving Ciphertext Checkable in the Clouds via PVPKE

Today more and more people prefer to upload their personal data contents to the clouds, but they do not want the cloud to know what the data contents are. Thus they need to encrypt the personal data contents before uploading them to the clouds. PVPKE can be used to achieve ciphertext checkable in this case, which can be seen in Figure3. When the data owner uploads the ciphertexts to the cloud, there may exist incident things, like data loss or malicious attacker modifying the ciphertexts; in these cases, a proxy can be used to check the ciphertext’s validity by using PVPKE. When the data owner or data user needs to retrieve the content, the clouds return the corresponding ciphertext to them. Also this time the proxy can be used to check the ciphertext’s validity by using PVPKE. Note here that the proxy needs only to be semitrusted; it can perform the check without any secret; this will greatly benefit reducing the system management. For example, the proxy can be the access infrastructure in the wireless network setting. Note here that we do not claim that every ciphertext needs to be checked, which will be too heavy. This check must be run probabilistically with randomly chosen ciphertext.Figure 3
Achieving ciphertext checkable in the clouds via PVPKE.


## 5. Conclusions

PVPKE is a very powerful block to construct other cryptographic primitives or protocols, and its construction remains open for almost decades. In [13], we give several constructions and analyze their security. In this paper, by using the fact that the DDH oracle can be instantiated in signed quadratic residues, we give newPVPKE construction and roughly prove its security. The future work will be further exploring our idea and prove our proposal’s security strictly.



---

*Source: 430797-2015-01-26.xml*