paillier_mta

Paillier-based Multiplicative-to-Additive (MtA) Share Conversion for GG18/CGGMP21

From: “Fast Multiparty Threshold ECDSA with Fast Trustless Setup” (GG18)

By: Rosario Gennaro, Steven Goldfeder

Published: CCS 2018 / ePrint 2019/114

URL: https://eprint.iacr.org/2019/114.pdf

• type: share conversion

• setting: Composite modulus (Paillier) + Elliptic Curve

• assumption: DCR (Decisional Composite Residuosity)

MtA converts multiplicative shares (a, b) where two parties hold a and b to additive shares (alpha, beta) such that a*b = alpha + beta (mod q). Unlike OT-based MtA, this uses Paillier’s homomorphic properties.

Authors:

Charm Developers

Date:

02/2026

class paillier_mta.PaillierKeyPair(pk: Dict, sk: Dict)

Bases: object

Container for Paillier key pair with additional precomputed values.

Attributes:

pk: Public key dict with ‘n’, ‘g’, ‘n2’ sk: Secret key dict with ‘lamda’, ‘u’ n: RSA modulus N = p*q n2: N squared n_bits: Bit length of N

class paillier_mta.PaillierMtA(rsa_group: RSAGroup, ec_order: int, paillier_bits: int = 2048)

Bases: object

Multiplicative-to-Additive share conversion using Paillier encryption.

This implements the MtA protocol from GG18/CGGMP21 using Paillier’s additive homomorphic properties: - Enc(a) * Enc(b) = Enc(a + b) - Enc(a)^k = Enc(a * k)

Protocol: 1. Alice (sender) has secret ‘a’ and Paillier keypair 2. Bob (receiver) has secret ‘b’ 3. Alice sends c_A = Enc(a) to Bob 4. Bob computes c_B = c_A^b * Enc(-beta) = Enc(a*b - beta) for random beta 5. Alice decrypts c_B to get alpha = a*b - beta 6. Result: alpha + beta = a*b

>>> from charm.toolbox.integergroup import RSAGroup
>>> group = RSAGroup()
>>> ec_order = 2**256 - 2**32 - 977  # secp256k1 order (approx)
>>> mta = PaillierMtA(group, ec_order, paillier_bits=512)  # Small for testing
>>> keypair = mta.generate_keypair()
>>> # Alice has a, Bob has b
>>> a = 12345
>>> b = 67890
>>> # Alice sends encrypted a
>>> sender_msg = mta.sender_round1(a, keypair)
>>> # Bob computes response
>>> receiver_msg, beta = mta.receiver_round1(b, sender_msg, keypair.pk)
>>> # Alice decrypts to get alpha
>>> alpha = mta.sender_round2(receiver_msg, keypair)
>>> # Verify: alpha + beta = a*b mod ec_order
>>> (alpha + beta) % ec_order == (a * b) % ec_order
True

generate_keypair() → PaillierKeyPair

Generate a new Paillier keypair.

Returns:

PaillierKeyPair with public and secret keys

receiver_round1(b: int, sender_msg: Dict[str, Any], sender_pk: Dict) → Tuple[Dict[str, Any], int]

Receiver (Bob) computes response using homomorphic properties.

Computes c_B = c_A^b * Enc(-beta) = Enc(a*b - beta) for random beta.

Args:

b: Receiver’s multiplicative share (integer) sender_msg: Message from sender_round1 sender_pk: Sender’s Paillier public key

Returns:

Tuple of (message for sender, beta)

sender_round1(a: int, keypair: PaillierKeyPair) → Dict[str, Any]

Sender (Alice) generates first message: encrypted share.

Args:

a: Sender’s multiplicative share (integer) keypair: Sender’s Paillier keypair

Returns:

Dict with encrypted share to send to receiver

sender_round2(receiver_msg: Dict[str, Any], keypair: PaillierKeyPair) → int

Sender decrypts response to get their additive share alpha.

Args:

receiver_msg: Message from receiver_round1 keypair: Sender’s Paillier keypair

Returns:

alpha: Sender’s additive share such that alpha + beta = a*b

class paillier_mta.PaillierMtAwc(rsa_group: RSAGroup, ec_order: int, paillier_bits: int = 2048)

Bases: PaillierMtA

Paillier MtA with correctness check (MtAwc).

Extends PaillierMtA with ZK proofs for malicious security. Used in GG18 and CGGMP21 for secure MtA with verification.

The protocol adds range proofs to ensure: 1. The encrypted value is in a valid range 2. The computation was performed correctly

receiver_round1_with_proof(b: int, sender_msg: Dict[str, Any], sender_pk: Dict) → Tuple[Dict[str, Any], int]

Receiver computes response with affine proof.

Args:

b: Receiver’s multiplicative share sender_msg: Message from sender with proof sender_pk: Sender’s Paillier public key

Returns:

Tuple of (message with proof, beta)

sender_round1_with_proof(a: int, keypair: PaillierKeyPair, range_bound: int | None = None) → Dict[str, Any]

Sender generates first message with range proof.

Args:

a: Sender’s multiplicative share keypair: Sender’s Paillier keypair range_bound: Upper bound for range proof (default: ec_order)

Returns:

Dict with encrypted share and range proof

sender_round2_with_verify(receiver_msg: Dict[str, Any], keypair: PaillierKeyPair) → Tuple[int, bool]

Sender decrypts and verifies receiver’s proof.

Args:

receiver_msg: Message from receiver with proof keypair: Sender’s Paillier keypair

Returns:

Tuple of (alpha, verification_result)