Forum for Science, Industry and Business

Sponsored by:     3M 
Search our Site:

 

Computer scientists develop 'mathematical jigsaw puzzles' to encrypt software

30.07.2013
Software remains completely functional but impervious to reverse-engineering

UCLA computer science professor Amit Sahai and a team of researchers have designed a system to encrypt software so that it only allows someone to use a program as intended while preventing any deciphering of the code behind it. This is known in computer science as "software obfuscation," and it is the first time it has been accomplished.

Sahai, who specializes in cryptography at UCLA's Henry Samueli School of Engineering and Applied Science, collaborated with Sanjam Garg, who recently earned his doctorate at UCLA and is now at IBM Research; Craig Gentry, Shai Halevi and Mariana Raykova of IBM Research; and Brent Waters, an assistant professor of computer science at the University of Texas at Austin. Garg worked with Sahai as a student when the research was done.

Their peer-reviewed paper will be formally presented in October at the 54th annual IEEE Symposium on Foundations of Computer Science, one of the two most prominent conferences in the field of theoretical computer science. Sahai has also presented this research in recent invited talks at Stanford University and the Massachusetts Institute of Technology.

"The real challenge and the great mystery in the field was: Can you actually take a piece of software and encrypt it but still have it be runnable, executable and fully functional," Sahai said. "It's a question that a lot of companies have been interested in for a long time."

According to Sahai, previously developed techniques for obfuscation presented only a "speed bump," forcing an attacker to spend some effort, perhaps a few days, trying to reverse-engineer the software. The new system, he said, puts up an "iron wall," making it impossible for an adversary to reverse-engineer the software without solving mathematical problems that take hundreds of years to work out on today's computers — a game-change in the field of cryptography.

The researchers said their mathematical obfuscation mechanism can be used to protect intellectual property by preventing the theft of new algorithms and by hiding the vulnerability a software patch is designed to repair when the patch is distributed.

"You write your software in a nice, reasonable, human-understandable way and then feed that software to our system," Sahai said. "It will output this mathematically transformed piece of software that would be equivalent in functionality, but when you look at it, you would have no idea what it's doing."

The key to this successful obfuscation mechanism is a new type of "multilinear jigsaw puzzle." Through this mechanism, attempts to find out why and how the software works will be thwarted with only a nonsensical jumble of numbers.

"The real innovation that we have here is a way of transforming software into a kind of mathematical jigsaw puzzle," Sahai said. "What we're giving you is just math, just numbers, or a sequence of numbers. But it lives in this mathematical structure so that these individual pieces, these sequences of numbers, can only be combined with other numbers in very specified ways.

"You can inspect everything, you can turn it upside-down, you can look at it from different angles and you still won't have any idea what it's doing," he added. "The only thing you can do with it is put it together the way that it was meant to interlock. If you tried to do anything else — like if you tried to bash this piece and put it in some other way — you'd just end up with garbage."

Functional encryption

The new technique for software obfuscation paved the way for another breakthrough called functional encryption. With functional encryption, instead of sending an encrypted message, an encrypted function is sent in its place. This offers a much more secure way to protect information, Sahai said. Previous work on functional encryption was limited to supporting very few functions; the new work can handle any computable function.

For example, a single message could be sent to a group of people in such a way that each receiver would obtain different information, depending on characteristics of that particular receiver. In another example, a hospital could share the outcomes of treatment with researchers without revealing details such as identifying patient information.

"Through functional encryption, you only get the specific answer, you don't learn anything else," Sahai said.

The UCLA-based researchers were funded in part by the National Science Foundation, a Xerox Faculty Research Award, a Google Faculty Research Award, an equipment grant from Intel and an Okawa Foundation Research Grant.

The UCLA Henry Samueli School of Engineering and Applied Science, established in 1945, offers 28 academic and professional degree programs and has an enrollment of more than 5,000 students. The school's distinguished faculty are leading research to address many of the critical challenges of the 21st century, including renewable energy, clean water, health care, wireless sensing and networking, and cyber-security. Ranked among the top 10 engineering schools at public universities nationwide, the school is home to eight multimillion-dollar interdisciplinary research centers in wireless sensor systems, wireless health, nanoelectronics, nanomedicine, renewable energy, customized computing, the smart grid, and the Internet, all funded by federal and private agencies and individual donors. (http://www.engineer.ucla.edu | http://www.twitter.com/uclaengineering)

For more news, visit the UCLA Newsroom and follow us on Twitter.

Matthew Chin | EurekAlert!
Further information:
http://www.ucla.edu

More articles from Information Technology:

nachricht Fraunhofer FIT announces CloudTeams collaborative software development platform – join it for free
10.01.2017 | Fraunhofer-Institut für Angewandte Informationstechnik FIT

nachricht Electron-photon small-talk could have big impact on quantum computing
23.12.2016 | Princeton University

All articles from Information Technology >>>

The most recent press releases about innovation >>>

Die letzten 5 Focus-News des innovations-reports im Überblick:

Im Focus: Designing Architecture with Solar Building Envelopes

Among the general public, solar thermal energy is currently associated with dark blue, rectangular collectors on building roofs. Technologies are needed for aesthetically high quality architecture which offer the architect more room for manoeuvre when it comes to low- and plus-energy buildings. With the “ArKol” project, researchers at Fraunhofer ISE together with partners are currently developing two façade collectors for solar thermal energy generation, which permit a high degree of design flexibility: a strip collector for opaque façade sections and a solar thermal blind for transparent sections. The current state of the two developments will be presented at the BAU 2017 trade fair.

As part of the “ArKol – development of architecturally highly integrated façade collectors with heat pipes” project, Fraunhofer ISE together with its partners...

Im Focus: How to inflate a hardened concrete shell with a weight of 80 t

At TU Wien, an alternative for resource intensive formwork for the construction of concrete domes was developed. It is now used in a test dome for the Austrian Federal Railways Infrastructure (ÖBB Infrastruktur).

Concrete shells are efficient structures, but not very resource efficient. The formwork for the construction of concrete domes alone requires a high amount of...

Im Focus: Bacterial Pac Man molecule snaps at sugar

Many pathogens use certain sugar compounds from their host to help conceal themselves against the immune system. Scientists at the University of Bonn have now, in cooperation with researchers at the University of York in the United Kingdom, analyzed the dynamics of a bacterial molecule that is involved in this process. They demonstrate that the protein grabs onto the sugar molecule with a Pac Man-like chewing motion and holds it until it can be used. Their results could help design therapeutics that could make the protein poorer at grabbing and holding and hence compromise the pathogen in the host. The study has now been published in “Biophysical Journal”.

The cells of the mouth, nose and intestinal mucosa produce large quantities of a chemical called sialic acid. Many bacteria possess a special transport system...

Im Focus: Newly proposed reference datasets improve weather satellite data quality

UMD, NOAA collaboration demonstrates suitability of in-orbit datasets for weather satellite calibration

"Traffic and weather, together on the hour!" blasts your local radio station, while your smartphone knows the weather halfway across the world. A network of...

Im Focus: Repairing defects in fiber-reinforced plastics more efficiently

Fiber-reinforced plastics (FRP) are frequently used in the aeronautic and automobile industry. However, the repair of workpieces made of these composite materials is often less profitable than exchanging the part. In order to increase the lifetime of FRP parts and to make them more eco-efficient, the Laser Zentrum Hannover e.V. (LZH) and the Apodius GmbH want to combine a new measuring device for fiber layer orientation with an innovative laser-based repair process.

Defects in FRP pieces may be production or operation-related. Whether or not repair is cost-effective depends on the geometry of the defective area, the tools...

All Focus news of the innovation-report >>>

Anzeige

Anzeige

Event News

12V, 48V, high-voltage – trends in E/E automotive architecture

10.01.2017 | Event News

2nd Conference on Non-Textual Information on 10 and 11 May 2017 in Hannover

09.01.2017 | Event News

Nothing will happen without batteries making it happen!

05.01.2017 | Event News

 
Latest News

Solar Collectors from Ultra-High Performance Concrete Combine Energy Efficiency and Aesthetics

16.01.2017 | Trade Fair News

3D scans for the automotive industry

16.01.2017 | Automotive Engineering

Nanoparticle Exposure Can Awaken Dormant Viruses in the Lungs

16.01.2017 | Life Sciences

VideoLinks
B2B-VideoLinks
More VideoLinks >>>