smol-mpc 0.1.0

A port of TinySMPC into Rust.
Documentation 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156

//! Implements all the functionalities for Mersenne fields.
//!
//! In multi-party computation protocols, it is common to use an underlying
//! algebraic structure in wich all the secure computations are performed. This
//! module defines all the basic functionalities to manipulate the Mersenne
//! fields used in the protocols supported by the library.
//!
//! The source code for `Mersenne61` was taken from [Secure Computation Library].
//!
//! [Secure Computation Library]: https://github.com/anderspkd/secure-computation-library/blob/master/src/scl/math/mersenne61.cc

use crate::utils::prg::Prg;

/// Defines an element in a Mersenne field $\mathbb{F}_p$ with $p = 2 ^ {61} - 1$.
#[derive(Clone)]
pub struct Mersenne61 {
    /// Value of the element. This value will belong to $\mathbb{F}_p$.
    pub value: u64,
}

/// Defines the operations over Mersenne fields elements.
pub trait MersenneField {
    /// Power of the Mersenne field. Mersenne fields are of the form
    /// $\mathbb{F}_p$ with $p = 2^n - 1$. This variable represents $n$.
    const POWER: u64;

    /// Order of the Mersenne field.
    const ORDER: u64;

    /// Creates an element in a Mersenne field.
    fn new(value: u64) -> Self;

    /// Computes the sum between two elements in a Mersenne field.
    fn add(&self, other: &Self) -> Self;

    /// Given a field element $a \in \mathbb{F}_p$, returns $-a$.
    fn negate(&self) -> Self;

    /// Computes the product of two elements in the Mersenne field.
    fn multiply(&self, other: &Self) -> Self;

    /// Given a field element $a \in \mathbb{F}_p$, returns $a^{-1}$.
    fn inverse(&self) -> Self;

    /// Computes the subtraction between two elements in the field.
    fn subtract(&self, other: &Self) -> Self;

    /// Generates a random element in the Mersenne field provided a
    /// pseudo-random generator.
    fn random(prg: &mut Prg) -> Self;

    /// Returns the value of the element in the Mersenne field.
    fn value(&self) -> u64;
}

impl MersenneField for Mersenne61 {
    const POWER: u64 = 61;
    const ORDER: u64 = (1 << Self::POWER) - 1;

    fn new(value: u64) -> Self {
        if value < Self::ORDER {
            Self { value }
        } else {
            // TODO: This is provisional while I find a way to do it in constant
            // time.
            Self {
                value: value % Self::ORDER,
            }
        }
    }

    fn value(&self) -> u64 {
        self.value
    }

    fn add(&self, other: &Self) -> Self {
        let sum = self.value + other.value;
        if sum >= Self::ORDER {
            Self {
                value: sum - Self::ORDER,
            }
        } else {
            Self { value: sum }
        }
    }

    fn subtract(&self, other: &Self) -> Self {
        self.add(&other.negate())
    }

    fn inverse(&self) -> Self {
        if self.value == 0 {
            panic!("You can not invert the zero element of a field.");
        }

        let mut k: i64 = 0;
        let mut new_k: i64 = 1;
        let mut r = Self::ORDER as i64;
        let mut new_r = self.value as i64;

        while new_r != 0 {
            let q = r / new_r;

            // Swaps and operates on k and new_k, and r and new_r
            swap_and_operate(&mut k, &mut new_k, q);
            swap_and_operate(&mut r, &mut new_r, q);
        }

        if k < 0 {
            k += Self::ORDER as i64;
        }

        Self { value: k as u64 }
    }

    fn multiply(&self, other: &Self) -> Self {
        let mult: u128 = (self.value as u128) * (other.value as u128);
        let mut a = mult >> Self::POWER;
        let mut b: u64 = mult as u64;

        a |= (b as u128) >> (Self::POWER as u128);
        b &= Self::ORDER;

        let a_wrap = Self { value: a as u64 };
        let b_wrap = Self { value: b };

        a_wrap.add(&b_wrap)
    }

    fn negate(&self) -> Self {
        if self.value != 0 {
            Self {
                value: Self::ORDER - self.value,
            }
        } else {
            self.clone()
        }
    }

    fn random(prg: &mut Prg) -> Self {
        let random_bytes = prg.next((u64::BITS / 8) as usize);
        let random_value = u64::from_ne_bytes(
            random_bytes
                .try_into()
                .expect("Expected a vector with 8 bytes"),
        );

        Self::new(random_value)
    }
}

fn swap_and_operate(a: &mut i64, b: &mut i64, q: i64) {
    let temp = *b;
    *b = *a - q * temp;
    *a = temp;
}