44

RSA has not been cracked. No one has demonstrated practically viable computing that's anywhere in the realm of breaking RSA. There is no reason to change any of your practices. The first thing to understand is that D-Wave has a long history of repeatedly making bogus claims to the popular press. Experts in quantum computing have been criticizing and ...


35

Well, cryptographers have been contemplating a post-quantum world for some time now. Quantum computing, although in its infancy as far as real-life computers go, has been studied in a theoretical sense for a quite a while. Shor's algorithm was published 19 years ago; Grover's, 17 years ago. These are the two most-famous quantum algorithms, I think, but the ...


31

It is a bit dubious to claim that hash functions "are not based on any hard problem": inverting a standard hash function, or finding a collision, is itself a very hard problem. The point of a reduction is to gather the cryptanalytic effort on a smaller number of hypothesis. The fact that RSA-OAEP is CCA secure under the RSA assumption is not a proof that it ...


24

After contacting D-Wave and asking them the implications of their quantum computer against RSA, they responded that they had not cracked RSA for the following reasons… Short answers: Q. Is RSA effectively cracked by your quantum computer A. No. Q. Should our customers be concerned that companies with quantum computers are intercepting our ...


23

Unless Keccak has structural weaknesses that I am not aware of, the answer is surprisingly neither 128 nor 256! Gilles Brassard, Peter Høyer and Alain Tapp describe a sort of quantum birthday attack in their paper "Quantum Cryptanalysis of Hash and Claw-Free Functions" that effectively works by creating a table of size $\sqrt[3]{2^b}$ (versus the $\sqrt{2^b}...


21

Adding more qubits does not increase the computation speed. A quantum computer with 4 qubits does not factorize faster than one with 2. The qubits are the "memory" of the quantum computer. More qubits mean you can factor bigger numbers. If I remember correctly, you need a superposition of $\Theta(N^2)$ terms, which means $\Theta(\log(N^2))$ qubits to factor ...


20

What makes a problem suitable for cryptography is slightly different than what makes a problem NP-hard. What is required for cryptography is average-case hardness --- i.e., a randomly selected instance of a problem should be "hard" for an adversary to solve. However, random instances of some NP-hard problems (3SAT, e.g.) turn out to be easy with high ...


19

Post-quantum crypto is a very young field and is still changing quite rapidly. If you just want a reading list to introduce you to the topics, I would recommend the March 2015 report released by the EU's PQCrypto Project, and the April 2016 report from NIST. As of today, here's an (incomplete) list of candidate algorithms for post-quantum cryptography with ...


19

As mentioned in the comments, there is a serious flaw in the paper, and it has been withdrawn: see https://groups.google.com/forum/#!msg/cryptanalytic-algorithms/WNMuTfJuSRc/OtQMLRXgBwAJ and part (3) of http://www.scottaaronson.com/blog/?p=2996


18

Biclique cryptanalysis is the current best known attack on AES. It reduces the security of AES-256 from $2^{256}$ to $2^{254.4}$. Related key attacks are not practical attacks as they should never occur in the wild. they are symptomatic of a poor implementation, and contrary to the recommended use of AES. The best known theoretical attack is Grover's ...


17

With any $n$ bit hash it is possible to: Find preimages with work $2^n$ on classical computers and $2^{n/2}$ using quantum computers Find collisions with work $2^{n/2}$ on classical computers and $2^{n/3}$ using quantum computers I want to emphasize that these are generic attacks that always work, no matter which concrete hashfunction is used. Grover's ...


17

D-Wave's "Quantum computers" are NOT general purpose quantum computers. They can only do quantum annealing, which allows a small subset of problems to be solved. They can't run Shor's or Grover's algorithms, as these aren't quantum annealing problems. It's also still an open question whether D-Wave's machines even provide any speedup over classical simulated ...


16

How many qubits are required for breaking RSA 2048 and RSA 4096 in real-time with a quantum computer? Like the answer you linked to shows, about $\log_2(N^2) = 2 \log_2(N)$ or just $2n$ where $n$ is the number of bits of the modulus $N$, i.e. the key size of RSA. So 4096 for 2048-bit RSA, double that for 4096-bit. This paper (PDF) has an algorithm using ...


16

The authors themselves point out that this doesn't break lattice-based assumptions used in crypto. To quote: Lattice problems have received enormous attention in recent years, mainly because of their algebraic structure has allowed constructions of cryptographic primitives, culminating in the Learning-with-Errors (LWE) encryption scheme due to Regev [...


16

wondering what the largest integer is which they were able to factor with a small quantum computer Stunts Before the present answer, the largest claim for quantum-related factoring seems to have been 4088459=2017×2027, by Avinash Dash, Deepankar Sarmah, Bikash K. Behera, and Prasanta K. Panigrahi, in [DSBP2018] Exact search algorithm to factorize large ...


15

Unless I misunderstood the definitions, an algorithm for the problem in Definition 1 (i.e. their main result) is in fact enough to attack decision-LWE if the noise is small. The fact that they need a promise that the point is always close to the lattice doesn't seem to be a problem. A decision-LWE problem mod q, where samples are of dimension n and the ...


14

In short, the answer is yes, if the full 512 bit hash output length of Keccak[r=1088,c=512] is used, this provides security up to 2256 operations against Grover's quantum algorithm. Using Grover's algorithm, one can find a preimage of a n-bit hash function in time 2n/2 with a quantum computer. This is a generic attack in the sense that it applies to any n-...


14

With a 1024 qubit quantum computer you cannot break any of the algorithm you mentioned. Current estimations for an impelmentation of Grover's algorithm for AES requires much more qubits. According to this paper by Grassl et al. the required number of qubits required for AES-256 is 6681, see the following extracted table: I guess it's not unreasonable to ...


13

Yes, it is feasible. In fact, the NIST post-quantum submissions include a number of lattice-based cryptographic key exchange and signature protocols. As you can see from a summary of the different types of algorithms, lattice-based algorithms dominate the submissions. These include NTRU and its variants, R-LWE, and FALCON (designed in part by one of our ...


12

I believe that the conjugacy search problem is broken by probabilistic attacks (see chapter 7). I am not sure if this completely ends braid cryptography, however, since there are other difficult problems in braid groups that have not been studied extensively.


12

Do the post-quantum ciphers also automag/tically address the 1st problem? Not really, however to explore that in any detail, we need to explore what the 1st problem is. If $P=NP$ is proven true, what does that practically mean? Well, it might have absolutely no practical ramifications, or it might mean that virtually all known cryptographical systems can ...


11

Current symmetric cryptography and hashes are actually believed to be reasonably secure against quantum computing. Quantum computers solve some problems much faster than the best known classical algorithms, but the best known quantum attack against AES is effectively "try all the keys." In a quantum computer, the time taken to solve a general search problem (...


11

Answering myself... There is now a very analogous alternative to Diffie-Hellman in post-quantum cryptography: Towards quantum-resistant cryptosystems from supersingular elliptic curve isogenies The research paper is very new, but if the results turn out to be secure, this is a very competitive key agreement scheme for post-quantum cryptography.


11

What we traditionally call Elliptic Curve Cryptography (working in the group of points on an elliptic curve over a finite field) is vulnerable to an attack by a quantum computer running Shor's algorithm and is thus not considered a Quantum-Safe or Post Quantum Cryptographic algorithm. However there is an true Post Quantum Key Exchange algorithm which uses ...


11

Quantum computers don't attack the protocol, they attack the cryptographic primitives used in the protocol. You need to avoid primitives that can be broken by quantum computers. Quantum computers don't break all computationally secure cryptography, so you don't have to resort to information theoretic algorithms (one-time-pad). Symmetric encryption is ...


11

They're actually sampling $5n$ elements from $\Psi_{16}$. Perhaps Protocol 2 on page 5 shows this most clearly, where $\textbf{s}, \textbf{e} \stackrel{\$}{\leftarrow} \Psi_{16}^n$ and $\textbf{s}', \textbf{e}', \textbf{e}'' \stackrel{\$}{\leftarrow} \Psi_{16}^n$ are sampled (on line 3 on Alice' side, and line 1 on Bob's). This probably also answers part of ...


11

It has been folklore (since at least 2010) that you can do what you propose, but less efficiently than the "key transport" method of any Ring-LWE based encryption scheme or KEM. So here is what you can do: there is a public polynomial $a\in Z_q[X]/(X^n+1)$ that is shared by everyone. It needs to be uniformly random, so it can be set to XOF(1), where XOF is ...


11

It allows the security of the construction to be reduced to second-preimage-resistance, rather than collision-resistance. This is a significant distinction, since brute force against collision-resistance is $2^{n/2}$ while brute force against second-preimage-resistance is $2^n$. In short, this XOR trick allows signatures/keys in the scheme to be half as long ...


10

You can do key agreement with asymmetric encryption. Any asymmetric encryption algorithm (post-quantum or not) can be used for key agreement: just choose a random key and encrypt it. Password Authenticated Key Exchange looks harder, because it cannot be applied on just any key exchange or asymmetric encryption scheme. The IPAKE framework can be applied on ...


10

There are known impossibility results regarding basis public-key cryptography on NP-complete problems. In this paper by Goldreich and Goldwasser they show that under common types of reductions, it is not possible to base public-key cryptography on NP-hardness.


Only top voted, non community-wiki answers of a minimum length are eligible