All Questions
Tagged with lattice-crypto post-quantum-cryptography
178 questions
0
votes
1
answer
244
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 ...
- 63
2
votes
1
answer
211
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 ...
- 381
4
votes
1
answer
197
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 ...
- 505
1
vote
1
answer
83
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}...
- 381
0
votes
1
answer
54
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!
- 505
3
votes
2
answers
541
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 (...
- 381
3
votes
1
answer
113
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 $...
- 505
12
votes
3
answers
1k
views
Error-correcting Code VS Lattice-based Crypto
I'm not an expert in PQ-crypto, but as I understand error-correcting code and lattice-based crypto, the cryptographic assumptions are very similar. The key difference for me is the nature of the noise....
- 2,635
3
votes
0
answers
61
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 < ||...
- 762
1
vote
0
answers
101
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 ...
- 1,080
8
votes
0
answers
316
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 ...
- 315
1
vote
0
answers
31
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 ...
- 113
1
vote
1
answer
78
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 ...
- 341
3
votes
1
answer
212
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 ...
- 33
9
votes
0
answers
874
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,614
2
votes
1
answer
156
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}_{...
- 341
3
votes
0
answers
285
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 ...
- 167
1
vote
1
answer
92
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\...
3
votes
0
answers
108
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 ...
- 93
1
vote
1
answer
328
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 ...
- 93
7
votes
1
answer
687
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 ...
- 165
3
votes
1
answer
123
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 ...
- 93
7
votes
1
answer
365
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, ...
- 448
2
votes
0
answers
76
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{...
- 61
1
vote
1
answer
233
views
Explanation of the tables found in Kyber round1 code?
The precomp.c file in Kyber NIST round 1 submission has three tables, could you please let me know how to generate these three tables? If I want to understand how ...
- 11
3
votes
0
answers
73
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?
- 87
4
votes
1
answer
242
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 ...
- 61
2
votes
0
answers
578
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 ...
- 424
2
votes
1
answer
108
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 = ...
- 438
3
votes
1
answer
174
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 ...
- 41
1
vote
0
answers
465
views
RSA vs. Super Computer vs. Quantum Computer [closed]
I know that RSA is known to be secure in the current landscape of computing, and I know that RSA is known to be broken in the world of quantum computing and cryptography.
I have two questions, can ...
- 111
2
votes
1
answer
215
views
Can I connect the hardness of a linear short integer solution problem to that of SIS problem?
As we know, SIS problem is defined as: for a function $f_A(s)$=$As$, where $A$ is a fixed, randomly-chosen matrix in $\mathbb{Z}_q^{r \times n}$, it is hard to find elements $s \in \mathbb{Z}_q^{n}$ ...
- 33
1
vote
0
answers
578
views
Dilithium signature scheme - Public key derivation
I was looking at post quantum signature schemes, and I came across Dilithium(https://github.com/pq-crystals/dilithium), and our system currently runs on Ed25519 which based on my question can easily ...
5
votes
0
answers
300
views
Why is it safe to generate the secret key and masking vectors using rejection sampling in CRYSTALS-Dilithium?
In CRYSTALS-Dilithium module lattice-based digital signatures, the secret key vectors $s_1, s_2$ with coefficients in $[-\eta, \eta]$ and the signature masking vector $y$ with coefficients in $(-\...
- 438
9
votes
0
answers
177
views
Differences between “NewHope” and “NewHope-simple”
The well-known paper described a key exchange (KE) scheme named "NewHope" on USENIX 2016. The authors then proposed "NewHope-Simple" - a PKE/KEM scheme. They also submitted "NewHope for NIST" - ...
- 187
4
votes
1
answer
373
views
Adapting LWE Trapdoors for Ring-LWE
In the paper Trapdoors for Lattices: Simpler, Tighter, Faster, Smaller by Micciancio and Peikert, they present the following theorem about the existence of trapdoor for LWE.
Theorem 5.1: There is an ...
- 516
7
votes
1
answer
302
views
IND-CCA2 post-quantum key exchange
QUIC requires that servers reuse keys so that session resumption works. That breaks many post-quantum key exchange systems.
I am looking for a post-quantum key exchange algorithm with the following ...
- 4,813
2
votes
1
answer
298
views
Original NTRU : How to calculate the size of private key?
In the original NTRU paper：NTRU: A Ring-Based Public Key Cryptosystem,1996, the author proposes 3 choices of implementation parameters: moderate, high and highest. Let's take moderate security level ...
- 187
14
votes
1
answer
2k
views
Is lattice-based cryptography practical?
How viable is lattice-based cryptography in a "practical" setting?
It has been said that lattice-based cryptography would be a "post-quantum" cryptography scheme, but is it feasibly implementable?
- 313
2
votes
2
answers
438
views
Lattice generation from basis?
This might be a very short very obvious answer, because I've yet to come across a question similar to mine in my searches.
Given a lattice L, with a good base B1 and a bad base B2, what stops an ...
- 357
9
votes
1
answer
2k
views
Discrete Gaussian Sampling role in Lattice-Based Crypto?
I'm reading up on how post-quantum cryptography works, and stumbled upon the notion of discrete Gaussian sampling. However, I can't understand where it fits in the greater picture - currently it feels ...
- 357
3
votes
1
answer
285
views
Effect of tail cutting and precision of discrete Gaussian sampling on LWE / Ring-LWE security
How does tail cutting and precision of discrete Gaussian sampling implementations affect LWE / Ring-LWE security? Is there a rule of thumb or guideline for choosing the tail cut and the precision for ...
- 438
5
votes
0
answers
128
views
How does error distribution affect security in lattices?
It's easy to see that the crucial part of any lattice scheme is the added error. And different schemes seem to use different error distributions, some use Gaussian some use centered Binomial. Though, ...
user4936
3
votes
1
answer
372
views
Minkowski's theorem in lattice-based cryptography
I am studying basic lattice-based cryptography. In the course given by O. Regev, on page number 7, there is Claim 1 and Corollary 2 (Minkowski's First Theorem), both of which are difficult for me to ...
- 207
13
votes
0
answers
711
views
Potential Flaws With Lattice Based Cryptography?
From researching post-quantum cryptographic schemes it seems hash-based and lattice-based algorithms are the most promising (MQ-based seem to be covered by patents and have more potential unknowns ...
- 589
7
votes
1
answer
3k
views
What is the difference between Module-LWE and Ring-LWE?
Recently, the CRYSTALS lattice-based cryptographic suite has been published, which is based on "module lattices". What is Module-LWE? How is it different from Ring-LWE?
- 438
3
votes
1
answer
140
views
Why don't we use an Extendable Output Function to efficiently store the public key of Regev's LWE-based encryption scheme over standard lattices?
In LWE-based schemes the public key is generated by choosing a random matrix (or polynomial) $A$, and outputting the pair $(A, b = A\cdot s + e)$, where $s$ and $e$ are vectors/polynomials with ...
- 33
13
votes
5
answers
3k
views
Why is lattice-based cryptography believed to be hard against quantum computer?
Why is lattice-based cryptography believed to be hard against quantum computer?
Learning With Errors(LWE) problem (reduction to SVP) is just one example.
Can you provide some intuition of the ...
- 1,685
4
votes
2
answers
661
views
Why does Learning With Errors require a bunch of samples?
Solving Learning with Errors(LWE) with average case complexity is as hard as solving the SVP with worst case complexity.
LWE requires $n$ dimensional lattice and $m$ samples of it, and Decisional-LWE ...
- 1,685
4
votes
1
answer
611
views
Dilithium signature scheme and timing attacks – Does the running time actually depend on the secret key?
The paper “CRYSTALS – Dilithium: Digital Signatures from Module Lattices” (by Léo Ducas, Tancrède Lepoint, Vadim Lyubashevsky, Peter Schwabe, Gregor Seiler, and Damien Stehlé) introduces a digital ...
- 4,813