Bachelor / Master Thesis

Asynchronous verifiable secret sharing schemes with polynomial commitments

Secret sharing is the basis of threshold cryptography. It allows a dealer to share a secret in a way that only authorized sets of parties (we will define this using a threshold: any set of size equal or greater than the threshold is authorized) can later reconstruct it. The math behind secret sharing uses polynomials, and the simple property that any set of t+1 points uniquely define a polynomial of degree at most t. A secret sharing scheme assumes a trusted dealer that hands out correct shares, where correct means that, no matter which authorized set does the reconstruction, they will always result in the same reconstructed secret.

A verifiable secret sharing (VSS) scheme lifts this assumption. The dealer now computes not only a share for every party, but also some additional values which allow the parties to check the correctness of their shares. These additional values are called commitments; the dealer choses a random polynomial (of the appropriate degree) and commits to its coefficients.

Yet another extension is the asynchronous verifiable secret sharing (AVSS) scheme. While VSS schemes assume that parties can communicate with each other always with the same maximum and known latency, AVSS schemes make simply no assumptions about communication. Observe that this model is much more realistic, but also much harder to reason in.

Finally, a polynomial commitment [1] allows a prover that holds a polynomial to create commitments to it, but has a special and very interesting property. The prover can reveal evaluations of the polynomial at any desired point (e.g., reveal and prove that f(11) = 42), without revealing anything else about the polynomial.

The goal of this project is to explore AVSS schemes that use polynomial commitments. The work entails searching the literature, exploring and classifying existing work, and coming up with own protocols.

Requirements: basic algebra, knowledge of secure cryptographic protocols [2].

[1] Polynomial Commitments

[2] Course: Cryptographic protocols, FS2021

Contact Orestis Alpos or Duc V. Le for more information.

Nature of the project: Theory 100%.