My Ph.D. defence took place on October 26th, 2022. My thesis was entitled "Malleable Cryptography: Advances and Applications to Privacy-enhancing Technologies".
This thesis studies malleability in the context of public-key encryption and digital signatures, presenting advances and applications to privacy-enhancing technologies. The first part addresses the problem of Generic Plaintext Equality and Inequality Proofs. Given two ciphertexts generated with a public-key encryption scheme, the problem of plaintext equality consists in determining whether the ciphertexts hold the same value. Similarly, the problem of plaintext inequality consists in deciding whether they hold different values. Previous work has focused on building new schemes or extending existing ones to include support for plaintext equality/inequality. We propose generic and simple zero-knowledge proofs for both problems, which can be instantiated with various encryption schemes. We do so by formalizing notions related to malleability in the context of public-key encryption and proposing a definitional framework for Generic Randomisable Encryption, which we use to build our protocols. The next part turns to Structure-Preserving Signatures on Equivalence Classes, the main building block of subsequent parts. First, we propose new and more efficient constructions under standard assumptions. Then, we build an anonymous attribute-based credential (ABC) scheme under standard assumptions, which extends previous work in several ways. We improve expressiveness, provide efficiency trade-offs and propose an issuer-hiding notion that allows credential holders to hide the issuer's identity during showings. The last part is devoted to presenting Protego, a new ABC scheme for permissioned blockchains. It builds upon the previous contributions, and although it is discussed in the context of permissioned blockchains, it can also be used in other settings. To show the practicality of Protego, we provide a prototype implementation and benchmarks showing that Protego is more than twice faster than state-of-the-art approaches based on Idemix, the most widely used ABC scheme for permissioned blockchains.