LSV Seminar

Date

21.01.2020, 11:00

Place

Pavillon des Jardins

Speaker

Duong Hieu Phan (Université de Limoges)

Anonymity is a primary ingredient for our digital life. Several tool have been designed to address it, namely blind signatures, group signatures or anonymous credentials for authentication and randomizable encryption or mix-nets for confidentiality. When it comes to complex electronic voting schemes, random shuffling of ciphertexts with mix-nets is the only known tool and it has largely been used in practice, for example in the recent professional election of National Education with more than 430 000 votes. However, achieving anonymity requires huge and complex zero-knowledge proofs in order to guarantee the actual permutation of the initial ciphertexts. In this talk, we propose a new approach for proving correct shuffling based on linearly-homomorphic signatures: the mix-servers can simply randomize individual ballots (meaning the ciphertexts, the signatures, and the verification keys) with an additional global proof of constant size, and the output will be publicly verifiable. The computational complexity for the mix-servers is linear in the number of ciphertexts. It also remains linear in the number of ciphertexts for the verifiers, independently of the number of rounds of mixing. This leads to the most efficient technique of mix-nets, which is at the same time highly scalable. Finally, when considering post-quantum security, we solve the open problem of Boneh and Freeman on the hardness of the k-SIS problem (from an exponential loss to a polynomial loss) and thus make their linearly-homomorphic signatures more practical. (This talk is based on two works: one with Hebant Chloé and David Pointcheval and another one with San Ling, Damien Stehlé and Ron Steinfeld)