# Tag Info

11

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

4

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

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.

1

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