Posted on

#StackBounty: #post-quantum-cryptography #lattice-crypto #hardness-assumptions Error Correcting Code VS Lattice

Bounty: 50

I’m not an expert in PQ-Crypto. As I understood Error Correcting Code and Lattice based crypto.
The cryptographic assumptions are very similar. And the key-difference for me is the nature of the noise. In one case the noise is inspired of the "physical noise", and in the other one, it’s more mathematical and consider a more complex distance (euclidean distance instead hamming distance).

Intuitively, this reason makes sense about the fact that in every apllications I know lattice-based crypto is more efficient than Error-correcting based crypto.

  1. Is my intuition seems correct to you?
  2. If yes, is there a theorem which certify that every cryptographic protocol based on an error-correcting code assumption could be transformed in a more efficient protocol based on lattice (i.e with the same level of security and based on a weaker lattice assumption)?
  3. If No, is there more informal claim of known researcher which consider this question. Or it just doesn’t make sens to compare these two families of assumptions?

Get this bounty!!!

Posted on

#StackBounty: #post-quantum-cryptography #lattice-crypto #complexity Can LWE be NP-hard?

Bounty: 150

Regev’s reduction shows that LWE is quantumly at least as hard as CVP with an approximation factor of $n/alpha$ for $0<alpha<1$. But I just watched this talk which said that if $sqrt{n/log n}$-CVP is shown to be NP-hard, then the polynomial hierarchy collapses.

This seems to imply that, if the polynomial hierarchy does not collapse, we could not hope to show that $n/alpha$-CVP is NP-hard, meaning that Regev’s reduction cannot show that a poly-time LWE algorithm implies $NPsubseteq BQP$. Is that true?

If so, is there some sort of no-go theorem the other way? That is, maybe we want to come up with a better reduction. But if $sqrt{n/log n}$-CVP could solve LWE, then we can’t hope to reduce LWE to $O(1)$-CVP or else we would show that $sqrt{n/log n}$-CVP is NP-hard, again collapsing the polynomial hierarchy. Is this also true? What is the maximum approximation factor of CVP that can still solve LWE?

(and of course, similar questions apply to the classical reduction).

Get this bounty!!!

Posted on

#StackBounty: #lattice-crypto Finding the basis of the transpose of a q-ary lattice

Bounty: 50

Given $q$ and a matrix $A in mathbb{Z}_q^{n times m}$, the $q$-ary lattice is defined as
$$Lambda(A)={x in mathbb{Z}^m:Ax=0 bmod q} $$
An instance of a q-ary lattice and its short basis is computed in Generating short basis for hard random lattices. Once the short basis $T_A$ for $Lambda(A)$ is given, computing the short vector $s$ in $Lambda
(A)$ is given in SamplePre algorithm.

Is it possible to find a short basis for $Lambda(A^T)$, if we are given a short basis of $ Lambda(A)$?

Basically I want to find the short vector $s^prime$ such that $A^Ts^prime=0 bmod q$.

Get this bounty!!!