33

TL;DR     The answer is classical cryptography. Besides a quantum link, secure data communication with Quantum Cryptography uses classical links, a lot of mathematically provable classical cryptography, and a setup procedure using initially trusted material just as in classical cryptography. To perform the same other than by the One Time Pad, ...


26

The question to answer is "Is N the product of P*Q?" I believe that the easiest way to understand Shor is to imagine two sine waves, one length P and one length Q. Assuming that P and Q are co-prime, then the question above can also be answered "At what point does the harmony of P overlapped with Q repeat itself?" And the answer can be determined quickly, ...


23

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


21

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


14

No, Quantum Key Distribution is not any safer than conventional crypto is against an active Eve impersonating as Bob to Alice using the same equipment and knowledge as the rightful Bob (or/and impersonating as Alice to Bob using the same equipment and knowledge as the rightful Alice). Otherwise stated, QKD can resist Man Eve In The Middle only inasmuch as ...


14

Well, since I'm one of the authors on the paper, let me try to answer your question. First I should explain that the paper you link to is not the original paper proposing that approach, but rather the first implementation of it (in this case using quantum optics). The original paper which introduced the Universal Blind Quantum Computing (UBQC) protocol ...


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


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


10

As noted by kodlu, you are basically asking about the existence of whole field of quantum cryptography (which is different of 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 ...


9

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

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 zipfile and told someone the key you're quite safe. But things like PGP and SSL, where you have to agree to a ...


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

Well, to understand why QKD is often associated with OTP, we need to review what Quantum crypto is, and why it claims to be secure. Overall, we know of three implementable paradigms for cryptographical security: Informational: the attacker does not have enough information to determine the plaintext from the ciphertext Computational complexity: the process ...


8

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.


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

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

Let’s take your questions in order. Note that I’m a physicist working in quantum cryptography, so my opinion on this might be biased 1. What about authentication ? The classical channel between Alice and Bob has to be authenticated in order for the protocol to work. Formally, this is a pre-requisite for quantum key distribution (QKD), and is not part of ...


8

@fgrieu already wrote a little book, so I'll restrict my answer to a minimum to avoid repetitions. Think of this as an extended comment (which indeed wouldn't have fit the comment size limits). What makes Quantum Cryptography secure? … what makes it more secure than the classical version? In classical crypto, things like three party key distribution ...


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

What's to guarantee authentication or message integrity (particularly when Alice and Bob are exchanging which filters were correct and so on)? A pre-authenticated classical channel is an essential requirement in addition to the quantum channel on which the quantum key exchange (QKE) is performed. This implies that Alice and Bob must share an initial secret ...


7

There are several kind of quantum key distribution (QKD) protocols as of today. Are you looking for a particular one? The best known QKD protocol goes by the name BB84 after its inventors Bennett and Brassard and the year in which they presented their work. Searching on the Internet, I found this link http://fredhenle.net/bb84/demo.php with a simulation ...


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


7

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


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


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