Hot answers tagged

17

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 ...


6

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: \begin{equation} \mathcal L(B) = \{ B \cdot z \;: \; z \in \mathbb Z^n\} \end{equation} In cryptography, we are interested on integer ...


5

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 ...


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

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

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 ...


3

(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 ...


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

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

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

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

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 ...


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

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

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

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 ...


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 ...


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 ...


2

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, ...


1

The Gaussian function over a lattice, if you define it with or without the scaling factor $1/s^n$, is not a probability distribution, since it does not sum to 1. In order to construct a probability distribution, that samples points proportionally to the Gaussian function, one has to rescale anyway by dividing by the sum of the Gaussian over all lattice ...


1

With math and computational advances, for protecting systems we should increase key size. We know that recommended key size for lattice based systems such as the NTRU is approximately $3slog(s)+1000$ bit, which $s$ is a desired security level.Today $s=80$, but with the advances of math, $s$ is increasing. $s=96$ is believed to provide protection until ...


1

No. The key factor is the security level - a scheme has n bits of security if it takes roughly $2^n$ work ($\approx$ time x space) to break. So one can compare for example Diffie-Hellman key exchange in finite fields and over elliptic curves at the 128 bit security level and conclude that EC are more efficient (that is why they were invented, after all). ...


1

Almost all lattice-based schemes that have somewhat practical performance use lattices from a subset of all lattices. Those lattices have additional structure and can be described using polynomials. The big advantage of doing this is that on the one hand the size of a description of the lattice is much smaller than for arbitrary lattices and on the other ...



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