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).

71 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
11
votes
0answers
452 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 ...
8
votes
0answers
131 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" - ...
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}...
5
votes
0answers
540 views

How does post quantum key exchange in OpenSSH 8 work?

OpenSSH 8 supports a post quantum KEX, namely sntrup4591761x25519-sha512@tinyssh.org It says in its description that it is basically NTRU + ECC X25519. However, I have tried but cannot understand how ...
5
votes
0answers
103 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
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 ...
4
votes
0answers
62 views

Help with cryptanalysis of branching in schemes based on Multivariate Public Key Cryptography

I'm familiarized with the structure of branching found in Multivariate Cryptography, as it allows us to partition a $n$-tuple over $F_{q}$ into a $k$-tuple where the $i$-th element is in $F_{q^{\...
4
votes
0answers
89 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 $(-\...
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 < ||...
3
votes
0answers
67 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?
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 ...
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 ...
3
votes
0answers
80 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, ...
3
votes
0answers
108 views

can a quantum or classical computer perform “MATRIX factorisation”?

I know that thanks to Shor's algorithm, integer factorisation is easy on quantum computers, yet hard on classical computers. But what if I have two MATRICES, A and B, and compute the product N = A * ...
3
votes
0answers
220 views

How can I calculate the security level provided by a supersingular Elliptic Curve?

I want to know what security level is provided by an elliptic curve used in Supersingular isogeny Diffie–Hellman key exchange (SIDH). Is there any mathematical convention to follow or by looking at ...
3
votes
0answers
60 views

How can I obtain a code with same weight codewords?

I want to implement "A new one-time signature scheme from syndrome decoding". My first challenge is how to obtain $P$. $P$ is a generator matrix whose codewords have weight not exceeding an integer ...
3
votes
0answers
176 views

In NTRU, if $N$ is not prime, prove that one can recover the private key by solving a lattice problem in dimension lower than $2N$

In the NTRU cryptosystem, it is suggested to take $N$ prime. I want to understand why. In Jeffrey Hoffstein, Jill Pipher and H. Silverman An Introduction to Mathematical Cryptography, they suggest (...
3
votes
0answers
83 views

On a proposition in NTRU original paper: $\gamma_1 |f|_2 |g|_2 \leq |f \circledast g|_\infty \leq \gamma_2 |f|_2 |g|_2$

In the original paper of NTRU cryptosystem, we have the following proposition (that is said to be suggested by Don Coppersmith): For any $\epsilon > 0$, there are constants $\gamma_1,\gamma_2 &...
3
votes
0answers
101 views

Best Attack Against HFE cryptosystem

I am looking for the best know attack against HFE cryptosystem. Reading this paper DEGREE OF REGULARITY FOR HFE I found the next claim However, Faugere and Joux demonstrated that we can solve and ...
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 ...
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 ...
2
votes
0answers
58 views

Post-quantum aggregate / multi signatures

Are there any practical post-quantum aggregate / multi signatures? Currently, the aggregate / multi signature schemes seem to be limited to pre-quantum elliptic curve assumptions only, e.g., [BDN18], [...
2
votes
0answers
45 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{...
2
votes
0answers
95 views

A proposal for randomization of Niederreiter cryptosystem

The Niederreiter cryptosystem is a public key cryptosystem using Goppa code. Unfortunately it it is insecure unless it is a binary code. So I thought I could insert random linear codes into randomly ...
2
votes
0answers
45 views

IETF Recommendations for preparation for PQC- clarify in what way they are referring to bits

Which bits are being referred to when it is said by the IETF, "Continue to avoid baking-in algorithms, either explicitly or implicitly (e.g. via maximum field sizes)" ? Does that mean leave enough ...
2
votes
0answers
77 views

Is NIST testing all the round 2 submissions to quantum-resistant crypto?

Is NIST confirming the self-published quantum-resistant crypto round 2 data and do they make that available to the public when they do?
2
votes
0answers
270 views

Quantum Resistant Algorithms and types: PKE vs PKEs vs KEM vs KEMs vs DSS

I am trying to wrap my head around the second round Quantum Resistant Algorithm candidates currently under the NIST PQC Effort. Can someone verify if the following is a correct summary of the 17-...
2
votes
0answers
65 views

Are there any one-way operations that could be used for Diffie-Hellman post-quantum? (See criteria)

With quantum-computers looming, there is a need for Public Key Cryptosystems that can withstand attacks by quantum-computers. Are there any known one-way operations that fit the following criteria? ...
2
votes
0answers
178 views

Post quantum zkSNARK?

Do there exist any zkSNARK constructions that are based on post quantum cryptography? The encryption scheme used in the zkSNARK that is employed in Zcash for instance uses an encryption scheme of the ...
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, ...
2
votes
0answers
59 views

Does secure LWE implementation leak bit information?

We know RSA leaks one bit about the factors and improper yet secure implementations of Discrete Logarithm leak one bit about the discrete logarithm. Does LWE leak any information?
2
votes
0answers
446 views

XTS-AES-128 and Grover's algorithm

AES-128 is considered weak against quantum computers because Grover's algorithm effectively halves its key length to unacceptable 64 bits. XTS-AES-128 as described in IEEE 1619-2007 doubles key ...
2
votes
0answers
148 views

Security analysis of LWE with unequal error and secret distribution

Analysis of security of recent LWE based Key-exchange schemes, the error and secret vector is always chosen from the same Gaussian distribution. What will be the impact on the security if $\sigma_s\...
2
votes
0answers
73 views

One-Time-Signature based codes

I'm trying to understand the sentence in bold, in the follow paragraph of A new one-time signature scheme from syndrome decoding Keygen: Given a security parameter $\lambda$, choose a suitable ...
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 ). ...
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 ...
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 ...
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 ...
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
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 ...
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
vote
0answers
42 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 ...
1
vote
0answers
60 views

Help on Algebraic Side Channel Attacks

I am a master student in computer security, I am preparing a dissertation thesis in the theme is: Algebraic cryptanalys by auxiliary channels, I need reference on this theme (book, thesis, ...), and ...
1
vote
0answers
115 views

How to find kernel of isogeny from the dual isogeny

Let $E$ be a supersingular elliptic curve over $\mathbb{F}_{p^2}$, where $p = \ell_A^{e_A} \ell_B^{e_B} f \pm 1$ for some primes $\ell_A, \ell_B$. Let $R \in E[\ell_A^{e_A}]$ be a point of order $\...
1
vote
0answers
142 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 ...
1
vote
0answers
36 views

Precise Definition of 1-out-of-2 Oblivious Transfer

What's the precise definition for 1-out-of-2 OT? and what's the best way to show that it can't be achieved under unconditionally secure setting? I am reading about it and just couldn't get my head ...
1
vote
0answers
177 views

Using NewHope key exchange between browser and BouncyCastle implementation

I have been looking around with some new Post-Quantum secure key exchange methods, such as McEliece, NTRU and SIDH, but none of these seem to be working nicely between the browser and the BouncyCastle ...
1
vote
0answers
29 views

Why in the Rao-Nam private key version of McEliece scheme, P matrix is multiplied after adding error vector?

The private key version of McEliece known as Rao-Nam scheme, the encryption is done as c = (mSG + e)P. What is the need for applying permutation matrix on the error vector?