Master Thesis

Exploring threshold cryptosystems

Public-key cryptosystems work with a public-secret key pair (PK, SK). Any party that knows PK can encrypt a message, and the owner of SK can then decrypt it. Multiple security definitions exist for public-key cryptosystems, and each of them makes sense in specific applications and deployment conditions. One of them, that provides relatively stronger security and is thus more challenging to satisfy, is the security against Chosen-Ciphertext Attacks (CCA). Informally, a CCA-secure cipher ensures that the adversary cannot obtain any useful information from a challenge ciphertext, even if they are allowed to modify it as they wish and to obtain the decryption of any (other than the challenge) ciphertext of their choice.

In threshold cryptography, the secret key SK does not exist in a single place but is distributed over multiple parties. Every party only possesses a key share, which is a piece of the secret key, as resulting from a secret-sharing algorithm [1]. Hence, a public-key cryptosystem in threshold settings allows the parties to produce decryption shares of a ciphertext, and a party that receives enough such shares can then combine them to obtain the decrypted message. Achieving CCA security in threshold settings is more demanding than in the non-threshold case, considering both proving it and also keeping the scheme efficient.

Nevertheless, CCA-secure threshold public-key cryptosystems are well-known in the literature. These can be classified in two broad categories, based on the techniques employed for achieving CCA security. The schemes in the first category do the math in an appropriate subgroup of Z_p, they base their security on the Discrete Logarithm (DL) problem or (some version of) the Diffie-Hellmann (DH) problem, and employ zero-knowledge proofs (ZKP), such as proofs of knowledge of discrete logarithms or proofs of equality of discrete logarithms, to achieve CCA security. A representative example is the Shoup-Gennaro scheme [2]. Those in the second category use again the DH problem, but work in certain elliptic curves that allow pairings. These are maps between elliptic-curve groups. These schemes do not make use of additional ZKP, but rely on pairing calculations to achieve CCA-security [3].

This project aims at comparing the two aforementioned approaches and requires some theoretical and technical expertise. The comparison may use a theoretical approach and/or an experimental approach. As a first step, a high-level understanding of the concepts should be reached. Afterwards, different implementations of the schemes, as available in public repositories, will be considered. Implementations that already exist in the lab can be used as well. This thesis topic permits a lot of flexibiltiy and allows a choice between theoretical and experimental work.

[1] How to Share a Secret

[2] Securing Threshold Cryptosystems against Chosen Ciphertext Attack

[3] Simple and Efficient Threshold Cryptosystem from the Gap Diffie-Hellman Group

Contact Orestis Alpos for more information.

Nature of the project: Theory 50%, Systems 50%.