Extended Euclid Algorithm in Nada

[Envoy-VC]

Need help in calculating Multiplicative inverse of two numbers

Extended Euclidean Multiplicative Inverse:

It finds integers  𝑥 and  𝑦 such that  𝑎 𝑥 + 𝑏 𝑦 = gcd ⁡ ( 𝑎 , 𝑏 ). If  gcd ⁡ ( 𝑎 , 𝑏 ) = 1  
then  𝑥 is the modular inverse of  𝑎 modulo  𝑏, i.e.,  𝑎 𝑥 ≡ 1 ( mod 𝑏 ).

Current Progress: I am able to calculate reciprocals in nada using following code

from nada_dsl import *


def nada_main():
    party1 = Party(name="Party1")

    N = SecretInteger(Input(name="N", party=party1))

    result = Integer(0)
    remainder = Integer(1)
    start_zeros = Integer(0)

    for _ in range(10):
        remainder *= Integer(10)
        quotient = remainder / N

        is_zero = ((quotient + result) == Integer(0)).if_else(
            (quotient == Integer(0)).if_else(Integer(1), Integer(0)),
            Integer(0)
        )

        start_zeros += is_zero

        result = (result * Integer(10)) + quotient
        remainder = remainder - (quotient * N)

    # Example: 1/334 = 0.002994012
    # result = 2994012
    # start_zeros = 2

    return [Output(result, "approx_inverse", party1), Output(start_zeros, "start_zeros", party1)]

the pseudo code of Extended Euclidean Multiplicative Inverse is

def extended_euclidean(a, b):
    # Initialize variables
    x0, x1, y0, y1 = 1, 0, 0, 1
    
    while b != 0:
        quotient = a // b
        remainder = a % b
        
        a = b
        b = remainder
        
        x_temp = x1
        y_temp = y1
        
        x1 = x0 - quotient * x1
        y1 = y0 - quotient * y1
        
        x0 = x_temp
        y0 = y_temp
    
    return a, x0, y0

and here is my nada implementation

from nada_dsl import *


def nada_main():
    party1 = Party(name="Party1")

    a = SecretInteger(Input(name="a", party=party1))
    b = SecretInteger(Input(name="b", party=party1))

    x0, x1, y0, y1 = Integer(1), Integer(0), Integer(0), Integer(1)

    for _ in range(3):

        multiplier = (b == Integer(0)).if_else(Integer(1), Integer(0))

        quotient = a / b
        remainder = a % b

        a = (b * (multiplier + Integer(1))) + (a * multiplier)
        b = (remainder * (multiplier + Integer(1))) + (b * multiplier)

        x_temp = x1
        y_temp = y1

        x1 = (x0 - quotient * x1 * (multiplier + Integer(1))) + \
            (x1 * multiplier)
        y1 = (y0 - quotient * y1 * (multiplier + Integer(1))) + \
            (y1 * multiplier)

        x0 = (x_temp * (multiplier + Integer(1))) + (x1 * multiplier)
        y0 = (y_temp * (multiplier + Integer(1))) + (y1 * multiplier)

    return [Output(a, "gcd", party1),
            Output(x0, "x", party1),
            Output(y0, "y", party1)]

The Problems:

1. We cannot use while loops so we do not know number of iterations
2. there is a formula for estimating number of iterations: iterations≈ log ϕ (min(10,3))

$$iterations \approx log_\Phi (min(a,b))$$ $$\Phi \approx 1.618$$

but that cannot be computed in nada program.

[lapets]

You've made a lot of progress! The key insight is that when putting together a secure computation workflow, you cannot have the number of iterations depend on a secret input. This would leak information about the input to the nodes performing the computation (since they know how many iterations occur when they execute a program).

Thus, the approach is to rewrite the body of the loop so that the number of iterations is always some fixed, sufficiently large value. However, in that case it is also necessary to perform the assignments inside the body based on a condition (i.e., the original condition from the while loop that appears when computing in the clear).

The Python code below illustrates how you might go about finishing your program:

def egcd(a, b):
    (r_old, r) = (a, b)
    (x, x_old, y, y_old) = (0, 1, 1, 0)
    for _ in range(100):
        (r_old, q, r) = (r, r_old // r, r_old % r) if r > 0 else (r_old, q, r)
        (x, x_old) = ((x_old - q * x), x) if r > 0 else (x, x_old)
        (y, y_old) = ((y_old - q * y), y) if r > 0 else (y, y_old)

    return r_old, x_old, y_old

print(egcd(10, 6))

Good luck!

[Envoy-VC]

You've made a lot of progress! The key insight is that when putting together a secure computation workflow, you cannot have the number of iterations depend on a secret input. This would leak information about the input to the nodes performing the computation (since they know how many iterations occur when they execute a program).

Thus, the approach is to rewrite the body of the loop so that the number of iterations is always some fixed, sufficiently large value. However, in that case it is also necessary to perform the assignments inside the body based on a condition (i.e., the original condition from the while loop that appears when computing in the clear).

The Python code below illustrates how you might go about finishing your program:

def egcd(a, b):
    (r_old, r) = (a, b)
    (x, x_old, y, y_old) = (0, 1, 1, 0)
    for _ in range(100):
        (r_old, q, r) = (r, r_old // r, r_old % r) if r > 0 else (r_old, q, r)
        (x, x_old) = ((x_old - q * x), x) if r > 0 else (x, x_old)
        (y, y_old) = ((y_old - q * y), y) if r > 0 else (y, y_old)

    return r_old, x_old, y_old

print(egcd(10, 6))

Good luck!

I tried this program but the compilation takes a long time and never completes, here is my code also i am getting wrong outputs

from nada_dsl import *

def egcd(a, b):
    (r_old, r) = (a, b)
    (x, x_old, y, y_old) = Integer(1), Integer(0), Integer(0), Integer(1)
    for _ in range(100):
        multiplier = (r > Integer(0)).if_else(Integer(0), Integer(1))
        r_old = (r * (multiplier + Integer(1))) + (r_old * multiplier)
        q = r_old / r
        r = (r_old % r * (multiplier + Integer(1))) + (r * multiplier)

        x = (x_old - q * x * (multiplier + Integer(1))) + (x * multiplier)
        x_old = (x * (multiplier + Integer(1))) + (x_old * multiplier)

        y = (y_old - q * y * (multiplier + Integer(1))) + (y * multiplier)
        y_old = (y * (multiplier + Integer(1))) + (y_old * multiplier)

    return r_old, x_old, y_old


def nada_main():
    party1 = Party(name="Party1")

    a = SecretInteger(Input(name="a", party=party1))
    b = SecretInteger(Input(name="b", party=party1))

    (gcd, x0, y0) = egcd(a, b)

    return [Output(gcd, "gcd", party1),
            Output(x0, "x", party1),
            Output(y0, "y", party1)]

for ruuning loop for 4 iterations and values a = 30, b = 18 the output should be 6, 1, -2 but i get 36, 15, -15

[jcabrero]

In case it may be an option for your problem, Nada works in a prime modular field. In case you can set b = <Prime> you can use that to easily compute the modular inverse with Fermat's Theorem. The code for that is below. I also add the different Prime modulus. You should select the prime to be the same as in your nada-project.toml. The code is the following:

PRIME_64 = 18446744072637906947
PRIME_128 = 340282366920938463463374607429104828419
PRIME_256 = 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF98C00003
PRIME = PRIME_64


def public_modular_inverse(
    value: Integer | UnsignedInteger, modulo: int
) -> PublicUnsignedInteger | UnsignedInteger:
    """
    Calculates the modular inverse of a public value with respect to a prime modulus.

    Args:
        `value`: The value for which the modular inverse is to be calculated.
        `modulo`: The prime modulo with respect to which the modular inverse is to be calculated.

    Returns:
        The modular inverse of the value with respect to the modulo.
    """
    return value ** UnsignedInteger(modulo - 2)

def nada_main():
   ...
    a = UnsignedInteger(16)
    a_inv = public_modular_inverse(a)
   ...