Raising cryptography's standards

October 31, 2014

Most modern cryptographic schemes rely on computational complexity for their security. In principle, they can be cracked, but that would take a prohibitively long time, even with enormous computational resources.

There is, however, another notion of security -- information-theoretic security -- which means that even an adversary with unbounded computational power could extract no useful information from an encrypted message. Cryptographic schemes that promise information-theoretical security have been devised, but they're far too complicated to be practical.

In a series of papers presented at the Allerton Conference on Communication, Control, and Computing, researchers at MIT and Maynooth University in Ireland have shown that existing, practical cryptographic schemes come with their own information-theoretic guarantees: Some of the data they encode can't be extracted, even by a computationally unbounded adversary.

The researchers show how to calculate the minimum-security guarantees for any given encryption scheme, which could enable information managers to make more informed decisions about how to protect data.

"By investigating these limits and characterizing them, you can gain quite a bit of insight about the performance of these schemes and how you can leverage tools from other fields, like coding theory and so forth, for designing and understanding security systems," says Flavio du Pin Calmon, a graduate student in electrical engineering and computer science and first author on all three Allerton papers. His advisor, Muriel Médard, the Cecil E. Green Professor of Electrical Engineering and Computer Science, is also on all three papers; they're joined by colleagues including Ken Duffy of Maynooth and Mayank Varia of MIT's Lincoln Laboratory.

The researchers' mathematical framework also applies to the problem of data privacy, or how much information can be gleaned from aggregated -- and supposedly "anonymized" -- data about Internet users' online histories. If, for instance, Netflix releases data about users' movie preferences, is it also inadvertently releasing data about their political preferences? Calmon and his colleagues' technique could help data managers either modify aggregated data or structure its presentation in a way that minimizes the risk of privacy compromises.

Staying close

To get a sense of how the technique works, imagine an encryption scheme that takes only three possible inputs, or plaintexts -- "A," "B," and "C" -- and produces only three possible outputs, or ciphertexts. For each ciphertext, there is some probability that it encodes each of the three plaintexts.

The ciphertexts can be represented as points inside a triangle whose vertices represent the three possible plaintexts. The higher the probability that a given ciphertext encodes a particular plaintext, the closer it is to the corresponding vertex: Ciphertexts more likely to encode A than B or C are closer to vertex A than to vertices B and C. A secure encryption scheme is one in which the points describing the ciphertexts are clustered together, rather than spread out around the triangle. That means that no ciphertext gives an adversary any more information about the scheme than any other.

Of course, for most encrypted messages, there are way more than three possible corresponding plaintexts. Even a plaintext as simple as a nine-digit number has a billion possible values, so the probabilities corresponding to an encoded Social Security number would describe a point in a billion-dimensional space. But the general principle is the same: Schemes that yield closely clustered points are good, while schemes that don't are not.

An adversary wouldn't actually know the probabilities associated with any given ciphertext. Even someone with access to an encryption scheme's private key would have difficulty calculating them. For their analyses, Calmon, Médard, and their colleagues developed security metrics that hold for a wide range of distributions, and they augmented them with precise calculation of the worst cases -- the points farthest from the center of the main cluster. But the mathematical description of the degree to which the probabilities cluster together is a direct indication of how much information an adversary could, in principle, extract from a ciphertext.

Targeted protection

In their first Allerton paper, in 2012, the researchers used this probabilistic framework to demonstrate that, while a ciphertext as a whole may not be information-theoretically secure, some of its bits could be. It should thus be possible to devise encryption schemes that can't guarantee perfect security across the board but could provide it for particular data -- say, a Social Security number.

"Talking with cryptographers, they would always ask us, 'Oh, cool! You can guarantee that regardless of what you do, you can hide individual symbols. What about functions of the plaintext?'" Calmon says. "Standard cryptographic definitions of security care about that."

An encryption scheme might, that is, guarantee that an adversary can't extract an encoded Social Security number; but it might still allow the adversary to extract the last four digits of the number. Similarly, it might prevent an adversary from determining a subject's age; but it might allow the adversary to deduce that, say, the subject is between 30 and 40 years of age.

This is the problem that the researchers tackle in their last two Allerton papers. There, Calmon, Médard, and Varia show that if you can determine that a particular function is difficult or easy to extract from a ciphertext, then so are a host of correlated functions. In addition to addressing cryptographers' concerns about functions of the plaintext, this approach has the advantage of not requiring analysis of massively multidimensional probability spaces. Information about the security of a single function -- which can often be determined through a fairly simple analysis -- can provide strong guarantees about the security of an encryption scheme as a whole.
-end-
Written by Larry Hardesty, MIT News Office

Related links

Encryption is less secure than we thought

The elusive capacity of networks

Massachusetts Institute of Technology

Related Electrical Engineering Articles from Brightsurf:

Knotting semimetals in topological electrical circuits
Scientists created exotic states of matter using electrical circuit enhanced by machine-learning algorithm

Physicists make electrical nanolasers even smaller
Researchers cleared the obstacle that had prevented the creation of electrically driven nanolasers for integrated circuits.

Making plastic more transparent while also adding electrical conductivity
In an effort to improve large touchscreens, LED light panels and window-mounted infrared solar cells, researchers at the University of Michigan have made plastic conductive while also making it more transparent.

Using electrical stimulus to regulate genes
A team of researchers led by ETH professor Martin Fussenegger has succeeded in using an electric current to directly control gene expression for the first time.

2D oxide flakes pick up surprise electrical properties
Rice University researchers find evidence of piezoelectricity in lab-grown, two-dimensional flakes of molybdenum dioxide.

Electrical activity in living organisms mirrors electrical fields in atmosphere
A new Tel Aviv University study provides evidence for a direct link between electrical fields in the atmosphere and those found in living organisms, including humans.

3D-printed plastics with high performance electrical circuits
Rutgers engineers have embedded high performance electrical circuits inside 3D-printed plastics, which could lead to smaller and versatile drones and better-performing small satellites, biomedical implants and smart structures.

In and out with 10-minute electrical vehicle recharge
Electric vehicle owners may soon be able to pull into a fueling station, plug their car in, go to the restroom, get a cup of coffee and in 10 minutes, drive out with a fully charged battery, according to a team of engineers.

Electrical stimulation aids in spinal fusion
Spine surgeons in the U.S. perform more than 400,000 spinal fusions each year as a way to ease back pain and prevent vertebrae in the spine from wiggling around and doing more damage.

Fat pumps generate electrical power
A previously unknown electrical current develops in the body's cells when the vital fat pump function of the flippases transfers ('flips') lipids from the outer to the inner layer of the body's cell membranes.

Read More: Electrical Engineering News and Electrical Engineering Current Events
Brightsurf.com is a participant in the Amazon Services LLC Associates Program, an affiliate advertising program designed to provide a means for sites to earn advertising fees by advertising and linking to Amazon.com.