# Efficient Identity-Based Broadcast Encryption Scheme on Lattices for the Internet of Things

Authors: Kai He; Xueqiao Liu; Jia-Nan Liu; Wei Liu
Journal: Security and Communication Networks
 (2021)

---

## Abstract

In an identity-based broadcast encryption (IBBE) scheme, the ciphertext is usually appended with a set of user identities to specify intended recipients. However, as IBBE is adopted in extensive industries, the demand of anonymity for specific scenarios such as military applications is urgent and ought no more to be ignored. On the contrary, how to optimize computation and communication is an unavoidable challenge in the IBBE scheme construction, especially in the large-scaled resource-limited wireless networks such as the Internet of Things (IoT), where the cost of computation and communication should be mitigated as much as possible since other functions including connectivity and privacy should be given the top priority. Thus, we present an IBBE scheme from the lattice, in which we employ the Chinese remainder theorem and lattice basis delegation in fixed dimensions to obtain several desirable characteristics, such as constant-size public parameter, private key, and ciphertext. In addition, our encryption and decryption algorithms are more efficient than broadcast encryption (BE) schemes based on number-theoretic problems. To be noticed, our scheme can simultaneously achieve confidentiality and outsider anonymity against the chosen-plaintext attack under the hardness of the learning with error (LWE) problem.


---

## Body

## 1. Introduction

IoT is a network of interconnected things/devices, in which sensors, software, network connections, and necessary electronic devices are integrated to collect and exchange information and respond to real-time data requests. IoT allows data accumulation from and exchange between the physical world and computer systems through existing network infrastructures. With these connected tiny and smart devices, one’s life can be of higher quality, safer, smarter, more convenient, comfortable, and timely informed than ever before. Security is one of the main concerns mentioned by cybersecurity experts. They believe that even end device connectivity and information sharing can be exploited to have a negative impact on a person safety and well-being. Besides hacking IoT devices to compromise online data and privacy, it can also become the entry point of invading the entire network [1, 2].Remote terminal unit (RTU) [1] is an electronic device, which is installed in a remote site (generally, few people supervise the distant site). It is used to monitor and control sensors and equipment remotely and widely adopted in the supervisory control and data acquisition (SCADA) system. RTU usually converts the measured state or signal into a data format that can be sent on the communication medium by using the Modbus protocol. It can also receive commands sent by the central monitor computer to execute functional control of the equipment. As the Modbus protocol does not apply data encryption mechanism, the data flow between the monitor center and RTU is in plaintext. As a consequence, the data transmitted in the open network may be eavesdropped or tampered with. What is worse, the data tampering may cause disorder in the automated production process or even serious accidents of equipment damage. To keep the confidentiality of data transmission, cryptographic modules can be embedded in data collection equipment such as RTU/DTU and effectively help prevent data theft and command tampering [2]. Once the concern of confidentiality is got rid of, such devices can be safely applied to industrial control industries such as oil and gas exploitation, environmental monitoring, power transmission and transformation, oil and gas pipeline networks, and hydrological monitoring.Fiat and Naor [3] first introduced broadcast encryption, which allows a sender to send an encrypted message to a large number of receivers via public channels, and only authorized users can obtain the message, as shown in Figure 1. Compared with the public key encryption for a single recipient, BE significantly saves computing and communication costs. Therefore, BE has been promoted to numerous applications, such as key distributing [4], encrypted file sharing [5], satellite TV subscription [6], digital right management [7], and social network service [8]. Take pay service as an example. As shown in Figure 2, nonpaying user U2 cannot enjoy the service or just is able to enjoy limited service, while paying users U1,U3,…,Un can enjoy entire and high-quality service. There are a large number of related works that can be classified into the conventional BE [6, 9–13] since they are based on number-theoretic problems, such as big integer factoring and discrete logarithm problem, and rarely meet the requirements of industrial applications.Figure 1
Broadcast in the Internet of Vehicles network.Figure 2
IBBE for pay service.With the advent of quantum cryptography, the security of conventional BE schemes is heavily threatened. In FOCS′94, Shor [14] proposed a quantum algorithm to solve the problem of discrete logarithm and factorization in polynomial time. Thereafter, it becomes one of the most urgent topics to design BE schemes against quantum attacks.Lattice cryptography can resist quantum-computing attacks [15] and has multiple advantages over the conventional cryptography. Firstly, lattice is a vector space composed of n linearly independent vectors b1,…,bn in ℝm, which only request lightweight operations such as modular addition and matrix multiplication. Thus, it is suitable for devices with limited computational ability such as smart cards. Secondly, lattice cryptography enjoys pretty strong security guaranteed by the worst-case hardness assumptions [16, 17], such as shortest vector problem (SVP) [18] and closest vector problem (CVP) [18]. Thirdly, lattice cryptography can be adopted to comparable extensive industries as its conventional cryptography was, given almost all conventional public key encryption (PKE) schemes based on big integer factoring or discrete logarithm problems can also be realized in lattice cryptography.A desirable BE scheme on lattices should keep not only confidentiality but also anonymity as anonymity is an extremely favourable characteristic for diverse BE systems [19]. To distinguish authorized receivers from the unauthorized, BE ciphertext usually includes the intended recipients’ identities. This means users’ identity information is revealed. Specifically, such identity exposure is expected to be avoided when users’ identities are sensitive. For instance, in the military field, the set of broadcast receiver identities undoubtedly implies specific military objectives or personnel. Meanwhile, to support a large number of receivers in a BE system, the public key of every receiver can be conveniently chosen as a meaningful string, which is their unique identification, such as a passport number or an e-mail address. This is exactly the motivation of proposing an IBBE system that is capable to support exponential user scale.


### 1.1. Our Results

Each BE system involves multiple recipients. Thus, it is intricate to construct a BE scheme in a lattice context. Our main contributions include the construction of an anonymous IBBE from the lattice and the security reduction to the LWE problem. Our design is inspired by the lattice-based BE scheme of Wang et al. [20], which depends on the Chinese remainder theorem to achieve the dynamic anonymity. In this work, we rely on the Chinese remainder theorem to construct an IBBE scheme, and the core idea is as follows.The Chinese remainder theorem offers one-dimensional linear congruence equationx≡aimodqi that has and only has one solution x=Q1Q1′a1+⋯+QkQk′akmodQ. In order to construct a BE scheme on lattices, we combine the Chinese remainder theorem with the LWE hardness assumption.(i)
Firstly, we extend the Chinese remainder theorem to a matrix form, such asx and ai are extended to matrices X and Ai with dimension n×m, respectively. Thus, the system of linear congruence equations has the similar solution; that is, X=Q1Q1′A1+⋯+QkQk′AkmodQ, where X is close to uniform distribution [20] if Ai is a random matrix over Zqn.(ii)
Then, choose a random vectors, which is to blind X. Blind results are used to encapsulate symmetric keys K, e.g., C2=∑i=1kQiQi′Ai∑i=1kQiQi′s+2e+KmodQ, where Ai and qi are receiver i’s public keys and e is an error vector. Since the key encapsulation is constructed by the Chinese remainder theorem, its distribution is indistinguishable from the uniform distribution [20].(iii)
Thirdly, when authorized receiveri decrypts the ciphertext, he does not need to know the other users’ identities. He firstly computes C2 mod qi, where qi is his public key. and then C2 is transformed to a LWE instance vector related to his public key Ai, i.e., C2modqi=Ai⊤s+2e+Kmodqi. Now, authorized receiver i uses his private key to decrypt Ai⊤s+2e+Kmodqi to obtain the symmetric key K and then gets the broadcast message.(iv)
To obtain an IBBE scheme, we need to connect users’ public keysAi and qi to identity IDi. Firstly, we use an encoding function H1:ℤqn⟶ℤqn×n to map identities IDi∈ℤqn to matrices Ai∈ℤpn×n, i.e., Ai=H1IDi [21], and a division intractable hash function H2:0,1∗⟶ℤqn to map identities IDi∈ℤqn to integer qi∈ℤpn. Note that integer qi is a prime with an overwhelming probability [22] so that user i’s public key qi and user j’s public key qj are ensured mutually prime.(v)
Lattice basis delegation mechanisms were proposed by Cash et al. [23] and Agrawal et al. [21]. Given a matrix A∈Zqn×m and a lattice basis TA of Λq⊥A, a matrix B from A and a random basis TB for Λq⊥B can be generated. However, in [21, 23], the dimension of matrix B is larger than the dimension of the given matrix A. So, the ciphertext and private key sizes of their HIBE schemes increase as the hierarchy deepens. Thus, in terms of private key generation of our scheme, we employ lattice basis delegation with constant dimension technology [21] to generate the user private key, where B=AR−1∈Zqn×m and B has the same dimension as A. Thence, the private key size of our scheme is constant, and the size of the ciphertext has nothing to do with the number of recipients.


### 1.2. Related Work

Identity-based encryption (IBE) [24] is a special kind of BE. There is one receiver set specifying intended receivers, and in an IBE scheme, the user public key can be any string as long as the string can be a uniquely identified user, such as a passport number and e-mail address. In 2008, Craig et al. [25] proposed the technology of lattice-based one-way trapdoor function and constructed an IBE scheme whose security is based on the LWE problem [26] in the random oracle model. In their scheme, trapdoor sampling algorithm [27] is used for generating the master public key and master secret key. Then, the preimage sampler [25] takes the master secret key as the input to generate the user’s secret key. Finally, both the master public key and the user’s identity are used to generate two separate pseudorandom LWE instances as the ciphertexts.Hierarchical identity-based encryption (HIBE) [28, 29] is also a special kind of BE. Users in the broadcast set have a hierarchical structure, and the lower-level users’ keys are generated by the higher-level users. In 2010, Cash et al. [23, 30] proposed a new concept of cryptography, called bonsai tree, and constructed an HIBE scheme based on the LWE problem by utilizing the lattice basis delegation technique, which allows one to use a short basis of a certain integer lattice L to generate a short random basis for a new lattice L0 derived from L. However, in their HIBE scheme, the dimension of the child lattice L0 is greater than that of the parent lattice L for the reason that, as the hierarchical structure increases, the private key and ciphertext also become longer. Shweta Agrawal and Boyen [31] proposed a lattice basis delegation technique which does not increase the dimension of the lattices involved and presented two HIBE schemes with shorter ciphertext and private keys with and without the random oracle based on the LWE problem, respectively.Attribute-based encryption (ABE) [32] and BE are both one kind of one-to-many encryption. In the ABE system, the private key and the ciphertext are related to the attributes; when the attributes owned by the user match the ciphertext attributes, the user can obtain the ciphertext. Boyen [33] proposed an efficient ABE scheme and proved its security in the selective sense from LWE hardness assumption in the standard model. Nevertheless, BE needs to specify which users are authorized receivers.Fiat and Naor first introduced BE [3]. In 2005, Boneh et al. [11] proposed the first fully collusion-resistant BE scheme with static security, and both the size of ciphertexts and private keys are constant, but the size of the public key is proportional to the number of receivers. In 2009, Craig and Waters [13] proposed a BE scheme with adaptive security in the random oracle model. In 2007, Delerablée [34] proposed the first IBBE scheme, which obtains adaptive chosen-ciphertext attack (CCA) in the random oracle model, as well as has constant-size ciphertexts and private keys. In 2009, Craig and Waters [13] presented the first IBBE scheme, which is against adaptively chosen-plaintext secure in the standard model. In 2014, Boneh et al. [35] proposed the first IBBE scheme, which obtains selectively CCA-secure from multilinear maps and has constant-size ciphertexts. In 2015, Jongkil Kim et al. [36] proposed an IBBE scheme, which is adaptively CCA-secure in the standard model, but uses dual encryption technique. In 2016, Dan and Zhandry [37] proposed a BE scheme, which obtains adaptive security by using indistinguishability obfuscation technique and has short ciphertexts, secret keys, and public keys.Anonymity is a good security property; however, the aforementioned scheme cannot be obtained because the recipients’ identities are broadcasted as ciphertext. Thus, the identities’ information is exposed. In 2006, Adam et al. [12] presented two fully anonymous BE constructions; both of them obtain CCA security. The first one is a generic construction, and the decryption cost has a linear relationship with the number of receivers. The second is a specific construction, requiring a certain number of decryption operations, and the security proof relies on a random oracle model. In 2012, Libert et al. [19] proposed some fully anonymous BE schemes, which are fully anonymous and have adaptive CCA security in the standard model; at the same time, the formal security definition of the anonymous BE scheme is given. In 2012, two anonymous BE schemes with outsider anonymous were proposed by Fazio and Milinda Perera [38], and the two BE schemes have sublinear-size ciphertexts. In 2016, two anonymous BE schemes were proposed by He et al. [39]; the first one is the general scheme [39], and the second one is the specific scheme [39]. Both of these schemes are proven to be adaptive CCA-secure. However, all the aforementioned traditional BE/IBBE schemes cannot resist quantum attacks.In 2010, Wang and Bi [40] proposed a secure lattice-based IBBE scheme using the basis delegation technique [23], and their scheme can be easily extended to a hierarchical IBBE. However, their lattice basis delegation technique increases the dimension of users’ identity matrix. In 2013, Georgescu [41] used a tag-based hint system which is secure based on ring-LWE hardness and an IND-CCA-secure public key encryption scheme from LWE to construct a CCA-secure lattice-based anonymous BE scheme. In 2015, Wang et al. [20] used the Chinese remainder theorem to construct a dynamical and outsider-anonymous BE scheme over the lattice, which is proven semantic secure in the standard model under the hardness of the LWE problem. In 2020, Brakerski and Vaikuntanathan [42] proposed a lattice-based BE scheme where the size of the key and ciphertext has a logarithmic correlation with the number of users. However, their BE construction is based on a heuristic that allows to “invert” the key succinctness of the BGG + KP-ABE scheme [43] and does not have a security reduction for this heuristic; its security is an open problem. In 2020, Agrawal and Yamada [44] improved Boneh et al.’s [35] BE scheme which used multilinear maps by using LWE and bilinear mapping, and the parameters of the improved solution were also very small. Thus, in this paper, we construct an anonymous IBBE scheme on the lattice. We make a detailed function comparison between our scheme and other schemes in Table 1.Table 1
Comparisons with related works.
SchemeIdentity-basedAnonymity[41]×√[20]×√[40]√×[42]××Ours√√


## 1.1. Our Results

Each BE system involves multiple recipients. Thus, it is intricate to construct a BE scheme in a lattice context. Our main contributions include the construction of an anonymous IBBE from the lattice and the security reduction to the LWE problem. Our design is inspired by the lattice-based BE scheme of Wang et al. [20], which depends on the Chinese remainder theorem to achieve the dynamic anonymity. In this work, we rely on the Chinese remainder theorem to construct an IBBE scheme, and the core idea is as follows.The Chinese remainder theorem offers one-dimensional linear congruence equationx≡aimodqi that has and only has one solution x=Q1Q1′a1+⋯+QkQk′akmodQ. In order to construct a BE scheme on lattices, we combine the Chinese remainder theorem with the LWE hardness assumption.(i)
Firstly, we extend the Chinese remainder theorem to a matrix form, such asx and ai are extended to matrices X and Ai with dimension n×m, respectively. Thus, the system of linear congruence equations has the similar solution; that is, X=Q1Q1′A1+⋯+QkQk′AkmodQ, where X is close to uniform distribution [20] if Ai is a random matrix over Zqn.(ii)
Then, choose a random vectors, which is to blind X. Blind results are used to encapsulate symmetric keys K, e.g., C2=∑i=1kQiQi′Ai∑i=1kQiQi′s+2e+KmodQ, where Ai and qi are receiver i’s public keys and e is an error vector. Since the key encapsulation is constructed by the Chinese remainder theorem, its distribution is indistinguishable from the uniform distribution [20].(iii)
Thirdly, when authorized receiveri decrypts the ciphertext, he does not need to know the other users’ identities. He firstly computes C2 mod qi, where qi is his public key. and then C2 is transformed to a LWE instance vector related to his public key Ai, i.e., C2modqi=Ai⊤s+2e+Kmodqi. Now, authorized receiver i uses his private key to decrypt Ai⊤s+2e+Kmodqi to obtain the symmetric key K and then gets the broadcast message.(iv)
To obtain an IBBE scheme, we need to connect users’ public keysAi and qi to identity IDi. Firstly, we use an encoding function H1:ℤqn⟶ℤqn×n to map identities IDi∈ℤqn to matrices Ai∈ℤpn×n, i.e., Ai=H1IDi [21], and a division intractable hash function H2:0,1∗⟶ℤqn to map identities IDi∈ℤqn to integer qi∈ℤpn. Note that integer qi is a prime with an overwhelming probability [22] so that user i’s public key qi and user j’s public key qj are ensured mutually prime.(v)
Lattice basis delegation mechanisms were proposed by Cash et al. [23] and Agrawal et al. [21]. Given a matrix A∈Zqn×m and a lattice basis TA of Λq⊥A, a matrix B from A and a random basis TB for Λq⊥B can be generated. However, in [21, 23], the dimension of matrix B is larger than the dimension of the given matrix A. So, the ciphertext and private key sizes of their HIBE schemes increase as the hierarchy deepens. Thus, in terms of private key generation of our scheme, we employ lattice basis delegation with constant dimension technology [21] to generate the user private key, where B=AR−1∈Zqn×m and B has the same dimension as A. Thence, the private key size of our scheme is constant, and the size of the ciphertext has nothing to do with the number of recipients.


## 1.2. Related Work

Identity-based encryption (IBE) [24] is a special kind of BE. There is one receiver set specifying intended receivers, and in an IBE scheme, the user public key can be any string as long as the string can be a uniquely identified user, such as a passport number and e-mail address. In 2008, Craig et al. [25] proposed the technology of lattice-based one-way trapdoor function and constructed an IBE scheme whose security is based on the LWE problem [26] in the random oracle model. In their scheme, trapdoor sampling algorithm [27] is used for generating the master public key and master secret key. Then, the preimage sampler [25] takes the master secret key as the input to generate the user’s secret key. Finally, both the master public key and the user’s identity are used to generate two separate pseudorandom LWE instances as the ciphertexts.Hierarchical identity-based encryption (HIBE) [28, 29] is also a special kind of BE. Users in the broadcast set have a hierarchical structure, and the lower-level users’ keys are generated by the higher-level users. In 2010, Cash et al. [23, 30] proposed a new concept of cryptography, called bonsai tree, and constructed an HIBE scheme based on the LWE problem by utilizing the lattice basis delegation technique, which allows one to use a short basis of a certain integer lattice L to generate a short random basis for a new lattice L0 derived from L. However, in their HIBE scheme, the dimension of the child lattice L0 is greater than that of the parent lattice L for the reason that, as the hierarchical structure increases, the private key and ciphertext also become longer. Shweta Agrawal and Boyen [31] proposed a lattice basis delegation technique which does not increase the dimension of the lattices involved and presented two HIBE schemes with shorter ciphertext and private keys with and without the random oracle based on the LWE problem, respectively.Attribute-based encryption (ABE) [32] and BE are both one kind of one-to-many encryption. In the ABE system, the private key and the ciphertext are related to the attributes; when the attributes owned by the user match the ciphertext attributes, the user can obtain the ciphertext. Boyen [33] proposed an efficient ABE scheme and proved its security in the selective sense from LWE hardness assumption in the standard model. Nevertheless, BE needs to specify which users are authorized receivers.Fiat and Naor first introduced BE [3]. In 2005, Boneh et al. [11] proposed the first fully collusion-resistant BE scheme with static security, and both the size of ciphertexts and private keys are constant, but the size of the public key is proportional to the number of receivers. In 2009, Craig and Waters [13] proposed a BE scheme with adaptive security in the random oracle model. In 2007, Delerablée [34] proposed the first IBBE scheme, which obtains adaptive chosen-ciphertext attack (CCA) in the random oracle model, as well as has constant-size ciphertexts and private keys. In 2009, Craig and Waters [13] presented the first IBBE scheme, which is against adaptively chosen-plaintext secure in the standard model. In 2014, Boneh et al. [35] proposed the first IBBE scheme, which obtains selectively CCA-secure from multilinear maps and has constant-size ciphertexts. In 2015, Jongkil Kim et al. [36] proposed an IBBE scheme, which is adaptively CCA-secure in the standard model, but uses dual encryption technique. In 2016, Dan and Zhandry [37] proposed a BE scheme, which obtains adaptive security by using indistinguishability obfuscation technique and has short ciphertexts, secret keys, and public keys.Anonymity is a good security property; however, the aforementioned scheme cannot be obtained because the recipients’ identities are broadcasted as ciphertext. Thus, the identities’ information is exposed. In 2006, Adam et al. [12] presented two fully anonymous BE constructions; both of them obtain CCA security. The first one is a generic construction, and the decryption cost has a linear relationship with the number of receivers. The second is a specific construction, requiring a certain number of decryption operations, and the security proof relies on a random oracle model. In 2012, Libert et al. [19] proposed some fully anonymous BE schemes, which are fully anonymous and have adaptive CCA security in the standard model; at the same time, the formal security definition of the anonymous BE scheme is given. In 2012, two anonymous BE schemes with outsider anonymous were proposed by Fazio and Milinda Perera [38], and the two BE schemes have sublinear-size ciphertexts. In 2016, two anonymous BE schemes were proposed by He et al. [39]; the first one is the general scheme [39], and the second one is the specific scheme [39]. Both of these schemes are proven to be adaptive CCA-secure. However, all the aforementioned traditional BE/IBBE schemes cannot resist quantum attacks.In 2010, Wang and Bi [40] proposed a secure lattice-based IBBE scheme using the basis delegation technique [23], and their scheme can be easily extended to a hierarchical IBBE. However, their lattice basis delegation technique increases the dimension of users’ identity matrix. In 2013, Georgescu [41] used a tag-based hint system which is secure based on ring-LWE hardness and an IND-CCA-secure public key encryption scheme from LWE to construct a CCA-secure lattice-based anonymous BE scheme. In 2015, Wang et al. [20] used the Chinese remainder theorem to construct a dynamical and outsider-anonymous BE scheme over the lattice, which is proven semantic secure in the standard model under the hardness of the LWE problem. In 2020, Brakerski and Vaikuntanathan [42] proposed a lattice-based BE scheme where the size of the key and ciphertext has a logarithmic correlation with the number of users. However, their BE construction is based on a heuristic that allows to “invert” the key succinctness of the BGG + KP-ABE scheme [43] and does not have a security reduction for this heuristic; its security is an open problem. In 2020, Agrawal and Yamada [44] improved Boneh et al.’s [35] BE scheme which used multilinear maps by using LWE and bilinear mapping, and the parameters of the improved solution were also very small. Thus, in this paper, we construct an anonymous IBBE scheme on the lattice. We make a detailed function comparison between our scheme and other schemes in Table 1.Table 1
Comparisons with related works.
SchemeIdentity-basedAnonymity[41]×√[20]×√[40]√×[42]××Ours√√


## 2. Preliminaries

Let us briefly introduce some of the symbols and definitions used throughout the paper.


### 2.1. Collision Intractability [22]

ℋ=Hkk∈N is a family of hash functions. If it is difficult to find two inputs that hash to the same output, ℋ is collision intractable. Formally, for every probability polynomial-time (PPT) adversary A, there is a negligible function negl() such that(1)PrH∈HkAAH=x,x′,s.t.x≠x′andHx=Hx′=neglka.


### 2.2. Division Intractability [22]

ℋ is a hashing family; if it is division intractable, it is hard to find distinct inputs x1,…,xn,y such that hy divides ∏i=1nhxi. Formally, for every PPT adversary A, there is a negligible function negl() such that(2)Prh∈HkAAh=xii∈n,y,s.t.y≠xii∈nandhydivides∏i=1nhxi=neglk.It is not difficult to see that a hash familyℋ that is division intractable must also be collision intractable, but the reverse is not true. Such a function is easy to obtain by setting H0X=HX|1 (or only the lowest bit of HX) to be one.


### 2.3. Lattice and Lattice Problems

#### 2.3.1. Lattice [45]

LatticeΛ is generated by a set of n linearly independent vectors B=b1,b2,…,bn such that(3)Λ=Bc|Bc=c1b1+c2b2+⋯+cnbn∈ℤ.


#### 2.3.2.q-ary Lattices [45]

q,m,n are some integers, A∈ℤqn×m is a parity check matrix, and q-ary lattices are defined as(4)Λq⊥A=e∈ℤqm,Ae=0modq.In fact, all vectors in latticeΛq⊥A are orthogonal modulo q to the matrix A row vector.


#### 2.3.3. Gaussian over Lattices [45]

Gaussian functionρs:ℝm⟶0,1 is defined as(5)ρsx=exp−πx2s2,for any s>0 and dimension m≥1. The discrete Gaussian distribution DΛy⊥A,s over the coset L=t+Λy⊥A, t∈ℤm, whose probability is proportional to ρsxx∈Λy⊥A, and probability is zero elsewhere.


#### 2.3.4. LWE Problem [26, 45]

LetA←Rℤqm×n, s←Rℤqn, the error distribution χ be over As,χ, and e be distributed according to χ. Given A,As+emodq, the decision variant LWE problem is to distinguish A,As+emodq from uniform distribution.


#### 2.3.5. Gaussian Error DistributionsΦαm26

The standard error distributionΦαm is the Gaussian distribution on ℤqm, and the deviation is qα>n. According to the distribution Φαm, the error vector can be effectively sampled, as shown in the following:(i)
Sampleη1,η2,…,ηm comes from the Gaussian distribution Dα on ℛ(ii)
Letei=qηimodq where x is used to represent the integer closest to x(iii)
Lete=e1,…,em be the error vector in the LWE problem instance


#### 2.3.6. Trapdoor Sampling Algorithm [21]

Letq≥3 be odd and m:=⌈6nlogq⌉. There exists a PPT algorithm (TrapGen) q,n, and it outputs a matrix A and a full rank set T∈ℤm×m, where A’s distribution is statistically close to a uniform distribution, T is a lattice basis of Λ⊥A, which satisfies T˜≤Onlogq, and T≤Onlogq with almost negligible probability.The trapdoorT can be utilized to solve the LWE problem; that is, given y=Ats+emodq where e is any “short enough” vector, it can be used to recover s as follows [25]:(i)
CalculateTty=TtAts+e=ATts+Tte=Ttemodq and e=Tt−1Ttemodq. Now, since both T and e contain small entries, each entry of the vector Tte is less than q, so Ttemodq=Tte.(ii)
LWE secrets can be recovered via A,e,y.


#### 2.3.7. Algorithm Basis Delegation [21]

The basic delegation algorithmBasisDelA,R,TA,σ will not increase the dimension of the basic matrix [21]. On inputting a rank n matrix A in ℤqn×m, a ℤq-invertible matrix R in ℤm×m sampled from Dm×m, a basis TA of Λq⊥, and the parameter σ∈ℝ>0, output a basis TB of Λq⊥B, where B=AR−1 in ℤqn×m.


#### 2.3.8. Algorithm SampleR1n21

Our security proof uses algorithm sampleR. The sample matrix in ℤm×m comes from a distribution that is statistically close to Dm×m [21]. On the canonical basis T of the lattice ℤm, run ri←RSample Gaussianℤm,T,σ,0 for i=1,…,m. If R is ℤq− invertible, then output R; otherwise, run the sample Gaussian algorithm repeatedly.Algorithm sampleR with basis is used in our security proof, which gives a random rank n matrix A in ℤn×mq and generates a “low-norm” matrix R from Dm×m and the short base of Λq⊥AR−1 as follows.


#### 2.3.9. Algorithm SampleR with Basis A21

a1,…,am∈ℤqn are the m columns of the matrix A∈ℤqn×m.(i)
RunTrapGen(q, n) to generate a matrix B∈ℤqn×m with random rank n, as well as lattice λq⊥B base TB, where(6)TB˜≤L˜TG=σRwlogm.(ii)
Fori=1,…,m, do(1)
Sampleri by running SamplePreB,TB,ai,…, and we have Bri=aimodq, Bri=aimodq, where ri is sampled from a distribution statistically close to DΛqaiB,ρR(2)
Repeat Step (1) untilri is linearly independent of r1,…,ri−1(iii)
LetR∈ℤm×n be the matrix with columns r1,…,rm. Then, R has rank m. Output R and TB.


#### 2.3.10. Chinese Remainder Theorem [46]

Ifqi and qj are integers, gcdqi,qj=1, and ai1≤i≤k are arbitrary integers, a system of linear congruence(7)x≡a1modq1,⋮,x≡akmodqk,equations has only one solution:(8)x=Q1Q1′a1+⋯+QkQk′akmodQ,where Q=q1q2…qk, Qi=Q/qi, and QiQi′=1modqi for 1≤i≤k.We can also extend the Chinese remainder theorem to a matrix form, such asx and ai are extended to matrices X and Ai with dimension n×m, respectively; the system of linear congruence has the same solution; that is,(9)X=Q1Q1′A1+⋯+QkQk′AkmodQ,where X is close to uniform distribution [20].


## 2.1. Collision Intractability [22]

ℋ=Hkk∈N is a family of hash functions. If it is difficult to find two inputs that hash to the same output, ℋ is collision intractable. Formally, for every probability polynomial-time (PPT) adversary A, there is a negligible function negl() such that(1)PrH∈HkAAH=x,x′,s.t.x≠x′andHx=Hx′=neglka.


## 2.2. Division Intractability [22]

ℋ is a hashing family; if it is division intractable, it is hard to find distinct inputs x1,…,xn,y such that hy divides ∏i=1nhxi. Formally, for every PPT adversary A, there is a negligible function negl() such that(2)Prh∈HkAAh=xii∈n,y,s.t.y≠xii∈nandhydivides∏i=1nhxi=neglk.It is not difficult to see that a hash familyℋ that is division intractable must also be collision intractable, but the reverse is not true. Such a function is easy to obtain by setting H0X=HX|1 (or only the lowest bit of HX) to be one.


## 2.3. Lattice and Lattice Problems

### 2.3.1. Lattice [45]

LatticeΛ is generated by a set of n linearly independent vectors B=b1,b2,…,bn such that(3)Λ=Bc|Bc=c1b1+c2b2+⋯+cnbn∈ℤ.


### 2.3.2.q-ary Lattices [45]

q,m,n are some integers, A∈ℤqn×m is a parity check matrix, and q-ary lattices are defined as(4)Λq⊥A=e∈ℤqm,Ae=0modq.In fact, all vectors in latticeΛq⊥A are orthogonal modulo q to the matrix A row vector.


### 2.3.3. Gaussian over Lattices [45]

Gaussian functionρs:ℝm⟶0,1 is defined as(5)ρsx=exp−πx2s2,for any s>0 and dimension m≥1. The discrete Gaussian distribution DΛy⊥A,s over the coset L=t+Λy⊥A, t∈ℤm, whose probability is proportional to ρsxx∈Λy⊥A, and probability is zero elsewhere.


### 2.3.4. LWE Problem [26, 45]

LetA←Rℤqm×n, s←Rℤqn, the error distribution χ be over As,χ, and e be distributed according to χ. Given A,As+emodq, the decision variant LWE problem is to distinguish A,As+emodq from uniform distribution.


### 2.3.5. Gaussian Error DistributionsΦαm26

The standard error distributionΦαm is the Gaussian distribution on ℤqm, and the deviation is qα>n. According to the distribution Φαm, the error vector can be effectively sampled, as shown in the following:(i)
Sampleη1,η2,…,ηm comes from the Gaussian distribution Dα on ℛ(ii)
Letei=qηimodq where x is used to represent the integer closest to x(iii)
Lete=e1,…,em be the error vector in the LWE problem instance


### 2.3.6. Trapdoor Sampling Algorithm [21]

Letq≥3 be odd and m:=⌈6nlogq⌉. There exists a PPT algorithm (TrapGen) q,n, and it outputs a matrix A and a full rank set T∈ℤm×m, where A’s distribution is statistically close to a uniform distribution, T is a lattice basis of Λ⊥A, which satisfies T˜≤Onlogq, and T≤Onlogq with almost negligible probability.The trapdoorT can be utilized to solve the LWE problem; that is, given y=Ats+emodq where e is any “short enough” vector, it can be used to recover s as follows [25]:(i)
CalculateTty=TtAts+e=ATts+Tte=Ttemodq and e=Tt−1Ttemodq. Now, since both T and e contain small entries, each entry of the vector Tte is less than q, so Ttemodq=Tte.(ii)
LWE secrets can be recovered via A,e,y.


### 2.3.7. Algorithm Basis Delegation [21]

The basic delegation algorithmBasisDelA,R,TA,σ will not increase the dimension of the basic matrix [21]. On inputting a rank n matrix A in ℤqn×m, a ℤq-invertible matrix R in ℤm×m sampled from Dm×m, a basis TA of Λq⊥, and the parameter σ∈ℝ>0, output a basis TB of Λq⊥B, where B=AR−1 in ℤqn×m.


### 2.3.8. Algorithm SampleR1n21

Our security proof uses algorithm sampleR. The sample matrix in ℤm×m comes from a distribution that is statistically close to Dm×m [21]. On the canonical basis T of the lattice ℤm, run ri←RSample Gaussianℤm,T,σ,0 for i=1,…,m. If R is ℤq− invertible, then output R; otherwise, run the sample Gaussian algorithm repeatedly.Algorithm sampleR with basis is used in our security proof, which gives a random rank n matrix A in ℤn×mq and generates a “low-norm” matrix R from Dm×m and the short base of Λq⊥AR−1 as follows.


### 2.3.9. Algorithm SampleR with Basis A21

a1,…,am∈ℤqn are the m columns of the matrix A∈ℤqn×m.(i)
RunTrapGen(q, n) to generate a matrix B∈ℤqn×m with random rank n, as well as lattice λq⊥B base TB, where(6)TB˜≤L˜TG=σRwlogm.(ii)
Fori=1,…,m, do(1)
Sampleri by running SamplePreB,TB,ai,…, and we have Bri=aimodq, Bri=aimodq, where ri is sampled from a distribution statistically close to DΛqaiB,ρR(2)
Repeat Step (1) untilri is linearly independent of r1,…,ri−1(iii)
LetR∈ℤm×n be the matrix with columns r1,…,rm. Then, R has rank m. Output R and TB.


### 2.3.10. Chinese Remainder Theorem [46]

Ifqi and qj are integers, gcdqi,qj=1, and ai1≤i≤k are arbitrary integers, a system of linear congruence(7)x≡a1modq1,⋮,x≡akmodqk,equations has only one solution:(8)x=Q1Q1′a1+⋯+QkQk′akmodQ,where Q=q1q2…qk, Qi=Q/qi, and QiQi′=1modqi for 1≤i≤k.We can also extend the Chinese remainder theorem to a matrix form, such asx and ai are extended to matrices X and Ai with dimension n×m, respectively; the system of linear congruence has the same solution; that is,(9)X=Q1Q1′A1+⋯+QkQk′AkmodQ,where X is close to uniform distribution [20].


## 2.3.1. Lattice [45]

LatticeΛ is generated by a set of n linearly independent vectors B=b1,b2,…,bn such that(3)Λ=Bc|Bc=c1b1+c2b2+⋯+cnbn∈ℤ.


## 2.3.2.q-ary Lattices [45]

q,m,n are some integers, A∈ℤqn×m is a parity check matrix, and q-ary lattices are defined as(4)Λq⊥A=e∈ℤqm,Ae=0modq.In fact, all vectors in latticeΛq⊥A are orthogonal modulo q to the matrix A row vector.


## 2.3.3. Gaussian over Lattices [45]

Gaussian functionρs:ℝm⟶0,1 is defined as(5)ρsx=exp−πx2s2,for any s>0 and dimension m≥1. The discrete Gaussian distribution DΛy⊥A,s over the coset L=t+Λy⊥A, t∈ℤm, whose probability is proportional to ρsxx∈Λy⊥A, and probability is zero elsewhere.


## 2.3.4. LWE Problem [26, 45]

LetA←Rℤqm×n, s←Rℤqn, the error distribution χ be over As,χ, and e be distributed according to χ. Given A,As+emodq, the decision variant LWE problem is to distinguish A,As+emodq from uniform distribution.


## 2.3.5. Gaussian Error DistributionsΦαm26

The standard error distributionΦαm is the Gaussian distribution on ℤqm, and the deviation is qα>n. According to the distribution Φαm, the error vector can be effectively sampled, as shown in the following:(i)
Sampleη1,η2,…,ηm comes from the Gaussian distribution Dα on ℛ(ii)
Letei=qηimodq where x is used to represent the integer closest to x(iii)
Lete=e1,…,em be the error vector in the LWE problem instance


## 2.3.6. Trapdoor Sampling Algorithm [21]

Letq≥3 be odd and m:=⌈6nlogq⌉. There exists a PPT algorithm (TrapGen) q,n, and it outputs a matrix A and a full rank set T∈ℤm×m, where A’s distribution is statistically close to a uniform distribution, T is a lattice basis of Λ⊥A, which satisfies T˜≤Onlogq, and T≤Onlogq with almost negligible probability.The trapdoorT can be utilized to solve the LWE problem; that is, given y=Ats+emodq where e is any “short enough” vector, it can be used to recover s as follows [25]:(i)
CalculateTty=TtAts+e=ATts+Tte=Ttemodq and e=Tt−1Ttemodq. Now, since both T and e contain small entries, each entry of the vector Tte is less than q, so Ttemodq=Tte.(ii)
LWE secrets can be recovered via A,e,y.


## 2.3.7. Algorithm Basis Delegation [21]

The basic delegation algorithmBasisDelA,R,TA,σ will not increase the dimension of the basic matrix [21]. On inputting a rank n matrix A in ℤqn×m, a ℤq-invertible matrix R in ℤm×m sampled from Dm×m, a basis TA of Λq⊥, and the parameter σ∈ℝ>0, output a basis TB of Λq⊥B, where B=AR−1 in ℤqn×m.


## 2.3.8. Algorithm SampleR1n21

Our security proof uses algorithm sampleR. The sample matrix in ℤm×m comes from a distribution that is statistically close to Dm×m [21]. On the canonical basis T of the lattice ℤm, run ri←RSample Gaussianℤm,T,σ,0 for i=1,…,m. If R is ℤq− invertible, then output R; otherwise, run the sample Gaussian algorithm repeatedly.Algorithm sampleR with basis is used in our security proof, which gives a random rank n matrix A in ℤn×mq and generates a “low-norm” matrix R from Dm×m and the short base of Λq⊥AR−1 as follows.


## 2.3.9. Algorithm SampleR with Basis A21

a1,…,am∈ℤqn are the m columns of the matrix A∈ℤqn×m.(i)
RunTrapGen(q, n) to generate a matrix B∈ℤqn×m with random rank n, as well as lattice λq⊥B base TB, where(6)TB˜≤L˜TG=σRwlogm.(ii)
Fori=1,…,m, do(1)
Sampleri by running SamplePreB,TB,ai,…, and we have Bri=aimodq, Bri=aimodq, where ri is sampled from a distribution statistically close to DΛqaiB,ρR(2)
Repeat Step (1) untilri is linearly independent of r1,…,ri−1(iii)
LetR∈ℤm×n be the matrix with columns r1,…,rm. Then, R has rank m. Output R and TB.


## 2.3.10. Chinese Remainder Theorem [46]

Ifqi and qj are integers, gcdqi,qj=1, and ai1≤i≤k are arbitrary integers, a system of linear congruence(7)x≡a1modq1,⋮,x≡akmodqk,equations has only one solution:(8)x=Q1Q1′a1+⋯+QkQk′akmodQ,where Q=q1q2…qk, Qi=Q/qi, and QiQi′=1modqi for 1≤i≤k.We can also extend the Chinese remainder theorem to a matrix form, such asx and ai are extended to matrices X and Ai with dimension n×m, respectively; the system of linear congruence has the same solution; that is,(9)X=Q1Q1′A1+⋯+QkQk′AkmodQ,where X is close to uniform distribution [20].


## 3. Identity-Based Broadcast Encryption

(i)
Init: adversary A outputs two receiver subsets S0 and S1 that he wants to attack; it is required that S0=S1 in order to avoid trivial attacks(ii)
Setup: challengerC first runs Setup to generate the public parameters params and a master secret key msk, then gives params to adversary A, and keeps msk to itself(iii)
Phase 1: adversaryA adaptively issues the private key for identity ID∉S0∪S1 query, and challenger C runs skID← Extract msk,ID and returns skID to adversary A(iv)
Challenge: adversaryA selects two equal-length messages M0,M1∈ℳ and sends to challenger C, and challenger C flips a random coin β∈0,1 and returns the challenge ciphertext CT∗← Encrypt params,Sβ,Mβ to adversary A(v)
Phase 2: adversaryA continues to adaptively issue queries as in Phase 1(vi)
Guess: adversaryA outputs a guess β′∈0,1Definition 1.
An IBBE scheme consists of four algorithms (Setup, Extract, Enc, Dec) [19, 34] as follows:(i)
Setup1λ: intake a security parameter λ, and output the public parameters params and a master secret key msk(ii)
Extractmsk,ID: intake a master secret key msk and an identity ID, and output a private key skID for identity ID(iii)
Encparams,S,M: intake the public parameters params, a receiver set S, and a message M∈ℳ, and output a ciphertext CT(iv)
DecskID,CT: intake a private key skID and a ciphertext CT, and output either a message M or an error symbol ⊥
The correctness property requires that, for allID∈S, if (params, msk) ←Setup1λ, skID←Extractmsk, ID), and CT←Encparams, S, M), then DecskID, CT=M with overwhelming probability.
In the above definition, the setS is not required to intake the decryption algorithm which keeps the anonymity of an IBBE system.
We now present the security requirements for an IBBE scheme to be outsider anonymous against the chosen-plaintext attack (CPA). In an outsider-anonymous IBBE scheme, when the adversary receives a ciphertext of which he is not a legal recipient, he will be unable to learn anything about the identities of the legal recipients, but for those ciphertexts for which the adversary is in the authorized set of recipients, he might also learn the identities of some other legal recipients. First, we define the CPA of an outsider-anonymous IBBE scheme as a game, which we term oAIBBE-IND-CPA, played between a probabilistic polynomial-time (PPT) adversaryA and a challenger C. Meanwhile, we present a selective indistinguishable chosen-plaintext security game (sIND-CPA), where selective security is a weaker notion which forces the adversary A to announce ahead of time the identities it will target.Definition 2.
The oAIBBE-sIND-CCA game defined for an oAIBBE schemeΠ = (Setup, Extract, Enc, Dec), a PPT adversary A, and a challenger C is as follows:Definition 3.
Define adversaryA’s advantage in the above oAIBBE-sIND-CPA game as AdvA,IBBEoAIBBE−sIND−CPA=Prβ′=β−1/2. We say that an IBBE scheme is oAIBBE-sIND-CPA secure if for any PPT adversary A, the advantage AdvA,IBBEoAIBBE−sIND−CPA is negligible in the above oAIBBE-sIND-CPA game.


## 4. Construction

Our lattice-based IBBE scheme is designed by translating the lattice-based BE scheme of Wang et al. [20] into an identity-based environment. The private key generation depends on the lattice basis delegation without increasing the dimension [21].(i)
Setupn: intake a secure parameter n, set q≥3 to be odd and m:=⌈6nlogq⌉, and let H1:0,1∗⟶0,1n be a division intractability hash function and H2:0,1∗⟶ℤqm×m be a hash function. Invoke trapdoor sampling algorithm TrapGenq,n to generate a uniformly random matrix A0∈ℤqn×m with a basis T0∈ℤm×m satisfying A0T0=0modq such that T0≤Onlogq. Output public parameters(10)mpk=n,m,q,A0,H1,H2.and a master keymsk=T0.(ii)
Extractmpk,msk,ID: intake public parameters mpk, a master key msk, and an identity ID∈0,1∗, and compute RID=H2ID∈ℤqm×m and AID=A0RID−1∈ℤqn×m. Evaluate(11)SKID←Basis DelA0,RID,T0,σto obtain a short random basisSKID for Λq⊥AID. Output identity ID’s private key SKID.(iii)
Encryptmpk,S,M: intake public parameters mpk, a broadcast set S=ID1,…,IDd, and message M∈0,1m, and compute qIDi  =  H1IDi for IDi∈S. Moreover, to ensure the correctness of decryption, we need qIDi>q. According to the Chinese remainder theorem, it needs to compute Q=qID1…qIDd and QIDi=Q/qIDi, where QIDiQIDi′≡1modqIDi. Calculate(12)AIDi=A0H2IDi−1∈ℤqn×m,forIDi∈S, choose random vector s∈ℤqn and e∈Φ¯αm and a symmetric key K∈0,1m, and compute the ciphertext C1,C2 as follows:(13)C1=K+Mmod2,C2=∑i=1kQIDiQIDi′AIDi⊤∑i=1kQIDiQIDi′s+2e+KmodQ.(iv)
Decryptmpk,SKID,ID: user with identity ID in the broadcast set S uses his private key to decrypt ciphertext C1,C2 as follows:(14)qID=H1ID,AID=A0H2ID−1,K=SKID⊤−1SKID⊤C2modqIDmodqmod2=SKID⊤−1SKID⊤AID⊤s+2e+Kmodqmod2=SKID⊤−1SKID⊤2e+Kmod2=2e+Kmod2,M=C1+Kmod2.


## 5. Analysis of the Proposed Anonymous IBBE Construction

### 5.1. Parameters and Correctness

Given the security parametern, the analysis of parameters and correctness for our scheme is as follows.(i)
To ensure thatTrapGenq,n can operate, the following requirements should be met: m>6nlogq and q=polyn [21].(ii)
To guarantee the decryption of the ciphertext, the error term should be less thanqIDi/2, and let α,qIDi, andσ be set as [23, 47](15)α<1σmωlogm,qIDi>αm3/2ωlogm,σ=m3/2ωlog2n.(iii)
Parametersq should always satisfy q<qIDi and q=mlogm.To ensure that decryption works, we first note thatC2 is designed according to the Chinese remainder theorem, and recall that Q=qID1…qIDn and QIDi=Q/qIDi; then, QIDiQIDi′≡1modqIDi and QIDiQIDi′≡0modqIDj for i≠j. Hence, it would be valid.(16)C2modqIDi=∑i=1kQIDiQIDi′AIDi⊤∑i=1kQIDiQIDi′s+2e+KmodqIDi=AIDi⊤s+2e+hmodqIDi.By the properties of basis delegation,AIDi⋅SKIDi=0modq, where q<qIDi; therefore,(17)SKIDi⊤AIDi⊤s+2e+hmodqIDimodq=SKIDi⊤AID⊤s+2e+Kmodq=SKIDi⊤2e+Kmodq.Finally, we knowK∈0,1m,(18)SKIDi⊤−1SKIDi⊤2e+Kmodqmod2=SKIDi⊤−1SKIDi⊤2e+K=Kmod2=K.


### 5.2. Security

Theorem 1.
The above scheme is oAIBBE-sIND-CPA secure if the LWE problem is hard andH2 is simulated as a random oracle.Proof.
Suppose there exists a PPT adversary that is able to distinguish the above scheme’s ciphertext from random elements with advantageε. Then, there is a challenger C with advantage at least ε+1/2 that distinguishes A0,y0 between the two distributions(19)A0,y0|y0=A0ts0+e0modq:A0←ℤqn×m,s0←ℤqn,e0←Φαm,Unifℤqn×m×ℤqm.(i)
Init: adversary A outputs two different subsets S1∗=ID11∗,…,IDd1∗ and S2∗=ID12∗,…,IDd2∗ that he wants to distinguish. Challenger C samples 2d random matrices R1∗,…,R2d∗∼Dm×m by running Ri∗←SampleR1n (described in Section 3.1), where all Ri∗ are invertible mod q.(ii)
Setup: challenger C chooses two collision-intractable hash functions H1 and H2. H1 is a division intractability hash function, and H2 is simulated as a random oracle. Let QH be the number of H2 queries made by A. Let the master public key be A0, and the master secret key is unknown to C. The system parameters mpk=n,m,q,A0,H1,H2 are given to A.(iii)
Phase 1: adversary A adaptively issues queries as follows:(iv)
Random oracle hash queries:A may adaptively query the random oracle H2 on any identity IDi of its choice at any time. C answers the query as follows.
IfIDi∈S1∗∪S2∗, define H2IDi←Ri∗, return Ri∗ to adversary A, and save the tuple IDi,Ri∗ in a list ℒ.
IfIDi∉S1∗∪S2∗, sample a random matrix R˜i←SampleR1n, where R˜i is invertible mod q, compute Ai=A0⋅R˜i−1modq, and then run sample R with basis Ai (described in Section 3.1) to obtain a random matrix R^i∼Dm×m and a short basis TBi for(20)Bi=AiR^i−1modq=A0⋅R˜i−1R^i−1modq=A0⋅R˜i−1R^i−1modq=A0⋅Ri−1modq.
Save the tupleIDi,Ri,Bi,TBi in a list ℒ for future use, and return H2IDi←Ri to adversary A.(i)
Secret key queries:A makes interactive key extraction queries on arbitrary identity IDi. C answers a query on IDi as follows:IfIDi∈S1∗∪S2∗, C aborts and fails.IfIDi∉S1∗∪S2∗, C retrieves the saved tuple IDi,Ri,Bi,TBi from the hash oracle query list ℒ; else, it runs the random oracle hash query on IDi. Let Bi=A0⋅Ri−1modq and TBi be a short basis for Λq⊥Bi, and return TBi to adversary A.Notice thatBi is exactly the encryption matrix for IDi, and therefore, TBi is a trapdoor for Λq⊥Bi.Challenge: adversary A chooses two equal-length messages M1,M2∈0,1m and sends to challenger C. Challenger C chooses at random a symmetric key K∈0,1m and a random bit β∈0,1; challenger C computes Qβ∗=qID1β∗⋯qIDdβ∗, where qIDjβ∗=H1IDjβ∗ and j∈Sβ∗, and then returns the challenge ciphertext to adversary A.(21)C1=Mβ+Kmod2,C2=2y0+KmodQβ∗.(ii)
Phase 2: adversary A adaptively issues queries as Phase 1.(iii)
Guess: adversary A outputs a guess bit β′, and A wins the game if β=β′.(iv)
Analysis: in the following, we analyse the correctness of the challenge ciphertext.(v)
On the one hand, ify0 is a uniformly random matrix, then the challenge ciphertext is also uniformly random, regardless of the choice of β. Hence, in this case, C outputs 1 with probability at most 1/2.(vi)
On the other hand, ify0=A0s0+e0modq, then the challenge ciphertext is 2y0+KmodQ=2A0s0+e0+KmodQβ∗=2AIDiβ∗⋅Ri∗⋅s0+e0+KmodQβ∗=2AIDiβ∗⋅Ri∗⋅s0+e0+KmodQβ∗=AIDiβ∗⋅2Ri∗⋅s0+2e0+KmodQβ∗=AIDiβ∗⋅s′+2e0+KmodQβ∗=∑i=1kQIDiβ∗QIDiβ∗′AIDiβ∗∑i=1kQIDiβ∗QIDiβ∗′s′+2e0+KmodqIDiβ∗=∑i=1kQIDiβ∗QIDiβ∗′AIDiβ∗∑i=1kQIDiβ∗QIDiβ∗′s′+2e0+KmodQβ∗.
s′=Ri∗⋅2s0modqIDiβ∗ is uniformly distributed (since Q and 2 are relatively prime). This is identical to the output distribution of the real ciphertext.
Hence, if adversaryA succeeds in guessing the right Mβ and Sβ with probability 1/2+ε, then challenger C will correctly guess the nature of the LWE oracle with probability at least 1/2+ε/2. This concludes the proof of the security reduction.Remark.
The above scheme cannot achieve the anonymity for the insider attacker. Because any authorized receiver can obtain the private informations, e, and K, he/she uses s, e, and K to decrypt C2. The decryption process is similar to Thrapdoor Sampling Algorithm of Section 2.1 Therefore, in order to ensure whether or not ID is an authorized receiver, adversary A only needs to calculate whether C2modH1ID and AID⊤s+2e+hmodH1ID are equal. If yes, ID is an authorized receiver; otherwise, ID is not an authorized receiver.


## 5.1. Parameters and Correctness

Given the security parametern, the analysis of parameters and correctness for our scheme is as follows.(i)
To ensure thatTrapGenq,n can operate, the following requirements should be met: m>6nlogq and q=polyn [21].(ii)
To guarantee the decryption of the ciphertext, the error term should be less thanqIDi/2, and let α,qIDi, andσ be set as [23, 47](15)α<1σmωlogm,qIDi>αm3/2ωlogm,σ=m3/2ωlog2n.(iii)
Parametersq should always satisfy q<qIDi and q=mlogm.To ensure that decryption works, we first note thatC2 is designed according to the Chinese remainder theorem, and recall that Q=qID1…qIDn and QIDi=Q/qIDi; then, QIDiQIDi′≡1modqIDi and QIDiQIDi′≡0modqIDj for i≠j. Hence, it would be valid.(16)C2modqIDi=∑i=1kQIDiQIDi′AIDi⊤∑i=1kQIDiQIDi′s+2e+KmodqIDi=AIDi⊤s+2e+hmodqIDi.By the properties of basis delegation,AIDi⋅SKIDi=0modq, where q<qIDi; therefore,(17)SKIDi⊤AIDi⊤s+2e+hmodqIDimodq=SKIDi⊤AID⊤s+2e+Kmodq=SKIDi⊤2e+Kmodq.Finally, we knowK∈0,1m,(18)SKIDi⊤−1SKIDi⊤2e+Kmodqmod2=SKIDi⊤−1SKIDi⊤2e+K=Kmod2=K.


## 5.2. Security

Theorem 1.
The above scheme is oAIBBE-sIND-CPA secure if the LWE problem is hard andH2 is simulated as a random oracle.Proof.
Suppose there exists a PPT adversary that is able to distinguish the above scheme’s ciphertext from random elements with advantageε. Then, there is a challenger C with advantage at least ε+1/2 that distinguishes A0,y0 between the two distributions(19)A0,y0|y0=A0ts0+e0modq:A0←ℤqn×m,s0←ℤqn,e0←Φαm,Unifℤqn×m×ℤqm.(i)
Init: adversary A outputs two different subsets S1∗=ID11∗,…,IDd1∗ and S2∗=ID12∗,…,IDd2∗ that he wants to distinguish. Challenger C samples 2d random matrices R1∗,…,R2d∗∼Dm×m by running Ri∗←SampleR1n (described in Section 3.1), where all Ri∗ are invertible mod q.(ii)
Setup: challenger C chooses two collision-intractable hash functions H1 and H2. H1 is a division intractability hash function, and H2 is simulated as a random oracle. Let QH be the number of H2 queries made by A. Let the master public key be A0, and the master secret key is unknown to C. The system parameters mpk=n,m,q,A0,H1,H2 are given to A.(iii)
Phase 1: adversary A adaptively issues queries as follows:(iv)
Random oracle hash queries:A may adaptively query the random oracle H2 on any identity IDi of its choice at any time. C answers the query as follows.
IfIDi∈S1∗∪S2∗, define H2IDi←Ri∗, return Ri∗ to adversary A, and save the tuple IDi,Ri∗ in a list ℒ.
IfIDi∉S1∗∪S2∗, sample a random matrix R˜i←SampleR1n, where R˜i is invertible mod q, compute Ai=A0⋅R˜i−1modq, and then run sample R with basis Ai (described in Section 3.1) to obtain a random matrix R^i∼Dm×m and a short basis TBi for(20)Bi=AiR^i−1modq=A0⋅R˜i−1R^i−1modq=A0⋅R˜i−1R^i−1modq=A0⋅Ri−1modq.
Save the tupleIDi,Ri,Bi,TBi in a list ℒ for future use, and return H2IDi←Ri to adversary A.(i)
Secret key queries:A makes interactive key extraction queries on arbitrary identity IDi. C answers a query on IDi as follows:IfIDi∈S1∗∪S2∗, C aborts and fails.IfIDi∉S1∗∪S2∗, C retrieves the saved tuple IDi,Ri,Bi,TBi from the hash oracle query list ℒ; else, it runs the random oracle hash query on IDi. Let Bi=A0⋅Ri−1modq and TBi be a short basis for Λq⊥Bi, and return TBi to adversary A.Notice thatBi is exactly the encryption matrix for IDi, and therefore, TBi is a trapdoor for Λq⊥Bi.Challenge: adversary A chooses two equal-length messages M1,M2∈0,1m and sends to challenger C. Challenger C chooses at random a symmetric key K∈0,1m and a random bit β∈0,1; challenger C computes Qβ∗=qID1β∗⋯qIDdβ∗, where qIDjβ∗=H1IDjβ∗ and j∈Sβ∗, and then returns the challenge ciphertext to adversary A.(21)C1=Mβ+Kmod2,C2=2y0+KmodQβ∗.(ii)
Phase 2: adversary A adaptively issues queries as Phase 1.(iii)
Guess: adversary A outputs a guess bit β′, and A wins the game if β=β′.(iv)
Analysis: in the following, we analyse the correctness of the challenge ciphertext.(v)
On the one hand, ify0 is a uniformly random matrix, then the challenge ciphertext is also uniformly random, regardless of the choice of β. Hence, in this case, C outputs 1 with probability at most 1/2.(vi)
On the other hand, ify0=A0s0+e0modq, then the challenge ciphertext is 2y0+KmodQ=2A0s0+e0+KmodQβ∗=2AIDiβ∗⋅Ri∗⋅s0+e0+KmodQβ∗=2AIDiβ∗⋅Ri∗⋅s0+e0+KmodQβ∗=AIDiβ∗⋅2Ri∗⋅s0+2e0+KmodQβ∗=AIDiβ∗⋅s′+2e0+KmodQβ∗=∑i=1kQIDiβ∗QIDiβ∗′AIDiβ∗∑i=1kQIDiβ∗QIDiβ∗′s′+2e0+KmodqIDiβ∗=∑i=1kQIDiβ∗QIDiβ∗′AIDiβ∗∑i=1kQIDiβ∗QIDiβ∗′s′+2e0+KmodQβ∗.
s′=Ri∗⋅2s0modqIDiβ∗ is uniformly distributed (since Q and 2 are relatively prime). This is identical to the output distribution of the real ciphertext.
Hence, if adversaryA succeeds in guessing the right Mβ and Sβ with probability 1/2+ε, then challenger C will correctly guess the nature of the LWE oracle with probability at least 1/2+ε/2. This concludes the proof of the security reduction.Remark.
The above scheme cannot achieve the anonymity for the insider attacker. Because any authorized receiver can obtain the private informations, e, and K, he/she uses s, e, and K to decrypt C2. The decryption process is similar to Thrapdoor Sampling Algorithm of Section 2.1 Therefore, in order to ensure whether or not ID is an authorized receiver, adversary A only needs to calculate whether C2modH1ID and AID⊤s+2e+hmodH1ID are equal. If yes, ID is an authorized receiver; otherwise, ID is not an authorized receiver.


## 6. Conclusions

We propose a lattice-based anonymous IBBE scheme employing the Chinese remainder theorem and lattice basis delegation in fixed dimensions. Our scheme achieves chosen-plaintext security in the random oracle model and is with multiple attractive properties, such as constant-size private/public key and ciphertext and constant encryption/decryption overhead.



---

*Source: 2847731-2021-12-13.xml*