Questions tagged [lattice-crypto]

Lattice-cryptography is the study and use of lattice problems applied to cryptography.

Filter by
Sorted by
Tagged with
1
vote
0answers
18 views

Artificial abort in Adaptively-secure Lattice IBE in [ABB10]

I have read the paper [ABB10] several times but I still cannot understand thoroughly the "artificial abort" in the security proof of the adaptively-secure IBE in the paper. So my questions ...
0
votes
0answers
26 views

CKKS security estimation for Palisade

My question is rather practical and specific. I am trying to setup an efficient CKKS scheme in Palisade. To this end, the automatic choice for secure parameters has to be turned off and I rely on the ...
2
votes
0answers
37 views

Rounding function used in Saber Key Exchange

In Saber: Module-LWR based key exchange, the authors use a rounding function called $\textit{bits}$, defined (in page 3) as follows: $bits(x, i, j)$, with $j \leq i$, gives $j$ consecutive bits of a ...
3
votes
1answer
100 views

Famous ideal lattices

I am wondering if there exist some special rings $R$ that gives us, under the canonical embedding, some special lattices, like the root lattices, Barnes-Wall lattices, Leech lattices, ... In more ...
7
votes
1answer
363 views

NewHope and NIST's Post-quantum standardization

Where can I find NIST's reasoning to eliminate NewHope from the 3rd round of the post-quantum competition? I see all the lattice KEMs finalists are based on modules. Is being a ring-based KEM ...
2
votes
1answer
127 views

Are all homomorphic encryption schemes based on latticed-based schemes?

PALISADE offers a pool of Homomorphic Encryption schemes and it is stated that "PALISADE is a general lattice cryptography library ...". My question is rather simple: are all homomorphic ...
3
votes
1answer
79 views

Lattice reduction question regarding the capability of LLL and BKZ

I've been reading How to estimate the hardness of SIS instances? and following some of its sources, and I want to confirm a few things. LLL algorithm runs in polynomial time, but isn't capable of ...
5
votes
2answers
140 views

MLWE (and RLWE) to LWE reductions proof

In crypto papers, cryptanalysis of MLWE/RLWE/etc. is often reduced to LWE. Why can we do this? Is there strict proof of such reductions?
1
vote
1answer
30 views

Guessing the Secret in RLWE Search-to-Decision

In On Ideal Lattices and Learning with Errors over Rings, the authors prove a search-to-decision reduction by guessing the RLWE secret $s$, and using the guess to transform a sample from $\mathfrak{q}...
0
votes
1answer
47 views

Voronoi regions of lattices with dimensions $\leq 16$

Is there any idea about calculating the exact Voronoi regions of lattices with dimensions $\leq 16$? Thank you!
4
votes
1answer
49 views

Proving LWE inversion in Micciancio-Peikert-2012 lattice trapdoors

I'm looking through the lattice trapdoor construction in https://eprint.iacr.org/2011/501. To summarize, assume we have a matrix $G$ where, on input $b$, we can efficiently find $(s,e)$ such that $s^...
3
votes
2answers
436 views

Distribution of the Difference of Uniformly Random Elements

In the search to decision reduction of 'On Ideal Lattices and Learning with Errors over Rings', the authors implicitly use the fact that the difference of distinct, uniformly random elements of a (...
1
vote
0answers
67 views

What are the prerequisites for understanding Lattice based Cryptography, LWE or RLWE based on SVP?

I'm new to Quantum Resistant Cryptography, so, I thought of diving into Lattice based crypto, LWE and ring LWE. I realise that the hard problem involving them is the "shortest vector problem"...
2
votes
1answer
54 views

Dual of a complex lattice

We know that for a real full-ranked lattice $\Lambda$, with real square matrix $\mathbf{B}$, the dual lattice $\Lambda^{\vee}$ has matrix $(\mathbf{B}^{-1})^T$. Now If we have a complex lattice with $...
8
votes
2answers
213 views

Error Correcting Code VS Lattice

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....
1
vote
2answers
77 views

Verify that a point is inside a lattice

I am wondering if there's a polynomial time algorithm that, given a lattice $\Lambda$ with basis $\mathbf{B}$ and a point $x$ in space, it tells you whether $x$ is in $\Lambda$ or not!
3
votes
1answer
74 views

iO from Matrix Branching Programs

Recently I'm learning about constructing iO from Matrix Branching Programs via Multi-linear Maps (to be exact, [GGH+13] and [GGH15]). However, I have a small question that I couldn't figure out. It ...
1
vote
1answer
64 views

Solving modular matrix equations via Gaussian elimination or System of linear equations (SIS assumption?)

Suppose $S \in \mathbb{Z}_q^{m \times m}$, and the norm of $S$ is less than an upper-bound $\beta$. Additionally, $A_1, \cdots, A_k, C_1, \cdots, C_k \in \mathbb{Z}_q^{m \times n}$. Here, $k \geq m>...
1
vote
0answers
54 views

Code implementation of NTRU lattice attack

As mentioned here, BKZ is one way to break the NTRU lattice What is the most efficient attack on NTRU? I was wondering if there are any source codes which actually implemented this on the weaker NTRU ...
3
votes
0answers
51 views

It is possible to prove this in zero knowledge?

Let $\mathcal{R}_q = \mathbb{Z}_q/\langle x^n + 1 \rangle$, with $n$ a power of $2$. Suppose that we sample $\mathbf{r} \leftarrow \mathcal{R}_q^m$ uniformly at random with the property that $0 < ||...
4
votes
0answers
47 views

LWR parameter estimation

I am trying to estimate parameters for LWR $(n,q,p)$ instance using the LWE estimator. My $q,p$ are $283,256$-bit prime numbers and I am trying to find required $n$ for 128 bit security. For this, I ...
1
vote
0answers
47 views

Proof for, Vectors sampled from $D_{(L,r)}$ have Euclidean norm at most $r\sqrt{n}$ with a high probability

For any $n$-dimensional lattice $L$ and $r > 0$, a point sampled from $D_{L,r}$ has Euclidean norm at most $r\sqrt{n}$ except with probability at most $2^{-2n}$ (where $r$ refers to the standard ...
2
votes
2answers
66 views

LWE versus neural nets

It seems like that the construction of the LWE problem: $As + e = b$ resembles how neural nets work: $Ax + b = y$. In LWE, we are given the problem instance $A$, and the product with errors $b$ and ...
1
vote
0answers
82 views

Which are the most Promising Post-quantum Public Crypto Primitives in the Face of a Quantum Apocalypse?

I'm fairly new to the fundamentals of post-quantum cryptography. So, please forgive me for such a direct question. Searching Google opened up a whole lot of amazing ideas that are thought to be ...
2
votes
0answers
19 views

Probability that length of shortest nonzero vector is less than a number

Let $\Lambda\subset \mathbb{Z}^n$ be an $n-$ dimensional lattice with determinant $d$. We know that the probability that a uniformly random integer vector $x$ is a point in $\Lambda$ is given by $\...
0
votes
1answer
52 views

Why do we add error in the definition of LWE?

One of the various equivalent definitions of the LWE problem is the following: Let $n,q$ be integers ($q$ usually is a prime number), $\chi$ a discrete probability distribution over $\mathbb{Z}$ (...
1
vote
0answers
38 views

Why ideal lattices?

An ideal lattice is a lattice $\mathcal{L}(A)$ generated by a block matrix $A = \left[ A^{(1)} \mid \dots \mid A^{(m/n)} \right]$ whose blocks $A^{(i)}$ are constructed from a vector $a^{(i)}$ and a ...
2
votes
0answers
60 views

How to construct a set in which the elements in $\mathbb{Z}[x]/(x^n+1)$ and their differences are invertible and with coefficients in $\{-1,0,1\}$?

I know that in IACR - Better Zero-Knowledge Proofs for Lattice Encryption and Their Application to Group Signatures it constructs such a challenge set: {$ x^i $}. But the inverse of the difference of ...
0
votes
0answers
39 views

What is the code when looking at the LPN problem?

We are given the problem in this question. We know that we have to use the algorithm $A_D$ in order to get $e_i$. Our idea is that we construct a vector $l$ of $l_i$'s by getting $n$ samples from the $...
1
vote
0answers
37 views

Key-Privacy in Postquantum Public-key Encryption

is there any post-quantum public-key encryption that achieves "key-privacy" (IK-CPA, IK-CCA) as described in this paper? I saw one code-based public-key encryption construction, but I wonder if ...
0
votes
0answers
58 views

Hash chain based secret revealing using homorphic princples?

I have recently been looking into Homomorphic encryption and I am looking for a specific hash-based encryption/decryption scheme. I don't need a full implementation but I am not sure if what I want ...
4
votes
0answers
102 views

How are the constants found in the AVX2 implementation of CRYSTALS-KYBER round 2 generated?

The post-quantum lattice-based cryptosystem CRYSTALS-KYBER which has made it to the second round of NIST PQC includes two implementations: 1) a baseline reference implementation in C and 2) an ...
1
vote
0answers
33 views

Forging a new secret key in RLWE

In a RLWE setting where you are given a secret key $s$ and an associated public key $pk = (p_0,p_1) = (-(p_1s+e),p_1)$, is it possible/easy to forge a new secret key $s'$ such that $p_0+p_1s'$ has a ...
1
vote
0answers
23 views

Ring (or Ideal) version of Boyen's signature

Boyen's signature is a well-known post quantum digital signature scheme. It's a lattice based scheme that uses a trapdoor of the lattice $\Lambda^{\perp}(A)$ and it's security is based in the SIVP ...
1
vote
1answer
31 views

Reduction of decison SIS

In Lyu12, Lemma 3.6 is as follows. Lemma 3.6 For any non-negative integer $\alpha$ such that $gcd(2\alpha+1, q)=1$, there is a polynomial time reduction from the $SIS_{q, n, m, d}$ decsion ...
0
votes
1answer
40 views

Canonical inclusion map in subfield attack on overstretched NTRU

I'm trying to understand subfield attacks on overstretched NTRU. In the paper https://eprint.iacr.org/2016/127.pdf authors used "canonical inclusion map" to lift vector to full lattice. What does ...
0
votes
1answer
57 views

Hard random lattices

The content I ask in this question is in the following picture in [GPV08][1]. I do not understand the proof of the first claim in $\bf Lemma$ 5.2. In the proof, which reprensents the uniform ...
2
votes
1answer
78 views

Random lattices

The content I ask in this question is in the following picture in GPV08. I do not understand the sentence computing the syndrome $\bf{Ae} \mod q$ for some $\bf{e} \in \mathbb{Z}^{m}$ is equivalent ...
0
votes
1answer
71 views

Average case problem and worst case problem in lattice

In Regev's lecture there is "In contrast, virtually all other cryptographic constructions are based on some average-case assumptions. For example, in cryptographic constructions based on factoring, ...
3
votes
1answer
75 views

Hardware Gaussian random numbers for lattice-based cryptography

I have been recently reading about lattice-based cryptography. I read that a key aspect of such protocols rely on added Gaussian noise on lattices, and which therefore require highly efficient and ...
6
votes
0answers
137 views

Can LWE be NP-hard?

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}...
1
vote
1answer
37 views

average-case SIS and average-case BDD

In lattice based cryptography, we say the average-case SIS (short integer solution) problem because it is such kind problem " $A \stackrel{\$}{\leftarrow} \mathbb{Z}^{n\times m}_{...
1
vote
1answer
68 views

SVP=SIVP in ring lattice (ideal lattice)

SVP (shortest vector problem) is equivalent to SIVP (shortest independent vectors problem) in ring lattice (ideal lattice). How to prove this? Could someone explain it to me? Thanks!
1
vote
1answer
100 views

Coppersmith's method for small public exponent

Can Coppersmith's method be used to break RSA when we only have access to public key and one ciphertext? For e.g. suppose we have N and ciphertext c both are 1024-bit numbers and the public exponent e ...
3
votes
0answers
44 views

parameter choosing for SIS based scheme in lattice based cryptography

In SIS based scheme, there is a matrix $A \stackrel{\$}{\leftarrow} \mathbb{Z}^{n\times m}_{q}$, and $n$ is the security parameter. I want to ask that why $n=1$ is also okay for the scheme (in "A ...
0
votes
0answers
44 views

domain of Ajtai hash function

I know that when the domain is $\{0, 1\}^{m}$ in function $h(x)=Ax$ for $A \stackrel{\$}{\leftarrow} \mathbb{Z}^{n\times m}_{q}$, this function is called Ajtai hash function. So when the domain is ...
4
votes
1answer
51 views

Is Type I lattice trapdoor hard to find even given oracle access to compute inverse of trapdoor function?

Consider the Type I lattice trapdoor in [GPV08]: https://eprint.iacr.org/2007/432.pdf Suppose a PPT adversary is given the LWE trapdoor function in the picture: $g_{A^\top} (s,e) = A^\top s + e = b (...
0
votes
1answer
42 views

How to have a bound (upper or lower) of Gaussion distribution over lattice based crypto>

In lattice-based crypto, we always need to sample 'noise' from Gaussian distribution, but how to measure the bound the noise? For example, if the Gaussian distribution is D_{u,\sigma}, where u is the ...
0
votes
1answer
46 views

security parameter in lattice cryptography

In paper Lattice Signatures Without Trapdoors(Lyubashevsky2012), $n$ is the security parameter, why the authors set $n$ as 512 but not 80/100/112 to get 80-bit security/100-bit/112-bit security?
0
votes
1answer
69 views

Learning with rounding (LWR)

This may be a naive question: LWR assumption states that for ${A} \stackrel{$}{\leftarrow} \mathbb{Z}^{m \times n}_q, s \stackrel{$}{\leftarrow} \mathbb{Z}^n_q$, given $(A, \lfloor A\cdot s \rfloor_p$...

1
2 3 4 5 6