The place of cryptography in the Internet-connected world has been part of a major discussion for many years. Users want the ability to stop other entities -- including the government -- from being able to read the content of what they encrypt.
Yet, law enforcement agencies see the need to be able to decrypt a criminal's communications to gain the information that these messages contain.
The two sides of the debate have been pulling at each other's positions since public key cryptography became routinely used. There is a real tension between what has been called the two essential components of modern societies: the human right to privacy and the rule of law to provide safety.
However, two researchers think they have found what could be an acceptable compromise for both sides.
In a paper published this week, "Crypto Crumple Zones: Enabling Limited Access Without Mass Surveillance," Charles Wright, an assistant professor of Computer Science at Portland State University, and Mayank Varia, a research associate professor at Boston University, and co-director for the RISCS Center, propose a new kind of access to encrypted messaging that is very expensive in resources to effect decryption.
The researchers believe that this high bar of resource commitment would limit its use to only to a subset of the total number of encrypted messages that exist, making routine surveillance impossible but allowing for a selective decryption of important ones.
Here's how Wright and Varia summed up this finding:
Our symmetric crumpling technique uses a hash-based proof of work to impose a linear cost on the adversary for each message s/he wishes to recover. Second, our public key abrasion method uses a novel application of Diffie-Hellman over modular arithmetic groups to create an extremely expensive puzzle that the adversary must solve before she can recover even a single message. Our constructions are very simple and lightweight, and they can be easily retrofitted onto existing applications and protocols. Critically, we introduce no new third parties, and we add no new messages beyond a single new Diffie-Hellman key exchange in protocols that already use Diffie-Hellman.
The methods described in the paper are not a backdoor into the encryption, which could completely weaken and break it, but a different way to extract information that would require much work be done before any specific decryption could occur.
One of the authors, Varia, has developed this new technique, which he calls cryptographic "crumpling." The allusion of the name is to the part of a design that fails in an emergency situation but saves the overall object by its failure.
One of the preconditions of crumpling would be strong, modern cryptography which would allow the secure inspection of a small number of messages, as well as protecting against man-in-the-middle attacks.
Varia basically places cryptographic puzzles into the generation of per-message cryptographic keys. The keys for the message will then be decryptable, but very hard to do. Each puzzle is chosen independently for each key, so effort for each message must be performed.
The fundamentals of network security are being redefined -- don't get left in the dark by a DDoS attack! Join us in Austin from May 14-16 at the fifth-annual Big Communications Event. There's still time to register and communications service providers get in free!
However, an additional "abrasion" puzzle is overlaid that is far more computationally expensive than the key's puzzles. This is thought to ensure only nation-state levels of adversaries -- as opposed to 400-pound hackers sitting in their parent's basement -- would be able to undertake the effort to decrypt.
The researchers, whose work was funded by the National Science Foundation, view what they have come up with as a catalyst for further exploration of this kind of approach. They believe that society as a whole will have to decide "whether to entrust the government with the power of targeted access and whether to accept the limitations on law enforcement possible with only targeted access."
— Larry Loeb has written for many of the last century's major "dead tree" computer magazines, having been, among other things, a consulting editor for BYTE magazine and senior editor for the launch of WebWeek.