The scheme is designed in the framework of LWE (Learning with Errors) based schemes and its security depends on the stiffness of the LWE problem. The average case stiffness of the LWE problem can be reduced to the worst case stiffness of the lattice problem mentioned above.
Fully Homomorphic Encryption
An encryption scheme that can evaluate circuits of arbitrary complexity is said to be fully homomorphic. Using these techniques, a (flattened) fully homomorphic encryption scheme can be obtained from a somewhat homomorphic one without bootstrapping (a leveled FHE scheme can evaluate circuits of 'fixed' arbitrary complexity).
Hidden Subspace Membership
Outline of the Thesis
Notations
For a polynomial ring R and an ideal I, R≤r and I≤r denote the set of polynomials in R and I of highest degree r respectively for some r ∈ N. An example of a group is the set of integers together with the operation of addition indicated as (Z,+).
Multivariate Polynomials over Finite Fields
Grade reverse lexicographic ordering [CLO92]). and the rightmost nonzero entry of the vector α−β ∈Zn is negative. With respect to a monomial ordering, the leading monomial and leading term of a polynomial can be defined as follows.
Tensors
Lattices
Computational Problems based on Lattices
Given a basis B of an n-dimensional lattice L and a positive integer d, the GapSVPγ problem is to distinguish between the cases λ1(L(B))< d and λ1(L(B))> γ( n)·d . Another computational lattice problem that is a close variant of the shortest vector problem is the Shortest Independent Vectors Problem (SIVP) and its approximation variant can be defined as follows:
Statistical Distributions and Gaussian Measures
Discrete Gaussians
The normal distribution with mean 0 and variance σ2 is the distribution on R given by the density function σ√12πexp(−x2σ22). The sum of two normal variables with mean 0 and variancesσ12 andσ22 is a normal variable with mean 0 and variance σ12+σ22.
Cryptographic Encryption Schemes
The key generation algorithm, PK.Keygen, takes the security parameter λ and outputs a public encryption key pk and a secret decryption key sk, i.e. (pk, sk) ← PK.Keygen(1λ) (In the case of a symmetric key scheme , the algorithm SK.KeyGen(1λ) performs a single secret key sk). The encryption algorithm takes a message m and the public key pk and performs a ciphertext c ← PK.Enc(m, pk) (The algorithm SK.Enc(m, sk) performs an encryption of a message m out using the key sk).
Security
In this thesis, similar to other grid-based cryptographic algorithms, we mainly deal with IND-CPA security. The IND-CPA security of a public key encryption scheme can be formally defined in terms of the game shown in Figure 2.1. The Challenger uniformly randomly selects a bitβ ∈ {0,1} and performs the encryption of mβ given by PK.Enc(mβ, pk).
Opponent A wins the game if he can guess the value of β with a non-negligible advantage. The IND-CPA security of a symmetric encryption scheme can be defined similarly, except that in a public-key encryption scheme, an adversary can encrypt messages himself using the public encryption key, but in the case of a symmetric-key scheme, he has no way to see the ciphertexts.
Homomorphic Encryption
The IND-CPA security of a (public key) homomorphic encryption scheme is similar to that of any other encryption scheme, except that the adversary has access to both the public encryption key and the public evaluation key. In the case of a symmetric key homomorphic scheme, the adversary has access to the public evaluation key). The correctness of a homomorphic encryption scheme depends on the correct decryption of an evaluated ciphertext and can be defined as follows. A homomorphic encryption scheme is said to be compact if there exists a fixed polynomial bound b = b(λ) such that the size of the ciphertext output from HE.Eval is at most b bits, independent of the function φ.
If Φ denotes the set of all efficiently computable functions, then an encryption scheme is called completely homomorphic if it is compact and homomorphic for the set of functions Φ. A homomorphic encryption scheme is called offset fully homomorphic if it takes an additional input L ∈ N and compactly evaluates all functions of depth at most L such that the length of ciphertexts is bounded by b(λ), independent of L.
Learning with Errors
Hardness of LWE
Further, [Pei09] and [BLP+13] gave classical LWE reductions from the worst case GapSVPγ for an exponential modulus and a polynomial modulus, respectively. The robustness of LWE can be summarized in terms of the following theorem derived from the works of [Reg09, Pei09, BLP+13]. Then, there exists an efficiently bounded sampling distribution X such that if there is an efficient algorithm that solves the average case problem DLWEn,q,X, then.
Summary
The Basic Encryption Scheme
We describe the basic encryption scheme in terms of the following algorithms. The homomorphic operations are described separately in Section 3.1.3.) The. Construct a basis of (SI≤r)⊥ (as given in Equation 3.1) which can be written in terms of the matrix S I`−n. The decryption process involves calculating the inner product of the ciphertext with each column of the matrix Sdec and reducing it modulo q.
For each of these products, the decryption function outputs 0 for the corresponding input if the size of the inner product is < q/4, and 1 otherwise.
Security
Note that the distribution on ((v,−v·R−11 ST) +e) is similar to that discussed in Lemma 3.1.3 (for the case h= 1), except that the distribution on Sˆ is random in Z (`− n)×nq (while here the SR−T1 distribution is restricted to full-row rank matrices in Z(`−n)×nq. Thus, if there is an algorithm that can efficiently distinguish between the distribution (( v,−v·R− 11 ST)+e) = (y·Senc+e)R0 from the uniform distribution on Z`q for a non-negligible fraction of choices S and R1 can also distinguish the distribution on ( A,B) in lemma 3.1.3 from the uniform distribution for a non-negligible part of Sˆ (here non-negligible means O(n1c) . for some constant c). The above arguments prove that the probability of differentiating the distribution cm(R00)−1 from that c0(R00)−1 for any efficient algorithm is negligible under the LWE assumption (probability is assumed depending on the choices of S and R1 and the randomness involved in the encryption process).
Now, for an algorithm ˆW, let pWˆ(m) denote the probability that ˆW returns 1 when the input is sampled from the distribution on the encryptions of m. In other words, no efficient algorithm exists that can distinguish the distribution on the encryptions of.
Homomorphic Properties
For example, if n= 2 and `= 4, then the frontal slices of T for 1≤i≤` can be represented by the following matrices. The above linear map from I≤2r to I≤r naturally gives rise to the following linear map L from the evaluations of polynomials in I≤2r at (z1, . . . ,zt) to the evaluations of polynomials in I≤r at (z1 , . . . ,z`). Now, when c00mult is multiplied by the matrixQ (considering the elements of Q as inQ), we get the following vector ˜cmult.
The sequence of steps transforming the pair c1,c2 to ˜cmultR forms a bilinear map from Q` × Q` to Q`. This map, denoted by BM, can be represented by a 3-way tensor M where Mis given by.
Security with Multiplicative Homomorphism
Note that if the values are zero, the multiplication process maps two elements of SI≤r to another element of SI≤r (as vectors in Z`q). This fact could potentially be used to extract the secret key from the evaluation key. Although, to the best of the authors' knowledge, no efficient algorithms exist to extract such subspaces for everyone.
Noise in Multiplication
Now, instead of multiplying the cis by the Dis, if we multiply the PowersOfTwoq,u(ci)s by the respective Dfis, the corresponding Ki,js is given as. Then, givenc1enc2, cmult can be calculated by the corresponding bilinear map BM:Q`(u+dlogqe)×Q`(u+dlogqe) →Q` as.
Bootstrapping
Parameters and Performance
Private key to Public key Conversion
The security of the scheme follows from the security of the private key scheme and claim 5.3 of [Reg09] (a special case of the residual hash lemma). Then, for a uniform choice of S, given a hash function hA : {0,1}d→Z`qdefined ashA(x) =xAT mod q whereA(:, j) =gj for1≤j ≤d, the expectation of the statistical distance of the distribution of xAT against q from uniform has an upper limit forqq`/2d. We claim that for 0 ≤i≤d no efficient algorithm exists that can distinguish between vectors sampled from a uniform distribution on Di and vectors sampled from a uniform distribution on Z`q.
For a set S and an algorithm W, let pW(S) be the probability that W returns 1 when the input is sampled from a uniform distribution in S. Thus, if (pW(D0k)−pW(Z`q)) is non-negligible, then the W algorithm can be used to distinguish between vectors that are sampled from the uniform distribution on bk+1 encryptions (under the private key scheme) and vectors that are sampled from.
Summary
With the proposed multiplication technique, the size of the ciphertext does not increase after multiplication. To reduce the size of the ciphertext after multiplication, the relinearization process [BV14a] is used. In these schemes, the secret key and ciphertext are vectors of size n and n+ 1 respectively.
It scales down the ciphertext after each multiplication so that the associated noise is reduced by the same factor. It consists in choosing a decreasing module chain and after each multiplication the ciphertext is changed with respect to a module q1 to a smaller module q2 in the chain.
Regev’s Cryptosystem
The Proposed Multiplication Technique
Security
As discussed in Section 3.1.4 of Chapter 3, the multiplication operation defines an "almost" bilinear map from Zn+1q ×Zn+1q to Zn+1q (rounding operations introduce some non-linearity). In the absence of theis noiseless encryptions 0 form an invariant subspace of this map. We could create invariant subspaces of the multiplication process by randomly choosing a vector and repeatedly "multiplying" the vector by itself using evaluation.
Although this process has not been shown to converge in polynomial time, it presents a potential vulnerability.
Correctness of Multiplication and Noise Analysis
As a result, when two vectors in (s0)⊥ are multiplied, the result is no longer in (s0)⊥. Thus, immutability is lost. of s0 with cis in step 1 of the multiplication procedure. Values of |K1|,|K2| are bounded by a norm of s0 (s0 is seen as a full vector for the calculation of a norm). Alternatively, we can use the modified version of the vector decomposition technique described in Chapter 3.
We limit the choice of is to vectors with positive entries of the form Puj=1 1. These are of the form mijq2k + ˜ei + qK˜i and the size of these terms is O(nq(u+logq)).
Parameters and Performance
Summary
Then, for a noise distribution N, HSM`,n,q,Y,N can be defined in terms of the game shown in Figure 5.1. Clearly, LWEn,q,X is a specific case of the HSM problem, namely HSMn+1,n,q,Y,N where N = (0n,X) and Y is the distribution of subspaces of the form ( - s,1)⊥ where s is randomly selected from a uniform distribution over Znq. We start by considering Lemma 6.2 of [PW11], which proves the hardness of a special case of the HSM problem.
Since Hj does not differ from Lj and Lj does not differ from the uniform distribution, both terms on the right-hand side of the above inequality are negligible. Let NR,X be a distribution of vectors of the form (vR,v), where v is sampled from the distribution X`−n. Therefore, the possibility of making a RLWE version of the proposed scheme can be considered.
Although the RLWE variants perform better than their LWE counterparts, the hardness of the RLWE problem is based on the hardness of the superideal grids of the shortest vector problem.
