Elliptic Curve and Shenanigans for Sane People

A gentle introduction to elliptic curve cryptography and a few concepts around it, without the need for a PhD in mathematics.

21/11/2024 · 31 min read · sapling 🪴

Introduction

While chatting about math with a friend, he brought up modular arithmetic—a concept I hadn’t heard of but was instantly intrigued by. Imagine this: instead of dealing with endless numbers, what if we worked within a closed loop, where everything resets after hitting, say, ? Modular arithmetic does exactly that, turning numbers into a finite, repeating cycle that unlocks surprising properties and patterns.

Let’s take a simple equation to demonstrate this way of thinking:

The graph associated with this equation looks like this:

Now let’s instead consider:

For :

We can now see oscillating between as the modulo acts as a “wrap-around” operation. Finite Fields (also known as Galois Fields) make extensive use of this property to ensure that every operation on two numbers , e.g. , stays in . More generally, we say that any Finite Field with is isomorphic.

Even though I did not see any direct-application of this, I was intrigued by this new stuff, and began digging deeper into the subject, clicking Wikipedia links after Wikipedia links. This is how I stumbled upon Shamir’s Secret Sharing. But before we dive into this, let’s first understand underlying concepts.

Notations

Just so we’re all on the same page:

	such that
	Deterministic concatenation of and
	Finite / Galois field of order
	Multiply by the generator point of an elliptic curve
	Sample from

Polynomials

One of the most, if not the most important property of polynomials, is that each one of them can uniquely be described by points for a polynomial of degree , noted .

The most straightforward way of seeing this is by setting an equation for each point we have:

We can see that we have equations for factors of , noted , which could also be represented with the following Vandermonde matrix equation:

Written as , we can solve this by inverting :

Which could be done by applying the Jordan-Gauss algorithm to the augmented matrix , where is the identity matrix (diagonal filled with s), until we only have pivots equal to :

If you prefer to see this in a graphical way, let’s consider the following example:

We have two points and . We can represent them as follows:

It is visually obvious that we can only draw a single line that goes through both points.

A line is essentially just , which is of degree . We can guess and deduce we need at least points to describe a polynomial .

The same goes if we add a third point :

If we did not add this third point and still tried to find a polynomial , we would have an infinite number of solutions:

But now the question is: how do we actually find the polynomial that goes through all the points? This is where Lagrange interpolation comes into play.

Lagrange Interpolation

Let’s take , , and to demonstrate this method.

The main principle behind this is to split the wanted function into multiple sub-functions , that each contribute to one given point, also called “node”.

We want to construct so that:

Making a function equal to at a certain point is as simple as multiplying it by . Based on this property, we can already “guess” :

Why does multiplying by add a root ?

For a function , when :

That’s a good start! But we have a problem: is not equal to at . We can fix this by dividing by :

And we effectively have . We can now repeat this process for , and :

The polynomial is computed by summing all the together and multiplying them by the corresponding :

And we have our polynomial :

Which effectively goes through , , and .

The general formula for is:

How Shamir’s Secret Sharing Works

With the basics of polynomials and Lagrange interpolation in mind, let’s dive in!

The main idea behind this is to split a secret into parts, such that any parts can be used to reconstruct the secret, but any parts are not enough to do so, and do not give any information about the secret.

Splitting the Secret

Let’s take the following example: we want to split the secret into parts, such that any parts can be used to reconstruct the secret.

The first step is to sample a random polynomial of degree such that . This gives us the property that .

Our splits, also called shares, are in fact just points of our polynomial. We can generate them by evaluating for . Do not evaluate for as this would obviously just give away the secret.

So our shares are , , , and .

Let’s now plot the polynomial :

Reconstructing the Secret

Based on what we just learnt earlier and Lagrange interpolation, we know that points will suffice to construct the polynonial of degree .

In our case, , so we need points to restore , just as described in the beginning.

Based on the shares we generated earlier, let’s take , and to reconstruct the polynomial using Lagrange interpolation:

Commitments, Proofs and Verifications

In a perfect world where everyone is honest and where there are no transmission errors caused by cosmic rays, we could just send the shares to the participants and call it a day. But guess what? Sh*t happens.

We need a way to check that the share we receive as a shareholder after the secret has been split is actually a valid share. One could simply try to verify it by reconstructing the polynomial and checking if the secret is the same, but this clearly against the whole point of Shamir’s Secret Sharing.

Instead, let’s take advantage of the properties of elliptic curves to create a commitment scheme. After we have generated our polynomial , we can take each coefficient and multiply it by the generator point of the curve. This gives us a few values that we can send to the shareholders.

Point operations in an elliptic curve

The trapdoor function (easy to do one way, hard the other) of an elliptic curve is the multiplication of a point by a scalar . This consists of adding the point to itself times. This operation is denoted as .

Let’s start out by graphically representing the addition of two points and in an elliptic curve.

One easy way to think of the addition is to draw a line that goes through and , and find the third point of intersection with the curve. The symmetrical point is the result of the addition of and . This is because elliptic curve have the property that any line between two points intersects the curve at most one more time.

In the case where there is no third point of intersection (i.e. the line is vertical), we define the result of the addition as the point at infinity, denoted as .

The resulting point is then reflected to over the x-axis. This symmetry property is easily explained by the fact that the curve’s coordinates are squared, so for a given coordinate, there are two possible coordinates, and .

The operation can then be done over and over again to find subsequent points.

In the case where , we can’t really draw a line between the two points, so we take the tangent to the curve at and find the third point of intersection. This is the result of the addition of and , denoted as .

To find the tangent at , we need to find the slope .

Differentiating both sides with respect to , , which actually depends on can be written as for clarity:

See this as if we were differentiating , where .

The right side is just a function of , so we can differentiate it as we would with any other function:

Our differentiated equation is:

Solving for :

Notice that the tangent’s slope depends on both and , which makes sense because we’d have two different slopes otherwise:

And we have our tangent equation for and :

When a shareholder wants to verify their share , they can check with the following equation:

You could see this procedure as computing the “public keys” of the coefficients. This method is also called “Feldman’s Verifiable Secret Sharing”.

One may argue that disclosing could give information about the polynomial, but if we suppose that is an EC secret key, the public key is supposed public and may be shared. Finding with comes down to solving the discrete logarithm problem, which is supposed really hard here.

Another way the dealer could commit to the polynomial he generated without directly sharing , is to add a so-called “blinding polynomial”, a pretty common concept in cryptography.

Let’s now instead take where comes from a randomly generated polynomial , our blinding polynomial. is just another generator point on the curve. The dealer will now needs to distribute slightly different shares .

Shareholders may now verify their shares with:

This second method is known as “Pedersen’s Verifiable Secret Sharing”.

Bob just got hit by a bus, what now?

Our good old friend disappeared along with his share, and now other bearers are scared of losing too many shares until they can’t recover the secret. They could reiterate the dealing procedure by all sending their shares to a single person which then redistributes the new ones. However this is not feasible in the case where everyone distrusts each other. We need a multi-computational way of re-issuing a new share without someone ever recovering the secret.

We will need shareholders, denoted to re-issue a new share .

Each shareholder begins by computing their Lagrange multiplier:

After multiplying with their share’s , they randomly split it into so-called Lagrange-parts in order to distribute them to other bearers :

The exchange matrix can be represented as:

Where the ^th row corresponds to the Lagrange-parts that the shareholder will send and the ^th column to the Lagrange-parts the shareholder will receive.

Each shareholder computes the partial-share:

Where is the ^th Lagrange-part of . They respectively send to the new bearer , which finally computes his share:

This can be rewritten as:

Inception

Another angle to tackle this problem from is to re-use Secret Sharing inside our Secret Sharing scheme (Inception, anyone?).

Let’s say we have our recovery group , our new shareholders and for convenience.

1. Each shareholder generates a random polynomial of degree .
2. They each compute the auxiliary shares for .
3. Every shareholder receives the auxiliary shares from the recovery group.
4. Each shareholder computes the aggregated share and shares it to everyone in .
5. Each future bearer can interpolate the polynomial from the shares and compute their share

Let’s take a look at the math:

But wait! We just learnt how to implement a secure, verifiable secret sharing scheme and we aren’t even using it!

Verifiable Inception

Let’s review the protocol, this time including relevant checks to ensure the data we’re receiving is genuine. We assume the original dealer was a good guy and already used Feldman’s VSS, providing the commitments for the OG polynomial to everyone.

1. Each shareholder generates a random polynomial of degree .
2. They also compute and share for to see their commitments:
3. They each compute the auxiliary shares for , and shares them once they have received all other
4. Every shareholder receives the auxiliary shares from and checks whether they match
5. Before computing anything else, each shareholder commits to the upcoming polynomial and sends it to :
6. Each shareholder computes the aggregated share .
7. Each inductee first waits to receive all , checks that they are the same from everyone, and then receives .
8. Each future shareholder checks whether each given is genuine:
9. Each future bearer can interpolate the polynomial from the shares and compute their share

Single share issuing

In the case where we only want to issue a single share, conduition proposed a clever way to remove the subtracting step at the end by adding a root at to the blinding polynomial. This way, we have:

When interpolating , the blinding polynomials cancel out and we directly get :

Note that we could try to add multiple roots: , but then all the new shareholders would have access to the new shares.

You could also apply the same verifying scheme as before to this method.

Shared Secrets with Elliptic Curves

Sharing pre-defined secrets is cool, but what if we wanted to collectively generate one for people? Let’s say we have our good old Alice, Bob and Charlie trying to communicate with each other securely. Alice doesn’t trust Charlie to generate the secret locally and share it to everyone because he’s the type of guy to write his passwords on sticky notes. Bob doesn’t trust Alice either because her idea of a strong password is “password123” — used across five accounts.

In elliptic curves, we have the following property:

While this may just seem like simple associativity, it’s actually pretty cool.

Let’s say we have participants, Alice and Bob, each with their key pair , where is the private key and is the public key. We can generate a shared secret by leveraging the property above:

1. Alice generates a random scalar , her private key and sends to Bob.
2. Bob also generates and sends back to Alice.
3. Alice computes .
4. Bob computes .

You can see that both Alice and Bob end up with the same shared secret without ever having to share their private keys.

This process can also be extended to participants, let’s take with Alice, Bob and Charlie here for simplicity:

1. Alice, Bob and Charlie generate their private keys , and respectively.
2. They compute their public keys , and and share them with each other.
3. Alice computes , and sends them to Charlie and Bob respectively.
4. Bob computes and sends it to Alice, he can already compute .
5. Charlie computes .
6. Alice computes

And voilà! All participants now have the same shared secret . I’ll let figuring out the general case for participants as an exercise to the reader (not because I’m lazy, I swear).

This secret can now be used as a symmetric key for encryption, a seed for a PRNG, TOTP key, etc.

ECDSA Signatures

Elliptic curves may not write your emails, but they can help prove you sent them. Let’s take a look at the Elliptic Curve Digital Signature Algorithm (ECDSA). Our goal is to output a signature for a given message , so that the recipient can verify that the sender is authentic. The sender’s keys are , with the private key, and the public one.

1. Compute the hash where is any cryptographic hash function (e.g. SHA-256).
2. Generate a random number in in the current subgroup.
3. Calculate the associated random point on the curve , with a generator, with the -coordinate of this point.
4. Calculate the signature , where is the modular inverse of .

By sending , you confirm you know:

• The content of the message
• The private key associated to

The verifier may follow this procedure to check if the message that he received along with is authentic:

1. Compute the hash with the same cryptographic hash function defined before.
2. Calculate the modular inverse of :
3. Recover the random point used in the signature process:
4. Check whether , if so, then the message is authentic.

To prove this works, let’s start with the definition of the signature :

Incorporate into :

Which is just our definition of when generating the signature.

Cool Kids Public Key Recovery

Let’s suppose you are talking through a Tin can telephone with your friend and every byte you send matters. You don’t want to send the public key along with the signature because that’s just too much data. Instead, you can recover the public key from the signature and the message.

Given , there are typically two candidate points that fit. And since we know that , which we just verified works, it can be rearranged to isolate the public key :

To choose which one is the correct one, we need to verify the signature with each :

This ambiguity is often removed by adding a single bit into the signature message:

Schnorr Signatures

Schnorr signatures are a bit like ECDSA, but faster and simpler. We are going to use the same keys as before, with the private key and the public one. We’ll first see the procedure and then discuss the mathematical proof of why this works.

1. Sample a random nonce

What the hell is ?

The set is a cyclic group of integers, isomorphic to the quotient group . It is basically just the set of integers modulo .

In our case, is the order (how many points are in) of the subgroup generated by . If the curve’s cofactor is 1, then is the order of the curve. If is not 1, the order is

1. Multiply it by the generator:
2. We can now compute the challenge
3. And the signature:

The final signature is .

Once the signature has been emitted, verifying it is as easy as checking:

To know , the verifier needs to know the message , the public key . In some cases, you might not need to include the public key into the challenge and simply hash .

Why it Works

There isn’t really a proof needed for the verifying step as it’s just factoring out , but here you are:

One trickier part is to explain why we are adding a random nonce to both the signature and the challenge. This value has to be sampled randomly and must not be reused. If it is, the private key can be recovered. Let’s first take the case where no is used:

Recovering the private key is as simple as multiplying the challenge by the modular inverse of . Not good.

Now, let’s take the case where is reused, with two messages and , along with their respective signatures and :

Combining and :

You may see as an additional unknown variable that is used to prevent the linear equation system from being solved, because for messages, you have equations and unknowns, which is unsolvable in our case.

Aggregating Signatures

Schnorr signatures have the nice property that they can be aggregated, this means that a group of people can sign a message together and the signature can be verified as if it was signed by a single person. Let’s consider our signing group for Alice, Bob and Charlie respectively.

The aggregated nonce is simply the sum of all nonces:

Likewise for the public key:

Each of them computes the challenge along with the final signature with the parameters just agreed upon:

Aggregate again:

The final signature that can be sent to others is .

Because we are just adding signatures parts together, we can group the nonces and the private keys in our final signature:

In the verifying step, multiplying each side by :

But wait!

At no point in this procedure, we ever check if the nonces or the public keys provided are honest. What if Charlie provided a malicious key in the sharing step ? Because everyone doesn’t send their public key at the exact same time, Carol could wait for everyone to send theirs, and compute:

The aggregated key will look like:

Carol just wiped everyone else from the signing key, and is now in full control of the signature. How can we prevent that ?

Multi-Signatures, don’t trust, verify

The most common way to prevent this is to force everyone to provide a proof that their public key is honest. This is done by providing a Proof of Knowledge for the private key, proving that they know the private key associated to the public key they provided.

Let’s take the case of a prover Patricia and a verifier Victor. Patricia wants to prove that she knows the private key associated to the public key . The proof is done in four steps:

1. Patricia samples at random and sends to Victor.
2. Victor sends a challenge to Patricia.
3. Patricia computes and sends it to Victor.
4. Victor verifies that .

This works because:

But what if Patricia doesn’t know the associated private key but still wants to prove that her key is honest ? Remember commitment schemes ? We can use them here. In our case, every participant will commit to their public key before disclosing it. Think of it as putting your public key in a box, sealing it and waiting for everyone to do the same before opening it. Let’s get back to our group :

1. Each participant hashes their public key and sends to everyone.
2. Once everyone has sent their hash, they disclose their public key .
3. Everyone verifies that the hash they received matches the public key.
4. The signing process continues as usual.

This way, everyone can be sure that the public keys are honest and that no one is trying to pull a fast one.

There’s more!

Random nonces are also aggregated, and at no point we are verifying that they are authentic. The exploit method is a bit trickier, I recommend you to read this article by conduition on the subject if you want to know the details.

Rust Implementation

I’ve been using Rust for a while now (even though I feel like I’m a complete beginner and still can’t manage to fully understand lifetimes), so I thought it would be a good idea to implement Shamir’s Secret Sharing and other algorithms in Rust.

Dependencies

Because working with elliptic curves is a bit tricky, we’ll use bls12_381_plus, which is a Rust implementation of the BLS12-381 curve. This abstracts a lot of the complexity and allows us to focus on the actual implementation of the algorithm.

You could also have used any other elliptic curve, such as Secp256k1.

Little side note on the Secp256k1 curve

Secp256k1, popular in cryptocurrencies like Bitcoin, is chosen not only for its efficiency but for its simplicity and transparency—qualities that help to prevent hidden vulnerabilities.

A cautionary tale here is the Dual_EC_DRBG scandal, where it was discovered that a backdoor had likely been embedded into a cryptographic algorithm, making it insecure for sensitive use. Secp256k1’s constants were selected in a predictable way, which significantly reduces the possibility that the curve’s creator inserted any sort of backdoor into the curve.

The curve is defined by the equation , represented below, even though in reality it just looks like a bunch of points scattered around because it is taken over a finite field (yes, is prime, I know, it’s weird).

I also made my own Polynomial struct to handle the polynomial operations, such as addition, multiplication, evaluation, etc.

use crate::types::{Point, Scalar, GENERATOR, GENERATOR_BLINDING};
use elliptic_curve::Field;
use std::ops::Mul;
/// Helper struct to represent a polynomial and evaluate it
#[derive(Clone, Debug)]
pub struct Polynomial {
    pub coefficients: Vec<Scalar>,
}
 
impl Polynomial {
    pub fn evaluate(&self, x: Scalar) -> Scalar {
        if self.coefficients.is_empty() {
            return Scalar::ZERO;
        }
        let degree = self.coefficients.len() - 1;
        let mut out = self.coefficients[degree];
        for i in (0..degree).rev() {
            out *= x;
            out += self.coefficients[i];
        }
        out
    }
 
    pub fn random<D>(degree: D) -> Self
    where
        D: Into<usize>,
    {
        let mut rng = rand::thread_rng();
        let mut coefficients = vec![];
        for _ in 0..=degree.into() {
            coefficients.push(Scalar::random(&mut rng));
        }
        Self { coefficients }
    }
 
    pub fn fill<U>(&mut self, degree: U)
    where
        U: Into<usize>,
    {
        let mut rng = rand::thread_rng();
        for _ in self.coefficients.len()..=degree.into() {
            self.coefficients.push(Scalar::random(&mut rng));
        }
    }
 
    pub fn with_fill<U>(mut self, degree: U) -> Self
    where
        U: Into<usize>,
    {
        self.fill(degree);
        self
    }
 
    pub fn commit(&self) -> Vec<Point> {
        self.coefficients.iter().map(|e| GENERATOR * e).collect()
    }
 
    pub fn zip_commit(&self, other: &Self) -> Vec<Point> {
        self.coefficients
            .iter()
            .zip(other.coefficients.clone())
            .map(|(a, b)| a * GENERATOR + b * *GENERATOR_BLINDING)
            .collect()
    }
 
    /// Add a root at c by multiplying the polynomial by (x - c)
    pub fn add_root(&mut self, c: Scalar) {
        *self *= Polynomial::new(vec![c, -Scalar::ONE]);
    }
 
    pub fn with_root(mut self, c: Scalar) -> Self {
        self.add_root(c);
        self
    }
 
    pub fn new(coefficients: Vec<Scalar>) -> Self {
        Self { coefficients }
    }
 
    pub fn empty() -> Self {
        Self {
            coefficients: vec![],
        }
    }
 
    pub fn degree(&self) -> usize {
        if self.coefficients.is_empty() {
            return 0;
        }
        self.coefficients.len() - 1
    }
 
    pub fn lagrange(points: Vec<(Scalar, Scalar)>) -> Self {
        if points.is_empty() {
            return Self {
                coefficients: vec![],
            };
        }
 
        let degree = points.len() - 1;
        let mut result = vec![Scalar::ZERO; degree + 1];
 
        // For each point, calculate its contribution to the final polynomial
        for (i, (x_i, y_i)) in points.iter().enumerate() {
            let mut basis_poly = vec![Scalar::ONE]; 
 
            for (j, (x_j, _)) in points.iter().enumerate() {
                if i != j {
                    let mut new_coeffs = vec![Scalar::ZERO];
                    new_coeffs.extend(basis_poly.iter().cloned());
 
                    // Subtract x_j times each coefficient
                    for (k, coeff) in basis_poly.iter().enumerate() {
                        new_coeffs[k] -= *x_j * *coeff;
                    }
 
                    basis_poly = new_coeffs;
                }
            }
 
            // Calculate denominator: product of (x_i - x_j) for all j != i
            let mut denominator = Scalar::ONE;
            for (j, (x_j, _)) in points.iter().enumerate() {
                if i != j {
                    denominator *= *x_i - *x_j;
                }
            }
 
            // Multiply basis polynomial by y_i/denominator
            let coefficient = *y_i * denominator.invert().unwrap();
            for coeff in basis_poly.iter_mut() {
                *coeff *= coefficient;
            }
 
            for (k, coeff) in basis_poly.iter().enumerate() {
                result[k] += *coeff;
            }
        }
 
        Self {
            coefficients: result,
        }
    }
}
 
impl PartialEq for Polynomial {
    fn eq(&self, other: &Self) -> bool {
        self.coefficients == other.coefficients
    }
}
 
impl Mul<Scalar> for Polynomial {
    type Output = Self;
 
    fn mul(self, rhs: Scalar) -> Self::Output {
        let mut coefficients = vec![];
        for c in self.coefficients {
            coefficients.push(c * rhs);
        }
        Self { coefficients }
    }
}
 
impl Mul<Polynomial> for Polynomial {
    type Output = Self;
 
    fn mul(self, rhs: Polynomial) -> Self::Output {
        let mut coefficients = vec![Scalar::ZERO; self.degree() + rhs.degree() + 1];
        for i in 0..=self.degree() {
            for j in 0..=rhs.degree() {
                coefficients[i + j] += self.coefficients[i] * rhs.coefficients[j];
            }
        }
        Self { coefficients }
    }
}
 
impl std::ops::MulAssign<Scalar> for Polynomial {
    fn mul_assign(&mut self, rhs: Scalar) {
        for c in self.coefficients.iter_mut() {
            *c *= rhs;
        }
    }
}
 
impl std::ops::MulAssign<Polynomial> for Polynomial {
    fn mul_assign(&mut self, rhs: Polynomial) {
        if self.coefficients.is_empty() {
            return;
        }
        if rhs.coefficients.is_empty() {
            self.coefficients = vec![];
            return;
        }
        let mut coefficients = vec![Scalar::ZERO; self.degree() + rhs.degree() + 1];
        for i in 0..=self.degree() {
            for j in 0..=rhs.degree() {
                coefficients[i + j] += self.coefficients[i] * rhs.coefficients[j];
            }
        }
        self.coefficients = coefficients;
    }
}
 
impl std::ops::Add for Polynomial {
    type Output = Self;
 
    fn add(self, rhs: Self) -> Self::Output {
        let mut coefficients = vec![];
        let mut i = 0;
        let mut j = 0;
        while i < self.coefficients.len() && j < rhs.coefficients.len() {
            coefficients.push(self.coefficients[i] + rhs.coefficients[j]);
            i += 1;
            j += 1;
        }
        while i < self.coefficients.len() {
            coefficients.push(self.coefficients[i]);
            i += 1;
        }
        while j < rhs.coefficients.len() {
            coefficients.push(rhs.coefficients[j]);
            j += 1;
        }
        Self { coefficients }
    }
}
 
impl std::ops::AddAssign for Polynomial {
    fn add_assign(&mut self, rhs: Self) {
        let mut coefficients = vec![];
        let mut i = 0;
        let mut j = 0;
        while i < self.coefficients.len() && j < rhs.coefficients.len() {
            coefficients.push(self.coefficients[i] + rhs.coefficients[j]);
            i += 1;
            j += 1;
        }
        while i < self.coefficients.len() {
            coefficients.push(self.coefficients[i]);
            i += 1;
        }
        while j < rhs.coefficients.len() {
            coefficients.push(rhs.coefficients[j]);
            j += 1;
        }
        self.coefficients = coefficients;
    }
}
 
impl std::ops::SubAssign for Polynomial {
    fn sub_assign(&mut self, rhs: Self) {
        // Add the negation of the second polynomial
        *self += rhs * Scalar::ONE.neg();
    }
}
 
impl std::ops::AddAssign<&Polynomial> for Polynomial {
    fn add_assign(&mut self, rhs: &Self) {
        let mut coefficients = vec![];
        let mut i = 0;
        let mut j = 0;
        while i < self.coefficients.len() && j < rhs.coefficients.len() {
            coefficients.push(self.coefficients[i] + rhs.coefficients[j]);
            i += 1;
            j += 1;
        }
        while i < self.coefficients.len() {
            coefficients.push(self.coefficients[i]);
            i += 1;
        }
        while j < rhs.coefficients.len() {
            coefficients.push(rhs.coefficients[j]);
            j += 1;
        }
        self.coefficients = coefficients;
    }
}
 
impl std::ops::Sub for Polynomial {
    type Output = Self;
 
    fn sub(self, rhs: Self) -> Self::Output {
        // Add the negation of the second polynomial
        self + rhs * Scalar::ONE.neg()
    }
}

use bls12_381_plus::{G1Projective, Scalar as BLSScalar};
use elliptic_curve::hash2curve::ExpandMsgXmd;
use lazy_static::lazy_static;
 
pub type Scalar = BLSScalar;
/// A share of a secret
pub type Share = (Scalar, Scalar); // (i, f(i))
pub type PedersenShare = (Scalar, Scalar, Scalar); // (i, f(i), g(i))
 
/// Wrapper type for a commitment
pub type Point = G1Projective;
 
pub const GENERATOR: Point = G1Projective::GENERATOR;

Let’s get to the code!

Splitting the Secret

/// Split a secret into n shares, requiring k shares to recover the secret
pub fn split(s: Scalar, n: u8, k: u8) -> Result<Vec<Share>> {
    ensure!(k <= n, "Cannot require (k = {k}) > (n = {n})");
 
    // Random polynomial: secret + a_1 * x^1 + ... + a_(k-1) * x^(k-1)
    let mut poly = Polynomial::new(vec![s])
        .with_fill(k - 1);
    // Compute our n shares
    let shares = (1..=n)
        .map(|i| {
            let x = Scalar::from(i as u32);
            (x, poly.evaluate(x))
        })
        .collect();
 
    Ok(shares)
}

Verifying the Shares - Feldman’s VSS

/// Verify a share against a set of commitments
pub fn verify(share: Share, commitments: Vec<Point>) -> Result<()> {
    // We need to check that share_i * G = sum_(j=0)^(t-1) i^j * commitment_j
    let mut lhs = Point::identity();
    let rhs = GENERATOR * share.1;
    for (j, commitment) in commitments.iter().enumerate() {
        lhs += commitment * share.0.pow_vartime(&Scalar::from(j as u8).to_raw());
    }
 
    ensure!(
        bool::from((lhs - rhs).is_identity()),
        "Verification failed: {:#?} != {:#?}",
        lhs,
        rhs
    );
    Ok(())
}

Verifying the Shares - Pedersen’s VSS

lazy_static! {
    // We need a 2nd generator point - just hash a random message
    static ref GENERATOR_BLINDING: Point = G1Projective::hash::<ExpandMsgXmd<Sha256>>(
        b"generator_blinding",
        &[0xde, 0xad, 0xbe, 0xef]
    );
}
 
/// Verify a share against a set of Pedersen commitments
pub fn verify(share: PedersenShare, commitments: Vec<Point>) -> Result<()> {
    // We need to check that f(i) * G + g(i) * H = sum_(j=0)^(t-1) i^j * commitment_j
    let mut lhs = Point::identity();
    let rhs = share.1 * GENERATOR + share.2 * *GENERATOR_BLINDING;
    for (j, commitment) in commitments.iter().enumerate() {
        lhs += commitment * share.0.pow_vartime(&Scalar::from(j as u8).to_raw());
    }
 
    ensure!(
        bool::from((lhs - rhs).is_identity()),
        "Verification failed: {:#?} != {:#?}",
        lhs,
        rhs
    );
    Ok(())
}

Reconstructing the Secret

// See the Polynomial struct for the implementation of the Lagrange interpolation
pub fn recover(shares: Vec<Share>) -> Scalar {
    Polynomial::lagrange(shares).evaluate(Scalar::ZERO)
}

Schnorr Signatures

For this part, I used the Secp256k1 curve, via the really cool secp crate. The implementation is quite similar to the one I described earlier.

use rand::rngs::OsRng;
use secp::{Point, Scalar, G};
use sha2::{Digest, Sha256};
 
fn compute_challenge(public_nonce: Point, public_key: Point, message: impl AsRef<str>) -> Scalar {
    // H(R || P || m)
    let challenge: [u8; 32] = Sha256::new()
        .chain_update((public_nonce).serialize())
        .chain_update((public_key).serialize())
        .chain_update(message.as_ref().as_bytes())
        .finalize()
        .into();
    Scalar::reduce_from(&challenge)
}
 
fn sign(message: impl AsRef<str>, key: Scalar) -> Result<Signature> {
    // Enabled via the `rand` feature of the `secp` crate
    let nonce = Scalar::random(&mut OsRng); // r
 
    let public_nonce = nonce * G; // R
    let public_key = key * G; // P
 
    let challenge = compute_challenge(public_nonce, public_key, message); // e
    // s = r + e * p
    let signature = (nonce + challenge * key).not_zero()?;
 
    Ok((public_nonce, signature))
}
 
fn verify(message: impl AsRef<str>, public_key: Point, signature: Signature) -> Result<bool> {
    let challenge = compute_challenge(signature.0, public_key, message);
    // s * G =? R + e * P
    Ok(signature.1 * G == (signature.0 + challenge * public_key).not_inf()?)
}

References / Suggested readings

• Issuing New Shamir Secret Shares Using Multi-Party Computation
  conduition.io

• A Dive Into the Math Behind Bitcoin Schnorr Signatures
  conduition.io

• A (Relatively Easy To Understand) Primer on Elliptic Curve Cryptography
  Nick Sullivan
  cloudflare.com

• Feldman’s Verifiable Secret Sharing for a Dishonest Majority
  Yi-Hsiu Chen and Yehuda Lindell
  eprint.iacr.org [PDF]

• Adaptively Secure Feldman VSS and Applications to Universally-Composable Threshold Cryptography
  Masayuki Abe and Serge Fehr
  eprint.iacr.org [PDF]

• Asymmetric Key Ciphers
  Svetlin Nakov
  cryptobook.nakov.com

• Novel Secret Sharing and Commitment Schemes for Cryptographic Applications
  Mehrdad Nojoumian
  dspacemainprd01.lib.uwaterloo.ca [PDF]

• A Share-Correctable Protocol for the Shamir Threshold Scheme and Its Application to Participant Enrollment
  Raylin Tso, Ying Miao, Takeshi Okamoto and Eiji Okamoto
  citeseerx.ist.psu.edu [PDF]

Acknowledgements

I wanted to thank conduition.io for his amazing articles on cryptography. They are a great source of inspiration and knowledge, and I highly recommend you to check them out if you want to learn more about cryptography.