How can two parties guarantee that their communications are not tampered with by an outside party? UCLA computer scientists have developed a new method to address this problem. Their work creates what is called a “non-malleable commitment,” an electronic equivalent of a locked box.
Using new mathematical proofs that they developed, the researchers have demonstrated that this is a secure way to protect data being sent between two parties. This work is the first solution supported by such proofs that requires only two rounds of one-way communication from the sender to the recipient.
The research paper (PDF) was presented at the 2016 IEEE Foundations of Computer Science symposium, considered the most prestigious conference in the field of theoretical computer science, held earlier this month. The authors of the paper are computer science professor Amit Sahai; Dakshita Khurana, a UCLA computer science doctoral student working with Sahai; and Vipul Goyal, of Microsoft Research, India, a former graduate student of Sahai’s.
“Consider a sealed bid auction and suppose that you are asked to send your bid in an envelope, but you don’t trust the delivery agent,” Sahai said. “You’re worried that they might be working for other bidders, and may open your envelope, tamper with your bid, and deliver a tampered message in its place,” he said.
“In real life, you might solve this problem by mailing a securely locked box with your message inside, and then separately mail the key after the auctioneer has already received your locked box,” he said. “We’re looking for the cyber equivalent of this ‘lockbox-and-key’ method.”
A sender can “lock” his or her message in this virtual box, and only later, provide a key to open it. An interceptor, who does not know the key, not only would have no idea what message is inside the box but also would not be able to come up with a new virtual lockbox that hides a related message.
That the non-malleable commitment only requires one-way communication is important, as the auction house may be corresponding with multiple bidders, and it would be cumbersome to require the auction house to engage in a back-and-forth with each bidder. Instead, the bids are secured by the senders only.
The main idea behind the work is a new mathematical construction that proceeds in two rounds of communication. In the first round, a sender sends several messages, but only some of them are important. It is in the second round that the sender reveals which messages were important. As Khurana explained in her presentation at the symposium, it is possible to prove that if an adversary tries to corrupt messages in the first round, he will be unable to complete the second round without invalidating his communication entirely.
The concept of a non-malleable commitment has uses far beyond electronic auctions to situations where guaranteeing data integrity is important, Khurana said.
Sahai described one hypothetical example of the application called “secure multi-party computation.”
“Suppose that several space agencies want to launch satellites into orbit, and they want to make sure that these satellites will not collide with each other,” he said. “But they want to do this without revealing the planned orbits to each other.”
He explained that data integrity would be a big concern if, for example, one member of the group wants to trigger false warnings of a potential collision, by declaring that his satellite’s orbit will be the same as the orbit of another member’s satellite.
“Non-malleable commitments can be used to solve this problem,” Sahai said, “allowing the group to learn whether their planned satellite orbits are safe, without revealing anything more about the orbits of any satellite.”
Other possible scenarios where the method could be applied include a group of hospitals collaborating to find cures for diseases without wanting to give out confidential patient information; or several companies that want to find out if they have been victims of the same cyber-attack without revealing the specific attacks the companies have suffered.
“Constructing non-malleable commitments is a key prerequisite to solving these problems,” Khurana said.
The research was supported by the National Science Foundation. Khurana and Sahai are affiliated with UCLA’s Center for Encrypted Functionalities. Sahai is the center’s director and Khurana is a student member.