As the title suggests, this thesis is an exploration of the bijective links between three families of combinatorial objects: planar maps, Tamari intervals and parking trees. Along the way, we will encounter many other kinds of combinatorial animals with exotic names, such as fighting fish, quadrant excursions, embedded mobiles, closed flows and blossoming trees…
Planar maps have been well known to combinatorialists since they were intro- duced about sixty years ago. Their rich underlying combinatorial structure has contributed to the development of a strong bijective framework surrounding them. We can cite the examples of bijections with blossoming trees, which allow elegant proofs of beautiful formulas counting families of planar maps. More recently, the discovery of similar formulas for Tamari intervals has led to the exploration of the bijective connection with planar maps. In this manuscript, we revisit some of these bijections and create new ones, shedding new light by integrating numerous combi- natorial families.
At the crossroads of the correspondences developed in our work, we will en- counter several models of parking trees. Not only do these trees appear naturally to encode families of planar maps and Tamari intervals, but they are also proto- types of objects governed by catalytic equations. In this sense, the general study of parking trees, initiated by Duchi and Schaeffer in 2023, and continued here, seems very promising for a further refined understanding of the bijective and enumerative schemes surrounding this manuscript.

This manuscript focuses on defining and optimizing code-based cryptographic primitives, with a particular emphasis on digital signatures derived through the Fiat-Shamir transformation of zero-knowledge proofs of knowledge. It presents three main contributions.
The first contribution introduces a five-round zero-knowledge proof of knowledge protocol based on the RSD problem, employing an advanced witness conversion technique. The protocol is then transformed into a digital signature scheme using the Fiat-Shamir heuristic, adapted for post-quantum security. Performance is further optimized through a novel hypercube technique, achieving competitive speeds relative to existing schemes. The second contribution focuses on improving the efficiency of the MPC-in-the-Head paradigm by defining multi-instance puncturable pseudorandom functions (PPRFs) specifically designed for code-based protocols: replacing traditional hash-based approaches with fixed-key block ciphers, the proposed PPRFs reduce signing and verification times by up to 55×, establishing new performance benchmarks for MPC-in-the-Head-based schemes.
The third contribution extends the initial digital signature scheme into a threshold signature framework, addressing the challenges of efficiently adapting MPC-based schemes for multi-user collaborative signing. The proposed methodology minimizes the trade-off between signature size and user count, outperforming naive concatenation techniques. Applied to the earlier code-based signature scheme, this approach results in a practical and efficient threshold signature solution.
In conclusion, this manuscript presents significant advancements in code-based post-quantum cryptography by addressing fundamental challenges in security and efficiency. Combining rigorous theoretical design with practical relevance, the contributions align with the goals of the NIST standardization process and address emerging needs such as blockchain and decentralized systems.

In this thesis, we put forward advancements in Multi-Party Computation (MPC), enabling parties to jointly compute arbitrary functions while preserving the privacy of their inputs. Our focus is on MPC with correlated randomness, where efficiency is improved through correlations generated using preprocessing. We investigate two key paradigms for generating such randomness: Pseudorandom Correlation Generators (PCGs) and Pseudorandom Correlation Functions (PCFs). First, we propose new PCG-based constructions for Private Set Intersection (PSI), achieving either tighter security or improved performance. We then explore the applications of PCGs and PCFs in Zero-Knowledge Proofs (ZKPs), addressing both interactive and non-interactive settings. For interactive ZKPs, we design a privately verifiable protocol for circuit satisfiability with sublinear communication and efficient computation. In the non-interactive setting, we introduce a new designated-verifier ZKP (DV-NIZK) leveraging PCF with a public-key structure (PK-PCF). Finally, we introduce a novel MPC framework for binary circuits, utilizing a PCG optimized for small fields.

The connection between logic and computer science has been fruitfully explored for years, and yet there is still so much to uncover. This thesis aims to further enrich this fascinating field by delving into the interplay between the ecosystem of linear logic and that of programming languages. In the first part, we introduce a new definition of parallel cut elimination for multiplicative-exponential linear logic (MELL) proof nets. Drawing inspiration from Tait and Martin-Löf’s parallel reduction in the lambda calculus, we address the challenges posed by untyped proof nets by defining a generalized notion of substitution on more abstract structures called prestructures. This approach allows us to define parallel exponential cut elimination for MELL prestructures in a rigorous and systematic way. Through the strong confluence of this operation, we provide a confluence proof for cut elimination in MELL proof nets without relying on Newman’s lemma or strong normalization. Furthermore, we extend this framework to define complete parallel cut elimination, offering an alternative confluence proof that closely mirrors Tait and Martin-Löf’s approach for the lambda calculus. The second part of this work introduces a new logic system, PiL, which extends first-order multiplicative and additive linear logic by incorporating a non-commutative, non-associative connective and nominal quantifiers. We prove that PiL enjoys cut elimination and embed the recursion-free fragment of the pi-calculus within PiL, demonstrating that the operational semantics of the pi-calculus can be captured by linear implication in PiL. This result allows us to characterize key properties such as deadlock freedom, ensuring that a network of processes can continue executing until termination, and progress, particularly for systems without mobility.Additionally, we establish a choreographies-as-proofs correspondence, providing the first completeness theorem for choreographies within this fragment of the pi-calculus. Finally, we introduce proof nets for PiL by integrating techniques from conflict nets and unification nets, thereby defining the first syntax for conflict nets in the context of multiplicative-additive linear logic with first-order quantifiers. By linking computation trees to derivations and deriving canonical representatives of these trees in the same manner as proof nets represent sequent calculus proofs, this work opens new avenues for bridging computation and logic.