Questions tagged [lattice-crypto]

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

Filter by
Sorted by
Tagged with
4
votes
1answer
36 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
24 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
33 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
34 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
vote
0answers
23 views

Block size of BKZ algorithm and related security of CRYSTALS-Kyber

Security of lattice-based schemes in the NIST Posto-Quantum Project often relies on the complexity of dual attack. Complexity of this attack depends on the running time of lattice basis reduction ...
0
votes
2answers
45 views

set of integers modulo an integer q in lattice

Some literature about lattices set $\mathbb{Z}_{q}$ in $[-\frac{q}{2}, \frac{q}{2})\cap \mathbb{Z}$ but not $[0,q-1]$ such as "lattice signatures without trapdoors" and "lattice based blind ...
2
votes
1answer
106 views

How to find the inverse of a polynomial in NTRU-PKCS

I am coding a java based implementation of the NTRU public-key cryptosystem. I can comprehend the majority of the algorithms involved in the encryption and decryption process well enough, but the key ...
1
vote
1answer
41 views

Classification of attacks against lattices

I'm interested about the cryptanalysis side of lattice-based cryptography, and was wondering whether there is a survey paper or something that gives some classification of attacks against lattices, ...
1
vote
0answers
52 views

How decode works in CCA1 scheme based on MP12 construction?

In Section 6.3 from MP12 we have that $encode(m) = Sm$, for $S$ any basis of $\Lambda(G^t)$. Then I have: $S = \begin{pmatrix} 1 & 2 & 4 & 8 & 16 & 32 & 64 & 128 & 256\...
0
votes
1answer
26 views

Is the “decapsulate” function from lattice based cryptography homomorphic?

Observing the code example from pqcrypto-kyber, is the decapsulate function $d$ homomorphic? If $d(ct, sk_i) = ss_i$, is it true that $d(ct, \sum_i sk_i) = \sum_i ss_i$ ?
3
votes
1answer
32 views

A problem about Gaussian distribution in paper GPV08

These are contents from the paper Trapdoors for Hard Lattices and New Cryptographic Constructions(GPV08). I do not know the reason about the last sentence. Why these two distributions D_{\Lambda, s, c}...
1
vote
1answer
83 views

Is it possible that a signing algorithm produces no output?

I am reading Vadim Lyubashevsky's paper on Lattice Signatures without Trapdoors and I came across a somehow counter-intuitive part where he defined an algorithm $\mathcal{A}$: $y\leftarrow D_\sigma^m$...
0
votes
0answers
33 views

Multibit LWE Encryption

What's the simplest way to encrypt multiple bits with LWE public key cryptosystem? Some paper say use a different secret key for each bit of the message. Does that mean the length of the message ...
0
votes
1answer
75 views

Trying to Understand Ring Learning With Error Encryption

I'm trying to understand the following RLWE encryption scheme from this Chris Peikert's paper Say i choose $q = 97$, $n=8$ and the polynomial $a = 96 x^8+30 x^7+76 x^6+12 x^5+57 x^4+77 x^3+70 x^2+49 ...
0
votes
0answers
26 views

Understanding signature length computation

In the following paper, the authors provide a lattice-based ring signature from a 1-out-of-N proof, copied below. They illustrate their discovery with a table on the bottom of page 28, summarizing ...
6
votes
1answer
99 views

Decision to Search LWE when modulus $q=p^e$

I am reading Applebaum et al.. In Lemma 1. (page 7), Applebaum et al. proved the decision to search reduction when the modulus $q=p^e$ for prime $p$. In the proof, they define the hybrid ...
5
votes
0answers
32 views

Relation between LPN and GAPSVP?

I have a question regarding the relationship between the (search) LPN problem and the GapSVP problem. I have read a related problem that explains the main theorem in Reg05: the GapSVP problem can be ...
1
vote
1answer
45 views

Compute statistical distance between two distributions over tuples

Let $X$ denote one distribution. Let $f,g, \text{ and } h$ denote three functions. If we have the results: $g(X)$ is within a negligible statistical distance of $h(X)$. Is it possible to prove $$(f(...
3
votes
1answer
77 views

Randomness of Decision Learning With Error Problem

I read the statement of the Decision Learning with error problem is: distinguish between $(\vec a, \langle \vec a, \vec s \rangle + e)$ from uniformly random samples. Can anyone explain what does ...
0
votes
1answer
62 views

understanding LWE public key algorithm

I'm trying to understand this LWE public key system say I use matrix A = [[44, 73, 20, 54],[92, 19, 78, 22],[31, 34, 94, 29],[82, 32, 70, 68]] q = 97 bit = 1 and secret key s: [56, 90, 0, 46] and ...
4
votes
1answer
82 views

Are there any masking methods for integer multiplication masking?

I'm interested in lattice type cryptosystem such as Mod-LWR. But I found that integer multiplication¹ is not safe for side-channel attacks. I tried to make masking method by own method but it failed ...
2
votes
1answer
39 views

Security of somewhat homomorphic encryption via LSB encoding?

I'm reading this paper https://eprint.iacr.org/2011/344.pdf It says that "The secret-key encryption scheme whose security is based on the LWE assumption is rather straightforward. To encrypt a bit, $...
1
vote
1answer
61 views

Is there a LWE based public-key encryption scheme which is CCA1-secure?

Is there a lattice based PKE which is IND-CCA1 secure? Actually I am only familiar with LWE and SIS. So I want to know that what the IND-CCA1-secure LWE based PKE scheme looks like?
0
votes
1answer
49 views

Trapdoors for Lattices: CCA-secure encryption

In Trapdoors for Lattices:Simpler, Tighter, Faster, Smaller, Micciancio and Peikert proposed a CCA-secure encryption. However, I am confused about the step in decryption algorithm (p.36 Lemma 6.2.). ...
6
votes
1answer
80 views

Is LPN not as important as LWE and SVP?

I've been learning about lattice cryptography and have noticed that most resources such as this survey by Chris Peikart, the Winter School on Lattice Cryptography etc don't include material on LPN, ...
5
votes
1answer
101 views

What's the purpose of the smoothing parameter in lattice-based cryptography?

I see nearly all the lattice-based crypto papers talk about the smoothing parameter $\eta$. And I believe even some parameters are chosen with respect to that. However, I do not quite understand what'...
1
vote
0answers
40 views

How many ring-LWE samples are required for the (Search) Ring Learning With Errors problem to have a unique solution?

Consider the LWE distribution $\{(\pmb{a}_{i},\left<\pmb{a}_{i} , \pmb{s}\right> + e_{i})\}$ where secret $\pmb{s} \in \mathbb{Z}_{q}^{n}$, randomness is $\pmb{a}_{i} \xleftarrow{\$} \mathbb{Z}_{...
2
votes
0answers
49 views

ZKPoK for RLWE secret and error

I came across How to validate the secret of a Ring Learning with Errors (RLWE) key paper by Ding et al., which seems to provide a ZK proof that the given $p$ is of the form $as + e$ with $s, e$ small ...
0
votes
0answers
30 views

The implementation of Lattice-based HIBE

There are many lattice-based scheme papers adopt the lattice basis delegate technical from Agrawal et al. But I can't find the relevant implementation on the Internet since 2010. In fact, I almost ...
1
vote
1answer
47 views

Choices of $q$ and $f$ for RLWE-based constructions

I understand that RLWE was introduced to avoid the quadratic overhead in the matrices that appear in plain LWE. However, I have a series of questions about this setting. First, Ring-LWE-based ...
2
votes
0answers
40 views

Why round off vector sampling from continuous Gaussian distribution not directly sample from discrete Gaussian distribution

For any vector $\mathbf{c}$, real $s > 0$, and lattice $\Lambda$, define the probability distribution $D_{\Lambda, s,\mathbf{c}}$ over $\Lambda$ by $$D_{\Lambda, s,\mathbf{c}}(\mathbf{x})=\frac{...
1
vote
0answers
28 views

Again on discrete gaussians over lattices [duplicate]

Define $$\rho_{s,c}(x) = exp(-\pi \cdot \frac{\|x - c\|^2}{s^2})$$ and $$\rho_{s,c}(L) = \sum_{x \in L} \rho_{s,c}(x)$$ Then Discrete Gaussian over $L$ with center $c$ and standard deviation $s$ is ...
8
votes
1answer
189 views

Most influential/illuminating papers/books/courses on lattice based cryptography?

I'm interested in some sort of "compendium" on lattice-based crypto. There are a bunch of maths behind FALCON and other stuff. A lot of articles are devoted to lattice crypto, but not of them are of ...
0
votes
1answer
50 views

Trapdoors of Lattices: SampleD and SamplePre

In Trapdoors for Hard Lattices and New Cryptographic Constructions by Gentry et. al, they discuss SamplePre and in Trapdoors for Lattices: Simpler, Tighter, Faster, Smaller by Micciancio et.al, they ...
5
votes
0answers
90 views

Parameters for high density SIS

I am considering the SIS problem of finding $x\in \mathbb{Z}^m$ such that for random $A\in\mathbb{Z}_q^{n\times m}$, $Ax=0$ and $\lVert x\rVert < \beta$ for some $p$-norm and bound $\beta < q$. ...
3
votes
0answers
62 views

Lattice Based Cryptography domain

Some cryptosystems operate on the domain of the form $\mathbb{Z}_q[x]/\langle x^n-1\rangle$ and others operate on $\mathbb{Z}_q[x]/\langle x^n+1\rangle$. What's the security impact of the two forms?
4
votes
1answer
85 views

Why is the vector sampled from Gaussian or Subgaussian distribution in lattice-based cryptography? [duplicate]

I have known that the vector is sampled from Gaussian distribution in lattice-based cryptography because the distribution of the vector $\mod{\mathcal{P}(\mathbf{B})}$ approximates to uniform ...
1
vote
0answers
100 views

Canonical embedding vs. plaintext slots in Ring-LWE

I'm working on the canonical embedding mentioned in [LPR10] and [LPR13]. What confuses me is that the difference and the relationship between the canonical embedding and the concept of ''plaintext ...
3
votes
0answers
175 views

CVP over $\Bbb Z_{q}$ - is the problem still hard?

I'm reading about the CVP problem, and all the papers I've read so far handle the case where the CVP matrix and vector are over $\Bbb R^{n}$ (or over $\Bbb Z^{n}$), and the distance is a real number. ...
1
vote
1answer
77 views

Do q-ary lattices have parallelogram kind of structure?

An $m$-dimensional lattice is defined by a basis $A \in \mathbb{R}^{m \times n}$ is the set of points $\{Az : z \in \mathbb{Z}^n\}$. A picture of these points would be like a nice parallelogram kind ...
2
votes
0answers
64 views

Adaptation of Stern Zero-Knowledge protocol from coding to lattices

I'm currently working on Zero-Knowledge-proofs in lattice context, for which there exist two major frameworks. One of those two is the adaptation of Stern protocol from code-based-crypto. There is in ...
4
votes
1answer
136 views

Finding the basis of the transpose of a q-ary lattice

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 ...
2
votes
1answer
51 views

Calculation of failure probability in basic Ring-LWE-DH key agreement

This is the basic unauthenticated Ring-LWE-based Diffie-Hellman key exchange, based on Peikert's Ring-LWE KEM: (from BCNS15) Alice and Bob have shared public polynomial $a$ randomly drawn from $R_q = ...
6
votes
1answer
263 views

When does the SIS (Short Integer Solution) Lattice-problem start becoming easy (According to the parameters size)?

SIS (Short Integer Solution) Problem : Given $m$ uniformly random vectors $a \in Z_q^n$, grouped as the columns of a matrix $A \in Z_q^{n.m}$, find a nonzero integer vector $z \in Z^m$ with $||z|| \...
2
votes
0answers
56 views

Estimating the Security of SIS-Based Signature, by verifiying a subset of coordinates?

As I understood, the GPV signature scheme works as follows: KeyGen($1^n$) : Generate a Lattice with public $A \in Z_q^{n.m}$ and a secret trapdoor $t$. Sign $m$: compute $\vec y = H(m) \in Z_q^n$ ...
3
votes
2answers
133 views

Is lattice-based cryptography relevant in symmetric cryptography?

I've seen that lattice-based cryptography works well with public key cryptography as well as cryptographic hashing algorithms, but does it apply to symmetric key cryptography?
1
vote
1answer
111 views

What is the most efficient lattice problem solving algorithm?

I've recently become very interested in post-quantum cryptography, specifically lattice-based cryptography. As of this posting there exists no quantum algorithm that can perform better at solving ...
2
votes
1answer
82 views

Is there an equivalent to an RSA UFO in lattice-based cryptography?

So there's this concept within the realm of RSA cryptography called an RSA UFO. It is an extremely important function in the context of cryptocurrency. When starting up a cryptocurrency the creator(s) ...
3
votes
1answer
143 views

What makes lattice-based cryptography quantum-resistant?

As opposed to RSA or elliptic curve cryptography?
3
votes
1answer
87 views

Gentry-Halevi’s Fully-Homomorphic Encryption and hermite factor

In section 7.2, page 18 in Chen-Nguyen paper regarding BKZ 2.0, they point out different Hermite factors related to Gentry-Halevi FHE. More precisely, it is said that the critical Hermite factor for ...

1
2 3 4 5 6