Systems that protect user metadata entirely with cryptographic privacy are intricate, and they endure versatility and speed issues that have so far limited their practicality. A few strategies can work rapidly yet give a lot more vulnerable security.
In a new study, MIT scientists have developed a new system called ‘XRD,’ a metadata-protection scheme that can handle cryptographic communications from millions of users in minutes.
First author Albert Kwon Ph.D. ’19, a recent graduate from the Computer Science and Artificial Intelligence Laboratory (CSAIL), said, “There is a huge lack in protection for metadata, which is sometimes very sensitive. The fact that I’m sending someone a message at all is not protected by encryption. Encryption can protect content well. But how can we fully protect users from metadata leaks that a state-level adversary can leverage?”
XRD has put a new spin on a traditional E2EE metadata-protecting scheme, called ‘mix nets,’ which was invented decades ago but suffers from scalability issues.
For XRD, the scientists invented a far more efficient version of the cryptographic proofs, called “aggregate hybrid shuffle,” that ensures servers are receiving and shuffling message correctly, to detect any malicious server activity.
To further boost efficiency, they split the servers into multiple chains and divide their use among users. (This is another traditional technique they improved upon.) Using some statistical methods, they estimate how many servers in each chain could be malicious, based on IP addresses and other information. From that, they calculate how many servers need to be in each chain to guarantee there’s at least one honest server. Then, they divide the users into groups that send duplicate messages to multiple, random chains, which further protects their privacy while speeding things up.
In computer simulations of activity from 2 million users sending messages on a network of 100 servers, XRD was able to get everyone’s messages through in about four minutes.
Kwon said, “This seems slow in terms of absolute speed in today’s communication world. But it’s important to keep in mind that the fastest systems right now [for metadata protection] take hours, whereas ours takes minutes.”
Joining Kwon on the paper are David Lu, an undergraduate in the Department of Electrical Engineering and Computer Science; and Srinivas Devadas, the Edwin Sibley Webster Professor of Electrical Engineering and Computer Science in CSAIL.
The paper is being presented at the USENIX Symposium on Networked Systems Design and Implementation.