A new cryptanalytic application is proposed for a number theoretic tool Weil sum to the birthday attack against multivariate quadratic trapdoor function. This new customization of the birthday attack is developed by evaluating the explicit Weil sum of the underlying univariate polynomial and the exact number of solutions of the associated bivariate equation. I designed and implemented new algorithms for computing Weil sum values so that I could explicitly identify some class of weak Dembowski- Ostrom polynomials and the equivalent forms in the multivariate quadratic trapdoor function. This customized attack, also regarded as an equation solving algorithm for the system of some special quadratic equations over finite fields, is fundamentally different from the Grobner basis methods. The theoretical observations and experiments show that the required computational complexity of the attack on these weak polynomial instances can be asymptotically less than the square root complexity of the common birthday attack by a factor as large as 2^(n/8) in terms of the extension degree n of F2n. I also suggest a few open problems that any MQ-based short signature scheme must explicitly take into account for the basic design principles.

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.

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.

In large-scale distributed systems, where adversarial attacks can have widespread impact, authentication provides protection from threats involving impersonation of entities and tampering of data. Practical solutions to authentication problems in distributed systems must meet specific constraints of the target system, and provide a reasonable balance between security and cost. The goal of this dissertation is to address the problem of building practical and efficient authentication mechanisms to secure distributed applications. This dissertation presents techniques to construct efficient digital signature schemes using trapdoor hash functions for various distributed applications. Trapdoor hash functions are collision-resistant hash functions associated with a secret trapdoor key that allows the key-holder to find collisions between hashes of different messages. The main contributions of this dissertation are as follows: 1. A common problem with conventional trapdoor hash functions is that revealing a collision producing message pair allows an entity to compute additional collisions without knowledge of the trapdoor key. To overcome this problem, we design an efficient trapdoor hash function that prevents all entities except the trapdoor key-holder from computing collisions regardless of whether collision producing message pairs are revealed by the key-holder. 2. We design a technique to construct efficient proxy signatures using trapdoor hash functions to authenticate and authorize agents acting on behalf of users in agent-based computing systems. Our technique provides agent authentication, assurance of agreement between delegator and agent, security without relying on secure communication channels and control over an agent’s capabilities. 3. We develop a trapdoor hash-based signature amortization technique for authenticating real-time, delay-sensitive streams. Our technique provides independent verifiability of blocks comprising a stream, minimizes sender-side and receiver-side delays, minimizes communication overhead, and avoids transmission of redundant information. 4. We demonstrate the practical efficacy of our trapdoor hash-based techniques for signature amortization and proxy signature construction by presenting discrete log-based instantiations of the generic techniques that are efficient to compute, and produce short signatures. Our detailed performance analyses demonstrate that the proposed schemes outperform existing schemes in computation cost and signature size. We also present proofs for security of the proposed discrete-log based instantiations against forgery attacks under the discrete-log assumption.

Der Beitrag befasst sich mit der Anwendbarkeit von zerstörungsfreien Verfahren zur Bestimmung von Bodenparametern im Zuge der Qualitätssicherung, sowie der Überwachung von risikoreichen Untergrundsituationen. Durch eine oberflächenseimische Untersuchung können künstlich hergestellte Verdichtungskontraste in Sand abgebildet werden. Dabei zeigt sich eine Vergleichbarkeit der Ergebnisse mit Eindringwiderständen von Sondierungen. Im Anschluss wird ein Erdfallversuch zum Verständnis unterirdischer Bruchmechanismen behandelt. Dabei werden Einflussparameter aufgezeigt, welche eine Bodengewölbebildung begünstigen und somit einen Verbruch verhindern. Abschließend folgen Schlussfolgerungen bezüglich der autarken Überwachung von Erdfallphänomenen.

Este trabalho apresenta um estudo experimental sobre o comportamento de dutos enterrados sofrendo perda de apoio ou elevação em uma determinada região ao longo do comprimento. Foram realizados ensaios com modelos físicos compostos por um maciço de areia pura contendo um tubo repousando sobre um alçapão localizado no centro do vão. A pesquisa envolveu dois programas experimentais distintos. O primeiro foi desenvolvido na Escola de Engenharia de São Carlos/USP e contou com o desenvolvimento e a construção de um equipamento de ensaios possuindo um sistema de alçapão. Os modelos eram dotados de instrumental capaz de medir as deflexões e as deformações específicas ao longo do duto, além das tensões totais no maciço de solo circundante e na base do equipamento. O segundo programa experimental foi conduzido na Universidade do Colorado em Boulder, EUA, e envolveu ensaios em centrífuga. Essa fase da pesquisa teve por finalidade realizar uma investigação visual dos mecanismos de ruptura do sistema composto pelo solo e pelo duto sujeito à perda de apoio. Ambas as etapas do trabalho contaram com a execução de testes com modelos sem tubo. Os ensaios realizados revelaram aspectos importantes do problema investigado. A movimentação ativa ou passiva do alçapão exerceu uma forte influência na redistribuição das tensões no maciço de solo exterior à estrutura, a qual abrangeu distâncias horizontais superiores a 5 B e verticais superiores a 4 B. Após a perda de apoio ou a elevação, o topo, a base e as demais partes do conduto assumiram perfis de deflexão distintos ao longo do comprimento, os quais foram consideravelmente influenciados pela densidade relativa do solo e pela sobrecarga aplicada. A movimentação ativa do alçapão revelou ainda padrões de ruptura incluindo localizações de deformação propagando-se para a região do maciço de solo fora do alçapão / This thesis presents an experimental study on the behavior of buried pipes undergoing a loss of support or elevation in a localized region along its length. Tests with physical models comprising a pure dry sand and a tube resting on a rigid trapdoor base located at the center of its length were performed. The research included two distinct testing programs. The first testing program was carried out at the School of Engineering of Sao Carlos/USP, and included the construction of a laboratory facility containing a trapdoor system. The models were equipped with devices for measuring deflections and strains in the pipe, and total stresses in the soil mass and in the lower boundary of the model. The second phase of this investigation was conducted at the University of Colorado at Boulder, USA, and involved centrifuge testing. The main goal of this part of the research was to assess the failure mechanisms that take place when the pipe experiences loss of support. Models without the pipe were also tested in both phases. Important aspects of the soil-structure interaction were verified with the testing programs carried out in this study. A strong influence on the stress redistribution within the soil mass in the vicinity of the structure was achieved after the active or passive conditions were established, encompassing horizontal distances greater than 5 B and vertical distances greater than 4 B. The crown, the base, and the other parts of the pipe assumed distinct deflection profiles after the loss of support or elevation, which were strongly influenced by the relative density of the surrounding soil and by the surficial applied surcharge. The imposed downward boundary movement included the formation of shear bands initiating at the edge of the void and propagating towards the soil mass in the vicinity of the trapdoor

Este trabalho apresenta um estudo experimental sobre o comportamento de dutos enterrados sofrendo perda de apoio ou elevação em uma determinada região ao longo do comprimento. Foram realizados ensaios com modelos físicos compostos por um maciço de areia pura contendo um tubo repousando sobre um alçapão localizado no centro do vão. A pesquisa envolveu dois programas experimentais distintos. O primeiro foi desenvolvido na Escola de Engenharia de São Carlos/USP e contou com o desenvolvimento e a construção de um equipamento de ensaios possuindo um sistema de alçapão. Os modelos eram dotados de instrumental capaz de medir as deflexões e as deformações específicas ao longo do duto, além das tensões totais no maciço de solo circundante e na base do equipamento. O segundo programa experimental foi conduzido na Universidade do Colorado em Boulder, EUA, e envolveu ensaios em centrífuga. Essa fase da pesquisa teve por finalidade realizar uma investigação visual dos mecanismos de ruptura do sistema composto pelo solo e pelo duto sujeito à perda de apoio. Ambas as etapas do trabalho contaram com a execução de testes com modelos sem tubo. Os ensaios realizados revelaram aspectos importantes do problema investigado. A movimentação ativa ou passiva do alçapão exerceu uma forte influência na redistribuição das tensões no maciço de solo exterior à estrutura, a qual abrangeu distâncias horizontais superiores a 5 B e verticais superiores a 4 B. Após a perda de apoio ou a elevação, o topo, a base e as demais partes do conduto assumiram perfis de deflexão distintos ao longo do comprimento, os quais foram consideravelmente influenciados pela densidade relativa do solo e pela sobrecarga aplicada. A movimentação ativa do alçapão revelou ainda padrões de ruptura incluindo localizações de deformação propagando-se para a região do maciço de solo fora do alçapão / This thesis presents an experimental study on the behavior of buried pipes undergoing a loss of support or elevation in a localized region along its length. Tests with physical models comprising a pure dry sand and a tube resting on a rigid trapdoor base located at the center of its length were performed. The research included two distinct testing programs. The first testing program was carried out at the School of Engineering of Sao Carlos/USP, and included the construction of a laboratory facility containing a trapdoor system. The models were equipped with devices for measuring deflections and strains in the pipe, and total stresses in the soil mass and in the lower boundary of the model. The second phase of this investigation was conducted at the University of Colorado at Boulder, USA, and involved centrifuge testing. The main goal of this part of the research was to assess the failure mechanisms that take place when the pipe experiences loss of support. Models without the pipe were also tested in both phases. Important aspects of the soil-structure interaction were verified with the testing programs carried out in this study. A strong influence on the stress redistribution within the soil mass in the vicinity of the structure was achieved after the active or passive conditions were established, encompassing horizontal distances greater than 5 B and vertical distances greater than 4 B. The crown, the base, and the other parts of the pipe assumed distinct deflection profiles after the loss of support or elevation, which were strongly influenced by the relative density of the surrounding soil and by the surficial applied surcharge. The imposed downward boundary movement included the formation of shear bands initiating at the edge of the void and propagating towards the soil mass in the vicinity of the trapdoor

Yes / Arching in soils has received great attention due to its significance on the soil–underground structure interaction. The state of stress on underground structures as a result of cycles of active and passive arching was neither explored nor systematically assessed. In the present study, comprehensive investigation was carried out to examine: i. the effects of displacement direction to induce active or passive arching, ii. the behaviour of subsequent arching, iii. the effect of magnitude of initial displacement on the formation of arching and iv. the influence of soil height on sequential active and passive arching. The results showed that alternating the displacement of the underground inclusion exacerbated the formation of active and passive arching leading to a substantial reduction in shear resistance and stress redistribution. It is noted that sequentially alternating displacement of the underground inclusion was detrimental to the formation of full active and passive arches irrespective of the burial height.

To the field of cryptography, quantum mechanics is a game changer. The exploitation of quantum mechanical properties through the manipulation of quantum information, the information encoded in the state of quantum systems, would allow many protocols in use today to be broken as well as lead to the expansion of cryptography to new protocols. In this thesis, quantum encryption, i.e. encryption schemes for quantum data, is defined, along with several definitions of security, broadly divisible into semantic security and ciphertext indistinguishability, which are proven equivalent, in analogy to the foundational result by Goldwasser and Micali. Private- and public-key quantum encryption schemes are also constructed from quantum-secure cryptographic primitives, and their security is proven. Most of the results are in the joint paper Computational Security of Quantum Encryption, to appear in the 9th International Conference on Information Theoretic Security (ICITS2016).