Beefing up public-key encryption

February 18, 2013
Beefing up public-key encryption

Most financial transactions on the Internet are safeguarded by a cryptographic technique called public-key encryption. Where traditional encryption relies on a single secret key, shared by both sender and recipient, public-key encryption uses two keys that are mathematically related. One, the public key, is published on the Internet, and any sender can use it to encrypt a message; the second, the private key, is known only to the recipient and is required for decryption.

Standard public-key is secure as long as an attacker knows nothing other than the public key. But financial institutions and other large organizations seek security against more sophisticated attacks, called chosen-ciphertext attacks (CCAs), in which the attacker also has examples of successful decryption.

Unfortunately, public-key that are resilient against CCAs are hard to devise. Their complexity means that software implementations are prone to small errors that can introduce both vulnerabilities and inaccuracies during decryption.

At the International Conference on the Theory and Applications of Cryptographic Techniques this spring, a pair of postdocs at MIT's Computer Science and Artificial Intelligence Laboratory describe a new technique for taking one of these vulnerable, error-prone CCA schemes and turning it into a secure CCA scheme. The result could be of practical use, in the development of more-secure encryption protocols, but it could also provide theoretical insight into the very nature of .

Playing the odds

In cryptography circles, a message to be encoded is called a plaintext; the encrypted version of it is called a ciphertext. An encryption scheme is considered secure if even someone who knows two plaintexts in advance would find it virtually impossible to deduce which of two ciphertexts encodes which.

In the type of weak-CCA schemes that the MIT researchers—Huijia Lin and Stefano Tessaro—consider, the probability of distinguishing the ciphertexts is non-negligible. It may not be very big, but it's big enough to be a cause for concern. Similarly, there's also a non-negligible probability of errors during decryption.

Lin and Tessaro's result hinges on the observation that while, in the average case, the probability of distinguishing weakly encrypted ciphertexts may be unacceptably high, in some particular cases, it's negligible. Moreover, it's possible to compute the probability that the encrypted version of a randomly generated plaintext will be secure.

As it happens, combining a weakly encrypted ciphertext with a strongly encrypted one produces a strongly encrypted hybrid. In essence, Lin and Tessaro's scheme entails encrypting enough random plaintexts that, probabilistically, at least a few of them will be secure. Then they're all combined.

Lin and Tessaro's technique doesn't just secure transmissions against attackers who have some examples of successful decryption; it secures them against adversaries who have a black box that, without disclosing the , can decrypt any ciphertext they feed it—except the one that's under attack.

"In real life, maybe it seems more plausible that people would just get a couple of examples of ciphertexts and messages, but as cryptographers, we always want to prevent the worst possible scenario," Lin says. "Even if we want to handle the case where you just have examples of ciphertexts and the messages, it's hard to exhaust all possible scenarios. By considering the strongest attack, we automatically become immune to all possible scenarios, which are hard to enumerate."

"The question they ask"—how to improve the security of vulnerable encryption schemes—"is a very natural and intriguing one," says Abhi Shalat, an assistant professor of computer science at the University of Virginia, who studies encryption. "And the techniques that they use to show that demonstrate a lot of creativity and elegance."

In information theory, Shalat says, it's well established that "if you and I are trying to communicate, and we have a slightly better chance of less noise than the adversary has, you can sort of amplify that advantage so that we can actually talk privately." But "that technique doesn't necessarily work when the adversary is adaptive—when the adversary can query a [black-box decryption] oracle and be actively malicious, as is the case with encryption on the Internet," Shalat says. "One of the really nice ideas in the paper is the extension of this information-amplification idea to this adaptive setting."

Explore further: Perfecting email security

Related Stories

Perfecting email security

September 10, 2012

Millions of us send billions of emails back and forth each day without much concern for their security. On the whole, security is not a primary concern for most day-to-day emails, but some emails do contain personal, proprietary ...

Major step ahead for cryptography

May 26, 2010

Imagine you could work out the answer to a question, without knowing what the question was. For example, suppose someone thinks of two numbers and then asks another person to work out their sum, without letting them know ...

German researchers break W3C XML encryption standard

October 19, 2011

Standards are supposed to guarantee security, especially in the WWW. The World Wide Web Consortium (W3C) is the main force behind standards like HTML, XML, and XML Encryption. But implementing a W3C standard does not mean ...

World's toughest encryption scheme found 'vulnerable'

August 23, 2011

It was announced last week that cryptography researchers have found a “vulnerability” in the encryption scheme used in the vast majority of secure online transactions – a scheme known as AES-256.

Air Force grant to tighten online encryption

December 14, 2009

( -- Computer scientist Rafael Pass is seeking new approaches to cryptographic security with a $600,000, five-year grant from the Air Force Office of Scientific Research.

Recommended for you

New technique spots warning signs of extreme events

September 22, 2017

Many extreme events—from a rogue wave that rises up from calm waters, to an instability inside a gas turbine, to the sudden extinction of a previously hardy wildlife species—seem to occur without warning. It's often impossible ...


Adjust slider to filter visible comments by rank

Display comments: newest first

1 / 5 (1) Feb 19, 2013
This problem has already been solved in the Freemove Quantum Exchange System which is operational since 2007.

Some general information on this system can be found on

A proof this type of attack is not possible on certain schemes used in this system can eg. be found on

Note that in general it can be proven that a public-key scheme can not be unconditionally (so provable) secure.
1 / 5 (1) Feb 19, 2013
This problem has already been solved in the Freemove Quantum Exchange System

Quantum information transmission systems are stille very expensive - and won't be deployed fo private (or even most industrial) use for quite some time.

And quantum information systems have already been hacked (though not by circumventing the innate security, but by making use of the real-life shortcomings of the hardware)

There's a number of fun PDFs on this over at the quantum hacking lab
1 / 5 (1) Feb 19, 2013
@antialias_physorg : The Freemove Quantum Exchnage System to whihc is referred is not based on Quantum Information but on True Quantum Randomness Information-Theoretic Security. The information-theoretic proof to which is referred can be found on

Please sign in to add a comment. Registration is free, and takes less than a minute. Read more

Click here to reset your password.
Sign in to get notified via email when new comments are made.