New research by the Cryptography Research Center at the Technology Innovation Institute (TII) could extend the utility of secure decentralized computation beyond simply processing bitcoin transactions to innovative new use cases in decentralized finance, health, and supply chain management. Humanity could greatly benefit from better algorithms that learn from medical, financial, and other sensitive data. But the desire for progress often must contend with privacy and security considerations of the underlying data. Consequently, researchers have explored various cryptographic techniques that securely and discretely process sensitive data.
Secure Multi-Party Computation (MPC) is one popular subfield of cryptography that explores methods for parties to jointly compute results without revealing the underlying data. One promising approach has been to translate existing calculations into the special mathematical structure of a ring.
Prior research developed some novel techniques for running these algorithms, but was limited to rings that support commutative calculations, such as A x B = B x A. Now TII researchers have generalized these techniques to non-commutative rings — such as matrices, or quaternions — which puts fewer constraints on developers.
Eduardo Soria-Vazquez, Senior Cryptographer at TII, said, “This simplifies the process for developers since they can now work with more general data structures.” This should dramatically reduce the complexity of crafting multi-party computing algorithms for applications like privacy-preserving machine learning, where a lot of matrix operations are involved. In addition, the new technique promises to significantly improve the efficiency of applications that involve a larger number of parties compared to traditional approaches.
Crafting better circuits
|The new technique can help computer scientists transform the calculations required for a particular algorithm into the kinds of abstractions needed to run on existing computers. At a base level, computers consist of logical circuits which are composed of various gates that perform logical operations on binary numbers such as AND, OR, and NOR operations. Over the years, computer scientists have found ever more efficient ways to represent the infinite range of real numbers that form the basis of standard arithmetic. A core component for this task is the arithmetic logic unit (ALU).
Many MPC protocols are performed over finite fields. Translating this logic to run on modern computer architectures introduces unnecessary overheads. One promising line of research on MPC discovered a way to securely compute functions over finite commutative rings, rather than finite fields. This shows tremendous promise when problems can be expressed in these mathematical structures, as those are the ones that ALUs are optimized for as well.
But since previous efforts only worked for commutative rings, many types of calculations had to be translated into multiple simpler algorithms, which added both computational overhead and complexity for the developer. The new technique can calculate these more complex types of algorithms, such as matrix multiplication, directly in one step. “Now we can work with this more general layer of abstraction,” Soria-Vazquez said.
Another benefit is that, as more parties are added to computation, the cost of these non-commutative operations does not grow as quickly as when they had to be emulated using the older approach. For example, an implementation that supports four parties would be twice as fast using the new technique, while an implementation that supports 64-parties would be six times as fast as the traditional one.
This should make it easier to extend MPC to more parties or use cases. For example, it would simplify the math of calculating better machine learning algorithms across a larger number of individual hospitals or data sources. It could also make it easier to distribute each person’s data across multiple physical locations to enhance security and then run MPC algorithms across the distributed data of a larger number of individuals.
Many kinds of privacy
MPC is but one approach in the broader field of privacy-preserving technologies. Other approaches include trusted enclaves, federated learning, and homomorphic encryption. Trusted enclaves send encrypted data to a security-hardened processor, decrypt it, and then run the computation in the clear. This approach promises the least developer and computational overhead, but its security has been repeatedly compromised both by researchers and practitioners.
Federated computing runs incremental machine learning training operations across data stored on each device and only sends the model update to the cloud. However, researchers have discovered disastrous weaknesses in some of the current implementations. Homomorphic encryption is one of the most secure approaches because it runs the computations against encrypted data. It is slower than MPC, since MPC protocols can combine different techniques —including homomorphic encryption itself.
MPC promises both flexibility and security since it can run computation against encrypted data streams without revealing the raw data to anyone. However, the additional security comes at a significant performance cost compared to running algorithms on unencrypted data. Soria-Vazquez said the state-of-the-art MPC approaches are still around two to three orders of magnitude slower than running similar algorithms on unencrypted data, depending on a multitude of aspects such as the networking and number of participants.
An important step
The new research represents an important step in improving the fluency of MPC. Previous approaches worked mostly over finite fields, which resulted in slower execution and harder to describe programs. Soria-Vazquez hopes that further research and collaboration could help generalize these techniques to other algebraic and data structures, dramatically simplifying application development. He expects to see some early use cases in applications like crafting privacy-preserving machine learning. More significantly, the new research improves the understanding of the theoretical requirements for MPC, which creates the opportunity for further advances in the future.
TagsCryptography Research Center Edit Post
