Unanswered Questions
299 questions with no upvoted or accepted answers
16
votes
0
answers
1k
views
Given a 'good' basis for a lattice, how can we solve the CVP?
I'm doing a little bit of reading about lattices. I read that if we can find a 'short' basis for our given lattice, we can solve CVP and SVP very efficiently. However, the paper didn't describe an ...
- 4,736
13
votes
0
answers
723
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 ...
- 95.8k
12
votes
0
answers
690
views
Why SIVP Is Worst Case Problem?
I just started to study lattice Cryptography.
I'm now studying worst-case to average-case reduction for SIS.
In previous question, "worst means any and average means random".
And I wonder why the ...
- 49.7k
11
votes
0
answers
98
views
Decision R-LWE parameters for spherical error with worst-case hardness
In Peikert et al.'s most recent work (STOC 2017) a direct reduction of worst-case lattice problems to decision R-LWE is achieved for $\alpha q \ge 2 \cdot \omega(1)$ (Theorem 6.2), where $\alpha q$ is ...
- 4,082
9
votes
0
answers
935
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,756
9
votes
0
answers
181
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
9
votes
0
answers
532
views
Does there exist trapdoor permutation from lattices?
It seems that the lattice functions are either surjective (SIS) or injective (LWE), due to the error that is basically intended to destroy the structure and provide security. I was wondering whether ...
- 49.7k
8
votes
0
answers
255
views
Boolean-to-arithmetic masking
In the paper "Efficient Boolean-to-Arithmetic Mask Conversion in Hardware" by Aein Rezaei Shahmirzadi and Michael Hutter of PQShield, the authors claim to have found a method for boolean-to-...
- 193
8
votes
0
answers
355
views
Is the complexity of NIST's CTR_DRBG needed for security?
I'm trying to find an efficient deterministic PRF construction that can quickly output a large amount of pseudo-random data from a seed of collected entropy. I ran tests with a contruction based on ...
- 1,155
8
votes
0
answers
327
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 ...
- 15.6k
6
votes
0
answers
113
views
Why do Lattice-based Proof Systems not use the $\ell_2$ norm and canonical embedding?
I was recently reading the paper A non-PCP Approach to Succinct Quantum-Safe Zero-Knowledge.
Among other things, it discusses an adaption of the "folding" technique (from Bulletproofs) to ...
- 14.8k
6
votes
0
answers
281
views
How did Kyber's authors compute the error probability $\delta$?
I'm studying the specification of Kyber that was submitted to NIST PQC Round 3. However, I cannot figure out how they compute the error probability $\delta$ for Kyber 512, 768 and 1024. I have read ...
- 15.6k
6
votes
0
answers
100
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 ...
- 165
6
votes
0
answers
849
views
Is this PRG secure?
$G$ is a secure PRG in range $\{0,1\}^n\rightarrow\{0,1\}^{n+1}$.
Let us define $G'(S)=G(S\oplus G(S)_{1,...,n})$, s.t. $G(S)_{1,...,n}$ is the first n bits of $G(S)$.
Is $G'(S)$ a secure PRG?
...
- 46.6k
5
votes
1
answer
150
views
Ring LWE distribution definitions
This may be a stupid question but I've been stuck on parsing these definitions for a while.
I am reading the paper "On Ideal Lattices and Learning with Errors Over Rings" by Lyubashevsky, ...
CommunityBot
- 1