# Tag Info

29

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

17

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

15

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

7

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

7

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

5

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

5

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

5

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

5

QKD aims at exchanging key material to be used with encryption based on OTPs between two parties and thus to achieve perfect secrecy for transmitted messages. There are, however, several drawbacks for practical use in a wired setting of QKD (required hardware and their vulnerability to hacks, limited distance) which does not support their use for ...

5

I'm not going to exactly answer your question, because I have no idea. I simply do not know how fast the quantum computer is that NSA is building in secret. However I could explain why people recommend 256-bit security in the face of quantum computing using some numbers. If you feel that $2^{128}$ is a comfortable security against bruteforcing, remember ...

5

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

5

The standard answer in the research literature is to use information-theoretically secure message authentication codes, typically universal hashing (aka Carter-Wegman authenticators). Of course, you could use computationally-secure message authentication codes, like CMAC or HMAC, if you wanted, though that would partly defeat one of the reasons for using ...

4

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

4

The open source version of CyaSSL contains code that calls into the commercial NTRU library -- the library itself is missing of course. You might be able to make CyaSSL work with the open source NTRU implementation at https://github.com/tbuktu/libntru ; it's alpha level software though.

4

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

3

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

3

D-Wave does quantum annealing. It's not general-purpose quantum computing; in fact, the CEO claims that the gate-model for quantum computers is the worst thing that ever happened to the field. I have worked on quantum research as recently as 2012 and the gate-model is still the main focus for funded research. Shor's algorithm for factorization (which runs ...

3

In fact, the basic idea of Shor's algorithm for the discrete logarithm problem is reasonably simple. Assume (as in Section 4 Discrete Log: the easy case of Shor's paper) that you have an efficient quantum algorithm for the Fourier transform. Then, applying this Fourier transform twice (once for $a$ and once for $b$) on a quantum superposition of values ...

3

No. The Yale result describes a method of partial measurement that is not completely destructive to the quantum system's coherence, which is tied to its physical representation. It is not a refutation of quantum indeterminacy, which is the basis for (provably secure) quantum key exchange. In other words, the Yale team measured a qubit in such a way that ...

3

The main problem with the OTP is key distribution. You must share a random (not pseudo-random) key of the length of the message to make the OTP possible. QKD is one way (and possibly the most promising) to solve the problem of sharing a large enough, random key to use with the OTP. That said, QKD can be used with any cipher. My personal opinion is that most ...

3

To try to put this into perspective, the D-Wave system has (or at least claims) a 128-qubit processor. To factor a 1024-bit RSA key, you need roughly 2000 qubits (and, of course, many people are already using keys much larger than 1024 bits). If you were using elliptical curve cryptography instead, you'd be a bit closer to vulnerable. You can do a discrete ...

2

Just another point. Just because the complexity of quantum factoring is quadratic with respect to n for a composite N of length n bits does not mean it is cheap. It will still take a very long time on a quantum computer with a suitably large number of qbits (>= 2n). This difference is if you could produce a fast enough conventional system to crack 1024bit ...

2

The largest quantum computer that can definitely run Shor's algorithm is now up to 14 qubits. This was achieved sometime last year. This computer was probably not used to actually run Shor's algorithm, though. Shor's algorithm was actually demonstrated to work in 2001, with 7 qubits. We are still a long way from creating quantum computers that can work with ...

2

It seems difficult to combine the two. PUFs can provide authentication but they are based on the sender having first built up a small number of challenge/response pairs before handing the PUF over. So if Alice gives the PUF to Bob, Alice can authenticate Bob with the response. However if the protocol is two-phased, where Alice authenticates Bob and then they ...

2

Actually recently I found out about a complete QKD simulation toolkit that has become available, accessible online via this link, QKD simulator. It is a parameter-based simulator, so different scenarios (qubit numbers, Eve's influence, etc.) can be set up and simulated.

2

What you are describing is known as the Photon Number Splitting Attack (PNS), described for the first time (I think) by Brassard, Lütkenhaus, Mor ans Sanders in this 1999 paper. Several countermeasures have been invented since (single photon sources, robust protocols, decoy states), but detailing them would stray away from of your question. If one sends 2 ...

2

If the school has graduate courses that interest you and you think you can do well in (i.e. for comprehensive exams), and there is a strong crypto research group there, I would recommend any school that satisfied these criteria. As you move through academics, it becomes more and more clear that the quality of your research is the most important, and it is ...

1

The obvious approach is to help Bob learn $s_0 \oplus (s_0 \oplus s_1) \times c$, presumably using $F$ to help him learn this information. So, here is the natural protocol: Alice and Bob invoke $F$. Alice provides the input $s_0 \oplus s_1$, Bob provides the input $c$. Alice learns $p$ and Bob learns $q$, where we are guaranteed that \$p \oplus q = (s_0 ...

1

All mathematical groups can be used to perform an ElGamal encryption, so that is a first kind of math. That's where elliptic curves are useful: they have a group structure. If you find a group, you can build a cryptosystem out of it. However, as @poncho pointed out, different groups have different properties with regards to security. For instance, elliptic ...

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