Normale Supérieure de Lyon in Amphitheater B (3rd
Time: October 18th 2018 at 2:30PM
In this thesis, we study provably secure privacy-preserving cryptographic constructions. We focus on zero-knowledge proofs and their applications. Group signatures are an example of such constructions. This primitive allows users to sign messages on behalf of a group (which they formerly joined), while remaining anonymous inside this group. Additionally, users remain accountable for their actions as another independent authority, a judge, is empowered with a secret information to lift the anonymity of any given signature. This construction has applications in anonymous access control, such as public transportations. Whenever someone enters a public transportation, he signs a timestamp. Doing this proves that he belongs to the group of people with a valid subscription. In case of problem, the transportation company hands the record of suspicious signatures to the police, which is able to un-anonymize them. We propose two constructions of group signatures for dynamically growing groups. The first is based on pairing-related assumptions and is fairly practical. The second construction is proven secure under lattice assumptions for the sake of not putting all eggs in the same basket. Following the same spirit, we also propose two constructions for privacy-preserving cryptography. The first one is a group encryption scheme, which is the encryption analogue of group signatures. Here, the goal is to hide the recipient of a ciphertext who belongs to a group, while proving some properties on the message, like the absence of malwares. The second is an adaptive oblivious transfer protocol, which allows a user to anonymously query an encrypted database, while keeping the unrequested messages hidden. These constructions were made possible through a series of work improving the expressiveness of Stern’s protocol, which was originally based on the syndrome decoding problem.