Secure multi-party computation (MPC) allows parties to jointly compute on private data without revealing their inputs. While MPC handles basic numeric operations efficiently, the use of algorithms from abstract algebra and number theory in an MPC context has not been studied much.

Abstract algebra and number theory are sub-fields of mathematics that provide many of the building blocks of cryptography. The extended greatest common divisor, for example, can be used for modular inversion, an important step in RSA key generation. Our interest is in zero-knowledge proofs that allow an outsider to an MPC computation to verify that this computation was not tampered with.

In our recent paper, “Efficient Extended GCD and Class Groups from Secure Integer Arithmetic”, my PhD supervisor Berry Schoenmakers and I present a technique to implement certain number-theoretic operations within MPC. With this paper we extend the toolbox for MPC and enable cryptographic operations such as zero-knowledge proofs (ZKPs) in the MPC setting.

Zero-knowledge proofs and the role of class groups

Zero-knowledge proofs allow one party (the prover) to convince another (the verifier) that a statement is true, without revealing any information beyond the validity of the statement. Many ZKP systems rely on finite groups with specific properties, often elliptic curves or modular arithmetic groups.

One reason for finite groups being ubiquitous in cryptography is because of the discrete logarithm problem; for certain groups, this problem is believed to be hard, yielding a candidate one-way function.

Recall that the number of elements in a group is called the group order. Now, so-called class groups have a special property that sets them apart: their group order is unknown. If the size is chosen sufficiently large, no one can determine the exact order of the group, not even someone who creates an instance of this group.

This “unknown order” feature is extremely valuable because it allows building zero-knowledge proof systems that do not require a trusted setup, i.e., a system that requires its setup to be performed by an honest party. The unknown-order feature can also speed up zero-knowledge proof systems.

Being able to construct a zero-knowledge proof in MPC enables public verifiability of an MPC computation — letting an outsider to the computation verify the correctness of the computation. In other words, protection against tampering with the computation, even if all compute parties are corrupted. Additionally, bringing class groups into the MPC world means we can now construct ZKPs with the advantages of unknown-order groups we mentioned above.

The core challenge: secure arithmetic for XGCD and group operations

One of the foundations of our work is the extended greatest common divisor (xgcd) algorithm. The integer gcd algorithm computes, not surprisingly, the greatest common divisor of two integers. For example gcd(22, 33) = 11.

The xgcd computes two additional factors, namely u and v such that ua + vb = g = gcd(a, b). These additional factors are called the Bézout coefficients.

In a normal setting, the xgcd algorithm involves branching decisions based on comparisons. However branching on secret data is insecure, as it could leak information about the inputs via various side-channels. One of the core challenges of building an MPC-version is to redesign the xgcd algorithm so that all branching becomes secret independent, aka constant time.

A constant-time, integer-based XGCD

In our result, we adapt the Bernstein–Yang “divsteps” algorithm, which already runs in constant time, and rework it to operate purely on integers (instead of 2-adic representations). This is more suitable for our MPC setting. The protocol runs a fixed number of iterations, each performing only arithmetic and bitwise operations that can be done securely in MPC. The overall cost is O(N log N) secure multiplications, which is significantly more efficient than using traditional binary GCD methods (whose asymptotic complexity is O(N²)).

For the mathematicians, we also prove tight bounds on the size of the intermediate results (the Bézout coefficients):

|u|, |v| ≤ 3 max(a, b)

Explicit bounds on these intermediate results are essential to control the numeric range of secret shares and avoid overflows.

Secure groups in MPC

To go beyond integers, we implement the concept of a secure group. This describes how to represent and manipulate elements of a finite group under MPC.

A secure group implementation must support:

  • Group operations (multiplication, inversion)
  • Equality tests and conditional branching
  • Exponentiation
  • Random sampling
  • Encoding and decoding between representations

By defining these primitives generically, any group, for example based on elliptic curves, class groups, or others, can be instantiated as a “secure group” on top of your favorite MPC framework’s arithmetic layer. In our research setting, we used MPyC. This open-source MPC framework by Berry Schoenmakers is very convenient to use, performant and easy to extend.

Class groups via binary quadratic forms

We now dive a bit deeper into our MPC implementation of class groups.

Class groups of imaginary quadratic fields can be represented using binary quadratic forms:

f(x, y) = ax² + bxy + cy²

with discriminant Δ = b² - 4ac < 0.

The group operation (composition) and reduction can be expressed using integer arithmetic. We adapt these classical algorithms to the MPC setting:

  • Composition combines two forms using secure xgcd and modular arithmetic.
  • Reduction uses a binary algorithm that avoids explicit divisions, making it MPC-friendly.
  • Encoding maps integers to valid class group elements without expensive primality tests.

The composition operation required a performant extended gcd, which we touched upon above. For the reduction operation we optimized a result by Agarwal and Frandsen to the MPC setting. The result is a secure implementation of class group arithmetic inside MPC.

Applications: zero-knowledge proofs in MPC

With class groups implemented as secure groups, MPC can now support zero-knowledge proofs over secret-shared data. This opens several powerful applications:

  • Threshold ZKPs: multiple parties jointly prove knowledge of a secret without revealing it.
  • Threshold cryptography: secure group operations for distributed signatures and commitments.

Our work helps to bridge the worlds of MPC and ZKP: MPC handles private computation, while class groups provide the algebraic structure needed for trustless and verifiable computation.

Implementation and outlook

All protocols have been implemented in MPyC, a Python-based MPC framework. Developers can now perform:

  • Secure integer xgcd’s
  • Secure group operations
  • Class group arithmetic with unknown-order properties

The MPyC repo also includes demonstrations of a threshold signature scheme and a threshold zero-knowledge proof based on this work.

By bridging secure computation, abstract algebra and cryptography, we hope to show that, with the right abstractions, we can create new practical tools for privacy-preserving computation, like publicly verifiable MPC without trusted setups.