Liqiang WU, Yiliang HAN, Xiaoyuan YANG, Minqing ZHANG

1Key Laboratory of Network and Information Security, Engineering University of People’s Armed Police, Xi’an 710086, China

2MOE Key Laboratory of Computer Network and Information Security, Xidian University, Xi’an 710071, China

?E-mail: latticewj@163.com; hanyil@163.com

Received July 21, 2020; Revision accepted Oct. 8, 2020; Crosschecked Oct. 12, 2021

Abstract: Threshold proxy re-encryption (TPRE) can prevent collusion between a single proxy and a delegatee from converting arbitrary files against the wishes of the delegator through multiple proxies, and can also provide normal services even when certain proxy servers are paralyzed or damaged. A non-interactive identity-based TPRE (IB-TPRE) scheme over lattices is proposed which removes the public key certificates. To accomplish this scheme, Shamir’s secret sharing is employed twice, which not only effectively hides the delegator’s private key information, but also decentralizes the proxy power by splitting the re-encryption key.Robustness means that a combiner can detect a misbehaving proxy server that has sent an invalid transformed ciphertext share.This property is achieved by lattice-based fully homomorphic signatures. As a result, the whole scheme is thoroughly capable of resisting quantum attacks even when they are available. The security of the proposed scheme is based on the decisional learning with error hardness assumption in the standard model. Two typical application scenarios, including a file-sharing system based on a blockchain network and a robust key escrow system with threshold cryptography, are presented.

Key words: Post-quantum cryptography; Threshold proxy re-encryption; Lattices; Robustness; Decentralization

1 Introduction

Proxy re-encryption (PRE) (Blaze et al., 1998) is a cryptographic primitive allowing a semi-trusted proxy to convert a ciphertext under Alice’s public key into the ciphertext of the same message under Bob’s public key, without allowing access to sensitive data or full decryption. PRE is extended to the identitybased environment, named identity-based PRE(IB-PRE) (Green and Ateniese, 2007), where public keys of Alice and Bob can be expressed by any unique strings. IB-PRE can dramatically ease the workload for public key certificate management due to the“identity matching public key” property, so it has more abundant and practical scenarios, such as secure email forwarding with IBE and attribute-based delegations.

1.1 Related works

Lou and Cao (2010) combined PRE with a threshold technique for the first time, and proposed an identity-based threshold proxy re-encryption(IB-TPRE) scheme based on bilinear mapping. David(2018) proposed a TPRE scheme called UMBRAL using BBS-PRE and Shamir’s secret sharing. UMBRAL is a central solution to the NuCypher key management system (Egorov et al., 2017), and provides encryption and cryptographic access control that is performed by a decentralized network and PRE. However, these schemes are unable to resist quantum attacks because of the Shor algorithm (Shor,1997).

To deal with the challenges of quantum computing, cryptosystems from lattices, especially from learning with error (LWE), are booming because of similar average/worst case equivalence under a quantum/classical reduction, and because of the simple algebraic structure and almost linear operations.The first bidirectional and interactive PRE scheme(Xagawa, 2010) was constructed based on the LWE hardness assumption (Regev, 2009). Subsequent research on PRE over lattices includes mainly three aspects: (1) optimization of PRE schemes over LWE,such as a key-private PRE scheme under the standard model (Aono et al., 2013) and a unidirectional,collusion-resistant, and CCA-secure PRE scheme(Kirshanova, 2014); (2) PRE schemes based on NTRU—Nu?ez et al. (2015) proposed two unidirectional, multi-hop, non-interactive PRE schemes based on NTRU and Polyakov et al. (2017) constructed an NTRU-PRE scheme and estimated its performance with the Palisade Library (Polyakov et al., 2018); (3)enhancement of the PRE security model—An indistinguishable security model under honest re-encryption attack (HRA) (Cohen, 2019) was proposed, along with the concept of adaptive security(Fuchsbauer et al., 2019), which allows corrupting users at any stage of simulation.

To work under the identity-based framework, the first anonymous multi-hop IB-PRE scheme (Singh et al., 2014) was constructed under the random oracle model, which was bidirectional and interactive. Another IB-PRE scheme (Singh et al., 2014) was constructed, generating two private keys for each user,i.e., for decryption and re-encryption. The resulting scheme achieved indistinguishability of ciphertext under a selective-identity chosen-plaintext attack(IND-sID-CPA) and weak collusion resistance.

To enhance security and fault tolerance, a latticebased universal threshold constructor was proposed(Boneh et al., 2017) using homomorphic encryptions and homomorphic signatures, which could extend any cryptographic scheme into a threshold cryptosystem.A re-splittable threshold PRE scheme (Li et al., 2017)was constructed using two basic encryption schemes from lattices and Shamir’s secret sharing, in which any ciphertext share provided by the proxy server is publicly verifiable. However, due to the use of decisional Diffie–Hellman (DDH) over the discrete logarithm assumption, the resulting scheme cannot resist quantum attack, and many exponential operations with high complexity are involved in the verification,thus reducing the overall performance.

1.2 Motivation and our contributions

From the perspective of practice, distributed architectures, such as blockchain and Hadoop, which can provide strong reliability and scalability, have been rapidly developed and deployed recently. In an IB-PRE system, the semi-trusted proxy function is typically performed by a single server to carry out ciphertext conversion, so it almost cannot meet the current requirements under the new situation mainly due to three aspects: First, the centralized proxy server may not be constantly online due to a single point of failure or a denial-of-service attack; Second,a single proxy node in complete control of the whole re-encryption key may develop into an attractive attack target at the risk of permission abuse; Third, the single proxy server is the crucial node of the network connection, and its ciphertext conversion speed will become a bottleneck of the whole system.

A feasible solution to this problem is to decentralize the proxy conversion permission, for example,to divide and delegate it in multiple entities. Only when a certain number of entities meet the requirements of re-encryption, can the ciphertext conversion be completed successfully, thus forming an IB-TPRE scheme (Lou and Cao, 2010). IB-TPRE can effectively reduce or avoid some security risks, such as permission abuse, key exposure, or full control of the re-encryption key caused by a single proxy, and significantly improve fault tolerance and security. A comparison of IB-PRE and IB-TPRE is shown in Fig. 1. Here, if more than two of the three proxies perform ciphertext conversion, they can complete the conversion task successfully.

Fig. 1 Ciphertext conversion in IB-PRE (a) and IB-TPRE (b)

From a theoretical perspective, the development of quantum computers has posed serious threats to the security of public-key cryptography. So, the construction of cryptographic schemes against quantum attack is an important trend in cryptography research.

To address these issues, a non-interactive IBTPRE scheme from LWE (Regev, 2009) is proposed,and the contributions of this paper are summarized as follows:

1. Shamir’s secret sharing is employed twice in our construction. For the first time, it splits a public vector into multiple feature vectors attached to each proxy server. The user’s private trapdoor is used to hide the delegator’s private key information perfectly by sampling a short lattice basis with regard to its feature vector. For the second time, it splits the re-encryption key. The homomorphism between the re-encryption key shares and ciphertext shares makes the overall ciphertext conversion hold, which effectively decentralizes the proxy power.

2. A homomorphic signature from lattices is applied to make our scheme robust. Robustness means that a forged or wrong ciphertext share can be detected immediately. Each proxy server owns a share of the re-encryption key and the corresponding signature. Therefore, on verification, the evaluation circuit (defined by the original ciphertext), the new message (the re-encrypted ciphertext share), and the new signature (the signature corresponding to the re-encrypted ciphertext share) must be consistent.Our scheme realizes robustness using the unforgeability of homomorphic signatures.

3. Our scheme has many practical applications because of its high availability, low trust, and strong security. High availability means that ciphertext transformation can be completed successfully, even if one or more proxy servers are unavailable. Low trust means that dishonest or malicious transformation behaviors of proxy servers are detected by public verification, thus reducing the trust in them. Strong security means that quantum attacks are resisted by constructing schemes over lattices. Our scheme can be applied in access control in a decentralized environment, such as a file-sharing system based on a blockchain network and a robust key escrow system with threshold cryptography.

2 Preliminaries

2.1 Lattices and LWE

Denote the sets of real numbers and integers byandrespectively. Vectors are represented as lowercase bold letters, and matrices are represented as uppercase bold letters. The symbol (·|·) represents the horizontal connection and (·; ·) represents the vertical connection. Ann-dimensional vector is designed ass=(s1,s2, …,sn). For matrixS=(s1,s2, …,sk), ||S||denotes the longest vector inS; that is, ||S||=max||si||for 1≤i≤k.is the Gram-Schmidt orthogonalization ofS=(s1,s2, …,sk), so || ~S||is the Gram-Schmidt norm ofS.[N] denotes the set {1,2, …,N} for an integerN. A share of secretSin Shamir’s secret sharing scheme is denoted by

The lattice is defined as follows: Givenn-dimensional linearly independent vectorsb1,b2, …,bm∈Zn, the integer lattice generated by matrixB=[b1,b2, …,bm]∈Zn×mis the set of vectors:

Given a primeq, a vectore∈Zm, and a matrix,q-ary lattices are expressed as

LetLbe a subset of Zn. For a varianceσ, let a Gaussian function centered at 0beρσ(x)=is finite and computable, the Gaussian distribution over lattices is denoted by

Definition 1(LWE) (Regev, 2009) On input of a primeq, an integern, and a discrete Gaussian distribution denoted asψσ=DL,σ, a (Zq;n;ψσ)-LWE problem comes from an unspecified challenge oracle O, being either OSor O$:

OSoutputs samples with (A,ATs+e)∈where matrixis uniformly distributed, noiseis selected according to,ands∈is from a uniform distribution.

O$outputs true uniform samples fromat random.

The decisional (Zq;n;ψσ)-LWE problem refers to an algorithm Athatcan decide its distribution from OSor O$after repeated queries to the challenge oracle O, wheresis chosen from the discrete Gaussian distribution or the uniform distribution (Lindner and Peikert, 2011).

The computational (Zq;n;ψσ)-LWE problem is to recovers∈precisely given some samples with(A,ATs+e)from OS.

Regev (2009) proved that the LWE problem with certain choices ofqandσcould be reduced to some classical worst-case lattice problems (Gap-SVP and SIVP).

The short integer solution(SIS) problem, seen as duals of LWE, has served as the foundation for some“minicrypt” primitives, such as one-way and collision-resistant hash functions. Our homomorphic signatures used for robustness are based on the SIS problem.

Definition 2(SIS) For anyn∈Z and any functionsm=m(n),q=q(n), andβ=β(n), the SIS problem SISq,m,βis as follows: Given an integerq, a matrixchosen uniformly at random, and a real numberβ, the target is to find a non-zero integer vectorz∈Zm{0}satisfyingAz=0 modqand

Micciancio and Regev (2007) showed that solving the average-case SISq,m,βfor certain parameters is equivalent to solving worst-case instances on hard lattice problems.

2.2 Related functions and tools

1. Functions of Bits and Power2

Letu. There are bit vectorsui∈{0, 1}nsuch thatand

It is easy to check that Bits(u)?Power2(X)=uX∈.

2. Trapdoor generation algorithm and its properties

Theorem 1(Trapdoor generation) (Agrawal et al.,2010) Letq≥3 be odd,n∈Z, andm=「6nlog2q」.The probabilistic algorithm TrapGen(q,n) produces a pairin polynomial time such thatAis a matrix whose distribution is within negl(n)statistical distance and thatTAis a short basis for latticesatisfyingand(nlog2q).

The following lemma includes some standard properties of discrete Gaussian distributions and powerful tools designed for (H)IBE constructions:

2.3 IB-TPRE syntax and security

2.3.1 IB-TPRE definition and security model

Definition 3 (IB-TPRE) An IB-TPRE scheme includes eight algorithms, which can be classified into three categories according to their functionality. In terms of the delegation relationship, the parties involved in IB-TPRE include a PKG, a delegator, a delegatee, andNproxies. Ifk(k≤N) or more proxies attend, then the functionality of PRE can be realized.

1. Key generation algorithms

(1) Setup(λ). On input of a security parameterλ,PKG runs and outputs the public parameter PP and the master key MSK.

(2) KeyGen(MSK, id). On input of the master key MSK and a user id, PKG outputs the private key SKid.

(3) ReKeyGen(id1, id2, SKi1d,N,k). On input of user id1’s private key, the total number of key sharesN, and thresholdk, the delegator id1outputsNre-encryption key shares {kFragi} (1≤i≤N) and the verification key VK={vk1,vk2, …, vkN}. In general,the ReKeyGen algorithm can directly generate shares,or temporally generate a whole re-encryption key RKid1→id2and then divide it intoNshares.

2. Encryption and decryption algorithms

(1) Enc(id,M). On input of the user id and a messageMto be encrypted, a sender (anyone) outputs a ciphertextC.

(2) Dec(C, SKid). On input of the private key SKidand a ciphertextC, the delegator or delegatee outputs the decrypted messageMor ⊥.

3. Ciphertext share-processing algorithms

(1) PreEnc(C1, {kFragi}).On input of an original ciphertext of user id1and re-encryption key shares{kFragi}, a proxy outputs ciphertext shares {cFragi}corresponding to a user id2. In truth, it requires only at leastk(k≤N)proxies to perform this algorithm.

(2) Verify({vki}, {cFragi}). On input of a user’s ciphertext share {cFragi} and verification key {vki},the delegatee outputs 1 if the ciphertext share is legal;otherwise, it outputs 0.

(3) Comb(C1, {cFragi}i∈S). The input contains a ciphertext share setSof sizek′. Ifk′≥k, the delegatee outputs a complete ciphertextC2that can be decrypted by id2; otherwise, it outputs ⊥.

The correctness of an IB-TPRE scheme includes two requirements:

The first one is the correctness of decryption.?M∈{0, 1}, Setup(λ)→(PP, MSK), KeyGen(MSK,id1)→SKid1, KeyGen(MSK, id2)→ SKid2, ReKey-Gen(id1, id2, SKi1d,N,k)→{kFragi} (1≤i≤N),Enc(id1,M)→C1, and PreEnc(C1, {kFragi})→{cFragi}, the following expressions hold: (1) Dec(C1,SKid1)→M; (2) Comb(C1, {cFragi}i∈S)→C2and Dec(C2, SKid2)→M, whenkshares are collected.

The second requirement is the correctness of ciphertext share verification. For all {kFragi}(1≤i≤N), all ciphertext shares {cFragi} (1≤i≤N) obtained by PreEnc(C1,{kFragi}) satisfy Verify({vki},{cFragi})→1.

IB-TPRE’s selective security, called IND-sIDCPA, is described with a game played between an adversary A and a challenger C:

1. Init

Adversary A outputs a target identity id*intended to be attacked.

2. Setup

Challenger C performs the Setup algorithm to obtain PP and MSK, and then sends PP to adversary A.ΓCis a set of corrupted users, for which the adversary has made a private key query, andΓHis a set of honest users, for which the adversary has never made a private key query.ΓCis empty at the beginning andΓHhas only one element id*.

3. Query phase 1

Adversary A chooses some queries in the following three ways:

(1) KeyGen query

When the adversary issues a private key query on a user id(id?ΓH), challenger C runs the algorithm KeyGen(MSK, id), returns the private key to adversary A, and finally adds id to setΓC.

(2) ReKeyGen query

Whenadversary A issues re-encryption key share queries between users id1and id2if id1∈ΓH,challenger C temporally generates a whole RKid1→id2(this is similar to the re-encryption key from id1to id2in the IB-PRE system, and all theNre-encryption key shares can be derived from it), and then divides it intoNshares. Finally, challenger C returns allNshares to adversary A if id2∈ΓH; otherwise, if id2∈ΓC, it returns only the previousk?1 shares and keeps the key shares labeledk,k+1, …,Nconfidential. A is not allowed to obtain more thankre-encryption key shares when id1∈ΓHandid2∈ΓC, which could allow A to decrypt the challenge ciphertext by a sequence of re-encryptions. Note that when id1∈ΓC, adversary A can generate all re-encryption key shares with SKi1din a non-interactive setting, so we ignore the case for simplicity. In addition, when id1?(ΓH∪ΓC) is queried,there are two cases. First, if id2∈ΓC, challenger C adds id1toΓH, and then returns the result as a ReKeyGen query for id1∈ΓHandid2∈ΓCas mentioned above.Second, if id2?ΓCis queried, challenger C adds id2toΓH(if id2∈ΓH, ignore this step), and then returns the result as a ReKeyGen query for id1∈ΓHandid2∈ΓH.

(3) PreEnc query

This query works only when id1∈ΓHandid2∈ΓH,which is the integration of some algorithms in sequence: (a) asking our KeyGen(id1) without returning the private key to id1; (b) computing ReKeyGen(id1,id2,SKid1,N,k) and retaining only the firstk–1 key shares {kFragi} (1≤i≤k–1) corresponding to the firstk–1 proxy servers; (c) computing PreEnc(C1, {kFragi})→{cFragi} (1≤i≤k–1).

The adversary can repeat this polynomial for different queries.

4. Challenge phase

Make sure that identity id*belongs to setΓH, and that query KeyGen(MSK,id*) is not permitted.Challenger C picks a random bitb∈{0, 1}and an arbitraryCfrom the ciphertext space. Ifb=1, set the challenge ciphertext toC*=Encrypt(id*,M). Ifb=0,set the challenge ciphertext toC*=C.

5. Query phase 2

Adversary A could ask extra queries for the private key, re-encryption key, re-encryption on the identity id(id≠id*), and challenger responses, same as in query phase 1.

6. Guess

A makes a guessb'∈{0, 1} and wins the game ifb=b'.

The advantage of adversary A is defined as

Definition 4(IND-sID-CPA security) An IB-PRE scheme is IND-sID-CPA secure ifis negligible for any adversary A in polynomial time.

Some comments are given as follows:

1. A strong definition allows an adversary to obtain a re-encryption key from an uncorrupted identity to a corrupted identity except for one from the challenged identity to a compromised identity. In this work, we do not pursue such a definition.

2. The adversary does not explicitly handle the definition of the re-encryption query for id1∈ΓCand id2∈(ΓH∪ΓC), because the re-encryption query performed by the adversary is the same as the re-encryption key query when id1∈ΓC. This omission is not a loss of generality.

2.3.2 Robustness of IB-TPRE

Robustness is an important property for the IB-TPRE scheme. The basic idea is that an adversary cannot forge a ciphertext share that is not obtained by the re-encryption key share honestly, but can be verified correctly. The robustness of the IB-TPRE scheme is described with the following game Expt:

The interaction processes of Init, KeyGen queries, ReKeyGen queries, and PreEnc queries are the same as that described in Definition 4, but at the guessing stage, the adversary randomly selects id*∈ΓH, outputs a corresponding ciphertext share cFragj*,id*(1≤j*≤N), and satisfies

Then the adversary’s advantage is defined as Adv.

Definition 5(Robustness) (Boneh et al., 2017) If the advantageis negligible, the IB-TPRE scheme is robust.

2.3.3 IB-TPRE collusion resistance

Yin et al. (2018) introduced two definitions of collusion resistance, called strong anti-collusion and weak anti-collusion, of PRE. The difference between these two is whether the exact private key of the delegator is obtained when the proxy with a re-encryption key and the delegatee with its private key collude.

Our proposed scheme satisfies weak anticollusion as defined in Definition 6:

Definition 6 (Weak anti-collusion) In a threshold PRE scheme with weak anti-collusion, if some proxy servers and the delegatee collude, they cannot obtain the exact private key of the delegator, but could obtain an approximate value of the delegator’s private key.

2.4 Homomorphic signature and threshold secret sharing

2.4.1 Homomorphic signature

Our IB-TPRE provides robustness using an SIS-based homomorphic signature, which refers to a series of same operations performed on the original message and its corresponding signature without knowing the signing key. As a result, anyone with a verification key can verify the computation results in public. It is widely applied in outsourcing computing,retrievable proof, public verifiability, and other fields.

Definition 7(Homomorphic signature) A homomorphic signature (HS) scheme (Boneh et al., 2017)usually includes four algorithms:

(1) HS.KeyGen(λ,d,N)

When inputting a security parameterλ, a circuit depth boundd, and a message set boundN, it outputs a signing key hssk and a verification key hsvk.

(2) HS.Sign(hssk,M)

When the signing key hssk and the messageMto be signed are inputted, it outputs a signatureσ.

(3) HS.SignEval(C,σ)

When inputting an evaluation circuitC: {0,1}N→{0, 1} and a signatureσ, it outputs a homomorphically computed signatureσ*.

(4) HS.Verify(hsvk,y,C,σ*)

On input of a verification key hsvk, a circuitC,an output valuey,and a signatureσ*, the verification algorithm accepts the signature (and outputs 1) or rejects it (and outputs 0).

The correctness of HS is defined as follows: For any inputλ,d∈Z, HS.KeyGen(λ,d,N)→(hsvk, hssk),M∈{0, 1}N, HS.Sign(hssk,M)→σ, and any circuitC:{0, 1}N→{0, 1} with depthdandC(M)→y, the following equation holds:

Two security properties for a homomorphic signature are required (Boneh et al., 2017). The first property is unforgeability; that is, given homomorphically signed dataσ, the adversary cannot produce a circuitCor a valid signatureσy, for whichC(σ)=σy.The other property is context hiding; that is, given a homomorphically computed signatureσ*, the adversary does not obtain any useful information about the original messageMthat was signed, other than what was already implied by the outputC(M)=y.

At present, the security of the HS scheme(Boneh and Freeman, 2011; Gorbunov et al., 2015)can be reduced to the SIS assumption. These two schemes are sufficient to completely meet the design requirements for our robustness.

2.4.2 Shamir’s threshold secret sharing

Shamir’s threshold secret sharing scheme includes secret segmentation and secret reconstruction.

1. Secret segmentation

To share secretSamongNparticipants by Shamir’s (k,N) threshold scheme wherek≤N, it works as follows:

(1) Randomly choosek?1 coefficientsa1,a2, …,ak?1∈q.

(2) Construct a polynomial with degreek?1:

(3) For each participant labeledi(1≤i≤N), calculate=f(i) as its share and sendto theithparticipant.

2. Secret reconstruction

When anykinNparticipants are prepared to recover secret (without loss of generality, suppose that the valid shares are, the polynomialf(x) can be reconstructed as

whereλjdenotes Lagrange coefficients:

So,S=f(0), and the secretSis restored.

3 Identity-based threshold proxy reencryption scheme from lattices

Set security parametersn∈q,m≥「6nlog2q」, a primeq≥m2ω(log2n), andl=「log2q」. Define a uniform distributionUqonqand a discrete Gaussian distributionψionqwith noise parameteri∈{γ,e}.Choose a pseudo-random function[?r,r]2m+1for a bounded integerr. Let the number of the total proxy servers beNand the threshold bek;then defineη=(N!)2. Identities are assumed by the elements in, and the functionHrefers to the FRD map. In addition, to be more universal, denoteΠHS=(HS.KeyGen, HS.Sign, HS.SignEval,HS.Verify) as an abstract representation of a homomorphic signature. The re-encryption key shares for proxy servers are generated and distributed by individual users without the involvement of PKG.

3.1 Key generation algorithms

1. Setup(1λ)

Generate a uniformly distributed matrixwith its trapdoorby algorithm TrapGen. Choose two uniformly distributed matricesand a vector. The user dictionary UD and delegation dictionary DD are initialized by empty sets. Publish the public key PP={A0,A1,B,u} and keep the master private keyMSK =

2. KeyGen(MSK, id)

When a user id submits a request to PKG for a private key, check the user directory UD first. If there is already a private key record for the user id, retrieve and return it to the user. Otherwise, we perform the following:

(1) Convert the identity id intoH(id) ∈,obtain the corresponding public keyFid=(A0|A1+H(id)B), and calculate the private keyeidby SampleLeft(A0,A1+H(id)B,TA0,u,ψγ) satisfyingFideid=u.

(2) ObtainTid=SampleBasisLeft(A0,A1+H(id)B,T A0,st) satisfyingFidTid=0, wherestis the Gaussian parameter used to generate the user trapdoor.

Return private key SKid=(eid,Tid) to idand add it to UD.

3. ReKeyGen(id1,id2,SKid1,N,k)

On generating the re-encryption between id1and id2, check the delegation directory DD first. If re-encryption key shares are already contained in the directory, distribute these shares to the corresponding proxy server and then exit. Otherwise, compute all the re-encryption key shares {kFragi} (1≤i≤N) as follows:

(1) Run Shamir’s secret sharing to splitto(1≤i≤N) as feature vectors for each proxy server indexed byi, and store them locally (this process needs to be performed only once). Fori∈{1,2, …,N}, let the feature vector of theithproxy server beSamplePresatisfy.

(3) Run Shamir’s secret sharing on each coefficient from (P,Q) by the following:

Fori∈{1, 2, …, 2ml} andj∈{1, 2, …, 2m}, select a random polynomialyi,j(x) ∈Zq[x] satisfyingyi,j(0)=Pi,jwith its degree equal tok–1. Fori∈{1,2, …, 2ml}, choose a polynomialwi(x) ∈Zq[x] satisfyingwi(0)=Qiwith its degree equal tok–1.

For 1≤j≤N, the partial decryption share for thejthproxy server is

(4) The re-encryption key share for thejthproxy server is?Power2(1≤j≤N).

(5) Generate verification and signing keys (hsvk,hssk) by HS.KeyGen. SelectNkeys prfk1, prfk2, …,prfkNindependently by the pseudo-random functionFprfk. Fori∈{1, 2, …,N}, setXi=(,prfki)and compute=HS.Sign(hssk,Xi).

Publish hsvk to verify the signature in the subsequent process.Send shares {k Fragi}=(1≤i≤N) to the proxy server with indexiover a secure channel, and add them to DD.

3.2 Encryption and decryption algorithms

1. Encrypt(id,M)

To encrypt a bitM∈{0, 1}, it works as follows:

(1) On input of the user id ∈, encode it asFid=(A0|A1+H(id)B).

(2) Choose a uniform vectorsrandomly.

(3) Choose a uniform integer matrixRid∈{?1,1}m×mrandomly.

(4) Choose x ∈ψeand, and then calculatez=yRid

(5) Calculatec1=sTFid+η(y|z)andc2=sTu+ηx+M∈Zq. Output ciphertextC =(c1,c2).

2. Dec(Cid,eid)

On input of a ciphertextCid=(c1,c2) and the corresponding private keyeid, computeM′=c2?c1eid.IfM'∈(「q/4」, 「3q/4」), setM'=1; otherwise,M'=0.

3.3 Ciphertext share processing algorithms

1. PreEnc(Cid1, {kFragi})

The input contains a user id1’s ciphertextCid1=(c1,id1,c2,id1) and a PRE key share {kFragi}=.

2.Verify (hsvk,CcFrag,i)

On input of the verification key hsvk and a ciphertext share, the verification algorithm outputs HS.Verify

3.Comb(Cid1,{CcFrag,i}i∈S)

Assume that the participant set isS, andk′=|S|represents the valid share size. Ifk′

(1) For each ciphertext share {CcFrag,i}(i∈S),check Verify(hsvk, {CcFrag,i}). If the verification fails,output ⊥ and exit.

At last, recover a whole ciphertext as

The workflow of our proposed scheme is shown in Fig. 2. It works as follows: (1) The PKG initializes and generates PP and MSK; (2) Users submit their identity information to the PKG and receive their private keys; (3) A delegator named Alice receives a ciphertextCAlicethat is encrypted under her own identity from someone; (4) When Alice is unable to handle the ciphertext for some reason, she will forward the ciphertext to proxy servers; (5) At the same time, Alice generatesNproxy key shares {kFragi}(1≤i≤N) and authorizes the decryption permission to a delegatee named Bob; (6) Several of theNproxy servers obtain some ciphertext shares {cFragi} by re-encryption and forward them to Bob; (7) Bob verifies the validity of each received ciphertext share{cFragi} and accepts it if legal; (8) If Bob collects at leastk(k≤N) ciphertext shares, he can combine one whole ciphertextCBobintended for him; (9) Bob uses his private key to decryptCBoband receives the original message.

Fig. 2 Workflow of our proposed IB-TPRE scheme

4 Analysis of the IB-TRPE scheme

4.1 Correctness

Theorem 2(Correctness) AssumeandBγ(Be) the upper bound of the discrete Gaussian distributionψγ(ψe). The output of the pseudo-random functionFprfkis a uniform distribution with its upper boundBr, and setq≥8maxThe probability of successful decryption of our new IB-TPRE is close to 1 in a single hop.

Proof(1) For a normal ciphertext, decrypt it byc2?c1eidas follows:

Only when the noiseη[x–(y|z)eid] is no greater than, can the decryption algorithm recoverMcorrectly. In truth, none of the parametersx, (y|z), andeidwill exceedBeorBγ; that is,η(x?(y|z)eid)≤Therefore,q≥ 4ηBeBγis sufficient.

(2) For a transformed ciphertext, decrypt it with id2’s private key. We can obtain Eq. (7) at the top of the next page.

The fifth equal sign in Eq. (7) at the top of thenext page holds because.

The sixth equal sign in Eq. (7) holds becausec1,id1=sTFid+η(y|z) and=u.

Then decrypt the ciphertext using Eq. (8) at the top of the next page.

The third equal sign holds becauseP=RFid2+E,Q=Ru+e,Q?Peid2=e?Eeid2,andc2,id1=sTu+ηx+M

It can be verified that the transformed ciphertext is decrypted correctly despite there is more converted noise than the initial noise. The following lemma follows a simple combinatorial argument:Lemma 2(Boneh et al., 2017) For any setS∈of sizekand 1≤i≤N, the productis an integer and (N!)2≤(N!)3, whereare efficiently computable Lagrange coefficients.

From Lemma 2, we have

Therefore, the new noise can be expressed as a uniformly distributed noise and a linear combination of the product of uniformly distributed noise and Gaussian noise; i.e., the upper bound of all the kinds of noise is

Whenq≥8max(N!)3BrBγ,the decryption algorithm can recover plaintext correctly after one transformation.

In fact, our scheme can realize limited multihop, which is a limited version of the multi-hop property because the re-encryption function introduces some noise in the ciphertext after transformation. For this reason, depending on the parameters used, the accumulated noise causes the decryption to fail after a certain number of re-encryptions. So,correctness verification for the limited multi-hop of our proposed scheme is left for further research.

Correctness of the verification for a ciphertext share is guaranteed by HS.Verify from the HS scheme. The evaluation circuitgCid1in PreEnc, exactly defined by the original ciphertextCi1d, takes the signed re-encryption key share as its input. On one hand, the processes for(steps (1)–(3) in PreEnc) can be viewed as the calculation at the message level. On the other hand, the same operations will be performed on the signature by HS.SignEVal(step (4) in PreEnc).According to the correctness of the HS scheme, ifis the correct result honestly obtained by the proxy server with HS.SignEval, it can surely pass the verification algorithm, so the verification for a ciphertext share is correct.

4.2 Security

Theorem 3(Security) The IB-TPRE system is IND-sID-CPA secure if the LWE assumption holds.

ProofThe security proof is similar to that in Agrawal et al. (2010), except that we take a PRE interaction into consideration.

Assuming that there exists an adversary A that can break our scheme’s IND-sID-CPA security, then a challenger C can be constructed to solve the decisional LWE hardness assumption.

1. Init

Adversary A outputs a target id*intended to be attacked.

2. Setup

Challenger C generates system parameters as follows: It selectsA0randomly over Zn m q×without any trapdoor; however, it generatesBwith a trapdoorTBby the TrapGen algorithm. In addition, the public matrixA1is not obtained at random; however, it is computed byA1=A0R*?H(id*)B, where matrixR*is randomly generated for the creation of challenge ciphertext. The corrupted user setΓCis empty at the beginning, and the honest user setΓHhas only one element, which is id*. The other settings are identical as described in the real scheme.

3. Query phase 1

Adversary A chooses some queries.

(1) KeyGen query

Adversary A can make a private key query for user id. If id?ΓH, challenger C runs the algorithm KeyGen(MSK, id), where the public key is constructed asFid=(A0|A0R*+(H(id)?H(id*))B) and the private key is computed by SampleRight and SampleBasisRight withTB. At last, C returns the private key to A, and then adds id toΓC. Otherwise,return ⊥.

(2) ReKeyGen query

Whenadversary A issues re-encryption key shares between users id1and id2, challenger C provides different solutions according to different cases,as shown in Table 1.

Table 1 Strategies to answer ReKeyGen queries

(3) PreEnc query

When id1∈ΓHandid2∈ΓH, return a transformed ciphertext share by PreEnc after a ReKeyGen query between id1and id2.

4. Challenge phase

Challenger C queries the LWE oracle O form+1 instances (vi,wi) ∈(1≤i≤m+1), which may be either a truly random distribution from O$or a noisy pseudo-random distribution from OS.

(3) Output the challenge ciphertext

5. Query phase 2

A continues to make queries as does in query phase 1. Queries KeyGen for id*and ReKeyGen from id*to id2∈ΓCare not permitted.

6. Guess

A guessesb'∈{0, 1} to distinguish the real ciphertext from the random ciphertext, and challenger C picks a bitr'=b'accordingly, which will distinguish whether the obtained samples are subject to LWE distributions fromSor random distributions from$.

Next, we analyze the indistinguishability of the simulated behaviors from challenger C.

1. In the real scheme, matrixA1is taken from the uniform distribution, while challenger C generates matrixA1=A0R*?H(id*)B. It is identical by the hash leftover lemma (Agrawal et al., 2010), which states that the uniform distributionA1is statistically indistinguishable from the distributionA0R*, whereR*is a square randomly chosen from {?1, 1}m×m.

2. When answering the private key queries or re-encryption key queries, challenger C constructs the public key asFid=(A0|A0R*+(H(id)?H(id*))B). If id1≠id*,H(id)?H(id*) is a full-rank matrix by FRD definition, andTBcan be regarded as a trapdoor for. Challenger C can now generate a private keyeidsatisfyingFideid=uusing algorithm SampleRight(A0, (H(id)?H(id*))B,R*,TB,ψγ). Similarly, C first generates a user trapdoorTid=SampleBasisRight(A0, (H(id)?H(id*))B,R*,TB,st),and then computes,id(1 ≤i≤N)that satisfiesFinally, C obtains a re-encryption key share for each proxy server labeledi. If id=id*,Fid=(A0|A0R*) has nothing to do withBand the challenger’s trapdoorTBdisappears. As a result, the challenger is unable to generate a private key for id*or re-encryption key shares from id*to others, which prevents the adversary from obtaining the private key for id*or translating id*to user id instead, for which adversary A holds a private key.

3. If asked for the re-encryption key share query on id1=id*∈ΓHand id2∈ΓH, challenger C selects RK1→2=(P,Q), consisting of freshly random matrices. We stress that it is unable to distinguish the selected pair (P,Q) mentioned above fromP=RFid2+Eand computed in the real scheme,because the decisional LWE problem implies that it is indistinguishable between the LWE distribution and the true random uniform distribution.

In the following, we will show thatk?1 re-encryption key share and re-encryption share queries will not leak the private key information of id*.Q=Ru+e

The challenger randomly chooses the uniformly distributed RK1→2=(P,Q) as the re-encryption key and sends the firstk?1 key shares(1≤i≤k?1)to the firstk?1 corrupted servers that are owned by adversary A, thus forming a setS*(|S*|=k?1). After that, if asked for re-encryption, challenger C does the following:

(1) Calculate Lagrange coefficients, where

(2) Select an integer vector[ ?r,r]2m+1randomly fori∈*.

(3) Calculate

The calculation process and the final expression are the same as their counter parts of the Comb algorithm, and the resulting distribution is statistically indistinguishable. In truth, challenger C does not know the real re-encryption key. In other words, when id1=id*∈ΓHand id2∈ΓH, providingk?1 re-encryption key shares and answering the re-encryption share query will not reveal any information about the private key for id1and the re-encryption key between id1and id2.

(4) As to the challenge ciphertext, if the instances are from the LWE distribution, that is, assumingA0+x, thenC*=is distributed precisely as in the real scheme.First, sinceFid*=(A0|A0R*), then

which is exactly identical to the first part of a valid ciphertext created by our IB-TPRE scheme. Second,which is exactly identical to the second part of a valid ciphertext created by our scheme. If adversary A can distinguish challenge ciphertext from a random distribution, challenger C can solve the decisional LWE hardness assumption. Hence, our scheme is semantically secure.

Theorem 4(Robustness) If a homomorphic signature schemeΠHS=(HS.KeyGen, HS.Sign, HS.SignEval, HS.Verify) satisfies unforgeability, the proposed IB-TPRE scheme is robust.

ProofIntuitively speaking, a dishonest proxy server can successfully obtain an invalid re-encrypted ciphertext share and the corresponding signature using an arbitrarily chosen evaluation circuit. However, as described in HS.Verify(hsvk,y,C,σ*), the correct evaluation circuitCis essentially defined by the original ciphertext, and the verification fails if the forged evaluation circuit is different from the correct one; therefore, it forces the proxy servers to perform the transformation honestly.

In a formal proof, the robustness of the new IB-TPRE scheme can be reduced to the unforgeability of a homomorphic signature. If an adversary A can break through the robustness game described in Definition 5, then a simulator S can be constructed to break the unforgeability of the HS by interacting with adversary A. The process is as follows:

S first obtains the verification key hsvk, and adversary A chooses the re-encryption key between id1and id2intended to be attacked. When adversary A submits a forged re-encrypted ciphertext shareto the simulator S, S reconstructs (hsvk,gC id1,)and submits it to the homomorphic signature oracle.If adversary A can win the robustness game, that is,,where 1≤j*≤N, but Verify= 1, then the simulator S can successfully forge an illegal signature satisfying HS.Verify,= 1, which will be submitted to the homomorphic signature oracle later. This means that the unforgeability of homomorphic signature schemeΠHSis breakable. However, this is contrary to our assumption.

Therefore, our new IB-TPRE is robust, provided that the homomorphic signature algorithmΠHSis unforgeable.

Theorem 5(Weak collusion resistance) Our IB-TRPE scheme achieves weak collusion resistance.

ProofCollusion resistance means that it is impossible to derive SKAfor the delegator, even if the dishonest proxy with RKA→Band a malicious delegatee Bob with SKBcollude. Collusion resistance becomes important only when the same key pair is used for other purposes (e.g., signing and key derivation). Its goal is to allow Alice to delegate decryption privileges while preserving the signature privileges under the same public key.

Weak collusion resistance in our IB-TPRE is guaranteed by two steps. The first step is to introduce multiple proxies to prevent collusion between a proxy and the delegatee. Conversely, to obtain a whole PRE key, an attacker must first collectkshares out ofNre-encryption key shares by corruptingkproxy servers to obtain RKA→B=(P=RF+E,Q= Ru+e?, whereλiis a Lagrange coefficient fori∈S. Even if an attacker succeeds in step one,he/she can compute SKequal=Q?PeB=e?EeB?, whereeBis the private key for userB. The second step claims that SKequalallows recovering a similar secret key that can decrypt any ciphertext only for Alice. We explain it as follows:

The message will be recovered correctly because the noise above is quite small, and it seems that Alice’s private key is leaked completely if collusion occurred. However, this is not true because we might have recovered an equivalent private key with the ability to perform delegated decryption rights, but not the same key as Alice’s original private key. On one hand, if an attacker has both RKA→Band SKB, he/she is quite capable of re-encrypting and reading any data that, originally, is decryptable by SKA. In addition,SKequalworks only if it meets Bits(c1) when decrypted. On the other hand, another private user trapdoorSAmight be used for signing, which will never be recovered due to an irreversible lattice basis extension from the SampleBasisLeft algorithm.Therefore, our scheme is weak collusion resistant.

4.3 Comparison

There are two typical existing (IB-)TPRE constructions. The first one is UMBRAL (David, 2018),which is the central scheme of the NuCypher key management system. It is constructed on the decisional bilinear Diffie-Hellman (DBDH) assumption,which is vulnerable to quantum attack. The other one is the re-splittable threshold PRE scheme over lattices; it realizes robustness using a decisional discrete logarithm assumption that sacrifices efficiency,and it will also suffer from a quantum attack on re-encryption verification.

In our IB-TPRE scheme, the validity of a ciphertext share is verified by a homomorphic signature, which can be instantiated by the current efficient SIS-based fully homomorphic signature scheme(Boneh and Freeman, 2011; Gorbunov et al., 2015),and thus the final system can completely resist quantum attack. Also, when the original signature is evaluated by the Boolean circuit, that is, Bits(c1,id1),the homomorphic signature calculation is a Boolean operation and is not highly complex, so it is more efficient. These three schemes are compared in Table 2. The combined size of the ciphertext share and the key share does not include the payload for verification, and the ciphertext conversion does not include the computation complexity of verification for robustness.

Table 2 Property and complexity comparison of related works

5 Applications

The new IB-TPRE scheme has the advantages of high availability, low trust, and strong security.Therefore, it can become a core technique for private information secure sharing in outsourcing data security, secure multi-party computing, and decentralized encrypted computing. Two examples are given for two application scenarios.

5.1 File-sharing system based on a blockchain network

In a file-sharing system constructed by the traditional PRE, the proxy function is typically performed by an independent server. However, once the centralized proxy no longer remains neutral and refuses to provide re-encryption services, or offers wrong re-encryption services deliberately for some reason (such as war and commercial competition), it will directly lead to the failure of file sharing. To resolve this problem, a distributed file-sharing system with our IB-TRPE is constructed, where ciphertext transformation is carried out by a decentralized blockchain network, as shown in Fig. 3. Compared with the P2P technique, blockchain not only is decentralized, but also considers a trust model for each node. The verification of ciphertext shares in our IB-TPRE scheme provides a checking method for this trust relationship.

Fig. 3 A file-sharing system based on a blockchain network

Step 1: Users can select the storage location at will, such as Amazon S3 and IPFS. A sender, such as Alice, encrypts files with her public key or with a hybrid encryption mode before uploading them.

Step 2: When Alice wants to share an encrypted file FileAwith her friend Bob, each node from the blockchain network will act as a proxy server to receive a re-encryption key share between Alice and Bob. After that, Alice publishes a re-encryption task to the whole network, providing information such as the address of the file to be shared and the identities of recipients.

Step 3: When receiving a re-encryption request,each network node allows the re-encryption service to obtain some tokens independently. For example, the node that offers the firstkcorrect ciphertext shares for Bob will obtain some rewards from the system, and the robustness offers a method to identify whether the conversion result is correct.

Step 4: The storage server working for Bob will put the legal ciphertext shares together to form a new encrypted file FileB. Finally, Bob downloads and decrypts it.

The system resists collusion between proxy servers and the receiver by nature. It can also control the initiative of ciphertext conversion even if the attacker grasps a complete re-encryption key, but the plaintext will not be exposed online because it appears in the encrypted state. Therefore, the system realizes end-to-end encryption and privacy protection.

5.2 Robust key escrow system with threshold cryptography

There may be two conflicting requirements in current telecommunication systems. On one hand,users want to communicate with others secretly. On the other hand, to fight against crime and protect national security, the government requires the interception of user traffic. The key escrow system (Wang et al., 2019) is a solution that balances privacy protection and authorized monitoring.

A new robust key escrow system with threshold cryptography, evolving from our new IB-TRPE scheme, includes mainly the following four components: (1) The key generation center (KGC), which is responsible for initialization and maintenance of the key cryptosystem, is performed by PKG in our scheme; (2) Users such as Alice and Bob communicate with each other; (3) Key escrow agents (KEAs),which are authorized to escrow user keys, are played by proxy servers; (4) The legal enforcement agency(LEA) of the government, which is responsible for monitoring all user communication, has a unique identifier like a delegatee. The architecture of the proposed system is shown in Fig. 4.

Fig. 4 A robust key escrow system with threshold cryptography

Step 1: Alice and Bob apply their private keys to KGC. After that, they can communicate with each other securely. To be more efficient, the architecture can use hybrid encryption, in which the session key is randomly generated to encrypt actual messages by

symmetric encryption, and the session key itself is also encrypted by the receiver’s identity. LEA obtains its private key from the KGC under its own identity,and then publishes its identity to all users.

Step 2: KEAs, represented byNproxy servers in our IB-TRPE scheme, register in the KGC to obtain re-encryption key shares from Alice to the LEA, as well as from Bob to the LEA. Note that generating re-encryption key shares by KGC, not individual users, is feasible because KGC also has the user private key.

Step 3: When it is necessary to monitor the communications between Alice and Bob, the LEA applies the authorization to the government or regulatory affairs. After authorization, LEA forwards the authorization to KEAs for verifying correctness and timeliness. The KEAs convert Alice’s ciphertext into some Bob’s ciphertext shares by their own re-encryption key shares, and then send the converted ciphertext shares to the LEA for monitoring.

Step 4: After receiving the converted ciphertext shares, the LEA checks their validity. Whenkvalid shares are collected, they are combined into a complete ciphertext. The LEA decrypts it using its private key to obtain a session key, and obtains further communication content.

The excellent properties of the new IB-TPRE scheme enhance the key escrow system to be more secure and versatile: (1) The encrypted shares have been kept secret in an encrypted state, so there is no need for a secure channel between KEAs and the LEA; (2) Our IB-TPRE can detect some wrong or dishonest conversions of KEAs in time, which makes the system more reliable and secure; (3) It needs onlykout ofNKEAs online to complete the transformation; (4) The system avoids the “once monitor, monitor forever” approach in each session and achieves fine-grained control (Cheng et al.,2013), allowing only reconstruction of the current session key without leaking the previous and future communication content.

6 Conclusions

We proposed an IB-TPRE scheme over lattices by combining the threshold PRE, identity-based encryption, and homomorphic signature. After the IB-TPRE scheme was instantiated with an SIS-based fully homomorphic signature scheme, the final system can completely resist quantum attack. It provides encryption and cryptographic access control performed by a decentralized network, and some new compelling applications can be realized with the performance advantages under distributed systems.

Contributors

Liqiang WU designed the research. Xiaoyuan YANG processed the data. Yiliang HAN performed the security proof.Liqiang WU drafted the paper. Minqing ZHANG helped organize the paper. Yiliang HAN and Xiaoyuan YANG revised and finalized the paper.

Compliance with ethics guidelines

Liqiang WU, Yiliang HAN, Xiaoyuan YANG, and Minqing ZHANG declare that they have no conflict of interest.