by Staff Writers
Boston MA (SPX) Nov 04, 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 Medard, 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.
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, Medard, 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.
"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, Medard, 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.
Massachusetts Institute of Technology
Computer Chip Architecture, Technology and Manufacture
Nano Technology News From SpaceMart.com
|The content herein, unless otherwise known to be public domain, are Copyright 1995-2014 - Space Media Network. All websites are published in Australia and are solely subject to Australian law and governed by Fair Use principals for news reporting and research purposes. AFP, UPI and IANS news wire stories are copyright Agence France-Presse, United Press International and Indo-Asia News Service. ESA news reports are copyright European Space Agency. All NASA sourced material is public domain. Additional copyrights may apply in whole or part to other bona fide parties. Advertising does not imply endorsement, agreement or approval of any opinions, statements or information provided by Space Media Network on any Web page published or hosted by Space Media Network. Privacy Statement All images and articles appearing on Space Media Network have been edited or digitally altered in some way. Any requests to remove copyright material will be acted upon in a timely and appropriate manner. Any attempt to extort money from Space Media Network will be ignored and reported to Australian Law Enforcement Agencies as a potential case of financial fraud involving the use of a telephonic carriage device or postal service.|