Prototype your own Scheme

In this section, we provide a hands-on tutorial on how to implement a private-key encryption scheme based on ring-LWE.

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, which allows you to display the entire documentation. Press it to see the solution.

Private-Key Encryption Scheme - Ring-LWE

First, we look at the formal definition of the scheme that we want to implement.

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

\(sk \leftarrow \text{KGen}(1^n): sk \leftarrow {R}_q\)
\((a, b) \leftarrow \text{Enc}(sk, m): a \leftarrow {R}_q, e \leftarrow \chi, b:= sk \cdot a + e + m \text{, where } m \in {R}_2\)
\(m \leftarrow \text{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.

Defining the correct Trait

In order to implement a scheme, first define the common functionality of its primitive. In our case, the formal definition of a private-key encryption scheme provides all required information for this task:

\(sk \leftarrow \text{KGen}(1^n):\) generates a private key for encryption
\(c \leftarrow \text{Enc}(sk, m):\) encrypts the message
\(m \leftarrow \text{Dec}(sk, c):\) decrypts the message

Create a trait according to the specification above.

// Add the corresponding function signatures to this trait

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

    /// Generates a secret key that can be used for encryption and decryption.
   fn key_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

The next step is to implement the trait for our previously defined struct.

// This defines the structure
// We have to implement each algorithm individually

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

    fn key_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 \text{KGen}(1^n): sk \leftarrow {R}_q\) which corresponds to:

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

Now we have to implement the encryption. As it was more practical, we have as input an integer rather than a value of \( {R}_2 \). However, we need a way to transform an integer into an element in \({R}_{2}\) and back. Fortunately, qFALL-tools provides this functionality for arbitrary \({R}_{p}\) with the functions encode_value_in_polynomialringzq and decode_value_from_polynomialringzq.

For the encryption algorithm we have to implement the following.

\((a, b) \leftarrow \text{Enc}(sk, m): a \leftarrow {R}_q, e \leftarrow \chi, b:= sk \cdot a + e + m \text{, where } m \in {R}_2\)

The algorithmic description given above corresponds to the following implementation.

    fn enc(&self, sk: &Self::SecretKey, message: &Z) -> Self::Cipher {
        let mu_q_half = encode_value_in_polynomialringzq(message, 2, &self.q).unwrap();

        // a <- R_q
        let a = PolynomialRingZq::sample_uniform(&self.q);
        // e <- χ
        let e = PolynomialRingZq::sample_discrete_gauss(&self.q, 0, &self.alpha * &self.q.get_q())
            .unwrap();

        let b = sk * &a + e + mu_q_half;

        (a, b)
    }

Note that we use a discrete Gaussian error distribution.

The last function left to implement is decryption. At this point, it should be quite easy to finalize the implementation. So, we provide the solution directly:

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

        decode_value_from_polynomialringzq(&result, 2).unwrap()
    }

Choosing Parameters and Testing the Scheme

Finally, we introduce a set of parameters to test our construction. This can be done in the following way.

    pub fn parameter_set() -> 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 q = new_anticyclic(&n, q).unwrap();

        let alpha: Q = alpha.into();

        Self { n, q, alpha }
    }

The previously defined set of parameters can then be used to test whether encrypting and decrypting messages works.

    #[test]
    fn enc_and_dec() {
        let message = Z::from(17);
        let scheme = PrivKRingLWE::parameter_set();

        let sk = scheme.key_gen();
        let c = scheme.enc(&sk, &message);

        assert_eq!(message, scheme.dec(&sk, &c));
    }