## 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.

[2] Securing Threshold Cryptosystems against Chosen Ciphertext Attack

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