25

Elliptic curve cryptography is not presently vulnerable to quantum computing because there are no quantum computers big and reliable enough to matter. But it would be vulnerable to quantum computers big enough to run Shor's algorithm. All elliptic curve cryptography* is based on the difficulty of finding a secret integer $n$ given the scalar multiple $Q = [...


22

For example: the 5-qubit quantum computer created at MIT by using the technique of ion traps succeeded in prime-factorizing 15. Does that mean that since it succesfully managed that, that it is a all-purpose quantum computer which could be used for cryptanalysis and/or cryptographic attacks? No, not even close. Attacking e.g. RSA requires a lot more than ...


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


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


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


15

From the manufacturer's website: Quantis uses Quantum Physics to create truly random numbers Existing randomness sources can be grouped in two classes: software solutions, which can only generate pseudo-random bit streams, and physical (hardware) sources. Software solutions are not capable of providing true randomness as they are based on ...


13

There is, in principle, no limit to the dimension of the state space of a quantum system. This includes infinite dimension (usually countable, i.e. a separable Hilbert space) and any large but finite dimension. In the context of quantum information, systems with a state space of dimension $d\geq 2$ are usually called qudits. It's also important to mention ...


12

As noted by kodlu, you are basically asking about the existence of the whole field of quantum cryptography (which is different from post-quantum cryptography). All the field was arguably started by Stephen Wiesner’s invention of Conjugate Coding in 1969, but which was rejected remained unpublished until 1983. He proposed a theoretical way to use quantum ...


11

With Grover's algorithm, quantum computers can brute-force a block cipher with $n$-bit keys using $2^{n/2}$ steps, which is much smaller than the regular effort ($2^n$). This means, for example, that AES-128 could be broken with $2^{64}$ steps, and that AES-256 would offer the same security that AES-128 offers currently. In short, key sizes would need to be ...


11

There are a few key distinctions to make Quantum cryptanalysis This is what you hear all the buzzing about. Specifically, there is something called Shor's algorithm, that when used to break modern crypto, can be devastating. If you've encrypted a zip file and told someone the key you're quite safe. But things like PGP and SSL, where you have to agree to a ...


10

Actually, if RSA is being used in a deterministic way (and the public exponent $e$ is relatively small), someone could recover the value $N$. We know that $P^e = C \bmod N$; that's equivalent to $P^e - C = kN$ for some integer $k$; if $e$ is small, then Shor's algorithm might be able to factor $P^e - C$; allowing you to recover $N$. Alternatively, if you ...


9

Yes, it is possible to use quantum computer as a true random number generator, by applying Hadamard gates to all available qubits in initial $|0\rangle$ state and measuring them in the standard basis; but this is inefficient way of generating random numbers because quantum computer requires time to cool down its qubits to the initial state before starting a ...


9

Actually, most of the primitives that are currently believed to be secure FHE methods would appear to be quantum resistant; a partial list would include Craig Gentry's original scheme based on ideal lattices, BGV (based on ring-LWE), and this NTRU-based approach. All three are based on hard problems that are not susceptible to Shor's algorithm.


9

Quantum Key Distribution as a concept dates back to the BB84 (Bennett, Brassard) protocol, and has been implemented for countering passive attacks, such as Man in the Middle. In theory it is impossible to eavesdrop without disturbing the wave function describing the state of the quantum photon channel. ID Quantique is one company in this domain and ...


9

NO, if "messaging application" is software running on an stock consumer-grade computer or variant (including mobile phone, tablet): in any of its standard meanings, Quantum Cryptography requires specific hardware. For Quantum Key Distribution (actually quantum privacy amplification), which is how quantum cryptography does encryption, you'd need a specific ...


8

I see two problems with this idea. The first problem is Shor's algorithm; that's a quantum algorithm that is able to find the cycle length of a group (and if you can solve that problem, it is easy to factor and compute discrete logs). In this case, if we define the group of elements defined by the initial start state in the signature, where $H^n$ is the ...


8

The statement a 15360-bit RSA key is the equivalent to a 256-bit symmetric key does not take into account quantum algorithms. In fact, it is based on a specific computation model. It is just based on the fact that there exist sub-exponential algorithms for factoring and therefore you need longer keys than when using symmetric-key crypto where it is ...


8

Quantum key distribution takes advantage of physics to create a communication channel that can't be cleanly intercepted without corrupting part of the message. This can be used to create a shared secret key for a one-time pad to be used over a classical connection. Particles may have a quantum state which can be thought of as having multiple bases (such as ...


8

Two things: Firstly, the paper is not talking about factorization at all; instead, it is using the Quantum Computer as a "constant-that-doesn't-change-the-output" algorithm (that is, find an $s$ such that $f(x) = f(x \oplus s)$ for all $x$) to break certain message authentication algorithms (which may just happen to use AES). The paper notes that, with ...


7

This is by no means a comprehensive answer on this subject, but perhaps it's a good start. Shor's algorithm for (specific) ECC This paper by Proos and Zalka compares implementations of Shor's algorithm for integer factorization and discrete logarithms for some elliptic curve groups (notably, ONLY those over prime finite fields). If $n$ is the bit length of ...


7

There are many questions here; I am not answering the question in the title, but rather addressing the final questions in the body. One-time pad encryption nevertheless has a bright future. It is in fact the only crypto algorithm that has any future. Once that computational power and codebreaking technology has surpassed the capabilities of cryptologists ...


7

Sure, you can use Grover's algorithm to attack AES-128 in CTR mode. Assume the attacker knows a few plaintext blocks and the counter. The AES ciphertext blocks that are generated by encrypting this counter and XOR'ing it with the plaintext. In that case the input and output of the AES-128 block cipher are known and Grover's attack can be applied (as if AES-...


6

Is there any way to theoretically, by the use of mathematics, to calculate the time taken to brute-force RSA keys? Even classically, this is not so easy as you seem to imply. RSA is based on the hardness of the integer factorization problem. The fastest classical algorithm known that solves this problem is the General Number Field Sieve (GNFS), and it ...


6

In addition to the other answers, I want to add that D-Wave makes a type of machine called an Adiabatic Quantum Computer, which is fundamentally different from the general-purpose quantum computers capable of running Shor's algorithm. D-Wave's machines are good at optimization problems, but have zero applicability to cryptography. Moreover, it's not even ...


6

Statistically, yes, random is random (read: entropy). It's also worth stating that you can really only approximate how random something is based on samples. This means that you can't measure randomness explicitly, but you can make approximations based on expected outputs compared to conditional probabilities, etc. Quantum computing does have random ...


6

Could one adapt Shor's algorithm to solve the DLP? Yes: Shor's original paper (arXiv preprint) explains how, in §6 on p. 321. Could one adapt Shor's algorithm to solve the ECDLP? Yes. Researchers at Microsoft recently published estimates for how big a quantum computer you would need to do so. (Spoiler: Smaller than RSA at comparable classical security ...


6

Some ECC cryptosystems in wide use, including ECDSA and Ed25519, ECDH.. are theoretically vulnerable to quantum computing, should that ever become usable for cryptanalysis. These cryptosystems are based on a Discrete Logarithm problem and it becomes sub-exponential w.r.t. the bit size of the unknown exponent under quantum computing assumptions. On the other ...


6

What is Quantum Cryptography? Today's "normal" cryptography relies mostly on mathematical principles. For example RSA is based on the practical difficulty of the factorization of the product of two large prime numbers, the so-called "factoring problem". Quantum cryptography (quote from Wikipedia): Quantum cryptography is the science of exploiting ...


6

I happened to learn that encryption by quantum cryptography would be impossible to break as it's state changes the instant an eavesdropping event (by non-quantum systems) occurs. Actually, the QKD system doesn't assume that the eavesdropper is nonquantum; he is allowed to attempt to generate an entangled state with the qubit being transmitted. However, ...


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