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
15
votes
1answer
14k views

Are hash functions strong against quantum cryptanalysis and/or independent enough of mathematics?

I work on ethereum and other blockchain technologies. And seeing that quantum pc's are someday going to see the light I have some questions / doubts. I was wondering if hash functions are strong ...
23
votes
4answers
4k views

How will Cryptography be changed by Quantum Computing?

I realise this isn't a 'yes or no' question, and I apologise for asking something that could be seen as a discussion thread, but I had to ask. I'm currently doing an EPQ in CS (specifically how QC ...
50
votes
10answers
13k views

Now that quantum computers have been out for a while, has RSA been cracked?

D-wave systems has released a commercially viable quantum computer. This means in theory, that all asymmetric encryption algorithms — such as RSA — are now useless due to the speed at which quantum ...
32
votes
5answers
4k views

What security do Cryptographic Sponges offer against generic quantum attacks?

In the face of non-quantum attacker, Keccak[r=1088,c=512] with 512 bits of output provides: Collision resistance up to $2^{256}$ operations Preimage resistance up to $2^{256}$ operations Second ...
32
votes
1answer
26k views

Is AES-256 a post-quantum secure cipher or not?

We know Grover's algorithm speedup brute-force attacks two times faster in block ciphers (e.g brute-forcing 128-bit keys take $2^{64}$ operations, not $2^{128}$). That explains why we are using 256-...
32
votes
3answers
15k 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 ...
5
votes
4answers
965 views

What telltale signs would indicate that quantum computers are about to become dangerous to classical cryptography?

What would be telltale signs that quantum computers become imminent and sizable danger to classical cryptography in commercial applications ? Make classical cryptography consist of symmetric ...
25
votes
5answers
7k views

What is the post-quantum cryptography alternative to Diffie-Hellman?

Post-quantum cryptography concentrates on cryptographic algorithms that remain secure in the face of large scale quantum computers. In general, the main focus seems to be on public-key encryption ...
10
votes
1answer
731 views

Hash-based asymmetrical encryption (not digital signature) schemes?

In the Wikipedia article or another article about post-quantum crypto there's a plenty of information about hash-based signatures. But where are hash-based ecryption with pubkey? But, over the long-...
10
votes
1answer
2k views

For a one-time pad, which MAC method is information-theoretically secure?

In the the main post about MAC methods it mentions a few methods: Authenticate And Encrypt: The sender computes a MAC of the plaintext, encrypts the plaintext, and then appends the MAC to the ...
8
votes
1answer
9k views

How long does it take a quantum computer to brute force AES?

I understand that using Grover's algorithm it only requires $2^{64}$ lookups for a 128 bit AES encryption, leading people to say we need to increase to 256 bit keys. But how long would it actually ...
30
votes
4answers
17k views

Assuming a 1024qb quantum computer, how long to brute force 1024bit RSA, 256bit AES and 512bit SHA512

Assuming in the future there was a functioning 1024 qubit quantum supercomputer and it could run Shor's algorithm or Grover's algorithm to crack encryption very quickly. I'm interested in how the ...
17
votes
3answers
3k views

What exactly is the impact of the hidden subgroup problem on cryptography?

I understand my group theory (allegedly), so I can make partial sense of The Hidden Subgroup problem: Given a group $G$, a subgroup $H \leq G$, and a set $X$, we say a function $f : G \Rightarrow ...
16
votes
2answers
884 views

Can Grover's algorithm be parallelized?

Grover's algorithm can search an unordered list of length $N$ in time $\sqrt{N}$ on a quantum computer. Applied to cryptography, this means that it can recover n-bit keys and find preimages for n-bit ...
6
votes
1answer
648 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 ...
11
votes
4answers
1k views

Is key size the only barrier to the adoption of the McEliece cryptosystem, or is it considered broken/potentially vulnerable?

A recent paper showed that the McEliece cryptosystem is not, unlike RSA and other cryptosystems, weakened as drastically by quantum computing because strong Fourier sampling cannot solve the hidden ...
10
votes
2answers
1k views

Why is pqRSA in the NIST PQC submissions?

In the NIST post-quantum cryptography workshop, the round one submissions included pqRSA. If memory serves, this is an implementation of RSA using the product of a very large number of 4096-bit primes ...
4
votes
1answer
910 views

Shor algorithm and schnorr signature in ed25519

Does the application of Shor's algorithm in any way relate/affect the schnorr signature in ed25519?
3
votes
1answer
332 views

What is post Quantum Cryptography?

Post-quantum cryptography is cryptography under the assumption that the attacker has a large quantum computer; post-quantum cryptosystems strive to remain secure even in this scenario. Post-quantum ...
6
votes
2answers
287 views

LWE: Round a continuous Gaussian to a true Discrete Gaussian

Short version: how is it possible to round a continuous Gaussian into a true discrete Gaussian (usually denoted $\mathcal{D}_{\mathbb{Z},\alpha q}$)? The goal is to obtain a reduction from continuous ...
7
votes
2answers
581 views

Is there any quantum resistant pen-and-paper or mind cipher?

I know about VIC and Solitare but as I understand they are not quantum resistant ciphers. Is there any quantum resistant pen-and-paper or mind cipher?
2
votes
2answers
214 views

How would low-precision Gaussian sampling impact the security of BLISS?

For digital signature, I implemented BLISS in my cryptographic suite, and wrote the Gaussian sampler based on Lattice Signatures and Bimodal Gaussians. But unlike the reference implementation and ...
32
votes
3answers
3k views

New quantum attack on lattices (or Shor strikes again)?

Lior Eldar and Peter W. Shor published a paper on arXiv.org in which they present a new quantum algorithm against a variant of BDD. They claim that their new algorithm can efficiently solve the ...
19
votes
1answer
11k views

How many qubits are required to break RSA 2048 or 4096 with a universal quantum computer?

So in the news this week, IBM have created a universal quantum computer with 5 fully functional qubits. Logic and Moore's law dictates they will be able to scale this up to a lot more qubits within a ...
18
votes
3answers
2k views

Is braid-based cryptography proven insecure when looking towards post-quantum cryptography?

Braid groups has drawn the attention of cryptographers for a few years, as a promising platform for post-quantum cryptographic protocols. The security of the proposed schemes mostly relied on ...
30
votes
1answer
4k views

Proof for the SHA3 claim that 256 bit security is "post-quantum sufficient"?

On page 14 of "Keccak and the SHA-3 Standardization" (February 6, 2013) it says: Instantiation of a sponge function the permutation KECCAK-f 7 permutations: b → {25,50,100,200,400,800,...
3
votes
3answers
324 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,...
9
votes
3answers
6k views

Winternitz One-Time Signature

I am reading the page 38 in this "Post Quantum Cryptography" book (Equations 8 and 9). My question is, why to compute the verification key $Y$, $f$ is applied $2^w-1$ times? Are there any security ...
7
votes
3answers
1k views

What is a purpose of reducing lattice basis?

This may be too broad question but it is not. I have been studying lattices for few months now, more specifically I studied: Lattice problems ($SVP$, $CVP$ and etc.) Lattice cryptography in post ...
2
votes
2answers
437 views

After Google's breakthrough: When will quantum computers break today's encryption?

Google announced a breakthrough on the way to building usable and useful quantum computers. Since I'm not a cryptographer, I wanted to ask when quantum computers will be able to break the crypto ...
9
votes
5answers
929 views

Are there any applications of Quantum Computation to Cryptography? (besides Cryptanalysis)

I know that people may be yelling "of course!" at the title of the question, but my concern is not about how to construct quantum-resistant primitives, but rather how to use the power of quantum ...
8
votes
2answers
386 views

Is there a partially homomorphic quantum secure public key cryptosystem with IND-CCA1 security?

I recentely asked "IND-CCA1 RSA padding?" about whether there is a IND-CCA1 secure variant of RSA. The original version of the question also allowed usage of ECC which would allow usage of ElGamal, ...
6
votes
3answers
1k views

Are there any quantum-resistant symmetric encryption schemes?

It seems that quite a few currently available encryption schemes will possibly be broken by quantum computing. Are there any symmetric encryption schemes that will remain unbroken (either because of ...
6
votes
1answer
254 views

What are the implications of quantum collision search algorithms like Ambainis for collision-resistant hash functions?

I just stumbled onto a series of 2017 papers about applying the Ambainis quantum collision-finding algorithm to hash functions. (disclaimer: I haven't read all of them in full yet): Post-quantum ...
5
votes
1answer
2k views

Does perfect forward secrecy (using DH or ECDH) imply quantum resistance?

Does perfect forwarding secrecy, as used for e.g. the DHE_ and ECDHE_ TLS ciphersuites make it impossible for quantum analysis ...
3
votes
1answer
199 views

Post-Quantum security of Pseudo-Random Functions

I am wondering what is the exact post-quantum security of a PRF. I know that for most symmetric mechanisms, it is assumed it is sufficient to double the key size, but I am looking for a more precise ...
3
votes
2answers
618 views

Are hash trees an alternative, quantum-resistant signature scheme which can replace RSA?

Can hash trees provide quantum resistant signatures to replace RSA for signing securely? What is the key size and how many times can we use same key?
1
vote
1answer
366 views

Post-Quantum Primitives' Object Sizes

1. Alternative Cryptographic Primitives For quite a while, I've been thinking is it possible to "craft" a cryptographic primitive (like ECC) suitable for the purposes of post-quantum cryptography, ...
11
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, ...
8
votes
1answer
822 views

Which MAC scheme is quantum resistant?

will HMAC survive Grover algorithm ? if not then which MAC scheme provide post-quantum security ?
8
votes
3answers
591 views

SAT-Based Public Key Cryptosystem

I am researching post quantum cryptography and I've stumbled upon this article which presents a PKC with an np-complete (SAT) trapdoor. I was wondering if someone could help me understand the way the ...
6
votes
1answer
1k views

Implementations of Ntru TLS

Has anyone come across any implementations of Ntru TLS? I'm working a project for uni that does quantum secure encryption. It relies on a mix of Ntru & AES, but I can't find an implementation of ...
5
votes
1answer
218 views

$L^3$ Grover search of NTRU variants

I was reading a text on cryptology by Wayne Patterson and came across the $L^3$ algorithm which reduces integer lattices with respect to their base. I've also read on the NIST CFP A8 that attacks ...
5
votes
1answer
1k views

Can there be a need for 1024-bit (symmetric) encryption?

I think we are all aware of the CAESAR-competition. Now the aim of this competition is to select a (portfolio of) winner(s) which provide authenticated encryption. I'll now assume that the results ...
5
votes
1answer
2k views

How can Shor's Algorithm be applied to ECC?

I have not found a specific answer to this question on here. Shor's algorithm can be used to factorize a large (semi)prime $N$ by reducing the task to period-finding of a function $f(x)=x^a$ mod $N$. ...
4
votes
2answers
255 views

Small Quantum Signatures - Reality check needed

I've been thinking a bit lately about how to get quantum resistant signatures fast and (relatively) small. One idea I've been keen on exploring is finding a crypto PRNG that allows fast-forwarding, e....
2
votes
1answer
168 views

Why does lattice KEX not require sampling with high precision?

I was reading the NewHope paper, and I see that they are using Binomial distribution and not a discrete Gaussian distribution as was used by BCNS. I also remember hearing somewhere that lattice key ...
2
votes
5answers
5k views

Using one-way hash functions as the encryption method

Suppose two parties want to communicate securely with each other (Bob and Alice) using a simple messaging system in English. There are approximately 180,000 currently used words in the English ...
1
vote
1answer
427 views

Real world performance of (still theoretical) Grover's Algorithm

Grover's Algorithm is a quantum algorithm for searching "black box" functions and could be used to reduce the search space for things like symmetric ciphers and hashes by as much as half (quadratic ...
0
votes
0answers
113 views

Is chaos-based cryptography quantum-resistant?

Recently, I have been learning chaos-based cryptography. Is the Chebyshev map-based encryption algorithm quantum-resistant?