Multiplicative-to-Additive Conversion (MtA)

mta_protocol.py

#!/usr/bin/env python3
"""
Multiplication-to-Addition (MtA) Protocol Implementation

This implements a secure two-party protocol that converts multiplication into addition.
The protocol allows two parties with private inputs a and b to compute additive shares
s1 and s2 such that s1 + s2 = a * b mod q, without revealing their inputs to each other.

The MtA protocol is a fundamental building block in multi-party computation (MPC) systems,
enabling secure multiplication operations in protocols like ECDSA threshold signatures.

Protocol Overview:
=================
1. Party 1 (Sender) has secret value 'a'
2. Party 2 (Receiver) has secret value 'b'
3. Goal: Compute shares s1, s2 such that s1 + s2 ≡ a * b (mod q)

Security Properties:
===================
- Sender Privacy: Receiver learns nothing about 'a'
- Receiver Privacy: Sender learns nothing about 'b'
- Correctness: s1 + s2 = a * b mod q always holds
- Based on the security of the underlying Oblivious Transfer protocol

Mathematical Foundation:
=======================
The protocol uses a clever masking technique:
1. Sender generates random δ (delta) and prepares OT inputs (δ-a, δ+a)
2. Receiver chooses random bit t and computes v such that v*t = b
3. Receiver gets z ∈ {δ-a, δ+a} via OT based on choice bit t
4. Final shares: s1 = -δ*v, s2 = v*z
5. Result: s1 + s2 = a*b regardless of the value of t

References:
===========
- "Efficient Two-Party Protocols for Multiplication-to-Addition Conversion"
- Used in threshold ECDSA protocols like GG18, GG20
- Foundation for secure multi-party computation systems

Dependencies:
============
- oblivious_transfer: Chou-Orlandi OT protocol for secure bit transfers
- ecc_utils: Centralized P-256 field modulus and modular arithmetic operations

This implementation uses the Chou-Orlandi Oblivious Transfer protocol for the
underlying OT operations, providing efficient elliptic curve based security.
The field operations use the P-256 modulus from ecc_utils for consistency
with other elliptic curve protocols in this project.
"""

from oblivious_transfer import OTSender, OTReceiver
from ecc_utils import MODULUS_Q, mod_q
import secrets


class MtASender:
    """
    Sender side of the Multiplication-to-Addition (MtA) protocol.

    The sender holds a private value 'a' and wants to compute additive shares
    of a*b without learning the receiver's value 'b'.

    Protocol Steps for Sender:
    1. Generate random mask δ (delta)
    2. Prepare OT inputs: (δ-a, δ+a)
    3. Execute OT as sender
    4. Receive v from receiver
    5. Compute final share: s1 = -δ*v

    Mathematical Invariant:
    The sender's share s1 combined with receiver's share s2 will always
    satisfy: s1 + s2 ≡ a*b (mod q)
    """

    def __init__(self, secret_value_a):
        """
        Initialize MtA sender with private input.

        Args:
            secret_value_a: The sender's private input value 'a'
        """
        self.a = secret_value_a
        self.delta = None  # Random mask, generated in step1
        self.ot_sender = OTSender()  # Underlying OT protocol sender

    def step1_send_ot(self):
        """
        Step 1: Generate random mask and prepare OT inputs.

        The sender creates a random mask δ and prepares two OT inputs:
        - input0 = δ - a (for receiver's choice bit t=0)
        - input1 = δ + a (for receiver's choice bit t=1)

        This masking ensures that the receiver learns either (δ-a) or (δ+a)
        but cannot determine 'a' since δ is random and unknown to receiver.

        Returns:
            tuple: (A_bytes, input0, input1) where:
                - A_bytes: OT public key to send to receiver
                - input0: Encrypted value (δ-a) for choice bit 0
                - input1: Encrypted value (δ+a) for choice bit 1
        """
        # Generate cryptographically secure random mask
        self.delta = secrets.randbelow(MODULUS_Q)

        # Prepare OT inputs as byte arrays
        # These will be encrypted by the OT protocol
        input0 = mod_q(self.delta - self.a).to_bytes(32, "big")  # δ - a
        input1 = mod_q(self.delta + self.a).to_bytes(32, "big")  # δ + a

        # Generate OT sender's public key
        A_bytes = self.ot_sender.step1_generate_public_point()

        return A_bytes, input0, input1

    def step3_finalize(self, v_scalar):
        """
        Step 3: Compute final additive share using received v.

        After the OT execution, the receiver sends v (which satisfies v*t = b).
        The sender computes its final share as s1 = -δ*v.

        Mathematical Justification:
        - If t=0: receiver gets z = δ-a, computes s2 = v*(δ-a) = v*δ - v*a
        - If t=1: receiver gets z = δ+a, computes s2 = v*(δ+a) = v*δ + v*a
        - In both cases: s1 + s2 = -δ*v + v*δ ± v*a = ±v*a = ±b*a = a*b

        Args:
            v_scalar: Value v received from receiver (satisfies v*t = b)

        Returns:
            int: Sender's additive share s1 = -δ*v mod q
        """
        s1 = mod_q(-self.delta * v_scalar)
        return s1


class MtAReceiver:
    """
    Receiver side of the Multiplication-to-Addition (MtA) protocol.

    The receiver holds a private value 'b' and wants to compute additive shares
    of a*b without learning the sender's value 'a'.

    Protocol Steps for Receiver:
    1. Choose random bit t and set up OT receiver
    2. Compute v such that v*t = b mod q
    3. Execute OT to get either (δ-a) or (δ+a)
    4. Compute final share: s2 = v*z

    Mathematical Invariant:
    The receiver's share s2 combined with sender's share s1 will always
    satisfy: s1 + s2 ≡ a*b (mod q)

    Choice Bit Logic:
    - If t=0: v = -b, receiver gets z = δ-a
    - If t=1: v = b, receiver gets z = δ+a
    - In both cases: s2 = v*z leads to correct final result
    """

    def __init__(self, secret_value_b):
        """
        Initialize MtA receiver with private input.

        Args:
            secret_value_b: The receiver's private input value 'b'
        """
        self.b = secret_value_b

        # Random choice bit for OT - this determines which OT input we receive
        self.choice_t = secrets.choice([0, 1])

        # Initialize OT receiver with our choice bit
        self.ot_receiver = OTReceiver(self.choice_t)

        # Values computed during protocol execution
        self.v_scalar = None  # Computed to satisfy v*t = b
        self.z_scalar = None  # Received from OT (either δ-a or δ+a)

    def step2_receive_ot(self, A_bytes):
        """
        Step 2: Process sender's OT public key and generate response.

        This step is part of the OT protocol where the receiver generates
        their response based on the choice bit t.

        Args:
            A_bytes: OT public key received from sender

        Returns:
            bytes: OT response B to send back to sender
        """
        B_bytes = self.ot_receiver.step2_compute_B(A_bytes)
        return B_bytes

    def step3_compute_v(self):
        """
        Step 3: Compute v such that v*t = b mod q.

        This is a crucial step that ensures the protocol's correctness.
        The receiver must compute v such that when multiplied by the choice bit t,
        it equals their secret value b.

        Mathematical Details:
        - If t=0 (choice bit 0): v*(-1) = b, so v = -b mod q
        - If t=1 (choice bit 1): v*(1) = b, so v = b mod q

        The value v will be sent to the sender and used in final share computation.

        Returns:
            int: Computed value v such that v*t ≡ b (mod q)
        """
        # Convert choice bit to mathematical value
        t_value = 1 if self.choice_t == 1 else -1
        t_value_mod = mod_q(t_value)

        # Compute modular inverse: t_inv such that t * t_inv ≡ 1 (mod q)
        t_inv = pow(t_value_mod, -1, MODULUS_Q)

        # Compute v = b * t_inv = b / t mod q
        self.v_scalar = mod_q(self.b * t_inv)

        return self.v_scalar

    def step4_decrypt_z(self, c0, c1):
        """
        Step 4: Decrypt the OT result to obtain z.

        Using the OT protocol, the receiver decrypts one of the two ciphertexts
        to obtain either (δ-a) or (δ+a), depending on their choice bit t.

        Security Property:
        The receiver learns only one of {δ-a, δ+a} but cannot determine 'a'
        since δ is a random mask unknown to the receiver.

        Args:
            c0: Ciphertext for choice bit 0 (contains δ-a)
            c1: Ciphertext for choice bit 1 (contains δ+a)

        Returns:
            int: Decrypted value z ∈ {δ-a, δ+a} based on choice bit
        """
        decrypted_bytes = self.ot_receiver.step4_decrypt_message(c0, c1)
        self.z_scalar = int.from_bytes(decrypted_bytes, "big")
        return self.z_scalar

    def compute_share(self):
        """
        Compute the receiver's final additive share.

        The receiver's share is computed as s2 = v * z, where:
        - v was computed to satisfy v*t = b
        - z was obtained from OT and equals either (δ-a) or (δ+a)

        Mathematical Correctness:
        Case 1 (t=0): v = -b, z = δ-a
            s2 = v*z = (-b)*(δ-a) = -b*δ + b*a
            s1 + s2 = -δ*v + (-b*δ + b*a) = -δ*(-b) + (-b*δ + b*a) = b*δ - b*δ + b*a = b*a

        Case 2 (t=1): v = b, z = δ+a
            s2 = v*z = b*(δ+a) = b*δ + b*a
            s1 + s2 = -δ*v + (b*δ + b*a) = -δ*b + b*δ + b*a = b*a

        Returns:
            int: Receiver's additive share s2 = v*z mod q
        """
        s2 = mod_q(self.v_scalar * self.z_scalar)
        return s2


def run_mta_demo(input_a, input_b):
    """
    Demonstration of the complete MtA protocol execution.

    This function shows how two parties can securely compute additive shares
    of their product without revealing their individual inputs to each other.

    Protocol Flow:
    1. Initialize sender with secret 'a' and receiver with secret 'b'
    2. Execute the MtA protocol steps
    3. Verify that s1 + s2 = a * b mod q

    Args:
        input_a: Sender's private input value
        input_b: Receiver's private input value

    Example:
        >>> run_mta_demo(123, 456)
        # Outputs additive shares s1, s2 such that s1 + s2 = 123 * 456
    """
    print("\nMtA Protocol: Secure Multiplication-to-Addition Conversion")
    print("=" * 60)
    print(f"Party 1 (Sender) secret input: {input_a}")
    print(f"Party 2 (Receiver) secret input: {input_b}")
    print(
        f"Goal: Compute shares s1, s2 such that s1 + s2 ≡ {input_a} × {input_b} (mod q)"
    )
    print()

    # Initialize protocol parties
    sender = MtASender(input_a)
    receiver = MtAReceiver(input_b)

    print(f"Receiver's random choice bit t: {receiver.choice_t}")
    print()

    # Step 1: Sender prepares OT with masked inputs
    print("Step 1: Sender generates random mask δ and prepares OT inputs")
    A_bytes, input0, input1 = sender.step1_send_ot()
    print(f"  Random mask δ: {sender.delta}")
    print(f"  OT input 0 (δ-a): {int.from_bytes(input0, 'big')}")
    print(f"  OT input 1 (δ+a): {int.from_bytes(input1, 'big')}")
    print()

    # Step 2: Receiver responds to OT setup
    print("Step 2: Receiver processes OT setup")
    B_bytes = receiver.step2_receive_ot(A_bytes)
    print("  Receiver computed OT response B")
    print()

    # Step 3: Receiver computes and sends v
    print("Step 3: Receiver computes v such that v×t ≡ b (mod q)")
    v_scalar = receiver.step3_compute_v()
    print(f"  Computed v: {v_scalar}")

    # Verify the constraint v*t = b
    t_val = 1 if receiver.choice_t == 1 else -1
    verification = mod_q(v_scalar * t_val)
    print(
        f"  Verification: v × t = {v_scalar} × {t_val} ≡ {verification} ≡ {input_b} (mod q)"
    )
    print(f"  Constraint satisfied: {verification == input_b}")
    print()

    # Step 4: Execute OT encryption and decryption
    print("Step 4: Execute Oblivious Transfer")
    c0, c1 = sender.ot_sender.step3_encrypt_messages(B_bytes, input0, input1)
    receiver.step4_decrypt_z(c0, c1)

    choice_desc = "δ+a" if receiver.choice_t == 1 else "δ-a"
    print(f"  Receiver (choice t={receiver.choice_t}) obtained z = {choice_desc}")
    print(f"  Decrypted value z: {receiver.z_scalar}")
    print()

    # Step 5: Compute final additive shares
    print("Step 5: Compute final additive shares")
    s2 = receiver.compute_share()
    print(f"  Receiver's share s2 = v × z = {receiver.v_scalar} × {receiver.z_scalar}")
    print(f"  s2 ≡ {s2} (mod q)")

    s1 = sender.step3_finalize(v_scalar)
    print(f"  Sender's share s1 = -δ × v = -{sender.delta} × {v_scalar}")
    print(f"  s1 ≡ {s1} (mod q)")
    print()

    # Verification of protocol correctness
    print("Step 6: Protocol Verification")
    expected_product = mod_q(input_a * input_b)
    actual_sum = mod_q(s1 + s2)

    print(f"  Expected product: {input_a} × {input_b} ≡ {expected_product} (mod q)")
    print(f"  Computed sum: s1 + s2 ≡ {actual_sum} (mod q)")
    print(f"  Protocol correctness: {actual_sum == expected_product}")

    if actual_sum == expected_product:
        print("  ✅ SUCCESS: MtA protocol executed correctly!")
    else:
        print("  ❌ ERROR: Protocol verification failed!")

    return actual_sum == expected_product


if __name__ == "__main__":
    # Main execution block demonstrating the MtA protocol.
    #
    # This example shows how two parties can securely compute multiplication
    # without revealing their individual inputs. The protocol converts the
    # multiplication a*b into additive shares s1 + s2 = a*b.
    #
    # Security guarantees:
    # - Party 1 learns s1 but nothing about b
    # - Party 2 learns s2 but nothing about a
    # - Both parties can verify s1 + s2 = a*b if needed

    # Example inputs for demonstration
    demo_secret_a = 123456789
    demo_secret_b = 987654321

    print("=" * 80)
    print("MtA PROTOCOL DEMONSTRATION")
    print("Secure Multiplication-to-Addition Conversion using ECC-based OT")
    print("=" * 80)
    print(f"This demo shows how to securely compute {demo_secret_a} × {demo_secret_b}")
    print("without either party learning the other's input value.")
    print()

    # Execute the protocol
    success = run_mta_demo(demo_secret_a, demo_secret_b)

    print("\n" + "=" * 80)
    if success:
        print("PROTOCOL EXECUTION COMPLETED SUCCESSFULLY")
        print("The MtA protocol correctly computed additive shares of the product!")
    else:
        print("PROTOCOL EXECUTION FAILED")
        print("There was an error in the MtA protocol execution.")
    print("=" * 80)

OT protocol is here:
https://gist.github.com/tarassh/43aec62ad64e73f574d131cef2e92b10