Questions tagged [post-quantum-cryptography]

Cryptography that will remain secure should large-scale quantum computing become feasible. Based on hard problems with no known polynomial-time quantum algorithm (e.g., Shor's algorithm).

Filter by
Sorted by
Tagged with
1
vote
1answer
20 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
0answers
26 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!
0
votes
0answers
37 views

Is there anyone intrested in quantum fully homomorphic encryption?

Recently, I have read a paper named "Classical Homomorphic Encryption for Quantum Circuits". The author claims a quantum scheme that can apply an encrypted (like GSW encryption) bit to ...
3
votes
1answer
107 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 ...
19
votes
2answers
5k views

Largest integer factored by Shor's algorithm?

I'm studying Shor's quantum factoring algorithm. I was wondering what the largest integer is which they were able to factor with a small quantum computer. Does anybody has an idea about this?
3
votes
2answers
424 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 (...
7
votes
2answers
199 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....
0
votes
0answers
27 views

BIKE: Bit Flipping Key Encapsulation - Inverse encryption / decryption

I'm trying to understand white paper about BIKE Asymmetric crypt. And actually read about the inverse matrix that needs to be produced for decryption. My concern is: Can I actually encrypt data with ...
2
votes
1answer
59 views

Complexity of Gaussian Elimination over a Finite Field

I read somewhere that the complexity of solving a Linear $n\times n$ system over a Finite Field $\Bbb F_q$ using Gaussian Elimination is $\mathcal{O}(n^3)$ operations in $\Bbb F_q$. What's the role of ...
3
votes
1answer
55 views

Quantum-secure obfuscation

My question is a follow-up to a recent question regarding quantum-secure time-lock puzzles (TLPs). TLPs can be built (in principle) from indistinguishability obfuscation (iO) [BGJ+,BGL+] as noted in ...
2
votes
1answer
50 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 $...
3
votes
2answers
89 views

Ring-LWE in other fields

Can someone please tell me why in R-LWE we always make use of Cyclotomic fields, and specially those with degree equals to a power of $2$? Can we use another fields without losing in hardness of the ...
2
votes
0answers
41 views

Avoid storing the whole message when signing with SPHINCS+

Unlike pretty much every other signature scheme that I am aware of (excluding Picnic, the original SPHINCS, and SPHINCS-gravity) SPHINCS+ requires that the whole message be available during the ...
3
votes
3answers
231 views

Is there a quantum-safe time lock?

Most successive squaring time lock puzzles I've seen appear to be broken by Shor's algorithm. Is there another practical and efficient time lock protocol that is not broken by Shor's algorithm? If not,...
3
votes
0answers
48 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 < ||...
1
vote
0answers
61 views

Quantum computers and elliptic curves

I know, that quantum computers can theoretically break the discrete logarithm problem using the shor algorithm. The problem with quantum computers is not the time, but the space ( the needed qubits ). ...
0
votes
1answer
44 views

How SPHINCS+ Hash Signature ADRS structure define

can anyone help me to elaborate the structure of ADRS with example ( tree ADRS, layer ADRS, keypair ADRS etc)used to generate root SPHINCS+ signature. Also can some one help me to describe tree hash ...
1
vote
1answer
241 views

What basic knowledge is required to understand SIKE?

I'm interested in learning about Supersingular Isogeny based Key Encapsulation mechanism. Currently, I only know all the basic knowledge about how standard Elliptic Curve Cryptography, works, using ...
3
votes
1answer
203 views

FHE over the integers - Is that paper's scheme known to be insecure against quantum adversaries?

I was reading the paper Fully Homomorphic Encryption over the Integers, and started wondering if there is a known quantum attack on their main scheme, because There is an efficient quantum attack on ...
1
vote
0answers
50 views

Non-post quantum primitives in MPC protocols: for and against?

Is it acceptable from a security point of view for an MPC protocol to use non-post quantum cryptographic primitives? Note that except for secret sharing, which provides information-theoretic security, ...
1
vote
0answers
78 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 ...
3
votes
1answer
3k views

Is Diffie-Hellman post-quantum secure?

If Alice and Bob have a secure channel for key exchange and Mallory doesn't man-in-the-middle attack them, but in the future eavesdrops on their connection and sees the key exchange, can Mallory break ...
2
votes
1answer
172 views

Chaining one-time signatures

To introduce the notation for the question, consider a one-time signature algorithm: There are a private signing key $sk$ and a corresponding public key $pk$, generated by $Gen(seed)$. To sign a ...
1
vote
0answers
30 views

Understanding a method of vector multiplication

Recently, I attempted to implement the HQC Post-Quantum KEM in (almost) pure python. In the scheme specification whitepaper, it states the following: Here is a simplified version of the function I ...
3
votes
0answers
108 views

Check validity of generated parameters for SIDH

In section 4.1 of the paper Towards quantum-resistant Cryptosystems From Supersingular Elliptic Curve Isogenies by Feo, Jao and Plût it is described how you generate valid parameters for the SIDH ...
1
vote
0answers
53 views

Post-quantum crypto based on undecidable problems

Usual post-quantum crypto, like the isogeny-based algorithm, has its value lying in that no one yet has found a quick way to break it with quantum computer. This makes me wonder why don't we build ...
10
votes
3answers
2k views

Is full Homomorphic encryption quantum resistant?

Since most of our asymmetric encryption algorithms are going to be out-of-date in a couple of year due to Shor's algorithm, I was wondering about the future of FHE schemes. I have found this paper, ...
5
votes
2answers
420 views

Key Exchange vs Key Encapsulation

From what I understand, the steps of a key exchange protocol are Alice and Bob each encrypt something using their public key and private key and send the result to each other Alice and Bob each do ...
4
votes
2answers
166 views

what does output parameters of lwe estimator stands for?

I want to use lwe estimator to find classical and quantum security of my proposed key exchange protocol. On this website, I want to understand the output of sage code on lwe estimator given bellow. ...
4
votes
0answers
94 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
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
2answers
65 views

What is the implication for differential privacy if $\epsilon = 0$?

In pure differential privacy, the parameter $\epsilon$ represents the desired privacy loss. The smaller the $\epsilon$ is, the more privacy we can obtain. What happens when we want the privacy loss $\...
6
votes
0answers
110 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}...
3
votes
1answer
65 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 ...
0
votes
0answers
39 views

PQC schemes & theory on academic courses

This question doesn't cover any technical aspects of PQC but I would want to know if undergraduate computer scientists study at a good level any of the available PQC schemes in literature during their ...
28
votes
3answers
12k views

Are cryptographic hash functions quantum secure?

I was reading a paper related to post quantum cryptography. It says that RSA, ECC and ElGamal encryption schemes would be obsolete with the advent of quantum computers. But the hash functions can ...
2
votes
0answers
71 views

Using XL Algorithm to solve overdetermined systems, simple example required

Can someone give an example of how the XL algorithm is used to solve an overdetermined system as apposed to just a general case? I have a fairly good understanding of how steps of the algorithm work, ...
1
vote
1answer
66 views

What are the security implications of knowing the private polynomial $\mathcal{F}$

First, affine transformations $S,T$ are defined by $S=A_1+v_s, T=A_2+v_t$. Let the private polynomial function $\mathcal{F}$ be known. The short description of the public key map is $P(X) = T \circ \...
1
vote
1answer
35 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}_{...
2
votes
2answers
81 views

If we don't trust current PQ algorithms enough to use them on their own why should we trust them for a hybrid?

The second question my students have asked me about PQ/Classical Hybrids is about why we think they are good for protecting information with a long security lifetime. If we don't trust current PQ ...
0
votes
1answer
92 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 ...
6
votes
1answer
128 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 ...
0
votes
0answers
93 views

Is chaos-based cryptography quantum-resistant?

Recently, I have been learning chaos-based cryptography. Is the Chebyshev map-based encryption algorithm quantum-resistant?
0
votes
1answer
56 views

Suppose $H(X) \rightarrow Y$ is collision resistant. Is $H$ also one-way?

If we have $H(X) \rightarrow Y$ and it is collision resistant. Can we say that $H$ is also one-way? And if that is true can you give me an example?
0
votes
0answers
118 views

Is XChacha20 - Poly1305 Quantum resistant?

This is a question just out of curiosity, as I am a newbie to Post Quantum Cryptography. I have read several articles where they emphasize that current standardised symmetric encryption algorithms (...
1
vote
0answers
39 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 ...
1
vote
0answers
40 views

Primal and dual attack against NTRU

I am looking at the primal attack against schemes in the second round of the NIST Post-Quantum Standardization Project. The cost of primal attack usually comes from an estimate described in NewHope ...
6
votes
2answers
429 views

Can Grover's Algorithm be combined with a meet-in-the-middle attack?

We all know and love the meet-in-the-middle attack, which basically makes double encryption pointless using a time-memory trade-off. Now, the NSA recently recommended to use double encryption to ...
1
vote
0answers
68 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\...

1
2 3 4 5
8