by Mark Abspoel (CWI), Ronald Cramer (CWI and Leiden University) and Daniel Escudero (Aarhus University)
Secure computation with integers modulo powers of two has immense practical impact due to the use of these types in modern hardware. Unfortunately, the lack of a good algebraic structure makes the task of designing secure computation protocols over these domains a complex endeavour, which we approach in this project.
The goal of this project is to design protocols that enable a set of mutually distrustful parties to securely compute a function that is described using standard operations on integers modulo powers of two, while keeping the inputs to the function private and revealing only the output.
Traditional approaches to this problem do not support integers modulo powers of two, but rather focus on integers modulo a prime number. This is because of the nice algebraic structure that results in this case: every non-zero element admits a multiplicative inverse, and this helps immensely in the task of designing secure computation protocols. However, modern hardware and modern computations do not tend to make use of this type of arithmetic. Instead, it is more common to find arithmetic modulo powers of two, as is the case with the standard datatypes int32 and int64 found in most programming languages.
It is motivated by these issues that, as the first outcome of this project, the protocol SPDZ2k for power-of-two computation, the first one of its kind to tolerate active corruptions of all-but-one of the participants, was developed [1]. This protocol is built by adapting the message authentication codes from other protocols, like the SPDZ and MASCOT, to the power-of-two setting, a non-trivial task that was able to find many applications beyond this particular protocol.
The SPDZ2k protocol was implemented as part of the follow-up work [2]. There it is shown that, as expected, computation modulo powers of two via the SPDZ2k protocol has the potential to provide noticeable speedups with respect to other types of computation. This is particularly relevant for computations that require operations at the "bit level", such as secure comparisons, bit decompositions, or arithmetic over the reals (emulated via fixed point arithmetic). Furthermore, SPDZ2k was found to be particularly suitable for machine learning applications, such as SVM or decision trees evaluation. Finally, SPDZ2k is already implemented in one of the most popular secure multiparty computation frameworks: MP-SPDZ. This software enables the programmer to securely evaluate a function by simply writing high level Python-like code.
The SPDZ2k protocol tolerates a dishonest majority, that is, even if all but one parties are maliciously corrupted, the privacy of the remaining honest party is maintained. However, there are some settings in which it is reasonable to assume that not all parties are corrupted. If only the minority of the parties is corrupted, protocol design is highly simplified because the set of cryptographic techniques that can be used are much more efficient and simple. Unfortunately, like the dishonest majority setting, most protocols have been designed to operate over highly restrictive algebraic structures. As an outcome of this project [3], a set of protocols that tolerate fewer corruptions but achieve higher notions of security –such as perfect or statistical security – were devised. These are rooted in standard techniques to distribute a secret among several participants using Shamir secret sharing but extending them to work even if the underlying algebraic structure is not a field, as is typically assumed.
Improving the efficiency of secure computation protocols is still one of the biggest open problems in the area and considering computation domains such as integers modulo powers of two seems to be a promising way to move forward. This project will continue to expand this knowledge barrier in several directions, including more practical protocols, as well as theoretical results that illustrate how far can computation with powers-of-two moduli can be pushed.
References:
[1] R. Cramer, I. Damgård, D. Escudero, P. Scholl, and C. Xing. “SPDZ2k: Efficient MPC mod 2^k for Dishonest Majority.” CRYPTO 2018. Springer, 2018.
[2] I. Damgård, D. Escudero, T. K. Frederiksen, M. Keller, P. Scholl, and N. Volgushev. “New primitives for actively-secure MPC over rings with applications to private machine learning.” 2019 IEEE Symposium on Security and Privacy (S&P). IEEE, 2019.
[3] M. Abspoel, R. Cramer, I. Damgård, D. Escudero, and C. Yuan. “Efficient Information-Theoretic Secure Multiparty Computation over Z/p^k Z via Galois Rings.” Theory of Cryptography Conference (TCC 2019). Springer, 2019.
[4] R. Cramer, I. Damgård, and J. Nielsen. Secure Multiparty Computation and Secret Sharing. Cambridge University Press, 2015
Please contact:
Mark Abspoel
CWI, The Netherlands
Ronald Cramer
CWI and Leiden University, The Netherlands
Daniel Escudero
Aarhus University, Denmark
