Canary in the data mine

For anyone who uses a computer—and that’s all of us—random numbers are important. Without randomness, all encrypted operations would be predictable and hence insecure. However, reliance on randomness has long prevented experts from achieving “local testability”—the ability to quickly determine whether messages have been tampered with.

Now, Prof. Irit Dinur of the Weizmann Institute’s Department of Computer Science and Applied Mathematics has created a technique that transforms an encoded message into a so-called “super-canary”—an ideal code that reveals the existence of corruption buried anywhere in the code’s superstructure, based on simple testing at just a few spots. Working together with mathematicians

at the Hebrew University of Jerusalem, the Dinur team’s achievement is  a  breakthrough in computer science theory, as well as a practical step forward in protecting the data upon which we all depend.

In mathematics, many say, the opposite of randomness is structure, and so Prof. Dinur’s novel approach is based on a structure that is particularly complex: a multidimensional graph. Data encoded in this “strongbox” can be tested locally, making it obvious if it has been accessed or changed.

Although Prof. Dinur’s sophisticated  graph  is impossible to visualize—“That’s the whole point,” she says—the scientists’ work has brought something else clearly into view: a new and powerful way to keep our most important data secure.

Prof. Irit Dinur is supported by:   - Helen and Martin Kimmel Award for Innovative Investigation

                                                     - Prof. Dinur is the incumbent of the Dr. Hymie Moross Professorial Chair