Entries Tagged "quantum cryptography"

Page 2 of 3

Quantum Tokens for Digital Signatures

This paper wins “best abstract” award: “Quantum Tokens for Digital Signatures,” by Shalev Ben David and Or Sattath:

Abstract: The fisherman caught a quantum fish. “Fisherman, please let me go,” begged the fish, “and I will grant you three wishes.” The fisherman agreed. The fish gave the fisherman a quantum computer, three quantum signing tokens and his classical public key.

The fish explained: “to sign your three wishes, use the tokenized signature scheme on this quantum computer, then show your valid signature to the king, who owes me a favor.”

The fisherman used one of the signing tokens to sign the document “give me a castle!” and rushed to the palace. The king executed the classical verification algorithm using the fish’s public key, and since it was valid, the king complied.

The fisherman’s wife wanted to sign ten wishes using their two remaining signing tokens. The fisherman did not want to cheat, and secretly sailed to meet the fish. “Fish, my wife wants to sign ten more wishes.”

But the fish was not worried: “I have learned quantum cryptography following the previous story (The Fisherman and His Wife by the brothers Grimm). The quantum tokens are consumed during the signing. Your polynomial wife cannot even sign four wishes using the three signing tokens I gave you.”

“How does it work?” wondered the fisherman.

“Have you heard of quantum money? These are quantum states which can be easily verified but are hard to copy. This tokenized quantum signature scheme extends Aaronson and Christiano’s quantum money scheme, which is why the signing tokens cannot be copied.”

“Does your scheme have additional fancy properties?” the fisherman asked.

“Yes, the scheme has other security guarantees: revocability, testability and everlasting security. Furthermore, if you’re at the sea and your quantum phone has only classical reception, you can use this scheme to transfer the value of the quantum money to shore,” said the fish, and swam his way.

Posted on October 6, 2016 at 7:03 AM • View Comments

NSA Plans for a Post-Quantum World

Quantum computing is a novel way to build computers—one that takes advantage of the quantum properties of particles to perform operations on data in a very different way than traditional computers. In some cases, the algorithm speedups are extraordinary.

Specifically, a quantum computer using something called Shor’s algorithm can efficiently factor numbers, breaking RSA. A variant can break Diffie-Hellman and other discrete log-based cryptosystems, including those that use elliptic curves. This could potentially render all modern public-key algorithms insecure. Before you panic, note that the largest number to date that has been factored by a quantum computer is 143. So while a practical quantum computer is still science fiction, it’s not stupid science fiction.

(Note that this is completely different from quantum cryptography, which is a way of passing bits between two parties that relies on physical quantum properties for security. The only thing quantum computation and quantum cryptography have to do with each other is their first words. It is also completely different from the NSA’s QUANTUM program, which is its code name for a packet-injection system that works directly in the Internet backbone.)

Practical quantum computation doesn’t mean the end of cryptography. There are lesser-known public-key algorithms such as McEliece and lattice-based algorithms that, while less efficient than the ones we use, are currently secure against a quantum computer. And quantum computation only speeds up a brute-force keysearch by a factor of a square root, so any symmetric algorithm can be made secure against a quantum computer by doubling the key length.

We know from the Snowden documents that the NSA is conducting research on both quantum computation and quantum cryptography. It’s not a lot of money, and few believe that the NSA has made any real advances in theoretical or applied physics in this area. My guess has been that we’ll see a practical quantum computer within 30 to 40 years, but not much sooner than that.

This all means that now is the time to think about what living in a post-quantum world would be like. NIST is doing its part, having hosted a conference on the topic earlier this year. And the NSA announced that it is moving towards quantum-resistant algorithms.

Earlier this week, the NSA’s Information Assurance Directorate updated its list of Suite B cryptographic algorithms. It explicitly talked about the threat of quantum computers:

IAD will initiate a transition to quantum resistant algorithms in the not too distant future. Based on experience in deploying Suite B, we have determined to start planning and communicating early about the upcoming transition to quantum resistant algorithms. Our ultimate goal is to provide cost effective security against a potential quantum computer. We are working with partners across the USG, vendors, and standards bodies to ensure there is a clear plan for getting a new suite of algorithms that are developed in an open and transparent manner that will form the foundation of our next Suite of cryptographic algorithms.

Until this new suite is developed and products are available implementing the quantum resistant suite, we will rely on current algorithms. For those partners and vendors that have not yet made the transition to Suite B elliptic curve algorithms, we recommend not making a significant expenditure to do so at this point but instead to prepare for the upcoming quantum resistant algorithm transition.

Suite B is a family of cryptographic algorithms approved by the NSA. It’s all part of the NSA’s Cryptographic Modernization Program. Traditionally, NSA algorithms were classified and could only be used in specially built hardware modules. Suite B algorithms are public, and can be used in anything. This is not to say that Suite B algorithms are second class, or breakable by the NSA. They’re being used to protect US secrets: “Suite A will be used in applications where Suite B may not be appropriate. Both Suite A and Suite B can be used to protect foreign releasable information, US-Only information, and Sensitive Compartmented Information (SCI).”

The NSA is worried enough about advances in the technology to start transitioning away from algorithms that are vulnerable to a quantum computer. Does this mean that the agency is close to a working prototype in their own classified labs? Unlikely. Does this mean that they envision practical quantum computers sooner than my 30-to-40-year estimate? Certainly.

Unlike most personal and corporate applications, the NSA routinely deals with information it wants kept secret for decades. Even so, we should all follow the NSA’s lead and transition our own systems to quantum-resistant algorithms over the next decade or so—possibly even sooner.

The essay previously appeared on Lawfare.

EDITED TO ADD: The computation that factored 143 also accidentally “factored much larger numbers such as 3599, 11663, and 56153, without the awareness of the authors of that work,” which shows how weird this all is.

EDITED TO ADD: Seems that I need to be clearer: I do not stand by my 30-40-year prediction. The NSA is acting like practical quantum computers will exist long before then, and I am deferring to their expertise.

Posted on August 21, 2015 at 12:36 PM • View Comments

Successful Attack Against a Quantum Cryptography System

Clever:

Quantum cryptography is often touted as being perfectly secure. It is based on the principle that you cannot make measurements of a quantum system without disturbing it. So, in theory, it is impossible for an eavesdropper to intercept a quantum encryption key without disrupting it in a noticeable way, triggering alarm bells.

Vadim Makarov at the Norwegian University of Science and Technology in Trondheim and his colleagues have now cracked it. “Our hack gave 100% knowledge of the key, with zero disturbance to the system,” he says.

[…]

The cunning part is that while blinded, Bob’s detector cannot function as a ‘quantum detector’ that distinguishes between different quantum states of incoming light. However, it does still work as a ‘classical detector’ ­ recording a bit value of 1 if it is hit by an additional bright light pulse, regardless of the quantum properties of that pulse.

That means that every time Eve intercepts a bit value of 1 from Alice, she can send a bright pulse to Bob, so that he also receives the correct signal, and is entirely unaware that his detector has been sabotaged. There is no mismatch between Eve and Bob’s readings because Eve sends Bob a classical signal, not a quantum one. As quantum cryptographic rules no longer apply, no alarm bells are triggered, says Makarov.

“We have exploited a purely technological loophole that turns a quantum cryptographic system into a classical system, without anyone noticing,” says Makarov.

Makarov and his team have demonstrated that the hack works on two commercially available systems: one sold by ID Quantique (IDQ), based in Geneva, Switzerland, and one by MagiQ Technologies, based in Boston, Massachusetts. “Once I had the systems in the lab, it took only about two months to develop a working hack,” says Makarov.

Just because something is secure in theory doesn’t mean it’s secure in practice. Or, to put it more cleverly: in theory, theory and practice are the same; but in practice, they’re very different.

The paper is here.

Posted on September 2, 2010 at 1:46 PM • View Comments

Location-Based Quantum Encryption

Location-based encryption—a system by which only a recipient in a specific location can decrypt the message—fails because location can be spoofed. Now a group of researchers has solved the problem in a quantum cryptography setting:

The research group has recently shown that if one sends quantum bits—the quantum equivalent of a bit—instead of only classical bits, a secure protocol can be obtained such that the location of a device cannot be spoofed. This, in turn, leads to a key-exchange protocol based solely on location.

The core idea behind the protocol is the “no-cloning” principle of quantum mechanics. By making a device give the responses of random challenges to several verifiers, the protocol ensures that multiple colluding devices cannot falsely prove any location. This is because an adversarial device can either store the quantum state of the challenge or send it to a colluding adversary, but not both.

Don’t expect this in a product anytime soon. Quantum cryptography is mostly theoretical and almost entirely laboratory-only. But as research, it’s great stuff. Paper here.

Posted on August 3, 2010 at 6:25 AM • View Comments

Quantum Cryptography Cracked

Impressive:

This presentation will show the first experimental implementation of an eavesdropper for quantum cryptosystem. Although quantum cryptography has been proven unconditionally secure, by exploiting physical imperfections (detector vulnerability) we have successfully built an intercept-resend attack and demonstrated eavesdropping under realistic conditions on an installed quantum key distribution line. The actual eavesdropping hardware we have built will be shown during the conference.

While I am very interested in quantum cryptography, I have never been optimistic about its practicality. And it’s always interesting to see provably secure cryptosystems broken.

Posted on December 30, 2009 at 6:04 AM • View Comments

Quantum Computer Factors the Number 15

This is an important development:

Shor’s algorithm was first demonstrated in a computing system based on nuclear magnetic resonance—manipulating molecules in a solution with strong magnetic fields. It was later demonstrated with quantum optical methods but with the use of bulk components like mirrors and beam splitters that take up an unwieldy area of several square meters.

Last year, the Bristol researchers showed they could miniaturize this optical setup, building a quantum photonic circuit on a silicon chip mere millimeters square. They replaced mirrors and beam splitters with waveguides that weave their way around the chip and interact to split, reflect, and transmit light through the circuit. They then injected photons into the waveguides to act as their qubits.

Now they’ve put their circuit to work: Using four photons that pass through a sequence of quantum logic gates, the optical circuit helped find the prime factors of the number 15. While the researchers showed that it was possible to solve for the factors, the chip itself didn’t just spit out 5 and 3. Instead, it came up with an answer to the “order-finding routine,” the “computationally hard” part of Shor’s algorithm that requires a quantum calculation to solve the problem in a reasonable amount of time, according to Jeremy O’Brien, a professor of physics and electrical engineering at the University of Bristol. The researchers then finished the computation using an ordinary computer to finally come up with the correct factors.

I’ve written about quantum computing (and quantum cryptography):

Several groups are working on designing and building a quantum computer, which is fundamentally different from a classical computer. If one were built—and we’re talking science fiction here—then it could factor numbers and solve discrete-logarithm problems very quickly. In other words, it could break all of our commonly used public-key algorithms. For symmetric cryptography it’s not that dire: A quantum computer would effectively halve the key length, so that a 256-bit key would be only as secure as a 128-bit key today. Pretty serious stuff, but years away from being practical.

Here’s a really good essay on the realities of quantum computing and its potential effects on public-key cryptography.

Posted on September 22, 2009 at 2:00 PM • View Comments

Quantum Cryptography

Quantum cryptography is back in the news, and the basic idea is still unbelievably cool, in theory, and nearly useless in real life.

The idea behind quantum crypto is that two people communicating using a quantum channel can be absolutely sure no one is eavesdropping. Heisenberg’s uncertainty principle requires anyone measuring a quantum system to disturb it, and that disturbance alerts legitimate users as to the eavesdropper’s presence. No disturbance, no eavesdropper—period.

This month we’ve seen reports on a new working quantum-key distribution network in Vienna, and a new quantum-key distribution technique out of Britain. Great stuff, but headlines like the BBC’s “‘Unbreakable’ encryption unveiled” are a bit much.

The basic science behind quantum crypto was developed, and prototypes built, in the early 1980s by Charles Bennett and Giles Brassard, and there have been steady advances in engineering since then. I describe basically how it all works in Applied Cryptography, 2nd Edition (pages 554-557). At least one company already sells quantum-key distribution products.

Note that this is totally separate from quantum computing, which also has implications for cryptography. Several groups are working on designing and building a quantum computer, which is fundamentally different from a classical computer. If one were built—and we’re talking science fiction here—then it could factor numbers and solve discrete-logarithm problems very quickly. In other words, it could break all of our commonly used public-key algorithms. For symmetric cryptography it’s not that dire: A quantum computer would effectively halve the key length, so that a 256-bit key would be only as secure as a 128-bit key today. Pretty serious stuff, but years away from being practical. I think the best quantum computer today can factor the number 15.

While I like the science of quantum cryptography—my undergraduate degree was in physics—I don’t see any commercial value in it. I don’t believe it solves any security problem that needs solving. I don’t believe that it’s worth paying for, and I can’t imagine anyone but a few technophiles buying and deploying it. Systems that use it don’t magically become unbreakable, because the quantum part doesn’t address the weak points of the system.

Security is a chain; it’s as strong as the weakest link. Mathematical cryptography, as bad as it sometimes is, is the strongest link in most security chains. Our symmetric and public-key algorithms are pretty good, even though they’re not based on much rigorous mathematical theory. The real problems are elsewhere: computer security, network security, user interface and so on.

Cryptography is the one area of security that we can get right. We already have good encryption algorithms, good authentication algorithms and good key-agreement protocols. Maybe quantum cryptography can make that link stronger, but why would anyone bother? There are far more serious security problems to worry about, and it makes much more sense to spend effort securing those.

As I’ve often said, it’s like defending yourself against an approaching attacker by putting a huge stake in the ground. It’s useless to argue about whether the stake should be 50 feet tall or 100 feet tall, because either way, the attacker is going to go around it. Even quantum cryptography doesn’t “solve” all of cryptography: The keys are exchanged with photons, but a conventional mathematical algorithm takes over for the actual encryption.

I’m always in favor of security research, and I have enjoyed following the developments in quantum cryptography. But as a product, it has no future. It’s not that quantum cryptography might be insecure; it’s that cryptography is already sufficiently secure.

This essay previously appeared on Wired.com.

EDITED TO ADD (10/21): It’s amazing; even reporters responding to my essay get it completely wrong:

Keith Harrison, a cryptographer with HP Laboratories, is quoted by the Telegraph as saying that, as quantum computing becomes commonplace, hackers will use the technology to crack conventional encryption.

“We have to be thinking about solutions to the problems that quantum computing will pose,” he told the Telegraph. “The average consumer is going to want to know their own transactions and daily business is secure.

“One way of doing this is to use a one time pad essentially lists of random numbers where one copy of the numbers is held by the person sending the information and an identical copy is held by the person receiving the information. These are completely unbreakable when used properly,” he explained.

The critical feature of quantum computing is the unique fact that, if someone tampers with an information feed between two parties, then the nature of the quantum feed changes.

This makes eavesdropping impossible.

No, it wouldn’t make eavesdropping impossible. It would make eavesdropping on the communications channel impossible unless someone made an implementation error. (In the 80s, the NSA broke Soviet one-time-pad systems because the Soviets reused the pad.) Eavesdropping via spyware or Trojan or TEMPEST would still be possible.

EDITED TO ADD (10/26): Here’s another commenter who gets it wrong:

Now let me get this straight: I have no doubt that there are many greater worries in security than “mathematical crypography.” But does this justify totally ignoring the possibility that a cryptographic system might possibly be breakable? I mean maybe I’m influenced by this in the fact that I’ve been sitting in on a cryptanalysis course and I just met a graduate student who broke a cryptographic pseudorandom number generator, but really what kind of an argument is this? “Um, well, sometimes our cryptographic systems have been broken, but that’s nothing to worry about, because, you know, everything is kosher with the systems we are using.”

The point isn’t to ignore the possibility that a cryptographic system might possibly be broken; the point is to pay attention to the other parts of the system that are much much more likely to be already broken. Security is a chain; it’s only as secure as the weakest link. The cryptographic systems, as potentially flawed as they are, are the strongest link in the chain. We’d get a lot more security devoting our resources to making all those weaker links more secure.

Again, this is not to say that quantum cryptography isn’t incredibly cool research. It is, and I hope it continues to receive all sorts of funding. But for an operational network that is worried about security: you’ve got much bigger worries than whether Diffie-Hellman will be broken someday.

Posted on October 21, 2008 at 6:48 AM • View Comments

Switzerland Protects its Vote with Quantum Cryptography

This is so silly I wasn’t going to even bother blogging about it. But the sheer number of news stories has made me change my mind.

Basically, the Swiss company ID Quantique convinced the Swiss government to use quantum cryptography to protect vote transmissions during their October 21 election. It was a great publicity stunt, and the news articles were filled with hyperbole: how the “unbreakable” encryption will ensure the integrity of the election, how this will protect the election against hacking, and so on.

Complete idiocy. There are many serious security threats to voting systems, especially paperless touch-screen voting systems, but they’re not centered around the transmission of votes from the voting site to the central tabulating office. The software in the voting machines themselves is a much bigger threat, one that quantum cryptography doesn’t solve in the least.

Moving data from point A to point B securely is one of the easiest security problems we have. Conventional encryption works great. PGP, SSL, SSH could all be used to solve this problem, as could pretty much any good VPN software package; there’s no need to use quantum crypto for this at all. Software security, OS security, network security, and user security are much harder security problems; and quantum crypto doesn’t even begin to address them.

So, congratulations to ID Quantique for a nice publicity stunt. But did they actually increase the security of the Swiss election? Doubtful.

Posted on October 29, 2007 at 6:02 AM • View Comments

1 2 3

Sidebar photo of Bruce Schneier by Joe MacInnis.