Trapdoor functions, introduced in the seminal paper of Diffie and Hellman, are a fundamental notion in modern cryptography. Informally, trapdoor functions are injective functions that are easy to evaluate but hard to invert unless given an additional input called the trapdoor. Specifically, the classical security notion considered for trapdoor functions is one-wayness, which asks that it be hard to invert (except with very small probability) a uniformly random point in the range without the trapdoor. Motivated by the demands of emerging applications of cryptography as well as stronger security properties desired from higher-level cryptographic primitives constructed out of trapdoor functions, this thesis studies new strengthenings to the classical notion of one-way trapdoor functions and their applications. Our results are organized along two separate threads, wherein we introduce two new cryptographic primitives that strengthen the notion of one-wayness for trapdoor functions in different ways: Deterministic Encryption: Our notion of deterministic (public-key) encryption addresses the weaknesses of using trapdoor functions directly for encryption articulated by Goldwasser and Micali, to the extent possible without randomizing the encryption function (whereas Goldwasser and Micali address them using randomized encryption). Specifically, deterministic encryption ensures no partial information is leaked about a high-entropy plaintext or even multiple correlated such plaintexts. Deterministic encryption has applications to fast search on encrypted data, securing legacy protocols, and ``hedging' randomized encryption against bad randomness. We design a conceptually appealing semantic-security style definition of security for deterministic encryption as well as an easier-to-work-with but equivalent indistinguishability style definition. In the random oracle model of Bellare and Rogaway, we show a secure construction of deterministic encryption for an unbounded number of arbitrarily correlated high-entropy plaintexts based on any randomized encryption scheme, as well as length-preserving such construction based on RSA. In the standard model, we develop a general framework for constructing deterministic encryption schemes based on a new notion of ``robust' hardcore functions. We show a secure construction of deterministic for a single high-entropy plaintext based on exponentially-hard one-way trapdoor functions; single-message security is equivalent to security for an unbounded number of messages drawn from a block-source (where each subsequent message has high entropy conditioned on the previous). We also show a secure construction of deterministic encryption for a bounded number of arbitrarily correlated high-entropy plaintexts based on the notion of lossy trapdoor functions introduced by Peikert and Waters. paragraph*{Adaptive Trapdoor Functions:} Our notion of adaptive trapdoor functions asks that one-wayness be preserved in the presence of an inversion oracle that can be queried on some range points. The main application we give is the construction of black-box chosen-ciphertext secure public-key encryption from weaker general assumptions. (``Black-box' means that the specific code implementing the trapdoor function is not used in the construction, which typically incurs a huge efficiency cost.) Namely, we show such a construction of chosen-ciphertext secure public-key encryption from adaptive trapdoor functions. We then show that adaptive trapdoor functions can be realized from the recently introduced notions of lossy trapdoor functions by Peikert and Waters and correlated-product secure trapdoor functions by Rosen and Segev. In fact, by extending a recent result of Vahlis, we show adaptivity is strictly weaker than the latter notions (in a black-box sense). As a consequence, adaptivity is the weakest security property of trapdoor functions known to imply black-box chosen-ciphertext security. Additionally, by slightly extending our framework and considering ``tag-based' adaptive trapdoor functions, we obtain exactly the chosen-ciphertext secure encryption schemes proposed in prior work, thereby unifying them, although the schemes we obtain via adaptive trapdoor functions are actually more efficient. Finally, we show that adaptive trapdoor functions can be realized from a (non-standard) computational assumption on RSA inversion, leading to a very efficient RSA-based chosen-ciphertext secure encryption scheme in the standard model.

A proposta apresentada nesta dissertaÃÃo representa uma expansÃo do conceito original de assinatura em anel. Um esquema de assinatura em anel permite que um membro de um grupo divulgue uma mensagem anonimamente, de tal forma que cada um dos membros do grupo seja considerado o possÃvel autor da mensagem. A ideia principal de uma assinatura em anel à garantir o anonimato do assinante e ainda garantir a autenticidade da informaÃÃo, mostrando que a mensagem partiu de um dos membros do referido grupo. Esta dissertaÃÃo apresenta um esquema de assinatura em anel baseado no esquema de Rivest et al. (2001), em que o assinante pode, mais tarde, revogar seu anonimato apresentando valores secretos que provam que somente ele seria capaz de gerar tal assinatura. Esta propriedade serà chamada aqui de resgate de autoria. A principal diferenÃa em relaÃÃo ao trabalho de Rivest et al. (2001) à apresentada antes mesmo de comeÃar a geraÃÃo da assinatura. Os valores utilizados como entrada para a funÃÃo trapdoor serÃo cÃdigos de autenticaÃÃo de mensagem - MACs gerados pelo algoritmo HMAC, um algoritmo de autenticaÃÃo de mensagem baseado em funÃÃo hash resistente à colisÃo. Essa modificaÃÃo simples permitirà que, no futuro, o assinante revele-se como o verdadeiro autor da mensagem apresentando os valores secretos que geraram os MACs. / The proposal presented in this thesis represents an expansion of the original concept of ring signature. A ring signature scheme allows a member of a group to publish a message anonymously, so that each member of the group can be considered the author of the message. The main idea of a ring signature is to guarantee the anonymity of the subscriber also ensure the authenticity of information, showing that the message came from one of the members of that group. This thesis presents a signature scheme based on (RIVEST et al., 2001), where the subscriber can later revoke anonymity presenting secret values that prove that he would only be able to generate such a signature. This property will be referred to here as rescue of authorship. The main difference to the proposal of Rivest et al. (2001) is presented before we even begin signature generation. The values used as input to the trapdoor function are message authentication codes - MACs generated by the HMAC algorithm, an algorithm for message authentication based on hash function collision resistant. This simple modification will allow, in the future, the subscriber to reveal itself as the true author of the message by showing the secret values to generate those MACs.