===== Thesis Defense Information ===== **Defense Date and Time:** November 12, 2024, at 16:00 **Location:** Université Paris Cité, Bâtiment Halle aux Farines, Room 580F, 10 rue Françoise Dolto, 75013 Paris **Zoom Link:** * Meeting id : 584 894 5659 * Link : https://u-paris.zoom.us/j/5848945659?pwd=qIyhigjaapdKaDiylYKl2r55T1iJRM.1&omn=85832856426 * Password : 248469 **Directions to the Room:** To access the room, find staircase F2 on the ground floor and then go up to the 5th floor. [[https://hps.master.univ-paris-diderot.fr/sites/hps.master.univ-paris-diderot.fr/files/u566/Plan%20Halle%20aux%20farines.pdf| Here is a map if you need it.]] **Follow-Up Event:** After the defense, an apéro will be held on the 4th floor of the IRIF lab. Later, we’ll head to the bar Mambo Café BNF, starting at 8:30 pm. ===== Thesis Details ===== **Thesis Title:** Multi-Party Computation Based on the Computational Hardness of Coding Theory. **Abstract:** Since the beginning of modern cryptography, the question of secure computation (MPC) has been extensively studied. MPC allows for a set of parties to perform some joint computation while ensuring that their input remains secure up to what is implied by the output. The massive development of our daily Internet usage makes the need for secure computation methods more urgent: computations on private data is everywhere, from recommendation algorithms to electronic auctions. Modern MPC algorithms greatly benefit from correlated randomness to achieve fast online protocols. Correlated randomness has to be massively produced beforehand for the MPC protocols to work best, and this is still a challenge to do efficiently today. In this thesis, we study pseudorandom correlation generators (PCGs). This construction transforms a small amount of correlated randomness into a large amount of correlated pseudorandomness with minimal interaction and local computation. We present different PCG constructions whose security relies on variants of the Syndrome Decoding (SD) assumption, a classical assumption in coding theory. The intuition behind these constructions is to merge the SD assumption with some MPC techniques that enable additively sharing sparse vectors. We achieve state-of-the-art results regarding secure computation protocols requiring more than two players when the computation is over a finite field of size > 2. We show how to remove this constraint at the cost of a small overhead in communication. Next, we consider the construction of pseudorandom correlation functions (PCFs). PCFs produce correlations on-the-fly: players each hold correlated functions such that the outputs of the functions, when evaluated on the same entry, are correlated. These objects offer more flexibility than PCGs but are also harder to construct. We again rely on variants of SD to construct PCFs. We build on a previous PCF construction, showing that the associated proof of security was incorrect, and propose a correction. Additionally, we present optimizations of the construction, coming from a better analysis and precise optimization of parameters via simulations. We achieve parameters usable in practice. Finally, this thesis revolves around the use of certain codes, particularly the SD assumption. The search for good complexity entails efforts to find the most efficient codes while ensuring that security is not compromised. We consider a framework tailored to the study of promising attacks on SD and its variants. For each construction previously mentioned, we conduct a thorough security analysis of the associated variant of SD and attempt cryptanalysis efforts to compute concrete parameters. **Keywords:** Secure Computation, Pseudorandom Correlation, Coding Theory, Syndrome Decoding, Pseudorandom Correlation Generator, Pseudorandom Correlation Function. The current version of the manuscript can be found {{ :users:cducros:manuscript.pdf |here}}.