Secure Groups for Threshold Cryptography and Number-Theoretic Multiparty Computation

Abstract

In this paper, we introduce secure groups as a cryptographic scheme representing finite groups together with a range of operations, including the group operation, inversion, random sampling, and encoding/decoding maps. We construct secure groups from oblivious group representations combined with cryptographic protocols, implementing the operations securely. We present both generic and specific constructions, in the latter case specifically for number-theoretic groups commonly used in cryptography. These include Schnorr groups (with quadratic residues as a special case), Weierstrass and Edwards elliptic curve groups, and class groups of imaginary quadratic number fields. For concreteness, we develop our protocols in the setting of secure multiparty computation based on Shamir secret sharing over a finite field, abstracted away by formulating our solutions in terms of an arithmetic black box for secure finite field arithmetic or for secure integer arithmetic. Secure finite field arithmetic suffices for many groups, including Schnorr groups and elliptic curve groups. For class groups, we need secure integer arithmetic to implement Shanks’ classical algorithms for the composition of binary quadratic forms, which we will combine with our adaptation of a particular form reduction algorithm due to Agarwal and Frandsen. As a main result of independent interest, we also present an efficient protocol for the secure computation of the extended greatest common divisor. The protocol is based on Bernstein and Yang’s constant-time 2-adic algorithm, which we adapt to work purely over the integers. This yields a much better approach for multiparty computation but raises a new concern about the growth of the Bézout coefficients. By a careful analysis, we are able to prove that the Bézout coefficients in our protocol will never exceed 3max(a,b) in absolute value for inputs a and b. We have integrated secure groups in the Python package MPyC and have implemented threshold ElGamal and threshold DSA in terms of secure groups. We also mention how our results support verifiable multiparty computation, allowing parties to jointly create a publicly verifiable proof of correctness for the results accompanying the results of a secure computation.

Keywords

• multiparty computation
• extended gcd
• elliptic curve cryptography
• class groups
• threshold cryptography