Implementing Crypto

In the next section we provide a hands-on tutorial on how to implement a cryptographic scheme. Note: This section is a step-by-step tutorial and as such code-blocks only display the outline of the code. In the top right corner of every code field, there is an eye with which you can display the entire documentation. Press it to see the solution.

Private Key Encryption Scheme - Ring-LWE

We give the procedure of defining a private key encryption scheme based on ring-LWE.

Firstly, we look at the formal definition of the scheme we will implement:

Let \( R = \mathbb{Z}[X]/(X^n + 1) \), then we define the ring-based LWE private key encryption scheme as follows:

\(sk \leftarrow Gen(1^n): sk \leftarrow R_q\)
\((a, b) \leftarrow Enc(sk, m): \text{ where } m \in R_{0,1}, a \leftarrow R_q, e \leftarrow \chi, b:= sk \cdot a + e + m\)
\(m \leftarrow Dec(sk, (a,b)): d:= b - a\cdot sk\) and each coefficient of \(d\) is mapped to \(0\) if it is closer to \(0\) than to \(q/2\) and to \(1\) otherwise.

The error distribution \(\chi\) samples an element from \(R_q\) and the modulus \(q\) is also chosen appropriately.

Finding the correct Trait

In order to implement a scheme, first identify the commonly shared functionality between each scheme of that category. Here, this is easy, as it is the formal definition of a private key encryption scheme:

\(sk \leftarrow Gen(1^n)\) generate a private key for encryption
\(c \leftarrow Enc(sk, m):\) encrypt the message
\(m \leftarrow Dec(sk, c):\) decrypt the message

Now try to make a trait out of this:

// The trait is still missing the above described functionalities, try to add them
// manually

pub trait PrivKeyEncryption {
    type SecretKey;
    type Message;
    type Cipher;

    /// Generates a secret key that can be used for encryption and decryption.
   fn gen(&self) -> Self::SecretKey;
    /// Encrypts a message using the secret key.
   fn enc(&self, sk: &Self::SecretKey, message: &Self::Message) -> Self::Cipher;
    /// Decrypts a ciphertext using the secret key.
   fn dec(&self, sk: &Self::SecretKey, cipher: &Self::Cipher) -> Self::Message;
}

Determining Public Parameters and Defining a corresponding Struct

Traits are implemented for structs. The actual implementation of our scheme corresponds to an implementation of the trait for a struct. This struct holds the public parameters needed for the computation:

// The struct is still missing the public parameters, try to identify them

pub struct PrivKRingLWE {
    // the security parameter
    n: Z,
    // the modulus
    q: ModulusPolynomialRingZq,
    // the parameter for the error distribution
    alpha: Q,
}

Implementing the Scheme

Now we want to implement the trait for our previously defined struct.

// The structure, now we only have to fill out each algorithm individually

impl PrivKeyEncryption for PrivKRingLWE {
    type SecretKey = PolynomialRingZq;
    type Message = Z;
    type Cipher = (PolynomialRingZq, PolynomialRingZq);

    fn gen(&self) -> Self::SecretKey {
    }

    fn enc(&self, sk: &Self::SecretKey, message: &Z) -> Self::Cipher {
    }

    fn dec(&self, sk: &Self::SecretKey, (a, b): &Self::Cipher) -> Z {
}

For the generation algorithm we have to implement

\(sk \leftarrow Gen(1^n): sk \leftarrow R_q\) which corresponds to:

    fn gen(&self) -> Self::SecretKey {
        PolynomialRingZq::sample_uniform(&self.q)
    }

Now we have to implement the encryption. You might have realized that as input for the scheme we have chosen an integer rather than a value of \(R*{0,1}\), this was mainly due to practicability, but we need a way to transform an integer into an element in \(R*{0,1}\). Use the following function for the transformation:

impl PrivKRingLWE {
    /// Turns a [`Z`] instance into its bit representation, converts this bit representation
    /// into a [`PolynomialRingZq`] with entries q/2 for any 1-bit and 0 as coefficient for any 0-bit.
    fn compute_mu_half(&self, message: impl Into<Z>) -> PolynomialRingZq {
        // ensure mu has at most n bits
        let message: Z = message.into().abs();
        let mu = message.modulo(Z::from(2).pow(&self.n).unwrap());
        // set mu_q_half to polynomial with n {0,1} coefficients
        let bits = mu.to_bits();
        let mut mu_q_half = PolynomialRingZq::from((PolyOverZ::default(), &self.q));
        let q_half = self.q.get_q().div_floor(2);
        for (i, bit) in bits.iter().enumerate() {
            if *bit {
                mu_q_half.set_coeff(i, &q_half).unwrap();
            }
        }

        mu_q_half
    }
}

For the encryption algorithm we have to implement

\((a, b) \leftarrow Enc(sk, m): \text{ where } m \in R_{0,1}, a \leftarrow R_q, e \leftarrow \chi, b:= sk \cdot a + e + m\) which corresponds to (note that for the error distribution you can sample from a discrete gauss):

    fn enc(&self, sk: &Self::SecretKey, message: &Z) -> Self::Cipher {
        let mu_q_half = self.compute_mu_half(message);
        let a = PolynomialRingZq::sample_uniform(&self.q);
        let e = PolynomialRingZq::sample_discrete_gauss(
            &self.q,
            &self.n,
            0,
            &self.alpha * &self.q.get_q(),
        )
        .unwrap();
        let b = sk * &a + e + mu_q_half;
        (a, b)
    }

Now it only remains to decrypt the message. At this point this should probably be the easiest part, so we provide the solution directly:

    fn dec(&self, sk: &Self::SecretKey, (a, b): &Self::Cipher) -> Z {
        let result = b - sk * a;

        let q_half = self.q.get_q().div_floor(2);

        // check for each coefficient whether it's closer to 0 or q/2
        // if closer to q/2 -> add 2^i to result
        let mut vec = vec![];
        for i in 0..self.q.get_degree() {
            let coeff = Zq::from((result.get_coeff(i).unwrap(), self.q.get_q()));
            if coeff.distance(&q_half) < coeff.distance(Z::ZERO) {
                vec.push(true);
            } else {
                vec.push(false);
            }
        }

        Z::from_bits(&vec)
    }

Choosing Parameters and using the Scheme

Now we only have to use a set of parameters and we can use our construction. This could look as follows:

impl PrivKRingLWE {
    pub fn secure128() -> Self {
        Self::new(512, 92897729, 0.000005)
    }

    pub fn new(n: impl Into<Z>, q: impl Into<Modulus>, alpha: impl Into<Q>) -> Self {
        let n: Z = n.into();

        // mod = (X^n + 1) mod q
        let mut q = PolyOverZq::from((1, q));
        q.set_coeff(&n, 1).unwrap();
        let q = ModulusPolynomialRingZq::from(&q);

        let alpha: Q = alpha.into();

        Self { n, q, alpha }
    }
}

and can then be used to encrypt and decrypt messages: