Modern cryptography is concerned with the feasibility or infeasibility of securely realizing a task. The answer to whether or not a task can be securely realized depends on the assumed power of the adversary. The obtained security holds in a strong mathematical sense, meaning that breaking a secure cryptographic protocol is either impossible or it would require to solve some computational problem which is believed to be hard to solve. The most basic computational assumption made in cryptography is the existence of one-way functions. One-way functions are functions that are easy to compute but are hard to invert on almost all inputs. By just assuming the existence of one-way functions it is already possible to realize many cryptographic tasks, but there are some tasks that can only be realized by assuming the existence of trapdoor functions (also called backdoored functions). Trapdoor functions are easy to compute in one direction but hard to invert; the difference is the existence of a special value that allows the function to be easily inverted by any party that has knowledge of this special value.

In this thesis we have contributions in three different facets of backdoors in cryptography, that we describe next.

• Backdoors for legitimate usage: We define a new security goal for chameleon hash functions that we call enhanced collision resistance. This security definition informally says that a chameleon hash function must remain collision-resistant even after an adversary sees polynomially many collisions for the function. We also present a novel transformation from standard chameleon hash functions to enhanced ones; a full-fledged “redactable blockchain” application, that leverages the power of enhanced collision-resistant chameleon hashes, is built to show that this new security goal for chameleon hashes makes sense in practice.

• Backdoors for malicious usage: Motivated by the revelations of Edward Snowden about intelligence agencies intentionally undermining the security of cryptographic schemes, we cover the case where backdoors are used to perform attacks against signature schemes. In this vein, we define what is an undetectable subversion attack against a signature scheme and we also present two devastating attacks against randomized signature schemes that allows the complete extraction of the users’ signing key.
• Immunization techniques against malicious backdoors: Our contributions in this vein are twofold. We first show positive results for signature schemes against subversion attacks; we prove that unique signatures are secure against an undetectable class of subversion attacks and that re-randomizable signatures are secure against *all* classes of subversion attacks (by employing a cryptographic reverse firewall introduced in this thesis). In the other contribution on the immunization direction we define a secure model for the outsourcing of circuit fabrication, where the outsourcing facilities are untrusted and can potentially embed malicious hardware trojans in the circuit. We construct three compilers that upon input an arbitrary circuit it produces an outsourcing-secure version of the circuit.