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
22
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 ...
49
votes
10answers
12k 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 ...
30
votes
6answers
3k 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 ...
11
votes
1answer
7k 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 ...
27
votes
1answer
23k views

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

We know Grover's algorithm speedup brute-force attacks two time 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 bit ...
4
votes
4answers
868 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 ...
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?
10
votes
1answer
643 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-...
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
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
8k 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 ...
29
votes
4answers
14k 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 ...
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 ...
17
votes
3answers
2k 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 ...
15
votes
2answers
741 views

Can Grover's algorithm be parallelized?

Using a quantum computer, Grover's algorithm can search an unordered list of length $N$ in time $\sqrt{N}$. Applied to cryptography this means that it can recover $n$ bit keys and find preimages for $...
10
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 ...
6
votes
1answer
498 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 ...
3
votes
1answer
596 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?
1
vote
1answer
255 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 ...
7
votes
2answers
542 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
198 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 ...
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 ...
18
votes
1answer
10k 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 ...
31
votes
1answer
3k 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,...
13
votes
2answers
6k views

Can or can not D-Wave's quantum computers use Shor's and Grover's Algorithm to find encryption keys? Why?

I read that a company called D-Wave Systems has and is manufacturing quantum computers of 128 qubits. Can they or can they not use Shor's and Grover's algorithms for finding RSA-keys? If they can't ...
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 ...
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,...
8
votes
5answers
850 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 ...
5
votes
3answers
939 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 ...
3
votes
2answers
576 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
311 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, ...
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, ...
8
votes
3answers
504 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 ...
7
votes
2answers
328 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, ...
7
votes
1answer
649 views

Which MAC scheme is quantum resistant?

will HMAC survive Grover algorithm ? if not then which MAC scheme provide post-quantum security ?
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
914 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 ...
4
votes
2answers
247 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....
4
votes
1answer
177 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 ...
4
votes
1answer
1k 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 ...
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 ...
2
votes
1answer
144 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 ...
1
vote
1answer
326 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 ...
6
votes
3answers
470 views

Supersingular Isogeny Key Exchange broken?

Found this report detailing a quantum algorithm for computing isogenies between supersingular elliptic curves. http://cacr.uwaterloo.ca/techreports/2014/cacr2014-24.pdf with the quote "...
5
votes
1answer
460 views

Does Grover's algorithm effect block size or only key size?

We know that Grover's algorithm can speed up cracking symmetric keys. Basically the keyspace is halved. This means we have to use at least a 256-bit key (to get 128-bit security). I heard somewhere ...
4
votes
1answer
261 views

What does Keccak being “efficiently invertible” mean?

Reading through Wikipedia, I saw this: It has been shown that the Merkle–Damgård construction, as used by SHA-2, is collapsing and, by consequence, quantum collision-resistant, but for the sponge ...
3
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$. ...
2
votes
1answer
82 views

Can quantum algorithms solve the approximate GCD hard problem efficiently?

Some cryptographic schemes are based on the hardness of this problem. The answer to this question determines if those schemes are quantum resistant or not. There are a number similar questions but ...
2
votes
1answer
1k views

using Post-quantum asymmetric ciphers instead of RSA

We can't trust RSA to encrypt our Emails so what is best post-quantum cryptography system as alternative for RSA which provide good security and don't be breakable? because McEliece cryptosystem looks ...