Cryptographic system using pairing with errors

id="REI-00001" date="20210713"

CROSS-REFERENCE TO RELATED APPLICATIONS

id="REI-00001"

0001More than one reissue application has been filed for the reissue of U.S. Pat. No. 9,246,675. The reissue applications are U.S. application Ser. No. 16/678,335 (the present application and a divisional reissue), Ser. No. 16/678,838 (a divisional reissue), and Ser. No. 15/881,531 (granted as U.S. Pat. No. RE 47,841E1), all of which are reissue applications of U.S. Pat. No. 9,246,675.

0002U.S. Pat. No. 9,246,675, which issued on Jan. 26, 2016, is the National Stage of International Application No. PCT/CN2013/074053 filed on Apr. 11, 2013, which claims benefit under 35 U.S.C. § 119(e) of Provisional U.S. Patent Application No. 61/623,272, filed on Apr. 12, 2012, the disclosures of which are hereby incorporated by reference in their entireties.

0003The present disclosure claims priority to the U.S. provisional patent application with Ser. No. 61/623,272, entitled “New methods for secure communications and secure information systems”, filed Apr. 12, 2012 and PCT application with the same title and the PCT number PCT/CN2013/074053 filed on Apr. 11, 2013, which is incorporated herein by reference in its entirety and for all purposes.

BACKGROUND

0004This invention is related to the construction of cryptographic systems, in particular, key exchange (KE) systems, key distribution (KD) systems and identity-based-encryption (IBE) systems, which are based on essentially the same mathematical principle, pairing with errors.

0005In our modern communication systems like Internet, cell phone, and etc, to protect the secrecy of the information concerned, we need to encrypt the message. There are two different ways to do this. In the first case, we use symmetric cryptosystems to perform this task, where the sender uses the same key to encrypt the message as the key that the receiver uses to decrypt the message. Symmetric systems demand that the sender and the receiver have a way to exchange such a shared key securely. In an open communication channel without any central authority, like wireless communication, this demands a way to perform such a key exchange (KE) in the open between two parties. In a system with a central server, like a cell phone system within one cell company, this demands an efficient and scalable key distribution (KD) system such that any two users can derive a shared key via the key distribution (KD) system established by the central server. Therefore it is important and desirable that we have secure and efficient KE systems and KD systems. The first KE system was proposed by Diffie and Hellman [DiHe], whose security is based on the hardness of discrete logarithm problems. This system can be broken by future quantum computers as showed in the work of Shor [SHO]. There are many key-distribution systems including the system using pairing over quadratic forms [BSHKVY], and the one based on bilinear paring over elliptic curves by Boneh and Boyen (in U.S. Pat. No. 7,590,236). But the existing systems have either the problem of computation efficiency or scalability. For instance, the bilinear paring over elliptic curves is very computationally intensive.

0006In the second case, we use asymmetric systems, namely public key cryptographic systems, for encryption, where the receiver has a set of a public key and a private key, and the sender has only the public key. The sender uses the public key to encrypt messages, the receiver uses the private key to decrypt the messages and only the entity who has the private key can decrypt the messages. In an usual public key system, we need to make sure the authenticity of the public keys and therefore each public key needs to have a certificate, which is a digital signature provided by a trusted central authority. The certificate is used to verify that the public key belongs to the legitimate user, the receiver of a message. To make public key encryption system fully work, we need to use such a system, which is called a public key infrastructure (PKI) system.

0007In 1984, Shamir proposed another kind of public key encryption system [SHA]. In this new system, a person or an entity's public key is generated with a public algorithm from the information that can identify the person or the entity uniquely. For example, in the case of a person, the information may include the person's name, residential address, birthday, finger print information, e-mail address, social security number and etc. Since the public key is determined by the public information that can identify the person, this type of public key cryptosystem is called an identity-based encryption (IBE) system.

0008There are a few Identity-based-encryption (IBE) public key cryptosystems, and currently, the (best) one being practically used is the IBE system based on bilinear paring over elliptic curves invented by Boneh and Franklin (in U.S. Pat. No. 7,113,594). In IBE systems, a sender encrypts a message for a given receiver using the receiver's public key based on the identity of the receiver. The receiver decrypts the message using the receiver's private key. The receiver obtains the private key from a central server, which has a system to generate and distribute the IBE private key for the legitimate user securely. An IBE system does not demand the sender to search for the receiver's public key, but rather, a sender in an IBE system derives any receiver's corresponding public key using an algorithm on the information that identifies the receiver, for example, an email address, an ID number or other information. Current IBE systems are very complicated and not efficient in terms of computations, since the bilinear paring over elliptic curves is very computationally intensive. These systems based on pairing over elliptic curves can also be broken efficiently if we have a quantum computer as showed in the work of Shor [SHO]. There are also constructions based on lattices, but those are also rather complicated systems for applications [ABB] [ABVVW] [BKPW]. Therefore it is important and desirable that we have secure and efficient IBE systems.

0009Clearly, there are still needs for more efficient and secure KE, KD and IBE systems for practical applications.

BRIEF SUMMARY OF THE INVENTION

0010This invention first contains a novel method for two parties A and B to perform an secure KE over an open communication channel. This method is based on the computation of pairing of the same bilinear form in two different ways but each with different small errors. In the KE process, each users will choose a private matrix S_A, S_Brespectively with small entries following certain error distributions secretly and a public matrix M randomly. Then each user will compute the multiplication of the user's secret matrix with the publicly chosen matrix but with small errors, exchange the new matrices, and then perform the computation of pairing of S_Aand S_Bover the same bilinear form based on M in two different ways but each with different small errors. This kind of mathematical computation is called pairing with errors. The shared key is derived from the pairings with a rounding technique. This method can be viewed as an extension of the idea of the learning with errors (LWE) problem discovered by Regev in 2005 [Reg]. The security of this system depends the hardness of certain lattice problem, which can be mathematically proven hard [DiLi]. This system involves only matrix multiplication and therefore is very efficient. Such a system can also resist the future quantum computer attacks.

0011This invention second contains a novel method to build a KD system with a central server or authority. In this system, the central server or authority assigns each user i a public ID as a matrix A_iwith small entries or establish the ID of each user as a matrix A_iwith small entries following certain error distributions with the information that can identify the user uniquely, and, in a secure way, gives each user a private key based on certain multiplication of this ID matrix with the central server or authority's secret master key M, another matrix, but with small errors. Then any two users in the system will compute the pairing of the two ID matrices of the users with the same bilinear form based on the master key matrix M in two different ways but each with different small errors to derive a shared key between these two users with certain rounding technique. This method can be viewed as an extension of the idea of the learning with error problem discovered by Regev in 2005 [Reg]. The security of this system depends on the hardness of the problem related to pairing with errors. This system involves only matrix multiplication and therefore is very efficient.

0012This invention third contains a novel method to build a IBE system with a central server or authority. In this system, the central server or authority assigns each user i a public ID A_ias a matrix with small entries following certain certain error distributions or establish the ID of each user as a matrix with small entries following certain certain error distributions with the information that can identify the user uniquely. Each user is given by the central server or authority a private key S_ibased on certain multiplication of this ID matrix with the central server or authority's master private key S, another matrix, but with errors related to one part of the master public key M, another matrix. The central server or authority will establish another half of the mater key as the multiplication of M and S with small errors, which we call M₁. Then any user who wishes to send the user i a message in the system will compute public key of i which consists of M and a paring of M and A_iof the bilinear form based on the master secret key matrix S, then encrypt the message using the encryption system based on the MLWE problem, and the user i will use the secret key S_ito decrypt the message. This method can be viewed as an extension of the idea of the learning with error problem discovered by REGEV in 2005. The security of this system depends the harness of certain lattice problem, which can be mathematically proven hard. This system involves only matrix multiplication and therefore is very efficient.

0013In our constructions, we can replace matrices by elements in ideal lattice, and we can also use other type of rounding techniques. We can also build the system in a distributed way where several servers can work together to build KD and IBE systems.

0014In short, we use the same mathematical principle of paring with errors, which can be viewed as an extension of the idea of the LWE problem, to build secure and more efficient KE, KD and IBE systems.

0015Though this invention has been described with specific embodiments thereof, it is clear that many variations, alternatives, modifications will become apparent to those who are skilled in the art of cryptography. Therefore, the preferred embodiments of the invention as set forth herein, are intended to be illustrative, not limiting. Various changes may be made without departing from the scope and spirit of the invention as set forth herein and defined in the claims. The claims in this invention are based on the U.S. provisional patent application with Ser. No. 61/623,272, entitled “New methods for secure communications and secure information systems”, filed Apr. 12, 2012, only more technical details are added.

DETAILED DESCRIPTION OF THE INVENTION

00001.1 The Basic Idea of Pairing with Errors

0016The learning with errors (LWE) problem, introduced by Regev in 2005 [Reg], and its extension, the ring learning with errors (RLWE) problem [LPR] have broad application in cryptographic constructions with some good provable secure properties. The main claim is that they are as hard as certain worst-case lattice problems and hence the related cryptographic constructions.

0017A LWE problem can be described as follows. First, we have a parameter n, a (prime) modulus q, and an error probability distribution n on the finite ring (field) F_qwith q elements. To simplify the exposition, we will take q to be a odd prime and but we can also work on any whole number except that we may need to make slight modifications.

0018In F_q, each element is represented by the set {−(q−1)/2, . . . , 0, . . . , (q−1)/2}. In this exposition, by “an error” distribution, we mean a distribution we mean a distribution such that there is a high probability we will select an element, which is small. There are many such selections and the selection directly affect the security of the system. One should select good error distribution to make sure the system works well and securely.

0019Let Π_S,κ, on F_qbe the probability distribution obtained by selecting an element A in F_qⁿrandomly and uniformly, choosing e ϵF_qaccording to κ, and outputting (A, <A, S>+e), where + is the addition that is performed in F_q. An algorithm that solves the LWE problem with modulus q and error distribution κ, if, for any S in F_qⁿ, with an arbitrary number of independent samples from Π_S,κ, it outputs S (with high probability).

0020To achieve the provable security of the related cryptographic constructions based on the LWE problem, one chooses q to be specific polynomial functions of n, that is q is replaced by a polynomial functions of n, which we will denote as q(n), κ to be certain discrete version of normal distribution centered around 0 with the standard deviation σ=αq≥√{square root over (n)}, and elements of F_qare represented by integers in the range [−(q 1)/2, (q 1)/2)], which we denote as κ_σ.

0021In the original encryption system based on the LWE problem, one can only encrypt one bit a time, therefore the system is rather inefficient and it has a large key size. To further improve the efficiency of the cryptosystems based on the LWE problem, a new problem, which is a LWE problem based on a quotient ring of the polynomial ring F_q[x] [LPR], was proposed. This is called the ring LWE (RLWE) problem. In the cryptosystems based on the RLWE problem, their security is reduced to hard problems on a subclass of lattices, the class of ideal lattices, instead of general lattices.

0022Later, a new variant of LWE was proposed in [ACPS]. This variant of the LWE problem is based on the LWE problem. We will replace a vector A with a matrix A of size m×n, and S also with a matrix of size n×1, such that they are compatible to perform matrix multiplication A×S. We also replace e with a compatible matrix of size m×1. We will work on the same finite field with q elements.

0023To simplify the exposition, we will only present, in detail, for the case where A is a square matrices of the size n×n and, S and e of the size n×1.

0024Let Π_S,κ_{<sub2>n</sub2>}, over F_qbe the probability distribution obtained by selecting an n×n matrix A, whose each entry are chosen in F_quniformly and independently, choosing e as a n×1 vector over F_qwith entries chosen according to certain error distribution κ_n, for example, each entries follows an error distribution n independently, and outputting (A, A×S+e), where + is the addition that is performed in F_qⁿ. An algorithm that solves a LWE with modulus q and error distribution κ_n, if, for any vector S in F_qⁿ, with any number of independent sample(s) from Π_S,κ_{<sub2>n</sub2>}, it outputs S (with high probability).

0025For the case that we choose a small S, namely entries of S are chosen independently according to also the error distribution κ_n, we call this problem a small LWE problem (SLWE). If we further impose the condition A to be symmetric, we call it a small symmetric LWE problem (SSLWE). If we choose the secret S randomly and independently from the set −z, . . . , 0, 1 . . . , z with z a fixed small positive integer, we call such a problem uniformly small LWE problem (USLWE).

0026For practical applications, we can choose S and e with different kind of error distributions.

0027Due to the results in [ACPS], we know If the secret S's coordinates and the error e's entries are sampled independently from the LWE error distribution κ_σ, the corresponding LWE problem is as hard as LWE with a uniformly random secret S. This shows that the SLWE problem is as hard as the corresponding LWE problem. The same is true for the case of the RLWE problem that if one can solve the Ring LWE problem with a small secret namely the element S being small, then one can solve it with an uniform secret.

0028We further extend the problem to a full matrix form.

0029Let Π_S,κ_{<sub2>n</sub2>}₂over F_qbe the probability distribution obtained by selecting an n×n matrix A, whose each entry are chosen in F_quniformly and independently, choosing e as a n×n matrix over F_qwith entries following certain error distribution κ_n_{<sup2>2</sup2>}, for example, an distribution chosen according to the error distribution n independently, and outputting (A, A×S+e), where + is the addition that is performed in F_qⁿ^{<sup2>2</sup2>}. An algorithm that solves a LWE with modulus q and error distribution κ_n_{<sup2>2</sup2>}, if, for any n×n matrix S in F_qⁿ, with any number of independent sample(s) from Π_S,κ_{<sub2>n</sub2>}₂, it outputs S (with a high probability).

0030We call this problem matrix LWE problem (MLWE). For the case where we choose a small S, namely entries of S also follows the error distribution κ_n_{<sup2>2</sup2>}, we call this problem a small MLWE problem (SMLWE). If we further impose the condition A to be symmetric, we call it a small symmetric MLWE problem (SSMLWE). If we choose the secret S randomly and independently from the set −z, . . . , 0, 1 . . . , z with z a fixed small positive integer, we call such a problem uniformly small MLWE problem (USMLWE). It is clear the MLWE problem is nothing but put n LWE problem together and sharing the same matrices. Therefore it is as hard as the corresponding LWE problem.

0031We can use different error distributions for S and e.

0032The mathematical principle behind our construction comes from the fact of associativity of matrices multiplications of three matrices A, B and C: <br />A×B×C=(A×B)×C=A×(B×C).<br /> Such a product can be mathematically viewed as computing the bilinear paring of the row vectors of A with column vectors of C.

0033For two matrices A and B with small entries following certain error distributions, for example, with entries following some error distributions, instead of computing this product directly, we can first compute <br />AB+E_a,<br />then compute<br />(AB+E_A)C or (AB+E_A)C+E_AC,<br />or we will compute<br />BC+E_C,<br />then compute<br />A(BC+E_c) or (AB+E_A)C+E_BC,<br /> where E_A, E_B, E_AC, E_BCare matrices with small entries following the same (or different) error distributions. Then we have two way to compute the product ABC with small errors or differences between these two matrices. We call such a computation pairing with errors. All our constructions depends on such a paring with errors and on the fact that the two different paring are close to each other if A and C are also small.

0034We can mathematically prove the theorem that an MLWE problem is as hard as the corresponding LWE problem with the same parameters. This provides the foundation of the provable security of our constructions

00001.2 The Construction of the New KE Systems Based on Paring with Errors

0035Two parties Alice and Bob decide to do a key exchange (KE) over an open channel. This means that the communication of Alice and Bob are open to anyone including malicious attackers. To simplify the exposition, we will assume in this part all matrices involves are n×n matrices. But they do not have to be like this, and they can be matrices of any sizes except that we need to choose the compatible sizes such that the matrix multiplications performed are well defined.

0036Their key change protocol will go step by step as follows. <ul id="ul0001" list-style="none"><li id="ul0001-0001" num="0000"><ul id="ul0002" list-style="none"><li id="ul0002-0001" num="0037">(1) Alice and Bob will first publicly select F_q, n and a n×n matrix M over F_quniformly and randomly, where q is of size of a polynomial of n, for example q≈n³, and an error distribution κ_n_{<sup2>2 </sup2>}to be a distribution over n×n matrices over F_q, for example, a distribution that each component are independent and each component follow certain error distribution like the discrete error distribution κ_σas in the case of LWE, namely a discrete normal distribution over F_qcenter around 0 with standard deviation approximately √{square root over (n)}. All the information above is public. They jointly and publicly choose a small (prime) integer t (t&lt;&lt;n).</li><li id="ul0002-0002" num="0038">(2) Then each party chooses its own secret S_i(i=A, B) as a n×n matrix chosen according to the error distribution κ_n_{<sup2>2</sup2>}, e_ialso as a n×n matrix following the error distribution. For Alice, she computes <br />M_A=MS_A+te_A,<ul id="ul0003" list-style="none"><li id="ul0003-0001" num="0039">where t is a small integer (t&lt;&lt;n). <ul id="ul0004" list-style="none"><li id="ul0004-0001" num="0040">For Bob, he computes <br />M_B=M^tS_B+te_B.</li></ul></li></ul></li><li id="ul0002-0003" num="0041">(3) Both parties exchange M_iin the open communication channel. This means both M_i(i=A, B) are public, but keep S_iand e_i(i=A, B), secret.</li><li id="ul0002-0004" num="0042">(4) Alice computes: <br />K_A=S^t_A×M_B=S^t_AM^tS_B+tS^t_Ae_B.<ul id="ul0005" list-style="none"><li id="ul0005-0001" num="0043">Bob computes: <br />K_B=M^t_A×S_B=S^t_AM^tS_B+te^t_AS_B.</li></ul></li><li id="ul0002-0005" num="0044">(5) Both of them will perform a rounding technique to derive the shared key as follows: <ul id="ul0006" list-style="none"><li id="ul0006-0001" num="0045">(a) Bob will make a list T₁of all positions of the entries of K_Bsuch that these entries are in the range of [−(q−1)/4, (q−1)/4] and a list T₂of all positions which are not in the range of [−(q−1)/4, (q−1)/4]. Then Bob will send to Alice the list T₁.</li><li id="ul0006-0002" num="0046">(b) Then each party will compute the residues of these entries modular t in T₁, and for the entries not in T₁, which is in T₂, they will add (q−1)/2 to each entry and compute the residue modular q first (into the range of [−(q−1)/4, (q−1)/4]) then the residue modular t. That gives a shared key between these two users.</li></ul></li></ul></li></ul>

0047The reason that Alice and Bob can derive from K_Aand K_Ba shared secret to be the exchanged key via certain rounding techniques as in the case above is exactly that e_iand S_iare small, therefore K_Aand K_Bare close. We call this system a SMLWE key exchange protocol. We can derive the provable security of this more efficient system [Dili].

0048In term of both communication and computation efficiency, the new system is very good. The two parties need to exchange n²entries in F_q, and each perform 2n^2.8computations (with Strassen fast matrix multiplication [STR]) to derive n²bits if t=2.

0049S_iand e_ican follow different kind of error distributions.

0050We can prove the theorem that if we choose the same system parameters, namely n and q, the matrix SLWE key exchange protocol is provably secure if the error distribution is properly chosen [DiLi]. The proof relies on the mathematical hardness of the following pairing with error problem.

0051Assume that we are given <ul id="ul0007" list-style="none"><li id="ul0007-0001" num="0000"><ul id="ul0008" list-style="none"><li id="ul0008-0001" num="0052">(1) an n×n matrix M, a prime integer q, a small positive integer t, and an error distribution κ_nand; <br />M′_A=MS′_A+te_A<br />and<br />M′_B=M^tS′_B+te_B,  (2)<ul id="ul0009" list-style="none"><li id="ul0009-0001" num="0053">where e_i, a n×1 vector follows the error distribution κ_nand the entries of n×1 vectors also follows the same error distribution;</li></ul></li><li id="ul0008-0002" num="0054">(3) and the fact that <br />K′_B=M^t_A×S′_B=(S′_A)^tM^tS′_B+t<e_A,S′_B><ul id="ul0010" list-style="none"><li id="ul0010-0001" num="0055">is in the range of [−(q−1)/4, (q−1)/4] or not; <br /> the problem is to find an algorithm to derive <br />K′_A=(S′_A)^t×M_B=(S′_A)^tM^tS′_B+t<S′_A,e_B><br /> modular t if K′_Bis in the range of [−(q−1)/4, (q−1)/4], otherwise K′_A+(q−1)/2 first modular q then modular t, with a high probability. We call such a problem a pairing with error problem (PEP). </li></ul></li></ul></li></ul>

0056The proof follows from the fact that the SMLWE problem is as hard as the SLWE problem, since the matrix version can be viewed as just assembling multiple SLWE samples into one matrix SLWE sample.

0057We note here that we can choose also rectangular matrix for the construction as long as we make sure the sizes are matching in terms of matrix multiplications, but parameters need to be chosen properly to ensure the security.

0058Similarly we can build a key exchange system based on the ring learning with errors problem (RLWE) [LPR], we will a variant of the RLWE problem described in [LNV].

0059For the RLWE problem, we consider the rings R=Z[x]/f(x), and R_q=R/qR, where f(x) is a degree n polynomial in Z[x], Z is the ring of integers, and q is a prime integer. Here q is an odd (prime) and elements in Z_q=F_q=Z/q are represented by elements: −(q−1)/2, . . . , −1, 0, 1, . . . , (q−1)/2, which can be viewed as elements in 2 when we talk about norm of an element. Any element in R_q, is represented by a degree n polynomial, which can also be viewed as a vector with its corresponding coefficients as its entries. For an element <br />a(x)=a₀+a₁x+ . . . +a_n-1x^n-1,<br />we define<br />∥a∥=max|a_i|,<br /> the l_∞norm of the vector (a₀, a₁, . . . , a_n-1) and we treat this vector as an element in Zⁿand a_ian element in Z. We can also choose q to be even positive number and things need slight modification.

0060The RLWE_f,q,χ problem is parameterized by an polynomial f(x) of degree n, a prime number q and an error distribution X over R_q. It is defined as follows.

0061Let the secret s be an element in R_q, a uniformly chosen random ring element. The problem is to find s, given any polynomial number of samples of the pair <br />(a_i,b_i=a_i×s+e_i),<br /> where a_iis uniformly random in R_qand e_iis selected following certain error distribution X.

0062The hardness of such a problem is based on the fact that the b_iare computationally indistinguishable from uniform in R_q. One can show [LPR] that solving the RLWE_f,q,χ problem above is known to give us a quantum algorithm that solves short vector problems on ideal lattices with related parameters. We believe that the latter problem is exponentially hard.

0063We will here again use the facts in [ACPS], [LPR] that the RLWE_f,q,χ problem is equivalent to a variant where the secret s is sampled from the error distribution X rather than being uniform in R_qand the error element e_iare multiples of some small integer t.

0064To derive the provable security, we need consider the RLWE problem with specific choices of the parameters. <ul id="ul0011" list-style="none"><li id="ul0011-0001" num="0000"><ul id="ul0012" list-style="none"><li id="ul0012-0001" num="0065">We choose f(x) to be the cyclotomic polynomial xⁿ+1 for n=2^u, a power of two;</li><li id="ul0012-0002" num="0066">The error distribution χ is the discrete Gaussian distribution D_Z_{<sup2>n</sup2>}_,σfor some n>>σ>ω(√{square root over (log n)})>1;</li><li id="ul0012-0003" num="0067">q=1 (mod 2n) and q a polynomial of n and q≈n³;</li><li id="ul0012-0004" num="0068">t a small prime and t<<n<<q. <br /> We can also use other parameters for practical applications. </li></ul></li></ul>

0069There are two key facts in the RLWE_f,q,χ setting defined above, which are needed for our key exchange system. <ul id="ul0013" list-style="none"><li id="ul0013-0001" num="0000"><ul id="ul0014" list-style="none"><li id="ul0014-0001" num="0070">(1) The length of a vector drawn from a discrete Gaussian of with standard deviation a is bounded by σn, namely, <br />Pr(∥X∥>σn)≤2⁻ⁿ⁺¹,<ul id="ul0015" list-style="none"><li id="ul0015-0001" num="0071">for X chosen according to X.</li></ul></li><li id="ul0014-0002" num="0072">(2) The multiplication in the ring R_qincreases from the norms of the constituent elements in a reasonable scale, that is, <br />∥X×Y(mod f(x))∥≤n∥X∥∥Y∥,<ul id="ul0016" list-style="none"><li id="ul0016-0001" num="0073">for X, Y ϵ R_qand the norm is the l_∞norm defined above.</li></ul></li></ul></li></ul>

0074With the RLWE_f,q,χsetting above, we are now ready to have two parties Alice and Bob to do a key exchange over an open channel. It goes step by step as follows. <ul id="ul0017" list-style="none"><li id="ul0017-0001" num="0000"><ul id="ul0018" list-style="none"><li id="ul0018-0001" num="0075">(1) Alice and Bob will first publicly select all the parameters for the RLWE_f,q,χ including q(≈n³or similar polynomial functions of n), n, f(x) and χ. In addition, they will select a random element M over R_quniformly. All the information above is public.</li><li id="ul0018-0002" num="0076">(2) Then each party chooses its own secret s_ias an element in R_qaccording to the error distribution χ, and e_iindependently also as an element following the error distribution χ, but jointly choose a small prime integer t (t&lt;&lt;n) For Alice, she computes <br />M_A=Ms_A+te_A,</li><li id="ul0018-0003" num="0077">where t is a small integer (t&lt;&lt;n). <ul id="ul0019" list-style="none"><li id="ul0019-0001" num="0078">For Bob, he computes <br />M_B=Ms_B+te_B.</li></ul></li><li id="ul0018-0004" num="0079">(3) Both parties exchange M_i. This means both M_iare public, but certainly keep s_iand e_isecret.</li><li id="ul0018-0005" num="0080">(4) Alice computes: <br />K_A=s_A×M_B=s_AMs_B+te_Bs_A.<ul id="ul0020" list-style="none"><li id="ul0020-0001" num="0081">Bob computes: <br />K_B=M_A×s_B=s_AMs_B+te_As_B.</li></ul></li><li id="ul0018-0006" num="0082">(5) Both of them will perform a rounding technique to derive the shared key as follows: <ul id="ul0021" list-style="none"><li id="ul0021-0001" num="0083">(a) Bob will then make a list of size n, and this list consists of pairs in the form of (i, j), where i=0, . . . , n−1, and j=1 if the xⁱcoefficient of K_Bis in the range of [−(q−1)/4, (q−1)/4], otherwise j=0.</li><li id="ul0021-0002" num="0084">(b) Then Bob will send this list to Alice. Then each will compute the residue of the corresponding entries modular t in the following way: <ul id="ul0022" list-style="none"><li id="ul0022-0001" num="0085">for an element of the list (i, j),</li><li id="ul0022-0002" num="0086">1) if j=1, each will compute the i-th entry of K_Aand K_Bmodular t respectively;</li><li id="ul0022-0003" num="0087">2) if j=0, each will add (q−1)/2 to the i-th entry of K_Aand K_Bmodular q back to range of [−(q−1)/4, (q−1)/4], then compute the residues modular t.</li></ul></li></ul></li></ul></li></ul>

0088We can use different distributions for s_iand e_i.

0089That will give a shared key between these two users. We call this system a RLWE key exchange system. We can deduce that there is a very low probability of failure of this key exchange system. We note here that the commutativity and the associativity of the ring R_qplay a key role in this construction.

0090In terms of security analysis, we can show the provable security of the system following the hardness of the RLWE_f,q,χ problem by using a similar PEP over the ring R_q[DiLi].

0091Assume that we are given <ul id="ul0023" list-style="none"><li id="ul0023-0001" num="0000"><ul id="ul0024" list-style="none"><li id="ul0024-0001" num="0092">a random element M in R_q, prime integers t, q and the error distribution X with parameters selected as in the RLWE_f,q,χ above;</li><li id="ul0024-0002" num="0093">M_A=Ms_A+te_Aand M_B=Ms_B+te_B, where e_ifollows the error distribution X and s_ialso follows the error distribution χ;</li><li id="ul0024-0003" num="0094">and the fact that (K_B)_i, the coefficients xⁱof K_B=M_A×s_B=s_AMs_B+te_As_Bis in the range of [−(q−1)/4, (q−1)/4] or not; <br /> the problem is to find an algorithm to derive K_B(or K_A) modular t or K_B+(q−1)/2 (or K_A+(q−1)/2) modular q (into the range of [−(q−1)/4, (q−1)/4]) and then modular t with a high probability. We call such a problem a pairing with error problem over a ring (RPE). </li></ul></li></ul>

0095It is nearly a parallel extension of the proof of the provable security of the case of SLWE key exchange system to the RLWE key exchange system. We conclude that the RLWE key exchange system is provable secure based on the hardness of the RLWE_f,q,χ problem.

0096With the same parameters q and n, this system can be very efficient due to the possibility doing fast multiplication over the ring R_qusing FFT type of algorithms.

00001.3 The Construction of the New KD Systems Based on Paring with Errors

0097Over a large network, key distribution among the legitimate users is a critical problem. Often, in the key distribution systems, a difficult problem is how to construct a system, which is truly efficient and scalable. For example, in the case of the constructions of [BSHKVY], the system can be essentially understood as that the master key of a central server is a symmetric matrix M of size n×n and each user's identity can be seen as a row vector H_iof size n. The central server gives each user the secret H_i×M. Then two users can derive the shared key as H_i×M×H_j^t. The symmetric property of M ensures that <br />H_i×M×H_j^t=H_j^t×M×H_i.<br /> However, large number of users can collaborate to derive the master key. If one can collect enough (essentially n) H_i×M, which then can be used to find the master key M and therefore break the system.

0098We will build a truly scalable key distribution system using the pairing with error with a trusted central server, which can be viewed as a combination of the idea above and the idea of the LWE.

0099We work again over the finite field F_q, whose elements are represented by −(q−1)/2, . . . , 0, . . . , (q−1)/2. We choose q≈n³or other similar polynomial function of n, we choose again κ_n_{<sup2>2 </sup2>}to be an error distribution over the space of n×n matrices, for example, an distribution each component are independent, and each component follows error distribution κ_σ, the discrete distribution as in the case of LWE, namely a discrete normal distribution over F_qcentered around 0 with standard deviation approximately √{square root over (n)}. The choice of these parameters can be modified.

0100The key distribution system is set up step by step as follows. <ul id="ul0025" list-style="none"><li id="ul0025-0001" num="0000"><ul id="ul0026" list-style="none"><li id="ul0026-0001" num="0101">(1) We have a central server, which will select a symmetric randomly chosen n×n matrix S, as a master key, whose entries are in F_q: <br />S=S^t.</li><li id="ul0026-0002" num="0102">(2) For each user index as i, the central server gives it a (in general not symmetric) matrix A_t(as an ID) with small entries following error distribution κ_n_{<sup2>2</sup2>}. The ID matrix of each user is public and it can also be generated with information that can identify the user like email address, name and etc.</li><li id="ul0026-0003" num="0103">(3) For each user, the central server distribute securely a secret: <br />E_i=A_iS+te_i,</li><li id="ul0026-0004" num="0104">where e_iis a matrix (not symmetric) selected following certain error distribution, such as κ_n_{<sup2>2</sup2>}. This is kept private for each user.</li></ul></li></ul>

0105To obtain a secret key shared between the user i and the user j, the user i computes <br />K_i=E_i×A_j^t=A_iSA_j^t+te_iA_j^t;<br />and the user j computes<br />K_j=A_i×(E_j)^t=A_iS^tA_j^t+tA_ie_j^t=A_iSA_j^t+tA_ie_j^t.<br /> This is possible because the IDs are public. They then can use the following simple rounding method to derive a shared key between the two users. <ul id="ul0027" list-style="none"><li id="ul0027-0001" num="0000"><ul id="ul0028" list-style="none"><li id="ul0028-0001" num="0106">When the user j wants to establish a shared key with the user i, the user j will collect all the entries (including their positions in the matrix) in K_jthat are in the range of (−(q−1)/4, (q−1)/4), namely those entries which are closer to 0 than (q−1)/2. Then user j will send to the user i a list of the positions of the entries in the matrix (only the position not the values of the entries themselves) that are randomly selected from the collection, which is tagged by 0, and a list of entries not in the list tagged by 0. Then the user i will select the same entries in its own matrix E_i×A_j. Now they have a shared list of common entry positions, therefore the corresponding entries of the matrix. Then each user will compute the residue of these entries modular t tagged by 1 and compute the residue of the sum of each of these entries tagged by 0 with (q−1)/2 to build a new identical ordered list of values, which will be their shared secret key.</li></ul></li></ul>

0107Because S symmetric, we have that <br />A_iSA_j^t=A_iS^tA_j^t,<br />therefore the user j derives<br />A_iSA_j^t+tA_iA_ie_j^t.<br /> The difference between the results computed by the two users is: <br />E_i×A^t_j−A_i×E^t_J=A_iSA^t_j+te_iA^t_j−(A_iSA^t_j+tA_ie^t_j)<br />=te_iA^t_j−tA_ie^t_j.

0108This difference is small since t is small and e_iA_j^tand A_ie_j^tare small, which is due to the fact that e_i, e_j, A_iand A_jare all small. This allows us to get a common key for i and j by certain rounding techniques and therefore build a key distribution system.

0109Since the error terms for both matrices, te_iA_jand te_j^tA_i, are small, the corresponding selected entries with tag 1 in A_iSA_j(without the error terms) are essentially within the range of [(−(q−1)/4, (q−1)/4] or very close. Therefore the error terms will not push those selected terms in A_iSA_jover either (−(q−1)/2 or (q−1)/2), that is when added the error terms, those selected entries will not need any further modular q operation but just add them as integers, since each element is represented as an integer in the range of [(−(q−1)/2(q−1)/2)]. The same argument goes with entries tagged by 0. These ensures that the process give a shared key between these two users.

0110From the way matrices K_i, K_jare constructed, we know that each entry of K_iand K_jfollows uniform distribution. Therefore we expect that each time the size of the first list selected by the user j from the matrix K_jshould be around n². Therefore this system can provide the shared secret with enough bits if we choose proper n.

0111Also we can build a version of this system with none symmetric matrices, in this case, the central serve needs to compute more matrices like A_iS+e and A_i^tS+e′. Then it is possible, we can do the same kind of key distribution. This system again is less efficient.

0112On the other hand, since the RLWE problem can be viewed as a specialized commutative version of matrix-based LWE since an element in the ring can be view as a homomorphism on the ring. We can use the RLWE to build a key distribution in the same way.

0113Now let us look at why this key distribution is scalable. Clearly each user will have a pair A, and E_i=A_iS+te_i, and many users together can get many pairs, then to find the secret master key S is to solve the corresponding MLWE problem, except that, in this case, we impose the symmetric condition on the secret S. It is not difficult to argue again that this problem is as hard as a LWE problem, since given a LWE problem, we can convert it also into such a MLWE problem with symmetric secret matrix. Therefore, it is easy to see that this system is indeed scalable.

0114In terms of the provable security of the system, the situation is similar to the work done in the paper [DiLi]. We can give a provable security argument along the same line.

0115As we said before, since RLWE can be viewed as a special case MLWE, we will use the RLWE to build a very simple key distribution system.

0116We will choose the ring R_qto be F_q[x]/xⁿ+1. To ensure the provable security, we need to choose parameter properly n, q, properly, for example n=2^k, q=1 mod(2n)[LPR]. For provable secure systems, we assume that we will follow the conventional assumptions on these parameters, and the assumption on the error distribution like χ in [LPR].

0117This construction is essentially based on the systems of above. We assume that we have a ring R_qwith a properly defined learning with error problem on the ring R_qwith error distribution X. The problem is defined as follows:

0118We are given a pair (A, E), where <br />E=A×S+te′,<br /> A, S where e′ are elements in R, t is small integer, e′ is an error element following the distribution of χ, S is a fixed element and A is select randomly following uniform distribution, and the problem is to find the secret S.

0119With a central server, we can build a simple key distribution system as follows. <ul id="ul0029" list-style="none"><li id="ul0029-0001" num="0000"><ul id="ul0030" list-style="none"><li id="ul0030-0001" num="0120">(1) The central server will also select a random element M in R_qfollowing uniform distribution.</li><li id="ul0030-0002" num="0121">(2) For each user, the central server will assign an public ID as A_i, where A_ishould be in the form of a chosen small element in R_q, namely following an error distribution like χ.</li><li id="ul0030-0003" num="0122">(3) Each member is given a secret key by the central server: <br />S_i=MA_S+te_e,<ul id="ul0031" list-style="none"><li id="ul0031-0001" num="0123">where e_ifollows an error distribution χ.</li></ul></li><li id="ul0030-0004" num="0124">(4) If two user i and j wants to build a shared key, one user, say i can use the ID matrix of j, namely A_i, the its secret key to build a shared key with j by computing <br />K_i=A_j×S_i=A_jMA_i+tA_je_i,<ul id="ul0032" list-style="none"><li id="ul0032-0001" num="0125">and j can use its secret key to build a shared key with i by computing <br />K_j=A_i×S_j=A_jMA_i+tA_ie_j,</li><li id="ul0032-0002" num="0126">then derive the shared key with the rounding technique as follows: <ul id="ul0033" list-style="none"><li id="ul0033-0001" num="0127">(a) i will then make a list of size n, and this list consists of pairs in the form of (a, b), where a=0, . . . , n−1, and b=1 if the x^acoefficient of K_iis in the range of [−(q−1)/4, (q−1)/4], otherwise b=0.</li><li id="ul0033-0002" num="0128">(b) i will send this list to j. Then each will compute the residue of the corresponding entries modular t in the following way: <ul id="ul0034" list-style="none"><li id="ul0034-0001" num="0129">for an element of the list (a, b),</li><li id="ul0034-0002" num="0130">1) if b=1, each will compute the a-th entry of K_iand K_jmodular t respectively;</li><li id="ul0034-0003" num="0131">2) if b=0, each will add (q−1)/2 to the a-th entry of K_iand K_jmodular q back to range of [−(q−1)/4, (q−1)/4], then compute the residues modular t.</li></ul></li></ul></li></ul></li></ul></li></ul>

0132Since A_iand e_iare small elements in R_q, we have A_i×e_iis also small. This ensures that we indeed have a shared secret key. This, therefore, gives an key-distribution system.

0133Here we use very much the fact that in a RLWE problem that the multiplication is commutative. The key feature of our construction is that it is simple and straight forward. The provable security of the system is also straightforward.

00001.4 the Construction of the New IBE Systems Based on Paring with Errors

0134We will first build a new public key encryption based on MLWE. To build an encryption system, we choose similar parameter q≈n³or n⁴or similar polynomial functions of n, we choose again κ_n_{<sup2>2 </sup2>}to be an error distribution, for example the error distribution with each component are independent, and each component follow the same discrete distribution κ_σas in the case of LWE, namely a discrete normal distribution over F_qcenter around 0 with standard deviation approximately √{square root over (n)}. Surely we can also select high dimensional Gaussian distribution, which should be very convenient for the purpose to provable security. We select this simple distribution to simplify the argument concerning the validity of the encryption system. We can surely choose other parameters.

0135With such a setting, we can build an encryption system as in the case of the MLWE problem as follows: <ul id="ul0035" list-style="none"><li id="ul0035-0001" num="0000"><ul id="ul0036" list-style="none"><li id="ul0036-0001" num="0136">(1) We select an n×n matrix S, whose entries are small following an error distribution κ_n_{<sup2>2</sup2>}, for example, each entries independently and randomly follows the distribution κ_σ.</li><li id="ul0036-0002" num="0137">(2) In the setting of the MLWE, we will derive one output pair (A, E), where <br />E=A×S+e,<br />or<br />E=A×S+te,<ul id="ul0037" list-style="none"><li id="ul0037-0001" num="0138">and t is small, t&lt;&lt;n, and they form the public key of our encryption system. Here e follow certain error distributions, for example the distribution we use above.</li></ul></li><li id="ul0036-0003" num="0139">(3) S is the private key of the cryptosystem.</li><li id="ul0036-0004" num="0140">(4) A message in is represented as n×n matrix with binary entries of 0, 1 or n×n matrix with entries in the range modular t, namely 0, 1 . . . , t−1.</li><li id="ul0036-0005" num="0141">(5) A sender chooses a n×n small matrix B similar to S namely following an error distribution κ_n_{<sup2>2</sup2>}, for example, each entries independently and randomly follows the distribution κ_σ. Then the sender compute the encrypted message as: <br />(D₁,D₂)=(B×A+e₁,B×E+e₂+m (q/2)),<br />or<br />((D₁,D₂)=(B×A+te₁,B×E+te₂+m,<ul id="ul0038" list-style="none"><li id="ul0038-0001" num="0142">where e₁and e₂are error matrices selected independently following some error distribution like e.</li></ul></li><li id="ul0036-0006" num="0143">(6) To decrypt, the legitimate, in the first case, computes <br />D₂−D₁×S=(BE+e₂+m(q/2)−(BA+e₁)S)=eE+e₂−e₁S+m(q/2),<ul id="ul0039" list-style="none"><li id="ul0039-0001" num="0144">where everything is done in F_q, and we can check on each entry of the matrix, if it is near 0, we output 0, and if it is near (q−1)/2, we output 1, or we divide them by (q−1)/2 performed as a real number division and round them to 0 or 1 and the output will be the plaintext m; or in the second case, the legitimate user computes <br />D₂−D₁×S=(BE+te₂+m−(BA+te₁)S)=,teE+te₂−te₁S+m,</li><li id="ul0039-0002" num="0145">then modular t. This will be the plaintext m.</li></ul></li></ul></li></ul>

0146A, B, e_ican follow different error distributions.

0147With large n, the output can give us the right plaintext with as high probability as demanded. The reason we could decrypt with high probability comes from the following. <br />D₂−D₁×S=BE+e₂+m(q/2)−(BA+e)S<br />=B×(A×S+e)+e₂+m(q/2)−(BA+e₁)×S<br />=B×e+e₂−e₁×S+m(q/2)<br /> B×e+e₂−e₁×S can be viewed as a error terms, which is determined by the distribution of the following random variable. With proper choice of parameters, like in the case of KE or KD systems, the decryption process will surely return the right answer when n is large enough. The same argument goes with the second case.

0148One key point of this new method is that on average, we can do the encryption much faster in terms of per bit speed because we can use fast matrix multiplication [CW] to speed up the computation process.

0149We note here that since matrix multiplication is not commutative, when we multiply two elements, the order is very important, unlike the case of the RLWE related systems.

0150We can also use the same idea in the ring LWE (RLWE)[LPR] to do encryption, where all the elements are in the ring R_q, and we have <br />E=A×S+te,<br /> t is small positive integer and the entries of S is also small following error distribution κ_n_{<sup2>2</sup2>}. We encrypt a message as <br />(D₁,D₂)=(BA+te₁,BE+te₂+m).<br />Then we decrypt by computing<br />(BE+te₂+m−B(AS+te₁))(mod t).<br /> This works because <br />D₂−D₁×S=BE+te₂+m−(BA+t₁e₁)S<br />=B×(A×S+te)+te₂+m−(BA+te₁)×S<br />=tB×e+te₂−te₁×S+m<br /> Since the error terms are small, by modular t, we certainly should get back the original plaintext.

0151For the MLWE problem, we surely need to choose the distribution accordingly when we need to obtain the provable security of the system.

0152There are several versions of identity-based encryption systems based on lattice related problems including the LWE problem [ABB], [ABVVW], [BKPW]. But they all look rather complicated. We can use the MLWE to build an identity-based encryption system.

0153With a central server, we can build a simple identity-based encryption system as follows. <ul id="ul0040" list-style="none"><li id="ul0040-0001" num="0000"><ul id="ul0041" list-style="none"><li id="ul0041-0001" num="0154">(1) The central server will first select a secret n×n matrix S as the secret master key, where S is selected as a small element following certain error distribution κ_n_{<sup2>2 </sup2>}like error distributions like in KE and KD systems.</li><li id="ul0041-0002" num="0155">(2) The central server will also select a random element M following uniform distribution or similar distribution, but make sure that M has an inverse. If we could not find one first time, we will try again till we find one. We have a high probability of success to find such a M when q is large. Then the central serve will compute <br />M₁=MS+te,<ul id="ul0042" list-style="none"><li id="ul0042-0001" num="0156">where e is small following certain error distribution κ_n_{<sup2>2</sup2>}.</li></ul></li><li id="ul0041-0003" num="0157">(3) Then the central server will publicize M and M₁as the master public key.</li><li id="ul0041-0004" num="0158">(4) For each user, the central server will assign an public ID as A_i, where A_iis small following certain error distribution κ_n_{<sup2>2</sup2>}, and it can be generated from information that can identify the user.</li><li id="ul0041-0005" num="0159">(5) Each member is given a secret key: <br />S_i=SA_i+tM⁻¹e_i,<ul id="ul0043" list-style="none"><li id="ul0043-0001" num="0160">where e_i's entries are small following the error distribution n. Surely this is the same as given <br />MS_i=MSA_i+te_i,</li><li id="ul0043-0002" num="0161">since M is public.</li></ul></li><li id="ul0041-0006" num="0162">(6) Anyone can use the ID, namely A_i, and the master public key to build a new public key for the user with ID A_i, which is given as the pair (A_i, B_i), where <br />A_i=M<br />and<br />B_i=M₁A_i=MSA_i+teA_i,<ul id="ul0044" list-style="none"><li id="ul0044-0001" num="0163">and it is used as the public key to encrypt any message use the MLWE encryption system above. <br /> This gives an identity based encryption system. </li></ul></li></ul></li></ul>

0164S, A_i, e_i, e can also follow different error distributions.

0165Since A_iand e are small, we have A_i×e is also small. W also have that <br />MS_i−B_i=MS_i−B_i<br />=M(SA_i+tM⁻¹e_i)−MSA_i+teA_i<br />=MSA_i+tMM⁻¹e_i)−MSA_i+teA_i<br />=te_i−teA_i,<br /> Since e, A_iand e_iare small, e−A_ie_iis also small and te_i−tA_ie_iis also small. Therefore S_iis a solution to a MLWE problem with the pair (A_i, B_i) as the problem input. Therefore S_iis indeed a secret key that could be used for decryption. Therefore the construction works. We need to choose parameters properly to ensure security.

0166The key feature of our construction is that it is simple and straight forward. The provable security of the system is also straightforward.

0167we can extend this construction using the RLWE problem. We will choose the ring R to be F_q[x]/xⁿ+1. To ensure the provable security, we need to choose parameter properly n, q, properly, namely n=2^k, q=1 mod(2n)[LPR]. But we can select other parameters for secure applications.

0168This construction is directly based on the encryption systems of the RLWE[LPR], namely, we assume that we have a ring R with a properly defined learning with error problem on the ring R. The problem is defined as follows: we are given a pair (A, E), where <br />E=A×S+te′,<br /> A, S where e′ are elements in R_q, t is small integer, e′ is an error element following an error distribution X, S is a fixed element and A is select randomly following uniform distribution, and the problem is to find the secret S. We also know that one can build a public key encryption systems using the RLWE problem[LPR], where A, and E serve as the public key, and the secret S, which needs to be small, serves as the private key. We can use the fact that in a ring-LWE problem that the multiplication is commutative.

0169With a central server, we can build a simple identity-based encryption system as follows. <ul id="ul0045" list-style="none"><li id="ul0045-0001" num="0000"><ul id="ul0046" list-style="none"><li id="ul0046-0001" num="0170">(1) The central server will first select a secret S in R as the secret master key, where S is a selected small element follow certain error distributions χ.</li><li id="ul0046-0002" num="0171">(2) The central server will also select a random element M in R following uniform distribution and make sure that M has an inverse. If we could not find one first time, we will try again till we find one. We have a high probability of success to find such a M when q is large. Then the central serve will computer <br />M₁−MS−te,<ul id="ul0047" list-style="none"><li id="ul0047-0001" num="0172">where e is small and follows error distribution χ.</li></ul></li><li id="ul0046-0003" num="0173">(3) Then the central server will publicize M and M₁as the master public key.</li><li id="ul0046-0004" num="0174">(4) For each user, the central server will assign an public ID as A_i, where A, is a small element in R_q, and it follows error distribution χ.</li><li id="ul0046-0005" num="0175">(5) Each member is given a secret key: <br />S_i=SA_i+tM⁻¹e_i,<ul id="ul0048" list-style="none"><li id="ul0048-0001" num="0176">where e_ismall element in R, and it follow certain error distribution X. Surely this is the same as given <br />MS_i=MSA_i+te_i,</li><li id="ul0048-0002" num="0177">since M is public.</li></ul></li><li id="ul0046-0006" num="0178">(6) Anyone can use the ID, namely A_i, and the master public key to build a new public key for the user with ID A_i, which is given as the pair (A_i, B_i), where <br />A_i=M<br />and<br />B_i=A_iM₁=A_iMS+tA_ie=MSA_i+tA_ie,<ul id="ul0049" list-style="none"><li id="ul0049-0001" num="0179">and it is used as the public key to encrypt any message. <br /> This gives an identity based encryption system. </li></ul></li></ul></li></ul>

0180The small elements like S, A_i, e, e_ican follow different error distributions.

0181Since A_iand e are small elements in R, we have A_i×e is also small. We have that <br />S_iA_i−B_i=S_iM−B_i<br />=M(SA_i+iM⁻¹e_i)−MSA_i+A_ite<br />=MSA_i+tMM⁻¹e_i)−MSA_i+A_ite<br />=te−tA_ie_i,<br /> which is due to the fact that this is a commutative ring. Since e, A_iand e_iare small, e−A_ie_iis also small and te−tA_ie_iis also small. Therefore S_iis a solution to a ring LWE problem with the pair (A_i, B_i) as the problem input. Therefore S_iis indeed a secret key that could be used for decryption.

0182We can build easily a hierarchical IBE system using similar procedure, where each user can server as a central server.

0183The key feature of our construction is that it is simple, straight forward and efficient. The provable security of the system is also straightforward.

0184In the all the systems above using pairing with errors over the ring, one may use polynomials in the form of <br />f(x)=Πf_i(x)+g(x),<br /> where each f_i, g(x) is a extremely sparse matrix with very few terms, for example, 2 or 3 terms none-zero. Using this kind of polynomial can speed up the encryption and decryption computations.

LITERATURE CITED

0000<ul id="ul0050" list-style="none"><li id="ul0050-0001" num="0185">[ABB] S. Agrawal, D. Boneh, X. Boyen: Efficient Lattice (H)IBE in the Standard Model. In proceedings of Eurocrypt 2010, Lecture Notes in Computer Science, Volume 6110, pp. 553-572, 2010.</li><li id="ul0050-0002" num="0186">[ABVVW] S. Agrawal, X. Boyen, V. Vaikuntanathan, P. Voulgaris, H. Wee: Fuzzy Identity Based Encryption from Lattices. IACR Cryptology ePrint Archive 2011: 414 (2011)</li><li id="ul0050-0003" num="0187">[ACPS] B. Applebaum, D. Cash, C. Peikert, A. Sahai; Fast Cryptographic Primitives and Circular-Secure Encryption Based on Hard Learning Problems. Advances in Cryptology-CRYPTO 2009, Lecture Notes in Computer Science, Volume 5677 pp 595-618, 2009</li><li id="ul0050-0004" num="0188">[BKPW] M. Bellare, E. Kiltz, C. Peikert, B. Waters: Identity-Based (Lossy) Trapdoor Functions and Applications. In Proceedings of EUROCRYPT 2012, Lecture Notes in Computer Science, Volume 7237, pp 228-245 2012.</li><li id="ul0050-0005" num="0189">[BSHKVY] C. Blundo, A. De Santis, A. Herzberg, S. Kutten, U. Vaccaro, M. Yung: Perfectly-Secure Key Distribution for Dynamic Conferences. in Advances in Cryptology Crypto 92, Lecture Notes in Computer Science, Volume 740, pp 471-486, 1993</li><li id="ul0050-0006" num="0190">[BKW] A. Blum, A. Kalai, and H. Wasserman. Noise-tolerant learning, the parity problem, and the statistical query model. Journal of the ACM, 50(4), pp 506-19, 2003.</li><li id="ul0050-0007" num="0191">[COP] D. Coppersmith, Shmuel Winograd, Matrix multiplication via arithmetic progressions, Journal of Symbolic Computation—Special issue on computational algebraic complexity archive 9 (3), pp 251-280, 1990</li><li id="ul0050-0008" num="0192">[DiHe] W. Diffie, M. Hellman, New directions in cryptography, IEEE Transactions on Information Theory 22 (6), pp 644-54, 1976.</li><li id="ul0050-0009" num="0193">[DiLi] J. Ding, X. Lin, A Simple Provably Secure Key Exchange Scheme Based on the Learning with Errors Problem, Cryptology ePrint Archive, Report 688, 2012</li><li id="ul0050-0010" num="0194">[LNV] K. Lauter, M. Naehrig, V. Vaikuntanathan, Can Homomorphic Encryption be Practical?, Cryptology ePrint Archive, Report 2011/405, 2011, http://eprint.iacr.org,</li><li id="ul0050-0011" num="0195">[LPR] V. Lyubashevsky, C. Peikert, O. Regev, On ideal lattices and learning with errors over rings In Eurocrypt 2010</li><li id="ul0050-0012" num="0196">[REG] O. Regev, On lattices, learning with errors, random linear codes, and cryptography, in Proceedings of the 37th Annual ACM Symposium on Theory of Computing STOC05, ACM, pp 84-93, 2005</li><li id="ul0050-0013" num="0197">[SHA] A. Shamir, Identity-based cryptosystems and signature schemes, in Advances in CryptologyCrypto '84, Lecture Notes in Computer Science, Vol. 196, Springer-Verlag, pp. 47-53, 1984</li><li id="ul0050-0014" num="0198">[SHO] P. Shor, Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer, SIAM Journal of Computing 26, pp. 1484-1509, 1997.</li><li id="ul0050-0015" num="0199">[STR] V. Strassen, Gaussian Elimination is not Optimal, Numer. Math. 13, p. 354-356, 1969</li></ul>