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.

1. Introduction

A finite group is defined as a finite set of group elements together with an associative group operation and the corresponding inverse operation. We introduce secure groups as an oblivious data structure implementing finite groups in a privacy-preserving manner. Both the representation of group elements and the implementation of the group operations should be oblivious, meaning that no information can be inferred about the values of the group elements involved. Secure groups aim to significantly simplify implementations of threshold cryptography, providing efficient primitives for typical cryptographic operations such as secure exponentiation, random sampling, and encoding/decoding. This paper is an extended version of our paper published in CSCML 2023 [1].

We develop the underlying protocols in the setting of secure multiparty computation (MPC) based on Shamir secret sharing over a finite field. We will distinguish between generic constructions and specific constructions for finite groups used in cryptography, particularly the group of quadratic residues, elliptic curve groups, and class groups.

Generic constructions include the application of secure table lookup to the multiplication table of the group. Also, if a faithful linear representation over a finite field is available from representation theory, it directly permits an oblivious representation of the group elements (as square matrices over a finite field) and an oblivious implementation of the group operation (as matrix multiplication). We note that Bar-Ilan and Beaver already considered a generic protocol for secure inversion of group elements as a natural generalization of secure matrix multiplication ([2] Lemma 6). In general, the implementation of basic tasks such as the group operation and en/decoding depends on the representation of the secure group. Where practical, we may look for generic implementations first. Therefore, we present generic protocols for the following tasks: conditional (if–else), random sampling, inversion, and exponentiation.

We also define specific oblivious representations and operations for a set of frequently used finite groups. The multiplicative group ${\mathbb{F}}_q^{*}$ and any of its subgroups (quadratic residues and, more generally, Schnorr groups) directly permit an oblivious representation and group operation using secret shares over ${\mathbb{F}}_q$. Encoding and decoding for these groups is in general hard, so we present several techniques and trade-offs focusing on quadratic residues. Groups defined on elliptic curves over finite fields directly permit an oblivious representation. To facilitate the implementation of such groups, we employ complete formulas known for Weierstrass and Edwards curves. We employ a result from [3] for parallel architectures, which yields a secure group operation of particularly low multiplicative depth. Ideal class groups of imaginary quadratic fields have been studied extensively for use in cryptography by Buchmann et al. (see [4] and references therein) and recently received renewed interest (see, e.g., [5,6,7]). For the implementation of the class group operation, we present efficient protocols for the composition and reduction of binary quadratic forms.

A key step in our protocol for the composition of binary quadratic forms is the secure computation of the extended greatest common divisor. We start from the constant-time algorithms proposed by Bernstein and Yang [8]. Their approach relies on the use of 2-adic arithmetic, but we will work purely over the integers for an efficient solution in an MPC setting. The core of the protocol centers around Bernstein and Yang’s divsteps2 algorithm, which takes a fixed number of roughly $3\mathsf{\ell }$ iterations when run on numbers of bit length at most ℓ. The work for each iteration is dominated by secure comparisons with numbers of bit length at most ${log}_2\mathsf{\ell }$, requiring $O(log\mathsf{\ell })$ secure multiplications each. We develop a novel analysis showing that the Bézout coefficients are bounded above by $3max(a,b)$ in absolute value when computing the extended greatest common divisor of numbers a and b. The total number of $O(\mathsf{\ell }log\mathsf{\ell })$ secure multiplications compares favorably to, e.g., a basic binary gcd algorithm ([9] Algorithm 14.61), which requires $O\left({\mathsf{\ell }}^2\right)$ secure multiplications. Other binary gcd algorithms such as Bojanczyk and Brent [10] (and related algorithms as considered by [8]) as well as the algorithm attributed to Penk ([11] Vol. 2, Exercise 4.5.2.39) also lead to $O\left({\mathsf{\ell }}^2\right)$ secure multiplications due to the use of either full-size ℓ-bit secure comparisons or inner loops requiring $O\left(\mathsf{\ell }\right)$ secure multiplications in the worst case.

To obtain an efficient protocol for the reduction of forms, we start from the algorithm proposed by Agarwal and Frandsen [12]. A key property of their approach is that the use of full integer divisions is avoided in the main loop of the form reduction algorithm. We show how to adapt their algorithm to an MPC setting such that the work for each iteration of the main loop is limited to a small constant number of secure comparisons and operations of similar complexity requiring $O\left(\mathsf{\ell }\right)$ secure multiplications each. For discriminant $\Delta <0$ of bit length ℓ and forms with coefficients all of bit length at most ℓ, we show that $\mathsf{\ell }/2$ iterations suffice for the reduction, which leads to $O\left({\mathsf{\ell }}^2\right)$ secure multiplications overall.

Finally, as related work in the area of threshold cryptography, we note that several papers on threshold signatures [13,14], threshold $\mathsf{\Sigma }$-proofs [15], and verifiable (or auditable) MPC [16,17] implicitly implement some form of secure groups for ${\mathbb{F}}_q^{*}$ or elliptic curves, but these papers do not treat secure groups in general terms.

The paper is organized as follows. Above, we have elaborated on our contributions and related work regarding secure groups. In Section 2, we present preliminaries on secure multiparty computation. Section 3 presents our efficient protocol for the extended greatest common divisor, including a careful analysis establishing a nontrivial bound on the growth of the Bézout coefficients. Section 4 introduces our cryptographic scheme for secure groups. In Section 5, we present generic constructions for secure groups, and, in Section 6, we present generic protocols for the following tasks: conditional (if–else), random sampling, inversion, and exponentiation. Section 7 presents specific constructions and protocols for groups used in cryptography, particularly quadratic residues, elliptic curve groups, and class groups. As an example application in threshold cryptography, Section 8 presents a simple threshold cryptosystem built from secure groups. We conclude in Section 9 with remarks about implementations and applications.

2. MPC Setting

We consider an MPC setting with m parties tolerating a dishonest minority of up to t passively corrupt parties, $0\le t<m/2$. The basic protocols for secure addition and multiplication over a finite field rely on Shamir secret sharing [18,19], easily extended to cover secure and efficient dot products as well. We write $\left[\right[a\left]\right]$ (also ${\left[\left[a\right]\right]}_p$) for a Shamir secret sharing of a finite field element $a\in {\mathbb{F}}_{p^d}$, where we assume $p^d>m$. For secure integer arithmetic, we have $d=1$ (prime fields) and use the common representation for signed integers a in a bounded range, e.g., with $len\left(a\right)\le \mathsf{\ell }\ll p$, where $len\left(a\right)=\lceil {log}_2\left(\right|a|+1)\rceil$. The amount $len\left(p\right)-\mathsf{\ell }$ of excess bits is often referred to as “headroom”.

To operate on secret-shared integer values, we use common protocols for secure integer arithmetic as building blocks. For example, we let $\left[\left[r\right]\right]\leftarrow \mathsf{random}\left({\mathbb{F}}_p\right)$ denote the generation of a uniformly random $r{\in }_R{\mathbb{F}}_p$ and $\left[\left[a_0\right]\right],\dots ,\left[\left[a_{\mathsf{\ell }-1}\right]\right]\leftarrow \mathsf{bits}\left(\left[\left[a\right]\right]\right)$ denote the bit decomposition of a. Also, $\left[\right[e\left]\right]\leftarrow \mathsf{if}\_\mathsf{else}\left(\right[\left[c\right]],[\left[a\right]],[\left[b\right]\left]\right)$ denotes the secure conditional, where $e=c(a-b)+b$. A protocol that generates a vector of j secret-shared bits in ${\mathbb{F}}_p\cap \{0,1\}$ is denoted by $\mathsf{random}-\mathsf{bits}({\mathbb{F}}_p,j)$. See [20,21,22] for these and other common MPC protocols, which we will use as black boxes.

We also use secure integer division $\left(\right[\left[q\right]],[\left[r\right]\left]\right)\leftarrow \mathsf{divmod}\left(\right[\left[a\right]],[\left[b\right]\left]\right)$ with $a=bq+r$ and $0\le r<b$ as a primitive. Our implementation is based on the Newton–Raphson method [23,24,25]. Finally, we assume an efficient protocol for securely determining the bit length $\left[\right[len\left(a\right)\left]\right]$. See also Section 9.

3. Secure Extended GCD

This section presents a new protocol for the secure computation of the extended greatest common divisor (xgcd) of secret-shared integers. In Section 7.3, we use this protocol for the composition of binary quadratic forms in secure class groups.

We first present Algorithm 1, which can be viewed as an alternative to the divsteps2 algorithm by Bernstein and Yang [8], on which it is based, but without the use of any 2-adic arithmetic. Algorithm 1 works purely over the integers. To compute, for instance, a modular inverse, we do not need any (potentially costly) pre- or post-processing (in contrast to Bernstein and Yang’s algorithm recip2), which would complicate the conversion to an MPC protocol. Hence, our xgcd algorithm may also be of independent interest for other settings in which the use of 2-adic arithmetic is not straightforward. (Using precomputation for modular inverses can be beneficial, particularly in applications that reuse the modulus. In settings where inputs are not reusable, the precomputation cannot be reused. This is the case in our application of the xgcd to compute class group operations).

Algorithm 1 $\mathsf{xgcd}$($n,a,b$)                   $n,a,b\in \mathbb{N}$, a odd

1: $\delta ,f,g,u,v,q,r\leftarrow 1,a,b,1,0,0,1$          ▹  $f=ua+vb$, $g=qa+rb$  2: for $i=1$ to n do  3:     $g_0\leftarrow gmod2$  4:     if $\delta >0\mathrm{and}{g}_0=1$ then  5:         $\delta ,f,g,u,v,q,r\leftarrow -\delta ,g,-f,q,r,-u,-v$  6:     if $g_0=1$ then  8:         $g,q,r\leftarrow g+f,q+u,r+v$  8:     if $rmod2=1$ then  9:         $q,r\leftarrow q-b,r+a$ 10:     $\delta ,g,q,r\leftarrow \delta +1,g/2,q/2,r/2$ 11: if $f<0$ then 12:     $f,u,v\leftarrow -f,-u,-v$ 13: return $f,u,v$

As a starting point, we take the constant-time extended gcd algorithm divsteps2 by Bernstein and Yang ([8] Figure 10.1). Our protocol xgcd, see Protocol 1, retains the algorithmic flow of their divsteps2 algorithm, which is controlled by the following step function ([8] Section 8):

$$\mathsf{divstep}(\delta ,f,g)=\left\{\begin{array}{cc}(1-\delta ,g,(g-f)/2),\hfill & \mathrm{if}\delta >0\mathrm{and}g\mathrm{is}\mathrm{odd},\hfill \\ (1+\delta ,f,(g+(gmod2)f)/2),\hfill & \mathrm{otherwise}.\hfill \end{array}\right.$$

(1)

Throughout, variable f is ensured to be an odd integer, and therefore the divisions by 2 are without remainder in both cases of the step function. Bernstein and Yang argue that this step function compares favorably with alternatives from the literature, e.g., the Brent–Kung step function [26] and the Stehlé–Zimmermann step function [27]. The computational overhead of function divstep is small, and the required number of iterations n as a function of the bit lengths of the inputs a and b compares favorably with the alternatives. Concretely, with $({\delta }_n,f_n,g_n)={\mathsf{divstep}}^n(1,a,b)$ for odd a, Bernstein and Yang prove that $f_n=gcd(a,b)$ and $g_n=0$ holds for $n=\mathsf{iterations}\left(\mathsf{\ell }\right)$, where $\mathsf{\ell }=max(len(a),len(b\left)\right)$ and

$$\mathsf{iterations}\left(d\right)=\left\{\begin{array}{cc}\lfloor (49d+80)/17\rfloor ,\hfill & \mathrm{if}d<46,\hfill \\ \lfloor (49d+57)/17\rfloor ,\hfill & \mathrm{otherwise}.\hfill \end{array}\right.$$

(2)

Hence, $\mathsf{iterations}\left(\mathsf{\ell }\right)\approx 3\mathsf{\ell }$.

The first major change compared to Bernstein and Yang’s divsteps2 algorithm is that we entirely drop the use of truncation for f and g. In our MPC setting, f and g are secret-shared values (over a prime field of large order) and, therefore, limiting the sizes of f and g is not useful. The second major change is that we will avoid the use of 2-adic arithmetic entirely by ensuring that the Bézout coefficients will remain integral throughout all iterations. Concretely, this means that we will make sure that coefficients q and r are even before the division by 2 at the end of each iteration: if q and r are odd, we use $q-b$ and $r+a$ instead, which will then be even because a is odd by assumption. We thus obtain Algorithm 1 as an alternative to Bernstein–Yang’s constant-time algorithm.

Protocol 1 $\mathsf{xgcd}$($n,\left[\right[a\left]\right],\left[\right[b\left]\right]$)                $n,a,b\in \mathbb{N}$, a odd

1: $\left[\right[\delta \left]\right],\left[\right[f\left]\right],\left[\right[g\left]\right],\left[\right[v\left]\right],\left[\right[r\left]\right]\leftarrow 1,\left[\right[a\left]\right],\left[\right[b\left]\right],0,1$  2: for $i=1$ to n do  3:     $\left[\left[g_0\right]\right]\leftarrow \left[[gmod2]\right]$  4:     if $\left[\left[\delta \right]\right]>0\mathrm{and}\left[\left[g_0\right]\right]=1$ then  5:         $\left[\right[\delta \left]\right],\left[\right[f\left]\right],\left[\right[g\left]\right],\left[\right[v\left]\right],\left[\right[r\left]\right]\leftarrow -\left[\right[\delta \left]\right],\left[\right[g\left]\right],-\left[\right[f\left]\right],\left[\right[r\left]\right],-\left[\right[v\left]\right]$  6:     if $\left[\left[g_0\right]\right]=1$ then  7:         $\left[\right[g\left]\right],\left[\right[r\left]\right]\leftarrow \left[\right[g\left]\right]+\left[\right[f\left]\right],\left[\right[r\left]\right]+\left[\right[v\left]\right]$  8:     if $\left[\right[rmod2\left]\right]=1$ then  9:         $\left[\right[r\left]\right]\leftarrow \left[\right[r\left]\right]+\left[\right[a\left]\right]$ 10:     $\left[\right[\delta \left]\right],\left[\right[g\left]\right],\left[\right[r\left]\right]\leftarrow \left[\right[\delta \left]\right]+1,\left[\right[g\left]\right]/2,\left[\right[r\left]\right]/2$ 11: if $\left[\right[f\left]\right]<0$ then 12:     $\left[\right[f\left]\right],\left[\right[v\left]\right]\leftarrow -\left[\right[f\left]\right],-\left[\right[v\left]\right]$ 13: $\left[\right[u\left]\right]\leftarrow \left(\right[\left[f\right]]-[\left[v\right]]*[\left[b\right]\left]\right)/\left[\right[a\left]\right]$ 14: return $\left[\right[f\left]\right],\left[\right[u\left]\right],\left[\right[v\left]\right]$             ▹  $f=ua+vb=gcd(a,b)$

We turn Algorithm 1 into a secure protocol operating on secret-shared values as follows. We drop variables q and u from the main loop and instead set $u=(f-vb)/a$ at the end. Overall, this saves $3n$ secure multiplications for q and n secure multiplications for u, which are otherwise needed to implement the if–then statements obliviously. See Protocol 1 for the result.

All operations on the remaining variables $\delta ,g,f,v,r$ are completed securely. The secure computations of $\left[\right[gmod2\left]\right]$ and $\left[\right[rmod2\left]\right]$ are completed by using a secure protocol for computing the least significant bit. The secure computation of $\left[\right[\delta >0\left]\right]$ is the most expensive part of each iteration. However, by taking into account that $\delta$ is bounded above by $i+1$, we can further reduce the cost of this secure comparison.

The result is a secure protocol with a single loop of $n\approx 3\mathsf{\ell }$ iterations, where ℓ denotes the maximum bit length for a and b. Per iteration, the work is proportional to $O(log\mathsf{\ell })$ secure multiplications as the comparison for $log\mathsf{\ell }$ bit numbers determines the complexity of the adapted divstep. The resulting $O(\mathsf{\ell }log\mathsf{\ell })$ compares favorably to, e.g., the binary extended gcd from ([9] Algorithm 14.61), which would require $O\left({\mathsf{\ell }}^2\right)$ secure multiplications.

For the general case, where a is not known to be odd, we use an auxiliary protocol to securely count the number of trailing zeros of a given secret-shared integer. We have designed and implemented a novel approach requiring $O\left(\mathsf{\ell }\right)$ secure multiplications in $O\left(1\right)$ rounds for this task. Moreover, we have designed and implemented protocols for the secure modular inverse of a modulo b (provided $gcd(a,b)=1$), and for computing $gcd(a,b)$ and $lcm(a,b)$ securely. See also Section 9.

We conclude this section with a result on the bounds for the Bézout coefficients computed by our xgcd algorithm (and protocol). The novelty of this result is due to the fact that the bounds are explicit (avoiding big-O notation), while the xgcd algorithm avoids full-sized comparisons to control the size of intermediate variables. To this end, we analyze Algorithm 1 and show in Theorem 1 below that the Bézout coefficients are bounded by $3a$.

For the analysis, we partition an execution of Algorithm 1 into k consecutive runs as follows. A new run starts with each assignment to variable v: the first run starts with the initialization $v\leftarrow 0$ in the first line and each next run starts with an update $v\leftarrow r$ in line 5.

By $v_j$, we denote the value assigned to v at the start of the jth run, $1\le j\le k$. Hence, $v_1=0$ and $v_k$ will be the final value of v. We define $v_0=-1$.

Let $e_j$ denote the length of the jth run, which is defined as the number of times $\delta$ is incremented (in line 13) during the run. Hence, ${\sum }_{j=1}^k{e}_j=n$. Note that $e_1=0$ is possible, but $e_j\ge 1$ for $2\le j\le k$.

Let ${\delta }_j$ be the value of $\delta$ at the end of the jth run. We define ${\delta }_0=-1$. Then, ${\delta }_j\ge 1$ for $1\le j\le k-1$. Note that ${\delta }_k\le 0$ is possible, but this will be irrelevant for the analysis. Also, $e_j={\delta }_j+{\delta }_{j-1}$ for $1\le j\le k$.

We want to show by induction on j that all $v_j$ are bounded.

At the start of the jth run, r is set to $-v_{j-1}$. At the end of each loop iteration, the value of r, which is ensured to be even at that point, is halved. This will limit the growth of $\left|r\right|$. On the other hand, $\left|r\right|$ may grow because of the additions of v and/or a. Since $\delta >0$ precisely during the last ${\delta }_j-1$ iterations of the jth run, however, it follows that g must then be even, and therefore $\left|r\right|$ can only grow because of the addition of a.

To analyze the extreme values for r at the end of each run, we introduce the following three auxiliary functions:

$$\begin{array}{ccc}\hfill \varphi (r,v,N)& =& (r+v(2^N-1))/2^N,\hfill \\ \hfill \psi (r,v,\delta ,{\delta }^{\prime })& =& \varphi (\varphi (r,min(v,0),\delta +1),0,{\delta }^{\prime }-1),\hfill \\ \hfill \Psi (r,v,\delta ,{\delta }^{\prime })& =& \varphi (\varphi (r,max(v,0)+a,\delta +1),a,{\delta }^{\prime }-1).\hfill \end{array}$$

The relevant monotonicity properties of these functions are stated as follows.

Lemma 1.

Functions $\varphi (r,v,N)$, $\psi (r,v,\delta ,{\delta }^{\prime })$, and $\Psi (r,v,\delta ,{\delta }^{\prime })$ are increasing in r and nondecreasing in v.

The next two lemmas establish the basic bounds for $v_j$, which follow almost directly from the way we have defined $\psi$ and $\Psi$.

Lemma 2.

We have $v_0=-1$, $v_1=0$, and for $2\le j\le k$:

$$\psi (-v_{j-2},v_{j-1},{\delta }_{j-1},{\delta }_j)\le v_j\le \Psi (-v_{j-2},v_{j-1},{\delta }_{j-1},{\delta }_j).$$

Lemma 3.

$v_j\le \Psi (-v_{j-2},\Psi (-v_{j-3},v_{j-2},{\delta }_{j-2},{\delta }_{j-1}),{\delta }_{j-1},{\delta }_j)$ for $j\ge 3$.

Proof. 

From Lemma 2, we know that $v_j\le \Psi (-v_{j-2},v_{j-1},{\delta }_{j-1},{\delta }_j)$. Since function $\Psi (r,v,\delta ,{\delta }^{\prime })$ is nondecreasing in v, we obtain the claimed bound for $v_j$ because we also have $v_{j-1}\le \Psi (-v_{j-3},v_{j-2},{\delta }_{j-2},{\delta }_{j-1})$ (using that $j-1\ge 2$).    □

Finally, we prove our main result, establishing a nontrivial bound for the Bézout coefficients $v_j$.

Theorem 1.

$|v_j|\le 3a$ for $0\le j\le k$.

 Proof. 

The proof is by induction on j. Since $v_0=-1$ and $v_1=0$, the bound clearly holds for $j\le 1$ as $a\ge 1$. For $v_2$, we have the following bounds from Lemma 2:

$$\psi (1,0,{\delta }_1,{\delta }_2)\le v_2\le \Psi (1,0,{\delta }_1,{\delta }_2).$$

Since $\psi (1,0,{\delta }_1,{\delta }_2)\ge 0$ and $\Psi (1,0,{\delta }_1,{\delta }_2)\le a$, the bound also holds for $j=2$.

For $j\ge 3$, we first prove the lower bound $v_j\ge -3a$. From Lemma 2, we have

$$v_j\ge \psi (-v_{j-2},v_{j-1},{\delta }_{j-1},{\delta }_j).$$

Since $\psi (r,v,\delta ,{\delta }^{\prime })$ is increasing in r and nondecreasing in v, we then obtain

$$v_j\ge \psi (-3a,-3a,{\delta }_{j-1},{\delta }_j),$$

as $-v_{j-2}\ge -3a$ and $v_{j-1}\ge -3a$ follow from the induction hypothesis.

Hence, the lower bound for $v_j$ holds as

$$\psi (-3a,-3a,{\delta }_{j-1},{\delta }_j)=\varphi (-3a,0,{\delta }_j-1)\ge -3a.$$

Next, we prove the upper bound $v_j\le 3a$. From Lemma 3, we have

$$v_j\le \Psi (-v_{j-2},\Psi (-v_{j-3},v_{j-2},{\delta }_{j-2},{\delta }_{j-1}),{\delta }_{j-1},{\delta }_j).$$

Since $\Psi (r,v,\delta ,{\delta }^{\prime })$ is increasing in r and nondecreasing in v, we obtain

$$v_j\le \Psi (-v_{j-2},\Psi (3a,v_{j-2},{\delta }_{j-2},{\delta }_{j-1}),{\delta }_{j-1},{\delta }_j),$$

as $-v_{j-3}\le 3a$ on account of the induction hypothesis.

To complete the proof, we distinguish the cases $v_{j-2}\le 0$ and $v_{j-2}>0$.

If $v_{j-2}\le 0$, we see that

$$\Psi (\alpha a,v_{j-2},{\delta }_{j-2},{\delta }_{j-1})=\varphi (\varphi (3a,a,{\delta }_{j-2}+1),a,{\delta }_{j-1}-1),$$

which is independent of $v_{j-2}$ and is bounded above by $\varphi (3a,a,2)=3a/2$.

Since $\Psi (r,v,\delta ,{\delta }^{\prime })$ is nondecreasing in v, we therefore have

$$v_j\le \Psi (-v_{j-2},3a/2,{\delta }_{j-1},{\delta }_j).$$

Further, as $\Psi (r,v,\delta ,{\delta }^{\prime })$ is increasing in r, we conclude

$$v_j\le \Psi (3a,3a/2,{\delta }_{j-1},{\delta }_j),$$

as $-v_{j-2}\le 3a$ on account of the induction hypothesis. This leads to

$$v_j\le \varphi (3a,5a/2,2)=(3a+15a/2)/4=21a/8<3a.$$

If $v_{j-2}>0$, we see that

$$\Psi (3a,v_{j-2},{\delta }_{j-2},{\delta }_{j-1})=\varphi (\varphi (3a,v_{j-2}+a,{\delta }_{j-2}+1),a,{\delta }_{j-1}-1)$$

still depends on $v_{j-2}$. To prove the upper bound for $v_j$ in this case, we therefore introduce

$$f(v,\delta ,{\delta }^{\prime },{\delta }^{″})=\Psi (-v,\Psi (3a,v,\delta ,{\delta }^{\prime }),{\delta }^{\prime },{\delta }^{″}),$$

for $0<v\le 3a$, hence $\Psi (r,v,\delta ,{\delta }^{\prime })=\varphi (\varphi (r,v+a,\delta +1),a,{\delta }^{\prime }-1)$.

For the derivative of f with respect to v, we obtain, for $\delta ,{\delta }^{\prime },{\delta }^{″}\ge 1$

$$\frac{\partial f}{\partial v}=\left(3·2^{\delta +{\delta }^{\prime }}-2^{{\delta }^{\prime }+1}-2^{\delta +1}+1\right)2^{-\delta -2{\delta }^{\prime }-{\delta }^{″}}>0,$$

hence, we set $v=3a$ at its maximal value.

Finally, we have that $g(\delta ,{\delta }^{\prime },{\delta }^{″})=f(3a,\delta ,{\delta }^{\prime },{\delta }^{″})$ is increasing in $\delta$ and decreasing both in ${\delta }^{\prime }$ and in ${\delta }^{″}$ for $\delta ,{\delta }^{\prime },{\delta }^{″}\ge 1$:

$$\begin{array}{ccc}\hfill \frac{\partial g}{\partial \delta }& =& a\left(2^{{\delta }^{\prime }+1}-1\right)2^{-\delta -2{\delta }^{\prime }-{\delta }^{″}}log2>0\hfill \\ \hfill \frac{\partial g}{\partial {\delta }^{\prime }}& =& -a\left(7·2^{\delta +{\delta }^{\prime }}-3·2^{\delta +2}-2^{{\delta }^{\prime }+1}+2\right)2^{-\delta -2{\delta }^{\prime }-{\delta }^{″}}log2<0\hfill \\ \hfill \frac{\partial g}{\partial {\delta }^{″}}& =& -a\left(7·2^{\delta +{\delta }^{\prime }}+2^{\delta +2{\delta }^{\prime }+1}-3·2^{\delta +1}-2^{{\delta }^{\prime }+1}+1\right)2^{-\delta -2{\delta }^{\prime }-{\delta }^{″}}log2<0.\hfill \end{array}$$

Therefore, the maximum value of f is

$$\underset{\delta \to \infty }{lim}f(3a,\delta ,1,1)=3a,$$

which is the desired upper bound for $v_j$.    □

4. Secure Groups

Let $(\mathbb{G},\ast )$ denote an arbitrary finite group, written multiplicatively. To define secure group schemes, we use ${\left[\left[a\right]\right]}_{\mathbb{G}}$ to denote a secure representation of a group element $a\in \mathbb{G}$. In general, such a secure representation ${\left[\left[a\right]\right]}_{\mathbb{G}}$ will be constructed from one or more secret-shared finite field elements. Also, we may compose secure representations; e.g., we may put ${\left[\left[a\right]\right]}_{\mathbb{G}}=({\left[\left[a^{\prime }\right]\right]}_{{\mathbb{G}}^{\prime }},{\left[\left[a^{″}\right]\right]}_{{\mathbb{G}}^{″}})$ as secure representation of $a=(a^{\prime },a^{″})\in \mathbb{G}$ for a direct product group $\mathbb{G}={\mathbb{G}}^{\prime }\times {\mathbb{G}}^{″}$.

A secure group scheme should allow us to apply the group operation ∗ to given ${\left[\left[a\right]\right]}_{\mathbb{G}}$ and ${\left[\left[b\right]\right]}_{\mathbb{G}}$, and obtain ${\left[[a\ast b]\right]}_{\mathbb{G}}$ as a result. We will refer to this as a secure application of the group operation, or as a secure group operation, for short. Similarly, a secure group scheme may allow us to perform a secure inversion, which lets us obtain ${\left[\left[a^{-1}\right]\right]}_{\mathbb{G}}$ for a given ${\left[\left[a\right]\right]}_{\mathbb{G}}$. Another common task is to generate a random sample ${\left[\left[a\right]\right]}_{\mathbb{G}}$ with $a{\in }_R\mathbb{G}$ and hence to obtain a secure representation of a group element a drawn from the uniform distribution on $\mathbb{G}$.

To cover a representative set of tasks, we define secure groups as follows.

 Definition 1.

A secure group scheme for $(\mathbb{G},\ast )$ comprises protocols for the following tasks, where $a,b\in \mathbb{G}$.

• Group operation. Given ${\left[\left[a\right]\right]}_{\mathbb{G}}$ and ${\left[\left[b\right]\right]}_{\mathbb{G}}$, compute ${\left[[a\ast b]\right]}_{\mathbb{G}}$.
• Inversion. Given ${\left[\left[a\right]\right]}_{\mathbb{G}}$, compute ${\left[\left[a^{-1}\right]\right]}_{\mathbb{G}}$.
• Equality test. Given ${\left[\left[a\right]\right]}_{\mathbb{G}}$ and ${\left[\left[b\right]\right]}_{\mathbb{G}}$, compute $\left[\right[a=b\left]\right]$.
• Conditional. Given ${\left[\left[a\right]\right]}_{\mathbb{G}},{\left[\left[b\right]\right]}_{\mathbb{G}}$ and $\left[\right[x\left]\right]$ with $x\in \{0,1\}$, compute ${\left[\left[a^x{b}^{1-x}\right]\right]}_{\mathbb{G}}$.
• Exponentiation. Given ${\left[\left[a\right]\right]}_{\mathbb{G}}$ and $\left[\right[x\left]\right]$ with $x\in \mathbb{Z}$, compute ${\left[\left[a^x\right]\right]}_{\mathbb{G}}$.
• Random sampling. Compute ${\left[\left[a\right]\right]}_{\mathbb{G}}$ with $a{\in }_R\mathbb{G}$ (or close to uniform).
• En/decoding. For a set S and an injective map $\sigma :S\to \mathbb{G}$:
  • Encoding.Given $\left[\right[s\left]\right]$, compute ${\left[\left[\sigma \left(s\right)\right]\right]}_{\mathbb{G}}$.
  • Decoding.Given ${\left[\left[a\right]\right]}_{\mathbb{G}}$ with $a\in \sigma \left(S\right)$, compute $\left[\left[{\sigma }^{-1}\left(a\right)\right]\right]$.

By default, all inputs and outputs to these protocols are secret-shared. In addition, the scheme also comprises variants of default protocols where some of the inputs and outputs are public and/or private.

By definition, a secure group scheme thus includes an ordinary group scheme where all protocols operate on public values. Also note that there may be multiple encodings/decodings for a group $\mathbb{G}$, each defined on a specific set S.

To illustrate what we mean by variants of default protocols, consider the following cases for secure exponentiation (which are covered in Section 6.4): (i) given public a and secret $\left[\right[x\left]\right]$, compute secret ${\left[\left[a^x\right]\right]}_{\mathbb{G}}$; (ii) given secret ${\left[\left[a\right]\right]}_{\mathbb{G}}$ and public x, compute secret ${\left[\left[a^x\right]\right]}_{\mathbb{G}}$. Similarly, variants of the trivial secure encoding/decoding protocols with $S=\mathbb{G}$ and $\sigma$ the identity map on $\mathbb{G}$ will allow us to support private input and output of group elements: (i) given private input a, compute secret ${\left[\left[a\right]\right]}_{\mathbb{G}}$, and (ii) given secret ${\left[\left[a\right]\right]}_{\mathbb{G}}$, compute private output a. The private inputs and outputs may even belong to external parties not taking part in the MPC protocol.

We have included a representative range of tasks in our definition of secure groups. Even though some of the tasks are redundant, they are included nevertheless because these tasks cannot necessarily be implemented without loss of efficiency in terms of the other tasks. For instance, secure random sampling can be implemented by letting each party ${\mathcal{P}}_i$ generate a random group element $a_i{\in }_R\mathbb{G}$ as private input, for $i=1,\dots ,t+1$, and then computing the product ${\left[\left[a_1\right]\right]}_{\mathbb{G}}\cdots {\left[\left[a_{t+1}\right]\right]}_{\mathbb{G}}$ securely. Depending on the implementation, however, this may be completed more efficiently for particular groups.

A class of tasks that we have not (yet) incorporated in the definition of secure groups includes higher-order versions of basic tasks. An important example is multi-exponentiation ${\left[\left[{\prod }_i{a}_i^{x_i}\right]\right]}_{\mathbb{G}}$. Similarly, the n-ary group operation ${\left[\left[{\prod }_{i=1}^n{a}_i\right]\right]}_{\mathbb{G}}$ may be included as a basic task, for which there may be more efficient solutions compared to $n-1$ applications of the secure group operation.

5. Generic Constructions of Secure Groups

In this section, we present two generic constructions for secure groups. The first construction relies on secure (oblivious) table lookup and performs best for groups of limited size and without much structure. The second construction relies on linear representations, which may result in compact and efficient implementations for particular groups (like for Rubik’s Cube group of order 43,252,003,274,489,856,000). In Section 7, we will complement these results with specific constructions for number-theoretic groups used in cryptography.

5.1. Secure Groups from Table Lookup

For our first generic construction of secure group schemes for arbitrary groups $\mathbb{G}$, we apply secure table lookup to the multiplication table of $\mathbb{G}$. This construction works best for relatively small groups because the performance is polynomial in $n=\mid \mathbb{G}\mid$.

Let ${\sigma }_0:[0,n)\to \mathbb{G}$ be an arbitrary encoding for $\mathbb{G}$ such that ${\sigma }_0\left(0\right)=1$ is the identity element of $\mathbb{G}$. The multiplication table for $\mathbb{G}$ is then represented by a public matrix $X\in {[0,n)}^{n\times n}$ with $X_{i,j}={\sigma }_0^{-1}({\sigma }_0\left(i\right)\ast {\sigma }_0\left(j\right))$ for all $i,j\in [0,n)$.

For the secure representation of any $a\in \mathbb{G}$, we set ${\left[\left[a\right]\right]}_{\mathbb{G}}={\left[\left[{\sigma }_0^{-1}\left(a\right)\right]\right]}_p$ for a fixed prime $p\ge n$. Thus, each group element is represented by a secret-shared integer in the range $[0,n)$, and, in particular, we have ${\left[\left[1\right]\right]}_{\mathbb{G}}={\left[\left[0\right]\right]}_p$. To implement the group operation securely, we take ${\left[[a\ast b]\right]}_{\mathbb{G}}={\left[\left[u\right]\right]}_p^{T}X{\left[\left[v\right]\right]}_p$, where ${\left[\left[u\right]\right]}_p$ and ${\left[\left[v\right]\right]}_p$ are secret-shared unit vectors of length n corresponding to ${\left[\left[a\right]\right]}_{\mathbb{G}}$ and ${\left[\left[b\right]\right]}_{\mathbb{G}}$, respectively. A unit vector has one entry equal to 1 and all its other entries equal to 0. There are efficient protocols for converting ${\left[\left[i\right]\right]}_p$, $0\le i<n$ to the corresponding unit vector ${\left[\left[e_i\right]\right]}_p$ and back.

The secure equality test between ${\left[\left[a\right]\right]}_{\mathbb{G}}={\left[\left[i\right]\right]}_p$ and ${\left[\left[b\right]\right]}_{\mathbb{G}}={\left[\left[j\right]\right]}_p$ reduces to a secure equality test ${\left[[i=j]\right]}_p$.

The secure conditional can also be implemented efficiently given ${\left[\left[x\right]\right]}_p$ with $x\in \{0,1\}$. Given ${\left[\left[a\right]\right]}_{\mathbb{G}}={\left[\left[i\right]\right]}_p$ and ${\left[\left[b\right]\right]}_{\mathbb{G}}={\left[\left[j\right]\right]}_p$, we have ${\left[\left[a^x{b}^{1-x}\right]\right]}_{\mathbb{G}}={\left[\left[x\right]\right]}_p({\left[\left[i\right]\right]}_p-{\left[\left[j\right]\right]}_p)+{\left[\left[j\right]\right]}_p$; hence, the result is obtained with a single secure multiplication modulo p.

To generate a random group element, we generate a uniform random integer ${\left[\left[r\right]\right]}_p$ with $r{\in }_R[0,n)$. This requires about ${log}_{2}n$ secure random bits (modulo p).

For the remaining tasks, we can use the generic protocols presented later in this paper. If desired, these protocols can also be optimized.

5.2. Secure Groups from Faithful Linear Representations

Our second generic construction of secure group schemes builds on the existence of faithful linear representations for arbitrary groups $\mathbb{G}$. A faithful linear representation of $\mathbb{G}$ is an injective homomorphism $\rho :\mathbb{G}\to {\mathit{GL}}_d\left({\mathbb{F}}_q\right)$ for some finite field ${\mathbb{F}}_q$. The general existence of such linear representations can be inferred from Cayley’s theorem, which states that every group $\mathbb{G}$ is isomorphic to a subgroup of the symmetric group acting on $\mathbb{G}$; clearly, every permutation can be represented by a unique permutation matrix over ${\mathbb{F}}_2$.

The basic idea is to use encoding ${\sigma }_{\rho }\left(A\right)={\rho }^{-1}\left(A\right)$, defined for any $A\in \rho \left(\mathbb{G}\right)\subseteq {\mathit{GL}}_d\left({\mathbb{F}}_q\right)$. Hence, we set ${\left[\left[a\right]\right]}_{\mathbb{G}}={\left[\left[\rho \left(a\right)\right]\right]}_q$ such that group element a is represented by a secret-shared $d\times d$ matrix $A=\rho \left(a\right)$ with entries in ${\mathbb{F}}_q$. The secure group operation for ${\left[\left[a\right]\right]}_{\mathbb{G}}$ and ${\left[\left[b\right]\right]}_{\mathbb{G}}$ is implemented as a secure matrix product ${\left[\left[\rho \left(a\right)\right]\right]}_q{\left[\left[\rho \left(b\right)\right]\right]}_q$, which can be computed efficiently by performing $d^2$ secure dot products in parallel using one round of communication. The secure inverse of ${\left[\left[a\right]\right]}_{\mathbb{G}}$ can be computed efficiently by generating a matrix ${\left[\left[R\right]\right]}_q$ with $R{\in }_R{\mathit{GL}}_d\left({\mathbb{F}}_q\right)$ and opening ${\left[\left[\rho \left(a\right)\right]\right]}_q{\left[\left[R\right]\right]}_q$, inverting this matrix in the clear to obtain $\rho \left(a^{-1}\right)R^{-1}$, and multiplying this with ${\left[\left[R\right]\right]}_q$ to obtain the result. Here, R can be any matrix in ${\mathit{GL}}_d\left({\mathbb{F}}_q\right)$; hence, R does not have to lie in $\rho \left(\mathbb{G}\right)$.

The secure equality test reduces to securely testing if ${\left[[\rho \left(a\right)-\rho \left(b\right)]\right]}_q$ is the all-zero matrix. The secure conditional is implemented efficiently, provided ${\left[\left[x\right]\right]}_q$ with $x\in \{0,1\}$, by setting ${\left[\left[a^x{b}^{1-x}\right]\right]}_{\mathbb{G}}={\left[\left[x\right]\right]}_q({\left[\left[\rho \left(a\right)\right]\right]}_q-{\left[\left[\rho \left(b\right)\right]\right]}_q)+{\left[\left[\rho \left(b\right)\right]\right]}_q$; hence, the result is obtained with a single secure multiplication of a scalar with a matrix over $F_q$.

The representation theory of finite groups [28] helps us to find not just any linear representation but rather (faithful) linear representations $\rho$ of low degree d, preferably over a small finite field ${\mathbb{F}}_q$. As a simple example, we consider the representation of an arbitrary cyclic group of prime order p. These groups are all isomorphic to $({\mathbb{Z}}_p,+)$, the group of integers modulo p with addition. To obtain a linear representation of degree 2 for this group, one takes

$$\rho :{\mathbb{Z}}_p\to {\mathit{GL}}_2\left({\mathbb{F}}_p\right),i\mapsto \left(\begin{array}{cc}1& i\\ 0& 1\end{array}\right).$$

The essential property is that $\rho \left(i\right)\rho \left(j\right)=\rho (i+j)$ for all $i,j\in {\mathbb{Z}}_p$. However, a linear representation of degree 1 is also possible: in fact, for a cyclic group of any order n, $n\ge 1$, let g be an element of order n in ${\mathbb{F}}_q^{*}$ for some prime power q. Then, we simply take $\rho \left(i\right)=g^i$ for $i\in {\mathbb{Z}}_n$.

As a more advanced example, we illustrate the use of a linear representation of minimum degree for the well-known Rubik’s Cube group. The Rubik’s Cube group $\mathbb{G}$ is a subgroup of $S_{48}$ generated by the six permutations corresponding to a clockwise turn of each side (keeping the center pieces at rest). The smallest faithful linear representation of the Rubik’s Cube group turns out to be of degree 20 [29].

Concretely, linear representation $\rho :\mathbb{G}\to {\mathit{GL}}_{20}\left({\mathbb{F}}_7\right)$ can be used, where $\rho \left(a\right)$ for $a\in \mathbb{G}$ corresponds with a generalized permutation matrix that encodes all 20 movable cubies as positions (12 edge and 8 corner cubies). Each position encodes an edge flip or a corner twist as elements in ${\mathbb{F}}_7$ of multiplicative order 2 and 3, respectively. We can define $\rho \left(a\right)$ as a block diagonal matrix over ${\mathbb{F}}_7$ with two blocks: a $12\times 12$ generalized permutation matrix with its nonzero entries in $\{-1,1\}$ and an $8\times 8$ generalized permutation matrix with its nonzero entries in $\{2,4,1\}$. Moreover, the following conditions should be satisfied: for each block, the product of its nonzero entries is equal to 1 (modulo 7), and the permutations corresponding to the two blocks are of equal parity (i.e., both permutations are even, or both are odd). This results in $12!2^{12}8!3^8/2/3/2=2^{10}{3}^{7}8!12!$ possible representations, matching the order of the Rubik’s Cube group. As a “toy example” of an application of secure groups, one can replace the trusted shuffler in a Rubik’s Cube competition by using secure random sampling in the Rubik’s Cube group.

Note that cryptographic applications often require hardness of the discrete logarithm problem for the particular group, making linear representations unsuitable for these applications. However, in non-cryptographic applications of secure groups, linear representations can help the construction of an efficient secure group representation, as illustrated above for the Rubik’s Cube group.

6. Generic Protocols for Secure Groups

In Section 5, we have shown several representations for secure groups and discussed protocols for implementing the tasks listed in Definition 1. In general, the implementation of basic tasks such as the group operation itself and en/decoding strongly depends on the representation of the secure group. For other tasks, however, we may look for generic implementations. This section presents generic protocols for the following four tasks from Definition 1: conditional (if–else), random sampling, inversion, and exponentiation.

6.1. Secure Conditional

It is usually best to implement the secure conditional directly in terms of the underlying representation of a secure group, as we have shown in Section 5.1 and Section 5.2. Alternatively, the secure conditional can be evaluated in terms of secure exponentiation in either of these two generic ways, if applicable: as ${\left[\left[a\right]\right]}_{\mathbb{G}}^{\left[\right[x\left]\right]}\ast {\left[\left[b\right]\right]}_{\mathbb{G}}^{1-\left[\right[x\left]\right]}$, or as ${({\left[\left[a\right]\right]}_{\mathbb{G}}/{\left[\left[b\right]\right]}_{\mathbb{G}})}^{\left[\right[x\left]\right]}\ast {\left[\left[b\right]\right]}_{\mathbb{G}}$, where $x\in \{0,1\}$. This way, it suffices to implement the basic operation ${\left[\left[a\right]\right]}_{\mathbb{G}}^{\left[\right[x\left]\right]}$ with $x\in \{0,1\}$. Moreover, if base a is publicly known, it even suffices to implement $a^{\left[\right[x\left]\right]}$ (with Protocol 7 as a good option to implement this operation).

In pseudocode, the secure conditional will be denoted as $\mathsf{if}-\mathsf{else}(\left[\left[x\right]\right],{\left[\left[a\right]\right]}_{\mathbb{G}},{\left[\left[b\right]\right]}_{\mathbb{G}})$ with the obvious variations if a and/or b are publicly known. The condition $\left[\right[x\left]\right]$ should always be secret.

6.2. Secure Random Sampling

The task of secure random sampling from a group $\mathbb{G}$ corresponds to generating ${\left[\left[a\right]\right]}_{\mathbb{G}}$ with $a{\in }_R\mathbb{G}$ (or close to uniform); see Definition 1. In this section, we present several methods for secure random sampling.

A generic protocol is obtained by letting party ${\mathcal{P}}_i$ generate a random group element $a_i{\in }_R\mathbb{G}$ privately and then using t (threshold) secure group operations to form ${\left[\left[a\right]\right]}_{\mathbb{G}}={\prod }_i{\left[\left[a_i\right]\right]}_{\mathbb{G}}$ for a subset of $t+1$ parties. A potential drawback of this generic method is the cost of t secure group operations, which may be avoided if we use more direct methods, e.g., through efficient encodings for the group or direct use of the underlying representation of the group. For instance, to sample a point $(x,y)$ on an elliptic curve, we may first generate $\left[\right[x\left]\right]$ at random and then solve for $\pm \left[\right[y\left]\right]$, rejecting x if no solutions exist. Another potential drawback is the lack of public verifiability if parties generate random group elements privately. A common way to achieve verifiability is to start from publicly verifiable random bits and use these bits to deterministically generate random samples.

Given the structure of $\mathbb{G}$, we may reduce generating ${\left[\left[a\right]\right]}_{\mathbb{G}}$ with $a{\in }_R\mathbb{G}$ to generating a random $\left[\right[x\left]\right]$ with $x{\in }_R{\mathbb{Z}}_n$ in case $\mathbb{G}=\langle g\rangle$ is a cyclic group of order n, say. This extends to arbitrary abelian groups if we are given a generating set.

When we do not know the structure of the group, we adopt a different approach referred to as sampling in the black box group model. Dixon’s algorithm (Theorem 2 below) is the state of the art for provable complexity bounds, particularly for nonabelian groups.

We apply Theorem 2 in the clear to construct a public array of group elements, referred to as a random cube. The number of group operations to construct such a random element generator is proportional to ${log}^2\mid \mathbb{G}\mid$; see ([30] Remark 2). Then, given $0\le \epsilon <1$, Protocol 2 is then used to securely generate $\epsilon$ uniformly distributed random elements, meaning that each group element has probability $(1\pm \epsilon )/\mid \mathbb{G}\mid$ to appear as output. This technique reduces secure random sampling to secure generation of random bits. If these bits are generated in a publicly verifiable random way, it follows that the entire protocol for random sampling in a group can be made verifiable.

Define probability distribution $\mathit{Cube}(a_1,\dots ,a_j)=\{a_1^{{ϵ}_1}\cdots a_j^{{ϵ}_j}:({ϵ}_1,\dots ,{ϵ}_j){\in }_R{\{0,1\}}^j\}$, referred to as a random cube of length j, for $a_1,\dots ,a_j\in \mathbb{G}$. Given a generating set $\mathcal{G}$ of $\mathbb{G}$, Dixon’s theorem shows how to construct a random cube of length proportional to $log\mid \mathbb{G}\mid$ that is $1/4$-uniform with a given probability.

Theorem 2

([30] Theorem 1). Let $\mathcal{G}=\{g_1,\dots ,g_d\}$ be a generating set of $\mathbb{G}$. Let $W_j=\mathit{Cube}(g_j^{-1},\dots ,g_1^{-1},g_1,\dots ,g_j)$ be a sequence of cubes, where, for $j>d$, $g_j$ is chosen at random from $W_{j-1}$. Then, for each $\delta >0$, there is a constant $K_{\delta }$, independent of d or $\mathbb{G}$, such that, with probability at least $1-\delta$, distribution $W_j$ is $1/4$-uniform when $j\ge d+K_{\delta }log\mid \mathbb{G}\mid$.

Constant $K_{\delta }$ in Theorem 2 may still make the implementation impractical. The following theorem states that we can avoid the constant $K_{\delta }$ and reduce the cube length if we start from a distribution W that is close to the uniform distribution U on $\mathbb{G}$ w.r.t. to the statistical (or variational) distance $\Delta [W;U]=\frac{1}{2}{\sum }_{a\in \mathbb{G}}\left|W\left(a\right)-U\left(a\right)\right|={max}_{A\subset \mathbb{G}}\left|W\left(A\right)-U\left(A\right)\right|$. Ref. [30] (Lemma 13(b), page 11) describes the procedure in detail.

Theorem 3

([30] Theorem 3(c)). Let U be the uniform distribution on $\mathbb{G}$ and suppose W is a distribution with $\Delta [W;U]\le \epsilon <1$. Let $a_0,\dots ,a_{j-1}\in \mathbb{G}$ be chosen independently according to distribution W. If $Z_j=\mathit{Cube}(a_0,\dots ,a_{j-1})$, then, with probability at least $1-2^{-h}$, $Z_j$ is $2^{-k}$-uniform when   

$$j\ge \beta (2{log}_2\mid \mathbb{G}\mid +h+2k),\mathit{where}\beta :={log}_2(2/(1+\epsilon )).$$

(3)

To illustrate this approach, we apply this result to the Rubik’s Cube group $\mathbb{G}$ of order ≈$2^{65}$. Assume that we have generated a $1/4$-uniform random cube W using Theorem 2. In practice, this means that we construct a long random cube W and apply a statistical test to see if W is sufficiently large. Once this pre-processing step is completed, we can apply Theorem 3 with $\epsilon =1/8$, to generate, with probability at least $1-2^{-10}$, a new $2^{-k}$-uniform cube $Z_j$ of length $j\approx 0.83(10+2k+2·65.23)$ group elements. Choosing $k=20$ requires a random cube of length $j=150$ group elements.

Taking advantage of the particular structure of the Rubik’s Cube group as reflected by the linear representation of Section 5.2, a more efficient for uniformly random sampling runs as follows. A random element is constructed by first generating a random permutation of the 12 edge cubies, along with 12 binary edge orientation indicators, with values of +1 or −1 such that the product of all 12 indicators is +1. Similarly, a permutation for the 8 corner cubies is randomly generated, with their orientations selected from 1, 2, 4 modulo 7 subject to the condition that the product of all 8 orientations is 1 modulo 7. Both permutations must also have the same parity.

Given a random cube $Z_j$ of length j that is sufficiently close to uniform random, Protocol 2 is a general protocol for secure random sampling from a group $\mathbb{G}$. The protocol requires j secure random bits and $j-1$ secure group operations. The result is raised to the power x, where $x=1$ is intended as the default case, and this can be extended to several powers.

Protocol 2 $\mathsf{random}(\mathbb{G},x)$              random cube $Z_j\left(\mathbf{g}\right)$ for $\mathbb{G}$

1: $\left[\left[r_0\right]\right],\dots ,\left[\left[r_{j-1}\right]\right]\leftarrow \mathsf{random}-\mathsf{bits}\left(j\right)$ 2: ${\left[\left[g_i^{x{r}_i}\right]\right]}_{\mathbb{G}}\leftarrow \mathsf{if}-\mathsf{else}(\left[\left[r_i\right]\right],g_i^x,1_{\mathbb{G}})$, for $i=0,\dots ,j-1$ 3: ${\left[\left[a^x\right]\right]}_{\mathbb{G}}\leftarrow {\prod }_i{\left[\left[g_i^{x{r}_i}\right]\right]}_{\mathbb{G}}$ 4: return ${\left[\left[a^x\right]\right]}_{\mathbb{G}}$          ▹ random $\mathbb{G}$-element to the power x, $x\in \mathbb{Z}$

To conclude this section, we compare Dixon’s technique with two heuristics used in practice: the product replacement algorithm [31] and Prospector [32]. In the product replacement algorithm, the state is an array a of length n elements that generate the group. The product replacement algorithm repeatedly replaces the ith coefficient $a_i$ by $a_i\ast {a_j}^{\pm 1}$ or ${a_j}^{\pm 1}\ast a_i$ for random $1\le i,j\le n$ and $j\ne i$. After a given number of steps, a random element of a is then returned. Similar to Protocol 2 and given a pre-processed public array a, returning a random coefficient in MPC requires securely sampling a random unit vector of length n, r, and performing ${\prod }_i\mathsf{if}--\mathsf{else}(\left[\left[r_i\right]\right],a_i,1_{\mathbb{G}})$. The required length of a is polynomial in $log\mid \mathbb{G}\mid$ [33], but precise bounds on the length of the array and corresponding probability of uniformly random elements is an open problem.

The Prospector algorithm is an extension of product replacement and produces elements that have a close to uniform distribution when testing for a predetermined property of the group element. Heuristically, Prospector is shown to output public arrays of very short length. Outputs are represented by so-called straight line programs (SLPs), a sequence of elements of $\mathbb{G}$, a, such that, given a generating set $\mathcal{G}$, every new element either belongs to $\mathcal{G}$, which is the inverse of a preceding element, or the product of two preceding elements. The aim is to produce small SLPs (trading off algorithm efficiency).

Prospector tests newly produced elements for randomness. This is completed by producing batches of test data using a map $t:\mathbb{G}\to \mathbb{N}$ and applying the ${\chi }^2$ test. The Prospector paper ([32] Tables 1–6) demonstrates that it can produce SLPs of length $\le 100$ for large groups such as $Sym\left(1000\right)$ and $SL(150,{11}^3)$.

Using Prospector to create SLPs in MPC requires implementing secure protocols for the map t to produce test data. Their efficiency depends on the group property used for the statistical test. We leave the potential of this approach as further research.

6.3. Secure Inversion

The sampling protocols from Section 6.2 allow us to invert secure group elements for groups with known or unknown order. This requires (close to) uniform sampling of random elements in the secure group. Protocol 3 implements this functionality following the classical approach from [2].

Protocol 3 $\mathsf{inversion}\left({\left[\left[a\right]\right]}_{\mathbb{G}}\right)$

1: ${\left[\left[r\right]\right]}_{\mathbb{G}}\leftarrow \mathsf{random}\left(\mathbb{G}\right)$ 2: $a\ast r\leftarrow {\left[\left[a\right]\right]}_{\mathbb{G}}\ast {\left[\left[r\right]\right]}_{\mathbb{G}}$ 3: ${\left[\left[a^{-1}\right]\right]}_{\mathbb{G}}\leftarrow {\left[\left[r\right]\right]}_{\mathbb{G}}\ast {(a\ast r)}^{-1}$ 4: return ${\left[\left[a^{-1}\right]\right]}_{\mathbb{G}}$

6.4. Secure Exponentiation

We start this section with a generally applicable protocol for secure exponentiation ${\left[\left[a^x\right]\right]}_{\mathbb{G}}$ based on the binary representation of $\left[\right[x\left]\right]$; see Protocol 4. The computational complexity is dominated by about $2\mathsf{\ell }$ group operations and ℓ calls to $\mathsf{lsb}$. For the round complexity, we see that the ℓ iterations of the loop are completed sequentially. The protocol can be optimized in many ways. For instance, it is more efficient to compute the bits of $\left[\right[x\left]\right]$ all at once, including the sign bit, using a standard solution.

Protocol 4 $\mathsf{exponentiation}({\left[\left[a\right]\right]}_{\mathbb{G}},\left[\left[x\right]\right])$

1: ${\left[\left[b\right]\right]}_{\mathbb{G}},\left[\left[y\right]\right]\leftarrow \mathsf{if}-\mathsf{else}(\left[[x<0]\right],(\mathsf{inversion}\left({\left[\left[a\right]\right]}_{\mathbb{G}}\right),-\left[\left[x\right]\right]),({\left[\left[a\right]\right]}_{\mathbb{G}},\left[\left[x\right]\right]))$▹ skip if $x\ge 0$ ensured 2: ${\left[\left[c\right]\right]}_{\mathbb{G}}\leftarrow {\left[\left[1\right]\right]}_{\mathbb{G}}$ 3: for $i=0$ to $\mathsf{\ell }-1$do                           ▹$len\left(x\right)\le \mathsf{\ell }$ assumed 4:     $\left[\left[e_i\right]\right]\leftarrow \mathsf{lsb}\left(\left[\left[y\right]\right]\right)$ 5:     ${\left[\left[c\right]\right]}_{\mathbb{G}}\leftarrow \mathsf{if}-\mathsf{else}(\left[\left[e_i\right]\right],{\left[\left[b\right]\right]}_{\mathbb{G}}\ast {\left[\left[c\right]\right]}_{\mathbb{G}},{\left[\left[c\right]\right]}_{\mathbb{G}})$ 6:     $\left[\left[y\right]\right]\leftarrow (\left[\left[y\right]\right]-\left[\left[e_i\right]\right])/2$ 7:     ${\left[\left[b\right]\right]}_{\mathbb{G}}\leftarrow {\left[\left[b\right]\right]}_{\mathbb{G}}^2$ 8: return ${\left[\left[c\right]\right]}_{\mathbb{G}}$

For abelian groups, the linear dependency on ℓ for the round complexity can be removed, as we show in Protocol 5. The improvement is that the ℓ iterations of the loop can now be completed in parallel. Using standard techniques for constant rounds protocols (see, e.g., [2,22]), the overall round complexity can be established independent of ℓ.

Protocol 5 $\mathsf{exponentiation}({\left[\left[a\right]\right]}_{\mathbb{G}},\left[\left[x\right]\right])$                         $\mathbb{G}$ abelian

1: $\left[\left[x_0\right]\right],\dots ,\left[\left[x_{\mathsf{\ell }-1}\right]\right]\leftarrow \mathsf{bits}\left(\left[\left[x\right]\right]\right)$         ▹  $len\left(x\right)+1\le \mathsf{\ell }$ assumed for two’s complement 2: ${\left[\left[r\right]\right]}_{\mathbb{G}},{\left[\left[r^{-1}\right]\right]}_{\mathbb{G}},\dots ,{\left[\left[r^{-2^{\mathsf{\ell }-1}}\right]\right]}_{\mathbb{G}}\leftarrow \mathsf{random}(\mathbb{G},1,-1,\dots ,-2^{\mathsf{\ell }-1})$ 3: $b\leftarrow {\left[\left[a\right]\right]}_{\mathbb{G}}\ast {\left[\left[r\right]\right]}_{\mathbb{G}}$                                ▹   $b=a\ast r$ 4: for $i=0$ to $\mathsf{\ell }-1$do 5:     ${\left[\left[c_i\right]\right]}_{\mathbb{G}}\leftarrow \mathsf{if}-\mathsf{else}(\left[\left[x_i\right]\right],b^{2^i}\ast {\left[\left[r^{-2^i}\right]\right]}_{\mathbb{G}},1_{\mathbb{G}})$                  ▹   in parallel 6: return ${\left[\left[c_0\right]\right]}_{\mathbb{G}}\ast \cdots \ast {\left[\left[c_{\mathsf{\ell }-2}\right]\right]}_{\mathbb{G}}\ast {\left[\left[c_{\mathsf{\ell }-1}\right]\right]}_{\mathbb{G}}^{-1}$

These protocols can be optimized if either a or x is public. For instance, if a is public, the list of powers $a,a^2,a^4,\dots$ can be computed locally, and, if x is public, one can use techniques such as addition chains. We can also obtain more efficient protocols by securely randomizing the other input. Protocol 6 solves the case that x is public, assuming that the group is abelian. The protocol uses secure random sampling from $\mathbb{G}$ to obtain both a random group element and its $(-x)$th power.

Protocol 6 $\mathsf{exponentiation}({\left[\left[a\right]\right]}_{\mathbb{G}},x)$     public exponent x, $\mathbb{G}$ abelian

1: ${\left[\left[r\right]\right]}_{\mathbb{G}},{\left[\left[r^{-x}\right]\right]}_{\mathbb{G}}\leftarrow \mathsf{random}(\mathbb{G},1,-x)$ 2: $a\ast r\leftarrow {\left[\left[a\right]\right]}_{\mathbb{G}}\ast {\left[\left[r\right]\right]}_{\mathbb{G}}$ 3: ${\left[\left[a^x\right]\right]}_{\mathbb{G}}\leftarrow {(a\ast r)}^x\ast {\left[\left[r^{-x}\right]\right]}_{\mathbb{G}}$ 4: return ${\left[\left[a^x\right]\right]}_{\mathbb{G}}$

Protocol 7 solves the case that a is public. The protocol $\mathsf{random}-\mathsf{pair}\left(a\right)$ outputs a random exponent $\left[\right[r\left]\right]$ together with ${\left[\left[a^{-r}\right]\right]}_{\mathbb{G}}$ for public input $a\in \mathbb{G}$. For public output $a^x$, we can also use public $a^{-r}$ in the first step of the protocol. Finally, in the special case that a is an element of large order, parties may directly use their Shamir secret shares and perform Lagrange interpolation in the exponent to raise a to the power $\left[\right[x\left]\right]$.

Protocol 7 $\mathsf{exponentiation}(a,[\left[x\right]\left]\right)$                     public base a

1: $\left[\left[r\right]\right],{\left[\left[a^{-r}\right]\right]}_{\mathbb{G}}\leftarrow \mathsf{random}-\mathsf{pair}\left(a\right)$ 2: $x+r\leftarrow \left[\right[x\left]\right]+\left[\right[r\left]\right]$                ▹ $x+r$ should be sufficiently random 3: ${\left[\left[a^x\right]\right]}_{\mathbb{G}}\leftarrow a^{x+r}{\left[\left[a^{-r}\right]\right]}_{\mathbb{G}}$ 4: return ${\left[\left[a^x\right]\right]}_{\mathbb{G}}$

7. Specific Constructions of Secure Groups

In this section, we present specific constructions for three types of number-theoretic groups commonly used in cryptography. The first type are quadratic residue groups (more generally, Schnorr groups), allowing for a direct secure representation with secret shares in the surrounding finite field. The second type are elliptic curve groups, where we will apply secret-sharing coordinatewise over the curve’s field of definition. The third type are class groups, where we will apply secret-sharing to the components of binary quadratic forms in combination with secure integer arithmetic.

7.1. Secure Quadratic Residue Groups

The first specific type of group that we consider is ${\mathit{QR}}_p={\left({\mathbb{Z}}_p^{*}\right)}^2$, the group of quadratic residues modulo an odd prime p. Quadratic residue groups, and, more generally, subgroups of ${\mathbb{F}}_q^{*}$ (Schnorr groups), are used widely in cryptography, where $n=\mid {\mathit{QR}}_p\mid =(p-1)/2$ is chosen sufficiently large to ensure that the discrete log problem is hard. Often, n is assumed to be prime as well.

Secure group schemes for ${\mathbb{F}}_q^{*}$ and all its subgroups are easily obtained using ${\left[\left[a\right]\right]}_{\mathbb{G}}={\left[\left[a\right]\right]}_q$ as secure representation for $a\in {\mathbb{F}}_q^{*}$. Protocols for all tasks listed in Definition 1 can be obtained with standard techniques, except for the task of secure en/decoding. To enable integer-valued inputs and outputs for applications of secure groups, we often need encoding functions $\sigma :S\to \mathbb{G}$ with $S\subset \mathbb{Z}$. Efficient en/decoding is hard for arbitrary subgroups of ${\mathbb{F}}_q^{*}$, but, for ${\mathit{QR}}_p$, efficient solutions are possible.

Many encodings (or embeddings) for $\mathbb{G}={\mathit{QR}}_p$ have been proposed in the cryptographic literature. For our purposes, we consider the following four encodings for $\mathbb{G}$:

$$\begin{array}{cc}{\sigma }_1:\{1,\dots ,n\}\to \mathbb{G},\hfill & s\mapsto s^{2}modp\hfill \\ {\sigma }_2:\{1,\dots ,n\}\to \mathbb{G},\hfill & s\mapsto \left\{\begin{array}{cc}s,\hfill & \mathrm{if}s\in \mathbb{G}\hfill \\ p-s,\hfill & \mathrm{if}s\notin \mathbb{G}\hfill \end{array}\right.\hfill \\ {\sigma }_3:\{0,\dots ,\lfloor p/k\rfloor -1\}\to \mathbb{G},\hfill & s\mapsto min(\mathbb{G}\cap \{ks+i:0\le i<k\left\}\right)\hfill \\ {\sigma }_4:\{1,\dots ,n\}\to \mathbb{G},\hfill & s\mapsto H(s,arg\underset{i}{min}\{i\ge 1:H(s,i)\in \mathbb{G}\}),\hfill \end{array}$$

where $1<k<p$ and H is a cryptographic hash function with codomain ${\mathbb{Z}}_p^{*}$.

Encoding ${\sigma }_1$ is the natural encoding for $\mathbb{G}$. Since squaring is a 2-to-1 mapping on ${\mathbb{Z}}_p^{*}$ as $s^2={(-s)}^2$, it follows that ${\sigma }_1$ is a bijective encoding on $\{1,\dots ,n\}$. Decoding of $a\in \mathbb{G}$ amounts to taking the unique modular square root of $a\le n$.

For $p\equiv 3(mod4)$, ${\sigma }_2$ is another bijective encoding for $\mathbb{G}$, generalizing the encoding defined for safe primes p in ([34] Section 4.2, Example 2). We see that ${\sigma }_2\left(s\right)=p-s$ for $s\notin \mathbb{G}$ is indeed a quadratic residue modulo p because $p-s\equiv (-1)s(modp)$ is the product of two quadratic nonresidues. Decoding of $a\in \mathbb{G}$ amounts to ${\sigma }_2^{-1}\left(a\right)=a$ if $a<p/2$ and ${\sigma }_2^{-1}\left(a\right)=p-a$ otherwise.

Encoding ${\sigma }_3$ resembles an encoding introduced by Koblitz in the context of elliptic curve cryptosystems ([35] Section 3.2). The value of ${\sigma }_3\left(s\right)$ is well-defined as long as each interval $\{ks+i:0\le i<k\}$ contains a quadratic residue. This can be ensured by picking k sufficiently large as a function of p. The classical result by Burgess [36] implies that $k=\lceil \sqrt{p}\rceil$ ensures successful encoding for sufficiently large p (see also [37]). Under the extended Riemann Hypothesis, Ankeny [38] proved that the least quadratic nonresidue for prime p equals $O\left({log}^{2}p\right)$.

In practice, we may set parameter $k=\lceil {log}_{2}p\rceil$ or a small multiple thereof. Probabilistic heuristics for small primes (<20 bits) suggest that the greatest number of consecutive quadratic nonresidues in the average case is fit by ${log}_2\left(p\right)$. Buell and Hudson [39] computed the lengths of the longest sequences of consecutive residues and nonresidues. By numerical analysis, the authors find that the longest sequence of residues and nonresidues for a given prime p is fitted very closely by ${log}_2\left(p\right)+\delta$ with $\delta$ slightly larger than 1, which suggests a choice of k for an average-case selection of modulus p. A small dataset from [37] using smaller primes (http://www.math.caltech.edu/people/hummel.html, accessed on 20 September 2023) shows sequences of length $<2(log(p)+\delta )$ in the worst case. Heuristics for larger primes (say $\ge 256$-bit) are computationally heavy and beyond the scope of this paper.

In general, encoding ${\sigma }_3$ is not bijective. Decoding of any a in the range of ${\sigma }_3$ is simple as ${\sigma }_3^{-1}\left(a\right)=\lfloor a/k\rfloor$. Note that encoding ${\sigma }_3$ is not constant time and may leak sensitive information in certain applications.

Finally, encoding ${\sigma }_4$ corresponds to a hash function used in certain elliptic curve signature schemes ([40] Section 3.2). Since $Pr[H(s,i)\in \mathbb{G}]=\frac{1}{2}$ in the random oracle model, computing ${\sigma }_4\left(s\right)$ requires two hashes and two Legendre symbols on average. The collision resistance of H implies that the encoding will be “computationally injective” in the sense that it is infeasible to find $s\ne s^{\prime }$ for which ${\sigma }_4\left(s\right)={\sigma }_4\left(s^{\prime }\right)$. Due the one-wayness of H, however, decoding of any a in the range ${\sigma }_4$ amounts to an exhaustive search.

For our purposes, we are interested in secure computation of these encodings and decodings. We briefly compare the performance for the four encodings. A secure encoding $\left[\left[{\sigma }_1\left(s\right)\right]\right]$ amounts to a secure squaring of $\left[\right[s\left]\right]$, which is very efficient. Secure decoding $\left[\left[{\sigma }_1^{-1}\left(a\right)\right]\right]$ requires taking the modular square root of a quadratic residue $\left[\right[a\left]\right]$. This can be completed efficiently by multiplying $\left[\right[a\left]\right]$ with a uniformly random square ${\left[\left[r\right]\right]}^2$, opening the result $a{r}^2$, taking a square root $a^{1/2}r$ (in the clear) and dividing this by $\left[\right[r\left]\right]$. Finally, we need one secure comparison to make sure that the result is in $\{1,\dots ,n\}$.

Similarly, a secure encoding $\left[\left[{\sigma }_2\left(s\right)\right]\right]$ amounts to securely evaluating the Legendre symbol $\left[\right[(s\mid p)\left]\right]$. Since s is known to be nonzero, we simply multiply $\left[\right[s\left]\right]$ with a uniformly random square ${\left[\left[r\right]\right]}^2$ and also with $\left[[1-2b]\right]=\left[\left[{(-1)}^b\right]\right]$ for a uniformly random bit b, opening the result $s{r}^2{(-1)}^b$, for which we compute the Legendre symbol $z=(s{r}^2{(-1)}^b\mid p)$ in the clear. Then, $\left[\left[(s\mid p)\right]\right]=z\left[\left[{(-1)}^b\right]\right]$. Secure decoding boils down to a secure comparison with public $(p-1)/2$, which is quite efficient.

A secure encoding $\left[\left[{\sigma }_3\left(s\right)\right]\right]$ amounts to the secure evaluation of k Legendre symbols $\left[\right[(ks+i\mid p)\left]\right]$ and finding the first $+1$ among these. With k of the order ${log}_{2}p$, this represents a considerable amount of work. However, secure decoding $\left[\left[{\sigma }_3^{-1}\left(a\right)\right]\right]=\left[\left[\lfloor a/k\rfloor \right]\right]$ is much more efficient, especially if k is a power of two.

Finally, ${\sigma }_4$ is not practical to compute obliviously. To obliviously select the smallest i such that $\left[\right[\left(H\right(s,i)\mid p)\left]\right]=+1$ requires computing $\left[\right[H(s,i)\left]\right]$ for $0\le i<\left|\mathbb{G}\right|$, which is not practical. Also, ${\sigma }_4$ does not allow efficient decoding due to the one-wayness of H. However, this encoding is still useful to map private inputs $s\in \{1,\dots ,n\}$ to (unique) secret-shared group elements ${\left[\left[{\sigma }_4\left(s\right)\right]\right]}_{\mathbb{G}}$.

7.2. Secure Elliptic Curve Groups

Let $E\left({\mathbb{F}}_q\right)$ denote the finite group of points on an elliptic curve group E over ${\mathbb{F}}_q$. For cryptographic purposes, we often use a subgroup $\mathbb{G}\subseteq E\left({\mathbb{F}}_q\right)$ of large prime order, such that the discrete log problem and the (decisional) Diffie–Hellman problem are hard in $\mathbb{G}$.

As secure representation of an affine point $P=(x,y)\in \mathbb{G}$, we take ${\left[\left[P\right]\right]}_{\mathbb{G}}=(\left[\left[x\right]\right],\left[\left[y\right]\right])$, where it is left understood that x and y are secret-shared over ${\mathbb{F}}_q$. For efficient implementation of the secure group operation, it is advantageous to use complete formulas, that is, group law formulas without any exceptions. Complete formulas are known for groups of prime-order Weierstrass curves [41] and Edwards curves [3,42].

As an example, the complete formula for the group operation $P_1+P_2$ on a twisted Edwards curve is provided by

$$\left(\frac{x_1{y}_2+y_1{x}_2}{1+d{x}_1{y}_1{x}_2{y}_2},\frac{y_1{y}_2-a{x}_1{x}_2}{1-d{x}_1{y}_1{x}_2{y}_2}\right),$$

where $P_1=(x_1,y_1)$ and $P_2=(x_2,y_2)$ are arbitrary points on the curve. In particular, one can see that $(0,1)$ acts as the identity element. This way, it is straightforward to compute ${\left[[P_1+P_2]\right]}_{\mathbb{G}}$ given ${\left[\left[P_1\right]\right]}_{\mathbb{G}}$ and ${\left[\left[P_2\right]\right]}_{\mathbb{G}}$. The number of secure operations over ${\mathbb{F}}_q$ is low, like at most 7 secure multiplications (and 2 secure inversions). The multiplicative depth is, however, at least 3.

Using twisted Edwards curves with extended coordinates (and $a=-1$), the result from Hisil et al. ([3] Section 4.2) yields a multiplicative depth of 2 for secure curve point addition, performing four multiplications in parallel in each round. Protocol 8 is based on their complete formula. For secure point doubling, this protocol can be optimized, essentially replacing the four multiplications in the first round by four squarings.

Protocol 8 add(${\left[\left[P_1\right]\right]}_{\mathbb{G}},{\left[\left[P_2\right]\right]}_{\mathbb{G}}$)

1: $(\left[\left[x_1\right]\right],\left[\left[y_1\right]\right],\left[\left[t_1\right]\right],\left[\left[z_1\right]\right])\leftarrow {\left[\left[P_1\right]\right]}_{\mathbb{G}}$ 2: $(\left[\left[x_2\right]\right],\left[\left[y_2\right]\right],\left[\left[t_2\right]\right],\left[\left[z_2\right]\right])\leftarrow {\left[\left[P_2\right]\right]}_{\mathbb{G}}$ 3: $\left[\left[r_1\right]\right],\left[\left[r_2\right]\right],\left[\left[r_3\right]\right],\left[\left[r_4\right]\right]\leftarrow \left[\left[y_1\right]\right]-\left[\left[x_1\right]\right],\left[\left[y_2\right]\right]-\left[\left[x_2\right]\right],\left[\left[y_1\right]\right]+\left[\left[x_1\right]\right],\left[\left[y_2\right]\right]+\left[\left[x_2\right]\right]$ 4: $\left[\left[r_1\right]\right],\left[\left[r_2\right]\right],\left[\left[r_3\right]\right],\left[\left[r_4\right]\right]\leftarrow \left[\left[r_1\right]\right]\left[\left[r_2\right]\right],\left[\left[r_3\right]\right]\left[\left[r_4\right]\right],2d\left[\left[t_1\right]\right]\left[\left[t_2\right]\right],2\left[\left[z_1\right]\right]\left[\left[z_2\right]\right]$            ▹ 4M 5: $\left[\left[r_1\right]\right],\left[\left[r_2\right]\right],\left[\left[r_3\right]\right],\left[\left[r_4\right]\right]\leftarrow \left[\left[r_2\right]\right]-\left[\left[r_1\right]\right],\left[\left[r_4\right]\right]-\left[\left[r_3\right]\right],\left[\left[r_4\right]\right]+\left[\left[r_3\right]\right],\left[\left[r_2\right]\right]+\left[\left[r_1\right]\right]$ 6: $\left[\left[x_3\right]\right],\left[\left[y_3\right]\right],\left[\left[t_3\right]\right],\left[\left[z_3\right]\right]\leftarrow \left[\left[r_1\right]\right]\left[\left[r_2\right]\right],\left[\left[r_3\right]\right]\left[\left[r_4\right]\right],\left[\left[r_2\right]\right]\left[\left[r_3\right]\right],\left[\left[r_1\right]\right]\left[\left[r_4\right]\right]$              ▹ 4M 7: ${\left[\left[P_3\right]\right]}_{\mathbb{G}}\leftarrow (\left[\left[x_3\right]\right],\left[\left[y_3\right]\right],\left[\left[t_3\right]\right],\left[\left[z_3\right]\right])$ 8: return ${\left[\left[P_3\right]\right]}_{\mathbb{G}}$

We illustrate en/decoding for secure elliptic curve groups with an example similar to encoding ${\sigma }_3$ of Section 7.1. (The equivalent of ${\sigma }_4$ of Section 7.1 for elliptic curves is often referred to as hash to curve; see the IETF draft for Hashing to Elliptic Curves [43] for detailed specifications.) We conclude this section with an alternative en/decoding based on [44], which mitigates some of the concerns of ${\sigma }_3$ and ${\sigma }_4$ for elliptic curves at the cost of performance loss in MPC.

Consider a twisted Edwards curve $E\left({\mathbb{F}}_p\right)$ with curve equation $E:a{x}^2+y^2=1+d{x}^2{y}^2$ for given $a,d\in {\mathbb{F}}_p$. For encoding input s given parameter k, we repeatedly set $x=sk+i$ for varying i and test if x corresponds to a valid point $(x,y)\in E\left({\mathbb{F}}_p\right)$, which amounts to testing if $u=(1-a{x}^2)/(1-d{x}^2)$ is a quadratic residue modulo p. Then, we define $\sigma \left(s\right)=(x,y)$, where y is a square root of u modulo p.

Secure decoding amounts to recovering $s=\lfloor x/k\rfloor$. In general, secure decoding can be optimized if k is a power of 2. Moreover, if increment i is also available as an auxiliary secret-shared input $\left[\right[i\left]\right]$, secure decoding may be implemented basically for free as $\left[\right[s\left]\right]=\left(\right[\left[x\right]]-[\left[i\right]\left]\right)/k$.

Testing $O\left(k\right)$ times for quadratic residuosity may become a bottleneck. Note that, if the application requires constant-time encoding, one should test the full range of size k. Also note that many modern elliptic curve implementations with simple formulas do not provide a prime-order group but a group with a small cofactor h, usually $h=4$ or 8. This introduces the risk that this encoding leaks information, e.g., when an attacker creates a point whose order divides h. A defense is to multiply points by h and abort the protocol if the result is the identity.

For odd-characteristic elliptic curves with a point of order 2, Elligator [44] presents a bijective map that is constant-time and avoids $O\left(k\right)$ quadratic residuosity tests. The cost in MPC of the forward map $\sigma :{\mathbb{F}}_p\to E\left({\mathbb{F}}_p\right)$ is dominated by the Legendre symbol and the modular square root. The reverse map requires a comparison and two modular square roots. Choosing between naive hash to curve or Elligator is a security and efficiency trade-off that depends on the application.

7.3. Secure Class Groups

We now focus on ideal class groups of imaginary quadratic fields, using $\mathrm{Cl}(\Delta )$ to denote the class group with discriminant $\Delta <0$. We also use $\mathrm{Cl}(\Delta )$ to denote the isomorphic form class group of integral binary quadratic forms $f(x,y)=a{x}^2+bxy+c{y}^2$ with discriminant $\Delta =b^2-4ac<0$. These forms are written as $f=(a,b,c)$ with $a,b,c\in \mathbb{Z}$, where it is implied that f is primitive, that is, $gcd(a,b,c)=1$, and f is positive definite, that is, $a>0$.

For the composition of two forms $f_1,f_2\in \mathrm{Cl}(\Delta )$, we will use the algorithm due to Shanks [45], as presented by Cohen ([46] Algorithm 5.4.7). We slightly adapt the algorithm, skipping some case distinctions that were introduced for efficiency; see Algorithm 2. Apart from the computationally nontrivial reduction performed in the final step of the algorithm, the resulting algorithm only requires two xgcds and one integer division. This compares favorably with alternatives such as the classical composition algorithm by Dirichlet [47] (see also ([48] Lemma 3.2) and ([49] Algorithm 6.1.1)).

Algorithm 2 compose($f_1,f_2$)               $f_1,f_2$ primitive, positive definite, reduced

Input: $f_1=(a_1,b_1,c_1)$ and $f_2=(a_2,b_2,c_2)$  1: $s\leftarrow (b_1+b_2)/2$  2: $d^{\prime },x_1,y_1\leftarrow \mathsf{xgcd}(a_1,a_2)$                  ▹ $x_1{a}_1+y_1{a}_2=d^{\prime }=\mathsf{gcd}(a_1,a_2)$  3: $d,x_2,y_2\leftarrow \mathsf{xgcd}(s,d^{\prime })$                      ▹ $x_{2}s+y_2{d}^{\prime }=\mathsf{gcd}(s,d^{\prime })$  4: $v_1,v_2\leftarrow a_1/d,a_2/d$  5: $r\leftarrow (y_1{y}_2(s-b_2)-x_2{c}_2)mod{v}_1$                   ▹ integer division  6: $a_3\leftarrow v_1{v}_2$  7: $b_3\leftarrow b_2+2v_{2}r$  8: $c_3\leftarrow (b_3^2-\Delta )/\left(4a_3\right)$  9: $f_3=(a_3,b_3,c_3)$ 10: return $\mathsf{reduce}\left(f_3\right)$

As secure representation of a form $f=(a,b,c)\in \mathbb{G}$, we define ${\left[\left[f\right]\right]}_{\mathbb{G}}=({\left[\left[a\right]\right]}_p,{\left[\left[b\right]\right]}_p,{\left[\left[c\right]\right]}_p)$ for a sufficiently large prime p. The prime p should be sufficiently large such that the intermediate forms computed by Algorithm 2 do not cause any overflow modulo p (also accounting for the “headroom” needed for secure comparison and secure integer division). Using Protocol 1 for secure xgcd and a protocol for secure integer division, Algorithm 2 is then easily transformed into a protocol for the secure composition of forms.

To reduce a form $f=(a,b,c)$, the classical reduction algorithm by Lagrange (see ([4] Algorithm 5.3)) runs in at most $2+\lceil {log}_2(a/\sqrt{\Delta })\rceil$ steps ([4] Theorem 5.5.4), each step requiring an integer division. Our goal is to avoid the expensive (secure) integer divisions where possible.

To this end, we take the binary reduction algorithm by ([12] Algorithm 3) as our starting point. (Recently, Ref. [50] arrived at an equivalent algorithm to design a quantum circuit to reduce binary quadratic forms.) We minimize the number of comparisons by exploiting the invariant $a>0$ and $c>0$. The algorithm reduces forms by the following transformations in ${\mathit{SL}}_2\left(\mathbb{Z}\right)$:

$$S=\left(\begin{array}{cc}0& -1\\ 1& 0\end{array}\right)T_m=\left(\begin{array}{cc}1& m\\ 0& 1\end{array}\right).$$

The total number of iterations of the main loop required to achieve $\left|b\right|\le 2a$ is at most $len\left(b\right)$ if $f=(a,b,c)$ is the given form. This follows from the fact that, if $\left|b\right|\le 2a$ does not hold yet, an iteration of the main loop will reduce $len\left(b\right)$ by at least 1. We will ensure that $len\left(b\right)\le len(\Delta )$, such that it suffices to run the main loop for $len(\Delta )$ iterations, independent of the input. Note that we need to test $a>c$ in each iteration as well.

As an important optimization, we limit the number of iterations to $len(\Delta )/2$ by noting that it suffices to reduce b until $len\left(b\right)<len(\Delta )/2$. This ensures that $\left|b\right|\le \sqrt{|\Delta |}$ after the main loop. If $\left|b\right|\le 2a$ does not hold yet, then it follows that $a<\left|b\right|/2\le \sqrt{|\Delta |/4}$, and we only need one “normalization” step to ensure $\left|b\right|\le a$.

The result is presented as Algorithm 3. This algorithm avoids the integer division and multiple comparisons in the main loop of Lagrange’s reduction algorithm, at the cost of three secure comparisons and two secure bit length computations in the main loop. To compute the bit length securely we use a novel protocol avoiding the use of a full bit decomposition.

Algorithm 3 reduce(f)                      $f\in \mathrm{Cl}(\Delta )$ primitive, positive definite

Input: $f=(a,b,c)$  1: for $i=1$ to $\lceil len(\Delta )/2\rceil$ do                      ▹ invariant $a>0$ and $c>0$  2:     if $b>0$ then $s_b\leftarrow 1$ else $s_b\leftarrow 1$                  ▹ using $len\left(b\right)<len(\Delta )-i$  3:     $j\leftarrow len\left(b\right)-len\left(a\right)-1$  4:     $m\leftarrow -s_b{2}^j$           ▹ compute $2^j$ together with $len\left(a\right)$ and $len\left(b\right)$ at no extra cost  5:     if $s_{b}b>2a$ then                                   ▹$\left|b\right|>2a$  6:         $f\leftarrow f{T}_m$                        ▹ $f{T}_m=(a,b+2ma,m^{2}a+mb+c)$  7:     if $a>c$ then  8:         $f\leftarrow fS$                                  ▹$fS=(c,-b,a)$  9: $m\leftarrow \lfloor \frac{a-b}{2a}\rfloor$                                  ▹ integer division 10: $f\leftarrow f{T}_m$ 11:  if $a>c$ then 12:     $f\leftarrow fS$ 13: if $(a+b)(a-c)=0\mathrm{and}b<0$ then              ▹ ensure $b\ge 0$ if $a=-b$ or $a=c$ 14:     $b\leftarrow -b$                                   ▹$f\leftarrow fS=f{T}_1$ 15: return f

For secure encoding to class groups, a given integer s will be mapped to a form $(a,b,c)$ by computing a as a simple function of s and setting b as the square root of $\Delta$ modulo $4a$; see Algorithm 4. We note that this encoding improves upon the encoding proposed by [51] (compare to [52] as well), which relies on using prime numbers for a. Our algorithm avoids the need for primality tests, which are dominating the computational cost for the encoding algorithm.

Let k be our parameter as above. Given a worst-case prime gap for an ℓ-bit discriminant, ${\mathit{gap}}_{\mathsf{\ell }}$, we avoid the need to return the distance by setting parameter $k={\mathit{gap}}_{\mathsf{\ell }}$ and mapping input a to a prime $a^{\prime }=a·k+i$ for some $0\le i<k$. Algorithm 4 is similar to searching for candidates by incrementing i in encoding ${\sigma }_3$ of Section 7.1. After a successful encoding of $a^{\prime }$ per Algorithm 12 to a so-called prime form $f_{a^{\prime }}=(a^{\prime },b,c)$, we can discard the distance knowing that $a=⌊a^{\prime }/{\mathit{gap}}_{\mathsf{\ell }}⌋$.

Algorithm 4 encode($s,\mathrm{Cl}(\Delta )$)                s sufficiently small w.r.t. $|\Delta |$

1: $n=s·{\mathit{gap}}_{\mathsf{\ell }}$  2: $a\leftarrow n-1-(nmod4)$  3: repeat  4:     $a\leftarrow a+4$                          ▹$a\equiv 3(mod4)$  5:     $b\leftarrow {\Delta }^{\frac{a+1}{4}}moda$  6: until $b^2\equiv \Delta (moda)$ and $gcd(a,b)=1$  7: if $\Delta \neg \equiv b(mod2)$ then  8:     $b\leftarrow a-b$  9: $f\leftarrow (a,b,\frac{b^2-\Delta }{4a})$                       ▹$\Delta \equiv b^2(mod4)$ 10: $d\leftarrow n-a$ 11: return f, d

We improve upon the encoding suggested by [51]. We do not search for a prime a, which requires a costly primality test. Instead, we take $a\equiv 3(mod4)$ and simply test whether $b^2\equiv \Delta (moda)$ for $b={\Delta }^{\frac{a+1}{4}}moda$. This condition will certainly hold if a is prime and $\Delta$ is a quadratic residue modulo a because then we have $b^2\equiv {\Delta }^{(a+1)/2}\equiv {\Delta }^{(a-1)/2}\Delta \equiv \Delta (moda)$. Hence, the success rate will be no worse than for [51].

For $|\Delta |$, an odd prime, the frequency of prime forms $(a^{\prime },b,c)$ approximately corresponds to the quadratic residuosity of $a^{\prime }$ modulo $|\Delta |$. We refer to ([4] Proposition 3.4.5) for the exact frequency of prime forms.

Finally, we briefly discuss random sampling. Even though class groups are abelian, random sampling using a generating set is inefficient due to the complexity of computing the generating set for $Cl(\Delta )$. Given a (sufficiently complete) generating set $\mathcal{G}$ of the relevant (sub)group $\mathbb{G}$, without knowledge of the order $Cl(\Delta )$, the general idea is for $g_i\in \mathcal{G}$ and random $e_i\in \{1,\dots ,|\Delta \left|\right\}$, for $i\in \{0,\dots ,d-1\}$, to compute a random element ${\prod }_{i=0}^{d-1}{g}_i^{e_i}$, e.g., using techniques from Lenstra and Pomerance [53].

8. MPC-Based Threshold Cryptosystems

As a concrete example of MPC-based threshold cryptography, we consider the well-known threshold ElGamal cryptosystem [54]. Given a secure group for an MPC setting with m parties and a corruption threshold of t, $0\le t<m/2$ (cf. Section 2), we obtain the following scheme for the semi-honest case.

 Example 1. 

A $(t,m)$-threshold ElGamal cryptosystem is constructed as follows, given a secure group scheme for a cyclic group $\mathbb{G}=\langle g\rangle$ of large prime order p.

• Distributed key generation. The parties generate $\left[\right[x\left]\right]$ with $x{\in }_R{\mathbb{Z}}_p$ and use secure exponentiation to compute $h=g^x$. The parties keep private key $\left[\right[x\left]\right]$ in shares and output public key h.
• Encryption. Given message $M\in \mathbb{G}$, pick $u{\in }_R{\mathbb{Z}}_p$. The ciphertext for public key h is the pair $(g^u,h^{u}M)$.
• Threshold decryption. Given ciphertext $(A,B)$, the parties use $\left[\right[x\left]\right]$ to compute $A^x$ by secure exponentiation. The parties output message $M=B/A^x$.

The complexity of the protocols for distributed key generation and threshold decryption is entirely hidden in the underlying MPC framework supporting secure groups.

We may extend this basic threshold ElGamal cryptosystem as follows, noting that, instead of using message $M\in \mathbb{G}$ in the clear, we can also use ${\left[\left[M\right]\right]}_{\mathbb{G}}$ in shares, just as we keep the private key $\left[\right[x\left]\right]$ in shares.

 Example 2. 

The threshold ElGamal cryptosytem of Example 1 is extended as follows to handle secret-shared messages ${\left[\left[M\right]\right]}_{\mathbb{G}}$.

• Encryption of a shared message. Given message ${\left[\left[M\right]\right]}_{\mathbb{G}}$, the parties generate $\left[\right[u\left]\right]$ with $u{\in }_R{\mathbb{Z}}_p$ and output the pair $(g^{\left[\right[u\left]\right]},h^{\left[\right[u\left]\right]}{\left[\left[M\right]\right]}_{\mathbb{G}})$ as ciphertext for public key h. Here, secure exponentiation is used twice, either with public output $(A,B)$ or with secret-shared output $({\left[\left[A\right]\right]}_{\mathbb{G}},{\left[\left[B\right]\right]}_{\mathbb{G}})$.
• Threshold decryption to a shared message. Given ciphertext $(A,B)$, the parties compute ${\left[\left[A^x\right]\right]}_{\mathbb{G}}=A^{\left[\right[x\left]\right]}$ using secure exponentiation. The parties compute and keep message ${\left[\left[M\right]\right]}_{\mathbb{G}}=B/{\left[\left[A^x\right]\right]}_{\mathbb{G}}$ in shares. Similarly, the parties may decrypt a ciphertext $({\left[\left[A\right]\right]}_{\mathbb{G}},{\left[\left[B\right]\right]}_{\mathbb{G}})$.

Combining these two protocols, we can conduct things like reencryption of a given ciphertext for another public key: use a threshold decryption to a shared message followed by an encryption of the shared message under the other public key. As a final example, we show a direct way to perform reencryption.

 Example 3. 

The threshold ElGamal cryptosytem of Example 1 is extended as follows to support efficient reencryption.

• Reencryption. Assume the parties hold shares for private keys $\left[\left[x_1\right]\right]$ and $\left[\left[x_2\right]\right]$, and then they may compute $\left[[x_1/x_2]\right]$ and use this with secure exponentiation to convert ciphertext $(A,B)$ for public key $h_1=g^{x_1}$ into ciphertext $(A^{\left[[x_1/x_2]\right]},B)$ for public key $h_2=g^{x_2}$.
• Reencryption key. Assume the parties hold shares for private keys $\left[\left[x_1\right]\right]$ and $\left[\left[x_2\right]\right]$, and then they may compute and open $\left[[x_1/x_2]\right]$ as a reencryption key.

9. Conclusions

We have integrated secure groups as defined in this paper in the Python package MPyC [55], including support for symmetric groups, quadratic residues, Schnorr groups, various elliptic curve groups (Weierstrass, Edwards), and class groups. The secure groups implementation builds on the secure integer arithmetic provided by MPyC, which covers basic operations like $+,\ast ,<$ as well as more advanced operations such as secure integer division with remainder and secure computation of the bit length. In particular, the implementation includes our protocol for the extended gcd, which is of independent interest, and many of the specific protocols of Section 7. To demonstrate applications of secure groups in threshold cryptography, a demo for threshold ElGamal (cf. Examples 1 and 2) is provided ([55] elgamal.py). Also, a demo for threshold DSA (Digital Signature Algorithm) is provided ([55] dsa.py).

In a separate repository [56], we provide implementations of verifiable MPC built using secure groups. In verifiable MPC, the parties generate publicly verifiable proofs of correctness for the results of a multiparty computations. Even in the extreme case when all parties are corrupt, these proofs remain unforgeable. Technically, we extend a multiparty computation with the generation of these noninteractive proofs in terms of secure groups, covering, e.g., compressed $\mathsf{\Sigma }$-protocols [57]. We also cover succinct noninteractive arguments of knowledge (SNARKs) as used in Trinocchio [58].