# Tag Info

18

Post-quantum security: As you note, quantum attacks are not known to break lattice-based cryptosystems. But some other proposals like McEliece, as well as most symmetric primitives are not known to be poly-time breakable on a quantum computer. Security from worst case assumptions: In security proofs for cryptosystems we typically assume that some problem ...

8

One line: worst means any and average means random. Lattice-based cryptosystem Let me restate. Fix security parameter $n$. What the reduction shows is the existence of a solver for the lattice problem on input any $n$-dimensional lattice using the adversary breaking a lattice-based cryptosystem with the security parameter $n$ on the average case. Since ...

7

How is a lattice defined? A lattice $\mathcal L(B)$ is the set of all integer combinations of the basis $B = \{b_1, ..., b_n\}$ of $n$ linearly independent vectors. That is, lattice $\mathcal L(B)$ is defined as: $$\mathcal L(B) = \{ B \cdot z \;: \; z \in \mathbb Z^n\}$$ In cryptography, we are interested on integer lattices, ...

7

Thanks for the question! You are correct that there is a bug here. Indeed, the sentence "choose $\mathbf{b}_i$ s.t. $\ldots$" makes no sense: the LHS is in $H$, but the RHS may not be. Fortunately, there is a simple fix which guarantees $\mathbf{y}'_i \in H$. (This must have been what we intended in the first place, based on how the rest of the proof goes;...

6

I'm also afraid you couldn't understand this as D.W., but let us start. I sometimes cannot understand your questions. Please restate them, if possible. The definition of the Ajtai hash functions Let $n$, $m$, and $q$ be positive integers. Let $R = \mathbb{Z}_q$ be the quotient ring of integers modulo $q$. Let us define a function, which maps a vector in $D^... 4 xagawa's original answer is almost correct, except for the valid concern pointed out by Florian in the comments. (The updated answer looks good to me.) The answer to the question is "yes," except that the most 'lattice-y' proof works for the modified version of the Regev system defined in Applebaum-Cash-Peikert-Sahai CRYPTO'09. (A version of this was also ... 4 I give another simple proof using the leftover hash lemma. The proof goes as follows, where I'll abuse the notation and assume that q is prime. Game0 The adversary can see $$(A,b,c,u,v,w,s) = (A, As+e, At+f, rA, rb+x\lfloor q/2 \rceil, rc+y\lfloor q/2 \rceil, s).$$ Game1 The view is changed as $$(A,b,c,u,v,w,s) = (A, As+e, c, rA, rb+x\lfloor q/2 \rceil, ... 4 The main advantage of using q-ary lattices is that it allows a cryptosystem designer to rely on the standard Short Integer Solution (SIS) and Learning With Errors (LWE) problems, which are known to be at least as hard as worst-case lattice problems. So the SIS/LWE problems abstract away the connection to lattices, and give the designer a strong hardness ... 4 As you write, an algorithm for SVP_\gamma must output a nonzero lattice vector v \in L such that \| v \| \leq \gamma \cdot \lambda_1(L), where \lambda_1(L) denotes the minimum distance of L. It is also true that we don't have an efficient algorithm to verify that a candidate v meets this condition, because \lambda_1(L) appears hard to compute. ... 4 (I am one of the authors of the paper you're asking about. The isomorphism \varphi you wrote is the intended one.) The key observation is that a Gaussian D_r of parameter r over \mathbb{C} is "spherical," i.e., it is the sum of independent Gaussians (both of parameter r) for the real and imaginary components, and so is invariant under rotations ... 4 When decrypting in lattice-based cryptosystems, one computes a value v \in \mathbb{Z}_q that is guaranteed to be congruent to a "small" integer e \in \mathbb{Z}, where e encodes the message (e.g., as the parity of e modulo 2). By using the integer representatives between -q/2 and q/2, one can recover the small integer e (and thereby recover ... 4 It depends on the exact domain of the hash function and the quality of the SIS solution, i.e., its norm (and the choice of norm itself). Suppose the hash domain is \{-d, \ldots, d\}^m, i.e., vectors of \ell_\infty norm at most d. Then any nonzero vector in Ajtai's lattice having Euclidean norm at most d collides with the all-zeros input. (Actually, ... 4 Yes the Bernstein attack is applicable but the impact of the attack is reduced because the party generating the parameter is also going to be a legitimate participant of the key exchange. Here is why the attack does indeed apply. Consider a case where Bob and Alice wish to conduct a key exchange using the New Hope Lattice-Based Key Exchange. Bob will be ... 3 This is not quite an answer, because what I'll discuss is only about as powerful as the attack in the question, which refers to section 3 onwards in: Abderrahmane Nitaj and Tajjeeddine Rachidi, Factoring RSA moduli with weak prime factors (preliminary 2015-05 eprint). The method I'll discuss is acknowledged in section 2.3 of the above article. It was ... 3 It is very hard to give a concrete, "apples-to-apples" comparison of lattice-based and pairing-based IBE schemes. There are many reasons: the research surrounding concrete secure parameters for LWE is still evolving, efficient implementations of operations used in lattice-based IBE (e.g., discrete Gaussian sampling) are still works in progress, one can ... 3 Examining the definition provided by A. Sakzad, I now have the intuition for what this means which I'll explain through an example. In the diagram below, the red dots are a lattice, and the two red arrows represent a basis, B, for this lattice. We have a green vector, ψ' = [2, 2]. We might ask which point on the lattice ψ' is closest to. If we are ... 3 My understanding is that the coefficients of polynomials used in lattice crypto are often sampled from a discrete Gaussian distribution. A Gaussian is centered at 0, which would explain why the elements are represented as elements from the set \{\frac{−(q−1)}{2},…,\frac{(q−1)}{2}\}, as you mentioned. 3 Feasible? Sure, there are lattice algorithms that are competitive in performance with RSA. However, there are drawbacks, like: They've been studied less than RSA or ECC, especially the individual algorithms. The most well studied system, NTRU, is patented. No generic proof that I know of that there isn't a quantum algorithm to solve them. The first one ... 3 Sure you can do. There are many lattice attacks, using your second assumption, to ECDSA (which also applied to DSA). For instance see Smart and Howgrave-Graham and Shparlinski and Nguyen. All the lattice attacks base on finding small solutions (for the ephemeral key k and the private key a) to the signing equation sk-ra\equiv H(m)\pmod q. If you have ... 3 The equations mod 1 are supposed to have solutions that are very close to an integer value, say 3.99 or 4.01, which are reduced to a value very close to 0 (or 1, which is 0 mod 1). Specifically, they describe a set of samples that equate to the distance from an integer value all within ± {1/n} for some large value n, and the sum of the sample set is ... 3 Bruteforce appears to work well enough. The following Sage script finds an instance quickly: from sage.libs.fplll.fplll import FP_LLL from sage.libs.fplll.fplll import gen_uniform n = 5 # dimension q = 16 # size of matrix entries while True: M = gen_uniform(n, n, q) L = M.LLL(delta=0.999) S = FP_LLL(L).shortest_vector(algorithm='proved') ... 3 The nth cyclotomic polynomial \Phi_n\in\mathbb Z[x] is irreducible in \mathbb F_q[x] if and only if q is a generator of (\mathbb Z/n)^\times (proof). Hence, unfortunately, the polynomial x^n+1 is never irreducible modulo q if n>4 is a power of two: The group (\mathbb Z/n)^\times is not cyclic in that case. Thus it may indeed happen that ... 2 I am not aware of any work that proposes a Gap problem related to LWE. The reason is probably that LWE is an average-case problem specifically designed for the use in crypto. However, there are the related worst-case problems, e.g. the shortest vector problem (SVP), that come with a Gap version. So, you might want to have a look at GapSVP and GapCVP. 2 It is computationally infeasible to find R (or any other short matrix that satisfies the relation) because solving A R = V \pmod{q} for uniformly random A, V is the SIS problem (in its inhomogeneous version). SIS is provably as hard as solving worst-case approximation problems on lattices. (Also, for the parameters considered in the paper, [\bar{A} \... 2 This introduction and this one are well formed . Also have a look at this thesis . Notes from this course may be helpful . Oded Regev has numerous publications to the field. 2 The basic idea is to take random (Gaussian) integer combinations of the given LWE samples, and add a little "smoothing" noise. This will result in new samples which are statistically close to LWE samples with the same secret, but with a somewhat wider error distribution (by a factor of \tilde{O}(\sqrt{n}) for typical parameters). This is essentially Regev'... 2 It can be defined as follows:$$\psi = \psi' \pmod{\bf B} = \psi'-{\bf B}\cdot\lceil{\bf B}^{-1}\psi'\rfloor,$$where \lceil\cdot\rfloor denotes the round operation to the nearest integer. 2 Let \left\{\vec{b}_1,\ldots,\vec{b}_n\right\} ba a lattice basis and \left\{\hat{\vec{b}}_1,\ldots,\hat{\vec{b}}_n\right\} be its Gram-Schmidt orthogonolization. Here are some reasons: It helps computing a reduced basis (an equivalent basis with shorter vectors) using LLL or BKZ algorithm, The span of \{\vec{b}_1,\ldots,\vec{b}_i\} is equal to the ... 2 Let {\bf A} be a n\times m matrix with n|m and rank n. Write down {\bf A} as m/n blocks of m\times m matrices as follows:$${\bf A}=\left[{\bf A}_1|\cdots|{\bf A}_{m/n}\right].$$If {\bf x}\in\Lambda({\bf A}), then$${\bf 0}={\bf A}{\bf x} = \sum_{i=1}^{m/n}{\bf A}_i{\bf x}_i,\pmod{q}$$where${\bf x} = \left[{\bf x}_1^T|\cdots|{\bf x}_{m/n}^...

2

Your best bet at the moment are probably the lattice-based key exchange described in the "Post-quantum key exchange – a new hope" paper. You can also find different implementations. C code can be found on Peter Schwabe's homepage. For signatures, if you want to use lattices, you will end-up with BLISS or BLISS-B both of which are implemented by various ...

Only top voted, non community-wiki answers of a minimum length are eligible