Questions tagged [lattice-crypto]
Lattice-cryptography is the study and use of lattice problems applied to cryptography.
520
questions
0
votes
0
answers
44
views
What is this parameter? in Lyubashevsky's ID-scheme
I am studying Lybashevsky's ID-scheme from the article Fiat-Shamir With Aborts: Applications to Lattice and Factoring-Based Signatures(https://www.iacr.org/archive/asiacrypt2009/59120596/59120596.pdf) ...
- 315
1
vote
0
answers
43
views
Public seed expansion for uniform reference strings
Many cryptographic protocols are parameterized by a uniformly random reference string (e.g. the commitment key for Pedersen commitments).
Our goal is to publicly generate the random values of this ...
- 357
1
vote
2
answers
112
views
How "unorthogonal" can a LLL-reduced basis be?
I have been recently studying LLL-reduction. I get from the size condition and Lovasz condition that the basis are guaranteed to be somewhat orthogonal. But I couldn't figure out how orthogonal the ...
- 21
3
votes
1
answer
124
views
The successive minima of a lattice
I am new to lattice theory. I hope(will be grateful) that one could explain to me this claim 7 in REGEV course(this claim appears in this file page 6 : https://cims.nyu.edu/~regev/teaching/...
- 31
3
votes
1
answer
62
views
Why do we need "selective security" for ABE?
The general question is: Why are ABE schemes usually/sometimes proven in the selective-set of attributes model of security? Or even co-selective (both attributes and policy function)? Is it just ...
- 347
1
vote
1
answer
68
views
Hardness of a modified version of NTRU
Let the modified NTRU be $h=f/g$ such that $f$ is not necessarily a short polynomial, is the NTRU problem still hard in this case?
- 421
4
votes
1
answer
94
views
NTRUEncrypt proof that there are plenty of keys
In NTRU algorithm one is supposed generate a vector which is invertible as a polynomial in both $(\mathbb{Z}/p\mathbb{Z})[x]/(x^n-1)$ and $(\mathbb{Z}/q\mathbb{Z})[x]/(x^n-1)$. But is there a ...
0
votes
1
answer
102
views
How to show additive subgroup of $R^n$ is not discrete? [closed]
Suppose we have the additive subgroup of reals generated by $\sqrt{3}$ and $\sqrt{5}$. How would you show you that this subgroup does not form a lattice?
3
votes
1
answer
177
views
Hardness of LWE
I was reading "TFHE Deep Dive" from Ilaria Chillotti, and I am a bit confused over the sample given in 31:08
In the above toy sample, isn't it possible to directly eliminate noise by ...
- 51
5
votes
1
answer
111
views
Which lattice-based encryption scheme/signatures is fundamental?
If I would like to focus on only one signature scheme, and only one encryption based on lattices in a pedagogical context (to introduce the concept of lattice-based crypto to people familiar with ...
- 2,554
2
votes
1
answer
134
views
Avoid CKKS Bootstraping
CKKS is a levelled scheme, because the rescale $\lfloor\frac{x}{\Delta}\rceil$ operation requires truncating a modulus to be efficiently evaluated, and rescale is (usually) needed after every ...
- 51
3
votes
1
answer
327
views
CRYSTALS-KYBER versus FrodoKEM, what makes each of them different than the other?
NIST's main recommendation for encryption/decryption mechanism is CRYSTALS-KYBER. Whereas, the BSI (German equivalent) chooses FrodoKEM.
As far as my knowledge goes both these mechanisms use LWE ...
14
votes
4
answers
6k
views
Kyber and Dilithium explained to primary school students?
Kyber and Dilithium are post-quantum cryptographic designs, but the resources are hard to understand. Is it possible to explain those ciphers to children?
- 341
3
votes
1
answer
162
views
ISIS problem in the case of $m=n$
The Inhomogeneous Short Integer Solution (ISIS) problem is as follows: given an integer $q$, a matrix $A\in \mathbb{Z}^{n\times m}_q$, a vector $b\in \mathbb{Z}^{n}_q$, and a real $\beta$, find an ...
- 421
2
votes
2
answers
132
views
Base of $(n+1)$ elements in a lattice
Does there exist a lattice in $\mathbb{R}^n$, with an independent generative family $(b_1, \dots, b_{n+1})$ of $(n+1)$ vectors (without any loss of generality I suppose $(b_1, \dots, b_{n})$ is a $\...
- 2,554
2
votes
0
answers
51
views
High density SIS and Low density SIS
I am searching for the exact definition of High density SIS and Low density SIS, but there is something unclear about it.
SIS problem is to find $x\in \mathbb{Z}^m$ such that for random $A\in\mathbb{Z}...
- 363
3
votes
1
answer
267
views
NTRUEncrypt fails on sedonion algebra
This question is a direct follow-up (hopefully - the last) of my previous one; please see it for full information. I would like to further generalise NTRU cryptosystem on higher-order algebras. ...
- 189
2
votes
1
answer
114
views
NTRUEncrypt fails on quaternion algebra
This is a follow-up of my previous two questions (1 and 2), might be relevant to check them out first for a full context. I am trying to re-create results from this paper. The basic algorithm is ...
- 189
4
votes
1
answer
99
views
"Shifting" a dual-Regev keypair away from a trapdoored instance
This question pertains to identity-based key encapsulation mechanisms (IB-KEMs). To recap the functionality:
$\mathsf{KeyGen}(1^\lambda) \to (\mathsf{msk}, \mathsf{mpk})$ Generates the master keypair
...
- 290
3
votes
1
answer
208
views
Why is the best way to solve LWE (and Cryptographic related Systems) with SVP (approx)?
Community,
I'm new into lattice based cryptography, and I'm interested about the security of cryptography schemata like Kyber and why the focus of solving this problem lead into solving approx. SVP.
...
- 65
1
vote
1
answer
110
views
Choice of Polynomial Quotient Ring
In (lattice-based) cryptography, the quotient ring $\mathbb{Z}[X]/(X^n+1)$ where $n = 2^e$ is a power of 2 is used in various cryptographic schemes (e.g., CRYSTALS-Kyber). It is my understanding that ...
- 13
1
vote
0
answers
62
views
Good libraries for lattice-crypto [closed]
I'm searching good libraries to manipulate lattice tools to do cryptography.
I'm mainly interested by C/C++. But I'm also interested if it is in python.
- 2,554
3
votes
2
answers
428
views
Break Lattice-Based Cryptography with Variational Quantum Algorithm (only 25 k. Qbits for Kyber1024)?
I am currently writing a seminar paper on Kyber and other lattice-based methods. I was so excited about the lattice-based methods that I also currently searched quantum algorithms to solve the methods....
- 65
3
votes
1
answer
176
views
Question about Theorem 2 in CRYSTALS-Kyber Paper
I have some questions about the Kyber paper, especially about Theorem 2 on page 6, which I would like to ask here. First of all I quote the following theorem from the paper and ask my questions ...
- 393
1
vote
0
answers
29
views
Why the output of G-lattice sampling is spherical in the paper GM18?
In the paper GM18, they say that the sampling algorithm, SampleG, is shown in Figure 2. It takes as input a modulus $q$, an integer variance $s$, a coset $u$ of $\Lambda^{\perp}(g^T )$, and outputs a ...
- 11
1
vote
1
answer
132
views
NTRUEncrypt fails on complex algebra
I am following the NTRUEncrypt cryptosystem as described on the wikipedia. I have implemented it in Sage Math engine (with small problems along the way, but in the end - succesfully resolved) and the ...
- 189
2
votes
2
answers
130
views
Why does NTRUEncrypt fail on different values for large modulus?
I am trying to closely follow the algorithm here (keeping the same variable names) and reconstruct the cryptosystem in Sage Math engine. It seems to work on parameters ...
- 189
1
vote
1
answer
84
views
Decryption analysis for Regev's Public Key Cryptosystem
Regev's Public Key Cryptosystem is defined as follows:
I want to proof the correctness. For this it must be shown that a 0 is decoded correctly and equally that a 1 is decoded correctly. I would ...
- 393
3
votes
1
answer
92
views
Do ideal non-cyclotomic lattices provide better compression in lattice-based cryptography?
Let $f \in \mathbb{Z}[x]$ be an irreducible polynomial of degree $N$ and $q \in \mathbb{N}$. Consider the rings $R := \mathbb{Z}[x]/f$ and $R_q := R/q$. Obviously, an element of $R_q$ can be ...
- 355
2
votes
1
answer
184
views
Question on the proof of correctness in CRYSTALS-Kyber
I am currently trying to follow the proof of correctness in the CRYSTALS-Kyber paper. The following is an excerpt of the proof:
On the one hand, I am interested in how exactly one justifies/argues ...
- 393
2
votes
2
answers
322
views
Compression and Decompression in CRYSTALS-Kyber
I am currently studying the Kyber Paper. I have a question about section 2.2 Compression and Decompression, but first I would like to quote the statement:
Compression and Decompression. We now define ...
- 393
2
votes
1
answer
111
views
How does the SWIFFT algorithm relate finding hash collisions to a lattice problem?
I've been messing around with lattice based cryptography and came across the SWIFFT algorithm, a provably secure cryptographic hash function which has a security proof stating that finding collisions ...
- 25
1
vote
1
answer
200
views
How are public and private keys generated and used for encryption and decryption in a lattice based cryptosystem?
I've recently become quite interested in lattice based cryptosystems, and I wish to understand them more deeply. I have only a rudimentary understanding of the shortest vector problem (SVP), and its ...
- 265
1
vote
1
answer
105
views
Basis matrix of NTRU lattice
In NTRUEncrypt, we choose polynomials $\mathbf f,\mathbf g$ (with suitably small coefficients) such that $\mathbf f$ admits inverses $\mathbf f_p, \mathbf f_q$ with respect to the moduli $p,q$. The ...
2
votes
0
answers
59
views
How do lattice-based proofs with Reed-Solomon codes simultaneously avoid aborts and multiple repeats?
I'm trying to understand how lattice-based schemes with the Reed-Solomon proximity testing work and why the scheme in Bootle's et. al. Fig 3 has no aborts at all (nor big number of repetitions).
TLDR:...
- 528
2
votes
1
answer
140
views
Dense sphere packings and lattice-based cryptography
It is known that there are two popular applications of lattices: dense sphere packings and lattice-based cryptography. I didn't find any information on the Internet about possible interaction of these ...
- 355
2
votes
1
answer
76
views
Lattice-based Signatures and Hashes
Although many different lattice-based signature schemes exist, Hash and Sign signatures schemes, like [GPV08], are prevalent. On the other hand, it is well known that collision-resistant hash ...
0
votes
0
answers
60
views
Question about the definition of the CVP as an approximation variant
I have a question about the definition of the (Closest Vector Problem) CVP. In the literature you can find for example this definition of the approximation variant of CVP:
$CVP_\gamma$, Search: Given ...
- 393
4
votes
1
answer
83
views
Closest Vector Problem in RLWE
I am interested in a polynomial form of the lattice problem Closest Vector Problem (C.V.P), or in other words if C.V.P. can be ''transferred'' to Ring-LWE.
My idea about this question is that a ...
- 65
0
votes
1
answer
50
views
MITM against NTRU
In MITM attacks against the NTRU cryptosystem, we exploit the fact that in the ring of truncated polynomials of degree $n-1$ it holds that $$fg=h\mod q$$ for our secret and public keys $f,h$. The ...
1
vote
1
answer
93
views
value bound of r⋅e for LWE Decryption correctness
For LWE decryption, Someone told me that If we can bound r⋅e by q/4 then we can retrieve M by checking if this is closer to <...
- 121
2
votes
1
answer
154
views
The sum of independent discrete Gaussians is a discrete Gaussian
I am currently learning about lattice-based cryptography and, reading from A Decade of Lattice Cryptography by Peikert, specifically section 2.3, it emerges that
[...] if the parameter s is greater or ...
- 23
1
vote
1
answer
185
views
Encryption and decryption for LWE
For https://asecuritysite.com/public/lwe_ring.pdf#page=9 , could anyone explain how the encryption and decryption for LWE work ?
When I do more reading on https://summerschool-croatia.cs.ru.nl/2015/...
- 121
1
vote
1
answer
77
views
Coefficient Growth
In this survey, I don't understand the necessary of coefficient (paragraph 4.1.2) growth and the choice of $X^d\pm 1 $ or $ X^d \pm X^{d/2} +1 $, since later introduces $q$ which doesn't mention the ...
- 421
0
votes
1
answer
91
views
Comparison of Complete NTT and Incomplete NTT Multiplication
is the complete NTT is the fastest algorithm to multiply polynomials or there are hybrid versions that are faster than complete NTT multiplication?
- 421
2
votes
1
answer
103
views
Statistical Distance and Learning with Rounding
Given an integer $b$ modulo a prime $q$, one can define a `rounding’ function $\lfloor b\rceil_p$ for a prime $p$, $p<q$, as follows: $$\lfloor b\rceil_p = \lfloor \frac{p}{q}\cdot b\rceil\bmod p.$$...
- 381
1
vote
0
answers
202
views
Breaking RSA with P,Q LSB bits using LLL Lattice reduction
This question is someway correlated to Breaking RSA with P,Q LSB bits but more specific.
I would like to use LLL to fully reconstruct P,Q given some LSB bits of P and Q in an arbitrary base B.
Let's ...
- 31
1
vote
1
answer
77
views
Type 1 Trapdoor Sampling in LWE
In the BGN-like LWE cryptosystem, section $2.2$, we sample a $m \times m$ trapdoor matrix $T$ that is full rank such that $TA = 0 \pmod q$.
Suppose that $q$ is prime so we are in a finite field: if $T$...
- 11
4
votes
1
answer
184
views
Finding the exact solution of an LWE instance with a sparse matrix
I already asked a question about the feasibility of LWE when the matrix A is sparse or small here.
Let $q$ be a prime, let $\chi$ be a distribution of $\textit{small}$
elements over $\mathbb{Z}/q$, ...
- 113
2
votes
1
answer
289
views
How to choose the large noise when using noise flooding technique in FHE?
In LWE based multi party FHE schemes, the parties should choose a much larger noise when perform joint decryption. In this paper, the author just said that using noise flooding technique to avoid the ...
- 499