'''
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
'''
from typing import Dict, Tuple, Optional, Any
from charm.toolbox.integergroup import RSAGroup, integer, toInt, lcm
from charm.schemes.pkenc.pkenc_paillier99 import Pai99
from charm.toolbox.securerandom import SecureRandomFactory
import hashlib
# Type aliases
ZRElement = Any
GElement = Any
ECGroupType = Any
[docs]
class PaillierKeyPair:
"""
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
"""
def __init__(self, pk: Dict, sk: Dict):
self.pk = pk
self.sk = sk
self.n = pk['n']
self.n2 = pk['n2']
self.n_bits = int(self.n).bit_length()
def __repr__(self) -> str:
return f"PaillierKeyPair(n_bits={self.n_bits})"
[docs]
class PaillierMtA:
"""
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
"""
def __init__(self, rsa_group: RSAGroup, ec_order: int, paillier_bits: int = 2048):
"""
Initialize PaillierMtA.
Args:
rsa_group: RSA group for Paillier operations
ec_order: Order of the elliptic curve group (for modular reduction)
paillier_bits: Bit length for Paillier modulus (default 2048)
"""
self.rsa_group = rsa_group
self.ec_order = ec_order
self.paillier_bits = paillier_bits
self.paillier = Pai99(rsa_group)
self.rand = SecureRandomFactory.getInstance()
[docs]
def generate_keypair(self) -> PaillierKeyPair:
"""
Generate a new Paillier keypair.
Returns:
PaillierKeyPair with public and secret keys
"""
pk, sk = self.paillier.keygen(secparam=self.paillier_bits // 2)
return PaillierKeyPair(pk, sk)
[docs]
def sender_round1(self, 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
"""
# Ensure a is positive and in range
a_reduced = a % self.ec_order
# Encrypt a using sender's public key
ciphertext = self.paillier.encrypt(keypair.pk, a_reduced)
return {
'c_a': ciphertext,
'pk': keypair.pk,
}
[docs]
def receiver_round1(self, 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)
"""
c_a = sender_msg['c_a']
# Ensure b is positive
b_reduced = b % self.ec_order
# Sample random beta in range [0, ec_order)
beta_bytes = self.rand.getRandomBytes(32)
beta = int.from_bytes(beta_bytes, 'big') % self.ec_order
# Compute c_a^b = Enc(a*b) using Paillier homomorphism
# c^k mod n^2 = Enc(k*m)
c_ab = c_a * b_reduced # Uses Ciphertext.__mul__
# Add encryption of -beta: Enc(a*b) + Enc(-beta) = Enc(a*b - beta)
# In Paillier: -beta mod N, but we work mod ec_order
neg_beta = (-beta) % int(sender_pk['n'])
c_response = c_ab + neg_beta # Uses Ciphertext.__add__
return {'c_response': c_response}, beta
[docs]
def sender_round2(self, 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
"""
c_response = receiver_msg['c_response']
# Decrypt to get alpha = a*b - beta
alpha_raw = self.paillier.decrypt(keypair.pk, keypair.sk, c_response)
# Reduce modulo ec_order
alpha = alpha_raw % self.ec_order
return alpha
[docs]
class PaillierMtAwc(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
"""
def __init__(self, rsa_group: RSAGroup, ec_order: int,
paillier_bits: int = 2048):
super().__init__(rsa_group, ec_order, paillier_bits)
[docs]
def sender_round1_with_proof(self, a: int, keypair: PaillierKeyPair,
range_bound: Optional[int] = 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
"""
if range_bound is None:
range_bound = self.ec_order
# Get base message
msg = self.sender_round1(a, keypair)
# Generate simple commitment-based proof
# Full implementation would use Π^{enc} from CGGMP21
a_reduced = a % self.ec_order
commitment = self._compute_commitment(a_reduced, keypair)
msg['range_proof'] = {
'commitment': commitment,
'range_bound': range_bound,
}
return msg
def _compute_commitment(self, value: int, keypair: PaillierKeyPair) -> bytes:
"""Compute commitment for ZK proof."""
h = hashlib.sha256()
h.update(b"PAILLIER_MTA_COMMIT:")
h.update(value.to_bytes(32, 'big'))
h.update(str(keypair.pk['n']).encode())
return h.digest()
[docs]
def receiver_round1_with_proof(self, 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)
"""
# Verify sender's range proof if present
if 'range_proof' in sender_msg:
# In full implementation, verify Π^{enc} proof
pass
# Get base response
msg, beta = self.receiver_round1(b, sender_msg, sender_pk)
# Add affine operation proof (Π^{aff-g} in CGGMP21)
# Simplified: just include commitment to beta
h = hashlib.sha256()
h.update(b"PAILLIER_MTA_BETA:")
h.update(beta.to_bytes(32, 'big'))
msg['beta_commitment'] = h.digest()
return msg, beta
[docs]
def sender_round2_with_verify(self, 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)
"""
alpha = self.sender_round2(receiver_msg, keypair)
# Verify receiver's proof if present
verified = True
if 'beta_commitment' in receiver_msg:
# In full implementation, verify Π^{aff-g} proof
pass
return alpha, verified