Enhancing Goldreich, Goldwasser and Halevi’s scheme with intersecting lattices

Our contribution and paper organization

The initial practical schemes of GGH have been broken mostly because of the very specific structure of the keys used. The main idea developed in this paper is to intersect the public key with a random lattice of the same rank to hide the previously exploited specific structure. However, we also show that improving security using intersections is not as simple as just intersecting any key to any random lattice, and therefore we present specific choice of keys based on intersection properties.

The rest of the paper is organized as follows. We first review the basics of lattice theory and discuss the initial GGH scheme in Section 2. Then, in Section 3, we present our idea to enhance its security and show that this extra layer of security does not affect our capacity to encrypt or decrypt messages. We also explain how we compute keys in practice as a lot of properties arise from intersecting lattices, which can further be exploited to either enforce or weaken the security of the resulting system, and more importantly, we demonstrate how it hides the initial “weak” structure. We give a short comparison of efficiency and key sizes compared to other schemes. In Section 4, we discuss potential security concerns given by the stated properties. Finally, in Section 5, we discuss further applications of intersecting lattices.

2.1 Lattice theory

In this work, we only consider full-rank integer lattices, i.e., such that their basis can be represented by an n×n non-singular integer matrix.

The literature sometimes call det⁡(ℒ) the volume of ℒ (see [53]).

The HNF can be computed from any basis in polynomial time [36], is unique [15], and has a very compressed form, and thus is an ideal form for public keys [50]. We denote HNF⁡(M) the HNF of a matrix M. One of the easiest forms to work with when the HNF is computed is when we obtain a “perfect” HNF.

For consistency with the rest of the paper, we assume Idn is a perfect form HNF.

According to Nguyen and Shparlinski [57], the set of co-cyclic lattices represents 85 % of full-rank integer lattices. Note that if HNF⁡(ℒ) has perfect or pseudo-perfect form, then ℒ is co-cyclic.

Thus, if ℒ3=ℒ1∩ℒ2, then ℒ3 is a sublattice to both ℒ1 and ℒ2.

We note that the definition is a bit different to the one which can be found in fundamental mathematics books [11]. The other definition requires the sum of norms of non-diagonal entries in a row to be lower or equal to the norm of its diagonal entry in that same row (or line, depending how you consider the vectors). Here the definition of “low” is arbitrary, but the overall idea is the same. In our following experimentations, we will restrict ourselves to d=⌈n⌉, where n is the dimension, and μ=1.

We also define the “root lattice gap”, i.e., elevated to the power 1n, where n is the dimension of the lattice.

2.2 Lattice problems

The most famous problems on lattices are the shortest vector problem (SVP) and the closest vector problem (CVP). We tend to approximately solve CVP by solving heuristically SVP in an expanded lattice [27].

In cryptography, we rely on the “easier” versions of those problems.

Since λ1⁢(ℒ) is also hard to determine (it is indeed another lattice problem we do not state here), measuring the efficiency of an algorithm is another challenge by itself. Therefore, to measure algorithm efficiency, we must be able to define a problem with easily computable parameters, which is where the Hermite factor is originated from.

Some cryptosystems are based on worst-case hardness on uSVP with polynomial gap, such as [2, 66]. The practical hardness of uSVP depends on its gap compared to a fraction of the Hermite factor, where the constant in front of the factor depends on the lattice and the algorithm used [24]. There exists an attack that was specifically built to exploit high gaps [44].

It has been proved that BDD1/(2⁢γ) reduces to uSVPγ in polynomial time, and the same goes for uSVPγ to BDD1/γ when γ is polynomially bounded by n [48]; in cryptography, the gap is polynomial, so the target point x must be polynomially bounded, and therefore solving one or the other is relatively the same in our case.

2.3 The GGH cryptosystem

GGH is a public key cryptosystem named after its creators (Goldreich, Goldwasser and Halevi). Like every public key encryption scheme, GGH is composed of three algorithms, namely, a key generator, an encryption algorithm, and a decryption algorithm.

1. KeyGen⁡(n). Take a “good” basis Sk of a lattice ℒ of dimension n; compute a “bad” basis Pk from ℒ⁢(Sk); provide Pk as the public key, and keep Sk as the secret key.

2. Encrypt⁡(Pk,m). Use Pk to encrypt a message m, which is a “small” vector, less than half the size of the smallest vector of Sk, by adding a random vector v of ℒ; output c=m+v.

3. Decrypt⁡(Sk,c). Use Sk to decrypt a message, solving the BDD instance of c on ℒ⁢(Pk), thus separating m from v and thus recovering m.

To be able to decrypt m, it has to be relatively short, say, ∥m∥⪅γ, thus solving special instances of BDDγ. For this cryptosystem to be relevant, it must rely on three important points.

1. It is easy to encrypt a message with a public key (i.e., generate c given (Pk,m)).

2. It is easy to decrypt a message with a secret key (i.e., solve BDDγ with Sk).

3. It is hard to recover the secret key/original message from the public key.

The first point is pretty straightforward, and the second is guaranteed only by a proper key generation, which is where the concepts of “good basis” and “bad basis” are originated from. Sk is typically a diagonal dominant matrix and Pk its Hermite normal form. Because v is generated from Pk and ℒ⁢(Pk)=ℒ⁢(Sk), we can then recover v from c and thus m by solving BDDγ with the “good” basis Sk (typically composed of short and nearly orthogonal vectors). The problem stems from the third point.

2.4 Attacks on classical GGH

2.4.2 Special key recovery attack on diagonal dominant keys

For diagonally dominant keys of the form Sk=D+R, where D=d×Id, it is easier to attack the basis structure rather than the message itself.

Solving BDDγ for vectors

(d,0,…,0),(0,d,0,…,0),…,(0,…,0,d) in ℒ⁢(d×Id+R)=ℒ⁢(Sk)=ℒ⁢(Pk)

to recover R yields very short vectors R⁢[1],…,R⁢[n] and thus recovers the secret key: the difference between the i-th vector of the matrix d×Id and ℒ⁢(d×Id+R) is exactly the i-th vector of R, which holds small values within [-μ,μ] and is much shorter than a message. We will denote ϕ the BDDγ solving algorithm. It is not an oracle, but rather an algorithm that anybody could choose to solve the problem. Our suggestion for ϕ would be to use Kannan’s embedding technique [35], which transforms the BDD instance into a uSVPγ instance, and then apply lattice reduction techniques on the extended basis, using Klein’s algorithm [40] or more recent works such as Liu and Nguyen enumeration-based solver [43].

Algorithm 1 (Diagonal dominant key recovery attack.).

Note that on the above algorithm, each iteration on a position of the diagonal makes the next iteration easier: since ℒ⁢(Pk)=ℒ⁢(Sk), each short vector found of Sk decreases the complexity of ϕ. In fact, like most lattice-based cryptosystems, finding one shortest vector is enough to break GGH.

3.1 Modification of GGH using an intersecting lattice

If we denote Pk the public key and Sk our private key, our modification is to go from ℒ⁢(Pk)=ℒ⁢(Sk) to ℒ⁢(Pk)=ℒ⁢(Sk)∩ℒ⁢(R), where R is a random non-singular integer matrix of dimension n. The modified GGH scheme, informally, is the following:

1. KeyGen2⁡(n). Take a “good” basis Sk=(D×Idn)+([-μ,μ]n×n) of dimension n; compute the HNF basis Pk of ℒ⁢(Sk)∩ℒ⁢(R), where R is a random integral matrix of dimension n with a perfect HNF with a determinant co-prime to Sk; provide Pk as the public key, and keep Sk as the secret key.

2. Encrypt2⁡(Pk,m). Use Pk to encrypt a message m encoded in a small vector by adding a random vector v of ℒ⁢(Pk); output c=m+v.

3. Decrypt2⁡(Sk,c). Use Sk to decrypt a message the same way as in a classical GGH, separating m from v by solving the corresponding BDD instance and thus recovering m.

The secret key in our experiments used a diagonal coefficient D=n and a low noise of random values in μ=1, and our security analysis will be based on those parameters. However, we do not see a problem in taking noise within μ=4 as in the original GGH proposal [27] or as it was the case when Micciancio applied the use of a HNF [50]. Following the work in [50, 27], we can also choose our messages such that ∥m∥2≤12min∥si*∥2, where si* is the i-th vector of the orthogonalized basis obtained from the secret key using the Gram–Schmidt orthogonalization process, or simply encode it as a vector in [1-μ,μ-1]n. However, the message space we actually use in this paper will be different as we resort to a padding technique to attempt to reach IND-CCA security. The decryption works as v∈ℒ⁢(Pk)⊂ℒ⁢(Sk), thus separating m from v as before. We will discuss security concerns related to this scheme in the next section (and the appendix), especially why det⁡(R) has to be co-prime to Sk and has to have a perfect HNF. In particular, we will show that structural attacks are no longer effective when R is sufficiently large. Then ℒ⁢(Pk) no longer admits a diagonally dominant basis D+R; therefore, the BDDγ key recovery attack on (d,0,…,0),(0,d,0,…,0),…⁢(0,…,0,d) is no longer applicable. Nevertheless, the ratio between the size of the messages we can decrypt and the size of the public key will decrease. We will explicitly express the factor later. The question is now whether we solve the problem with the previous third point “it is hard to recover the secret key from the public key” in our modified scheme.

3.2 Modified attack on the intersected GGH key

As stated earlier, the structural key recovery attack using BDDγ on (d,0,…,0),(0,d,0,…,0),…,(0,…,0,d) in ℒ⁢(Pk) does not work since ℒ⁢(d×Id+R)≠ℒ⁢(Pk), but ℒ⁢(d×Id+R)=ℒ⁢(Sk)⊂ℒ⁢(Pk). Adapting this attack to ℒ⁢(Pk) requires finding ℒ⁢(Sk) in ℒ⁢(Pk), and then using the structural key recovery attack. We assume the existence of a function Δ which finds the “optimal” overlattice ℒ⁢(Sk) given ℒ⁢(Pk) (the overlattice that admits a diagonal basis; experimental data suggests it is indeed the “weakest” overlattice; see the next section).

Algorithm 2 (Modified diagonal dominant key recovery attack.).

To the best of our knowledge, the difficulty of recovering ℒ⁢(Sk) in ℒ⁢(Pk) is mostly dependent on the values of det⁡(Pk) and det⁡(Sk). The efficiency of the modified attack is dependent on the efficiency of the overlattice recovery function Δ.

In this case, we will consider Pk and R to have a perfect HNF and Sk to be able to be reduced to a perfect HNF as we believe it offers the best security assumptions. As a bonus, it also allows a fair comparison with random matrices as randomly selected matrices from an increasingly big random determinant tend to have a perfect HNF [29]. Experimental results also suggest that most lattices are “equivalent” to a lattice admitting a perfect HNF, whose easily computable “equivalency” relation might cover most of co-cyclic lattices (see Appendix A.2) and allow us to use Gama’s work on their structural worst-case to average-case reduction [23]. We state the following theorem, which partly solve the problem of requiring perfect HNFs for intersections.

The proof of this theorem can be found in Appendix A.1. If we intersect two lattices whose HNF bases are not perfect or whose determinant are not co-prime, the result will not be perfect, and common factors might appear (see Appendix A.1).

In our case, considering C=Pk, A=Sk and B=R, we have to avoid ℒ⁢(Sk) to be easily recovered. Theorem 2 is also interesting for an attacker as it reveals one of the main issues of our approach, which we discuss in the next subsection. Let ω⁢(M) be the number of prime factors counted without multiplicity in the decomposition of det⁡(M). Then

which means ω⁢(C)=ω⁢(A)+ω⁢(B) and very easily leads to the following property.

Therefore, recovering ℒ⁢(A) from ℒ⁢(C), i.e., the complexity of the overlattice distinguisher Δ, is assumed to be at least polynomially equivalent to distinguishing pi from qi in equation (3.1). As we work in post-quantum cryptography, we assume that the factorization problem can be solved in polynomial time [70]. As we explain later, we will purposely choose keys with very smooth determinants, which make factorization easy even in the non-quantum case.

As ω⁢(C) is lower-bounded by ω⁢(A) and has no upper bound limit (as we have complete control over det⁡(B)), one might first think that the number of combinations to search is 2ω⁢(C). However, if we assume an oracle that knows what type of lattice to search for, then it is unsafe to assume the attacker has no knowledge of ω⁢(A). We then assume an attacker has possession of exactly ω⁢(A) and ω⁢(B); the number of combinations^[1] he has to try is then (ω⁢(C)ω⁢(A))=(ω⁢(C)ω⁢(B)). In practice, the attacker will probably only have an approximation, which increases the number of combinations by quite a lot and is a much bigger number depending on how precise the approximation is, but for simplicity, we assume he has the exact value.

Hence, if ω⁢(C) is small or if ω⁢(A) or ω⁢(B) is too small relative to the number of possibilities, it might be too easy to recover ℒ⁢(A), which would nullify the point of our modification. In practice, if we let the scheme untouched as it is, then ω⁢(A) will most often be very low, as illustrated by the following theorem.

Experimental data on low dimensions suggest that ω⁢(Pk) is indeed too low to ensure a reasonable number of combinations. To deal with that problem, we first optimistically assume that, without the knowledge of det⁡(Sk), an attacker will have no choice rather than trying every possible combination stated by Property 1. Our proposed solution to this apparent weakness is to ensure the number of combinations is sufficiently large to make sure it is not feasible to recover ℒ⁢(Sk). Therefore, our target public key should have the form

where ω⁢(Sk)+ω⁢(R)=ω⁢(Pk) is large enough to allow a large number of combinations. To achieve this, we must generate Sk and R such that HNF⁡(Sk) and R have the same form as Pk (Theorem 2) while controlling ω⁢(Sk) and ω⁢(R).

3.3 Countermeasure by controlling ω⁢(Sk),ω⁢(R) on key generation

From the last subsection, two properties must arise from our keys if we want our modification to be effective: one is the perfectness of our HNF basis; the other the smoothness of our keys’ determinants.

First of all, we begin by showing the generation algorithm of the random matrix R. We first choose the determinant det⁡(R) we want to obtain, and create

such that R⁢[i,1] are random integer values in [0,det⁡(R)-1] for all i∈[2,n].

With the knowledge of how to generate R, one simple way to maximize ω⁢(Pk), and thus the number of possibilities, is to increase ω⁢(R) until we reach the number of required combinations without caring about ω⁢(Sk). However, this is not wise; we mentioned before that the ratio of message size over size of the public key is lower in our modified GGH than in the original GGH. As, in both schemes, we use the same private key, the size of the message m we decrypt remains unchanged. Let Pkorg be the public key of the original GGH scheme (i.e., HNF⁡(Sk)). Note that Size⁡(Pk)≈Size⁡(HNF⁡(Sk))+Size⁡(R)=Size⁡(Pkorg)+Size⁡(R)≈Size⁡(Pkorg)+n⁢log⁡(det⁡(R)). Let c be the factor determining the ratio decrease. Then we have

Therefore, compared to the original GGH, the size increase of the public key is solely determined by det⁡(R). Thus, for the benefit of key size, we choose to have ω⁢(R)<ω⁢(Sk). We will discuss later what this implies at the end of this subsection.

We know have to generate Sk. It is a bit harder to obtain a perfect HNF of a diagonal dominant matrix with a chosen determinant det⁡(Sk). Our targeted end result is

such that HNF⁡(Sk)⁢[i,1] are integer values in [0,det⁡(Sk)-1] for all i∈[2,n] and det⁡(Sk)=∏i=1ω⁢(Sk)pi and gcd⁡(pi,pj)=1 for all i≠j.

In the following, we will illustrate and then explain the way to achieve this. Let Dd be a diagonal dominant matrix of dimension n-1 with diagonal coefficient d whose HNF is perfect, and let c be a column of n-1 entries within [-μ,μ], where μ is also the bound of the noise of Dd. We concatenate c on the left of Dd and compute the HNF of the result to obtain

If a=Dd′⁢[1,1] and b=Dd′⁢[1,2] are not co-prime, we retry with a different column c until those two values are co-primes. Once they are co-prime, we compute u,v such that |u⁢a-b⁢v|=det⁡(Sk), ensuring det⁡(Sk) is co-prime with either a or b (for simplicity, we assume b is co-prime with u; the algorithm in Appendix A.3 provides a more general form), such that

We create a line l of n entries with l⁢[1]=v and l⁢[2]=u, reduce l with Babai’s nearest plane algorithm and concatenate the result l′ to c and Dd as shown below to obtain Sk as we wanted, which is still a diagonal dominant matrix relatively close of parameters d and μ and possess a perfect Hermite normal form.

The Hermite normal form of Sk is perfect since

and because we ensured a and b co-prime, |u⁢a-b⁢v|=det⁡(Sk) and u and b co-primes,

Now that we know how to create Sk and R with chosen determinants, we must decide how to choose det⁡(Sk) and det⁡(R) to obtain secure values of ω⁢(Sk) and ω⁢(Pk). This is how we suggest to do it and use in most experimentations. We first generate Dd as we see fit (the same matrix used when generating Sk), and we fix a prime we call a “scaling factor” that must be prime to det⁡(Dd), then enumerate all primes from a certain point (at least strictly greater than the “scaling factor”) and choose to pick them randomly until their product is bigger than Dd (and prime to det⁡(Dd)). We denote that set of primes Sp. We then take as much factors of Sp as we see fit to construct det⁡(R), keep the rest and multiply the remaining product by a power of the scaling factor to respect the bound given by equation (3.2). Suppose that the scaling factor is given away for free; the number of combinations an attacker has to search is indeed (|Sp|ω⁢(R)). Note that, given Sp, the maximum number of combinations is achievable if ω⁢(R)=|Sp|2.

Overall, the generation of keys is done in polynomial time; the computations of the HNF and Babai’s nearest plane algorithm are the most time consuming operations, and they both run in polynomial time. To study the complexity and how this can be generated in practice, we refer the readers to Appendix A.3.

We present in this table the minimum ratio ω⁢(R)/ω⁢(Pk) required to go over some 2λ combinations in total using the algorithm we just described, and to ensure ω⁢R<ω⁢Sk, we use a scaling factor of 2, enumerating and choosing all primes from 3 until the product Sp is bigger than det⁡(Dd)⁢d, assuming a diagonal coefficient of d=n, where n is the dimension, and getting an average determinant of nn/2 for Sk. When Sp is not sufficiently large, then we put the symbol “—”.

However, if we start enumerating from 2741, which is the 400th prime, and then its successive primes, we have the following table.

We put a blank entry at λ=160 for dimension n=800, but we are actually very close with

If we want to enforce ω⁢(R)<ω⁢(Sk) while using the same algorithm, we only need to increase d to a bigger value, increasing det⁡(Sk) and thus ω⁢(Pk). The next table shows the minimum amount of primes to put in Sp, which means the minimum value of ω⁢(Pk) (+1 if we count the scaling factor) to achieve a number of combinations strictly superior to 2λ.

As a “rule of thumb”, to achieve a number of combinations of 2λ, we require |Sp|=ω⁢(Pk)+1>λ+4 for λ∈[1,250]. We can deduce that, in practice, the number of combinations will always be as high as we need it to be, either by increasing the diagonal coefficient d of our secret key Sk or by adding factors to R. Therefore, security concerns do not lie in the number of combinations (ℒ⁢(Sk),ℒ⁢(R)) any longer.

3.4 Key size comparisons and perfect HNFs

First of all, we would like to stress that this comparison only aims to show that our obfuscation technique applied to GGH is not impractical as far as storage is concerned. LWE-based cryptosystems usually rely on stronger security assumptions than our proposal, and other cryptosystems, like NTRU, have been studied for a much longer time; the lack of literature on lattice intersections does not let us claim the same level of confidence in security assumptions. Here we compare in Table 1 our public key sizes to the public key sizes (in bits) presented in Lindner and Peikert’s work for LWE-based encryption [42] and the key sizes we obtain with intersections (in average). We only compare with the size of their keys per user, and not their full key which is already much bigger. Note that, unlike q-ary lattices, the values of the determinant are not set at the key generation, but usually do not stray away from each other by too much bits. To compute the key size of a perfect HNF, one just has to look at the number of bits of the determinant and multiply it by the lattice dimension. For dimension n, we use n as the diagonal coefficient and [-1,1] as the noise interval.

As we see, their partial public key is only smaller than our full public keys for higher dimensions. Furthermore, the technique used in their scheme is a very clever way to delegate part of the key to a trusted source or to the user that is an instance from an abstract system presented by Micciancio [51], while our scheme has mostly kept the basic setup from the GGH cryptosystem [27]. It might be possible that, in the future, such techniques become available for classical random lattices (and most of them admitting a perfect HNF), leading to better key sizes per user for higher dimensions.

Perfect Hermite normal forms also allow us to improve the encryption scheme. Instead of sending a vector c=m+v, where v∈ℒ is random, we can choose v such as v=(c1,0,…,0), i.e., only a single integer of size det⁡(ℒ) in average will be sent. This is done by reducing the message m by a Gaussian elimination with the rows of the public key, where they all have 1 in their diagonal. Furthermore, the security is not affected. Since the transformation will give the same result as m for any m′=m+v′ with any v′∈ℒ, breaking this transformation will break all schemes which use BDDγ as a security assumption. The decryption is left unchanged since the only difference is that c=m+v′, where v′∈ℒ is not random anymore. This is actually convenient from a practical point of view, where encryption can be reduced to n additions and n-1 multiplications (by relatively low integers on one side and big ones on the other side) modulo the determinant; this is comparable to a modular knapsack. Lindner and Peikert also presented in their paper their different ciphertext size for messages of 128 bits. The smallest ciphertext size they presented was for n=128 and q=2053, and it has the same size of our average determinant size (hence, in our case, ciphertext size) for a lattice of dimension n=475 and combinations security s=100.

Generating public keys, however, is slow as it involves computing Hermite normal forms. On the other hand, Gaussian sampling, which is required for a lot of LWE-based cryptosystems, was also far from fast and memory efficient and led to alternatives like LWR [9] or uniform distribution [45]. Weiden et al. reported that Gaussian sampling takes 50 % on the running time of their implementation of Lyubashevsky’s signature scheme [46], and Dwarakanath and Galbraith [17] reported that Peikert’s sampler can take up to 12 MB for some parameters [61]. Nevertheless, the research is still very active on that matter and has seen various improvements [17, 12, 16] mostly targeted at lattice-based cryptography thanks to the popularity of that matter in the community but not to a point where sampling is both very fast and memory efficient. On the other hand, research to compute Hermite normal forms nowadays is mostly done for random matrices [63, 60] and not targeted at structured matrices, especially ones that arise in cryptography. A rebound of interest towards Hermite normal forms in the community might lead to similar improvements in the future.

4.1 Smoothness of determinant

To discuss the problem of the smoothness of the determinant, we assume the existence of a polynomial time solving oracle which can determine if a combination of primes lattice is correct and output a weak basis out of it if yes. We also assume that the attacker does not have an algorithm that permits to eliminate prime overlattices one by one until only factors of Sk remain, or something easy to decipher, which would lead to an easier solution than searching through every possibility, which we think is reasonable as our experimentations could not distinguish any overlattice from random lattices. If there was such an algorithm, then this might apply to any random lattice and lowers the overall security of lattice problems. However, it is possible that the problem is much easier depending on the kind of secret keys we actually use and what we intersect it with.

The only attacks based on overlattices according to the best of our knowledge were one from Becker, Gama and Joux [22] and one from Gama et al. [23]; even then, the way their overlattices are generated is very different and does not search for integer overlattices specifically. Aside from the overlattices consideration, there is also no attack to the best of our knowledge that makes use of a smooth determinant on random lattices, and other popular schemes such as NTRU [31] and Ring-LWE [49] also rely on lattices with smooth determinants (q-ary lattices have naturally smooth determinants, but their factorization differ).

Under all of those assumptions, the total security provided by our enhancement is either solving the problem directly on the public key, finding the right combination multiplied by the time of running a detection oracle (find which integer overlattice is weak), or working in a properly chosen non-integer overlattice of a large enough volume. The latter possibility, which could seem the most efficient, is in our opinion not-effective; to the best of our knowledge, our system does not hold a particular weakness towards this approach compared to any other random lattice as our public key seems to hold the same structure as far as our heuristic experimentations on HKZ-reduced bases are concerned (see the next subsection) Assuming the “weak integer overlattice” detection oracle runs in polynomial time (for simplification, we will consider it constant, but in practice, we do not know how to even create a practical one; the latter security is bounded by (ω⁢(Pk)⌈ω⁢(Pk)/2⌉), which, as we discussed in the previous section, is not a problem in high dimensions as ω⁢(Pk) grow big, as, in our tests, we never reach that bound (Figure 2)).

We stress that finding the shortest vector for a small prime overlattice does not help solving the problem in the ring product in general. It is, in fact, still a research problem to be able to compare two numbers given their decompositions over a ring product without computing them back as it is the main issue with residue number systems (RNS for cryptography is an old and still active research topic [8, 25, 7, 6]). This is even more problematic when comparing vectors.

4.2 Perfectness of basis and primality between factors

Due to Goldstein and Mayer [29], taking a perfect Hermite normal form matrix with a random prime determinant can be considered as taking a random lattice. As we are intersecting a lot of lattices of this type, with different prime determinants which result in a perfect HNF, we are comparing our results with other perfect HNF bases with the same determinant and random entries. Since our experimental results show that 80 % of the bases generated with coefficients from bounded entries admits a perfect HNF or are equivalent to one by permutation of columns (see Appendix A.2), we believe the comparison to be fair.

This is further reinforced due to recent works from Nguyen and Shparlinski [57], used shortly after by Gama et al. [23] to make their generalized worst-case to average-case reduction which allows us to use a much more general lattice form and is therefore very different from those q-ary lattices first introduced by Ajtai [1]. In practice, Chen and Nguyen’s work [14] on Darmstadt’s lattice challenges lead us to think it is easier to solve problems (find short vectors) in a q-ary lattice than in a random lattice of large volume; therefore, in terms of basis recovery attacks, the perfect Hermite normal form could be actually more desirable.

On top of that, there is no currently known algorithm to our knowledge that will provide efficient secret keys with an imperfect HNF on purpose (one that cannot be converted to a perfect HNF; see Appendix A.2), where the imperfect coefficients do not leak information on the first element of the diagonal (they very often have common divisors for example). We also keep in mind that if ℒ⁢(M) is a lattice that admits a diagonal dominant basis, then so do ℒ⁢(σ⁢(M)), where σ is a column permutation, retaining the exact same values, measuring basis quality in every criteria known (see Appendix A.2).

Furthermore, given a finite set of prime factors on the diagonal, the perfect form gives the hardest challenge as it is harder to guess a large number of factors in a single position rather than a small fixed amount in multiple positions (given the same total amount of primes), provided we could make sure it could not be transformed into a perfect HNF by permutation (if having a perfect HNF becomes a weakness).

Having factors prime to each other not only ensures an easier perfect HNF, but also avoids giving information beneficial to the attacker (see Appendix A.1). As stated before, having a perfect HNF is also desirable when managing keys.

4.3 Shortest vector and basis structure

We present the result of experimentations for intersecting diagonal dominant type matrices with a random one with a perfect HNF form below. We chose 3 as our scaling factor, allowing our perturbation matrix to have a measurable determinant as a power of 2. To determine the impact of R over Pk’s resistance against enumeration and classical lattice reduction techniques compared to random lattices [69], we also observe the distribution of coefficients using SVP on small dimension (40), comparing them to the random case (every time with the exact same determinant and dimension). It seems like, after reaching a size of 32 bits, there is almost no difference between Pk or random lattices of the same determinant (Figure 1). As the difference tends to decrease very rapidly, we scale the graphs to the extrema.

Figure 1

Distribution of the shortest vector’s coefficients.

(a)

det⁡(R)=1

(b)

det⁡(R)=28

(c)

det⁡(R)=216

(d)

det⁡(R)=232

However, the obfuscation of ℒ⁢(Sk)’s structure is not exclusive to ℒ⁢(Sk)’ shortest vectors. We show with the following tests that the obfuscation works on the whole HKZ-reduced basis of ℒ⁢(Pk). In that regard, we compare condition numbers (CN) with the maximum norm. The test is done in dimensions 30, 40 and 50 with over 20 matrices per dimension and 20 witnesses per new determinant, the diagonal dominant type having noise in [-1,1] with the diagonal being ⌈dim⌉. We only choose matrices with a perfect form. Every matrix computed has been HKZ-reduced.

First, with dimension 30, det⁡(Sk) has on average 79 bits.

With dimension 40, det⁡(Sk) has on average 113 bits.

With dimension 50, det⁡(Sk) has on average 151 bits.

According to our experimental results, there is little influence on increasing the size of the perturbation over 32 bits as we get very close to the same condition number as a random HKZ-reduced matrix with the same determinant. This reflects the results we have when measuring the distribution of shortest vectors’ coefficients values. This means that obtaining a good basis of the public key will allow to decrypt nearly as well as with a good basis of a random matrix, being very sensitive to noise. Therefore, the only factor to consider is the number of primes, and as we grow larger in dimension, we will obviously take much bigger primes, ending up in a noise with a determinant size of over 32 bits. We can then take small primes to minimize the lattice gap (as we will measure below).

What we need to consider is the possibility to distinguish the different overlattices very easily (which would nullify our improvement of GGH), or the possibility to know if, by intersecting different overlattices, we could determine if we are getting closer to the right combination or not. Therefore, we compare condition numbers of Sk’s and R’s overlattices, the intersection of Sk’s and R’s overlattices separately or mixed together (with all matrices being HKZ-reduced) to HKZ-reduced bases of random lattices of the same respective determinant for every test. The result is that the overlattices themselves seem to be indistinguishable from random cases. Since removing several factors of Sk randomly does seem to make the problem harder (in the sense that the resulting lattice looks more random than keeping all factors), this observation should also hold for non-integer overlattices. For now, it does not seem that an attack on a random overlattice would be more effective.

4.4 Message recovery attacks

We now measure the influence of R on Pk against message recovery attacks, and we will use the lattice gap in that regard. We assume the attack used is the popular heuristic transformation from CVP to SVP by attacking an extended basis B. What we need then is closely enough approximate values of λ1⁢(B) and λ2⁢(B). In that regard, we consider λ1⁢(B) the size of our message m. With maximum decryption capacity, we have

As we take the best value possible,

and we assume λ2(B)≈n2⁢π⁢eDet(Pk)1/n with the Gaussian heuristic. It is the best approximation we can use as we do not know the length of the shortest vector in the public key^[2]. Therefore, the lattice gap is

It is a bit different than most schemes as our public key does not represent the same lattice as our private key. The first remark we do when looking at the formula is that the gap increases as det⁡(R) increases, which might give us a good reason to carefully manage Size⁡(det⁡(R)) besides key size considerations.

Here, we present our experimental results for the simulations on computing the root lattice gap (with primes starting from 3, scaling factor 2). From the earlier work of Gama and Nguyen [24], the problem is solvable as soon as the lattice gap is lower than a fraction of the Hermite factor. We observe the evolution of the lattice gap for different numbers of combinations over increasing dimensions, and it appears that increasing the number of combinations has a lower impact as we increase dimensions; thus a high value for det⁡(R) is not a problem as dimensions increase.

As the constants mentioned in Gama and Nguyen’s work [24] depend on the algorithm used and the lattice structure, we scale the curve with factors 0.50 and 0.20. We can observe that, under the pessimistic assumption of a constant of 0.20 (which is not the worst since [24] mentions a factor of 0.18 for BKZ-20), we do not reach the optimal factor of 1.005 (considered by many to be impossible to reach without proper structure in dimension 500, see [24]) even past dimension n=850.

Figure 2

Evolution of the root lattice gap from dimension 225 to 850.

(a)

C=1/2

(b)

C=1/5

4.5 IND-CCA security and message space

Suppose the private key has been generated by a diagonal coefficient D and a noise bound μ for a full-rank lattice of dimension; a first suggestion would be to use messages in the space [-M,M]n, where M=D-μ2. This allows us to decrypt a number of bits which would be a multiple of the lattice dimension. However, the scheme does not achieve IND-CCA security that way, and it is advised to sacrifice the number of bits and restrict the message space to achieve IND-CCA security.

To achieve IND-CCA security, one can set the ciphertext to encrypt only a single bit with a technique similar to the one proposed in Regev’s first LWE-based public-key encryption scheme [67], where the decryption is a test whether an integer is closer to 0 or to a certain bound, which, from a lattice-based point of view, just consists of set bounds for a norm on deciphered vectors m (original messages); for all deciphered plaintexts m and ∥m∥∈]a,b[, where a>0 and b is within our decryption capacity, if ∥m∥>a+b2, then return the bit 1 as the message, or 0 otherwise.

5.1 Parameter choices

To achieve a reasonably improved security (from lattice reduction techniques) without drastically increasing the key size, we suggest to use a matrix of dimension at least 400, with a diagonal coefficient of 20 and a noise bound of 1. Suppose we sacrifice half of the dimension for padding; this yields 4 bits per remaining dimension, which will be 800 bits. We suggest using any random family of primes whose total products slightly exceed the size of the determinant of the secret key, and furthermore, whenever possible, we should avoid very small primes to avoid any information potentially recovered by the scaling factor (even if unrealistic). The increase in key size will depend on the size of the random matrix we use to hide the secret lattice (as shown in Section 2). Moreover, taking too big primes will reduce the number of combinations, hence lowering the security in terms of discovering the secret lattice. We then recommend using primes between 541 (the 100th prime) and 2741 (the 400th prime); those are arbitrary choices but offer enough combinations for whatever matrix of such dimension, or even much higher, would need from what we see in the previous tables, and the size of the noise generated is, in our opinion, enough to protect against basis recovery attacks. The scaling factor can be as small as 2. Depending on the security level required (for various applications, as mentioned by NIST [54]), we can let λ>64,80,96,128 as far as the number of combinations 2λ is concerned. We note that intersecting a small random lattice is already improving the security; therefore, even if we do not reach the same average as random matrices, the public key is still more secure.

Intersecting lattices is a technique that can be used with any kind of lattice. This technique may give rise to other useful applications, which remain unknown.

5.2 Alternate secret keys

Our approach is not only limited to a diagonal dominant matrix. As any message generated using Pk is equal to a message generated using HNF⁡(Sk), any decryption process using HNF⁡(Sk) as a secret key remains unchanged. The main problem in our opinion is always how to hide the overlattice ℒ⁢(Sk). As an example, using tensor products as secret keys [19] would leave a slightly different issue in hiding det⁡(Sk). Other improvements on GGH type cryptosystems could be compatible with ours as we leave the decryption and message space unchanged; therefore, security improvements may become cumulative (a case-by-case study and adaptation might be necessary). An example of such a possible cumulative improvement to study can be found in [68].

Additionally, our approach is not limited to a perfect HNF either. A lot of properties do indeed arise when intersecting lattices which determinants are not co-prime which could lead to security issues when not kept in mind, as information on the factorization of det⁡(Sk) is leaked (see Appendix A.1). However, if we carefully generate non-perfect HNF matrices on purpose from intersections it might be possible to ensure a reasonable security without increasing the key size too much.

Another idea is to use weaker secret keys. In our experiments, we randomized the occurrence of the noise values in [-1,1]. However, seeing how intersections allow us to hide the secret basis’ structure, we can make it so in a line vector of the secret key (or even in both lines and columns) the number of times a non-zero value is used is limited. For example, what if we set 1 to appear α times and -1 to appear β times, which will leave χ zeroes, where χ=n-1-(α+β)? If we allow a big χ, this will lead to a bigger decryption capacity. We do not know if such a prefixed setting would create visible weaknesses in the result of the intersection, or the overlattices, and how much impact it will have on the root lattice gap.

Another type of weaker secret key is using ideal lattices. Ideal lattices are a powerful tool to compress keys and to enable fully homomorphic encryption [26]. The research development in ideal lattices has been very popular in the last years; hence we are providing some remarks on the intersection of ideal lattices. The advantage of ideal lattices is allowing a stable multiplication and offering very compressed keys. Some interesting properties arise when intersecting ideal lattices (see Appendices A.1 and A.2), but, to the best of our knowledge, there is no method to control the determinant of an ideal lattice, which is how we make intersections secure in our paper. The possibility of reinforcing the security of ideal lattice based schemes with intersections also remains an open question.