# Tag Info

12

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

7

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 lattce using the adversary breaking a lattice-based cryptosystem with the security parameter n on the average case. Since we can ...

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: $$\mathcal L(B) = \{ B \cdot z \;: \; z \in \mathbb Z^n\}$$ 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

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

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

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

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

1

Currently, there is no formal proof of NTRU being based on a lattice problem, but you can find a description of NTRU in terms of lattices in Section 5.2 of [Ber09]. For lattice-based attacks for NTRU you can review [HPS98]. There is, however, a provably-secure variant of NTRU that is ultimately based on the hardness of the SVP problem [SS11]. References: ...

1

Code based cryptography like McEliece cryptosystem, is based on the hard problem of decoding linear codes. But i think it lies to the group of quantum based crypto since as far as we know it is still immune to quantum attacks

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