Histoire des oracles,

Based on A. van Dale's De oraculis ethnicorum dissertationes duae.

Tool support for generating passive C++ test oracles from object-z specifications

A test oracle provides a means for determining whether an implementation behaves according to its specification. A passive test oracle checks that the correct behaviour has been implemented, but does not implement the behaviour itself. In previous work, we have presented a method that allows us to derive passive C++ test oracles from formal specifications written in Object-Z. We describe the "Warlock" prototype tool that supports the method. Warlock is built on top of an existing Object-Z type checker and generates oracle code for a substantial subset of the Object-Z language. We describe the architecture of Warlock and its application to a number of Object-Z specifications. We also discuss its current limitations.

Modeling key compromise impersonation attacks on group key exchange protocols

A key exchange protocol allows a set of parties to agree upon a secret session key over a public network. Two-party key exchange (2PKE) protocols have been rigorously analyzed under various models considering different adversarial actions. However, the analysis of group key exchange (GKE) protocols has not been as extensive as that of 2PKE protocols. Particularly, the security attribute of key compromise impersonation (KCI) resilience has so far been ignored for the case of GKE protocols. We first model the security of GKE protocols addressing KCI attacks by both outsider and insider adversaries. We then show that a few existing protocols are not secure even against outsider KCI attacks. The attacks on these protocols demonstrate the necessity of considering KCI resilience for GKE protocols. Finally, we give a new proof of security for an existing GKE protocol under the revised model assuming random oracles.

Design and analysis of group key exchange protocols

A group key exchange (GKE) protocol allows a set of parties to agree upon a common secret session key over a public network. In this thesis, we focus on designing efficient GKE protocols using public key techniques and appropriately revising security models for GKE protocols. For the purpose of modelling and analysing the security of GKE protocols we apply the widely accepted computational complexity approach. The contributions of the thesis to the area of GKE protocols are manifold. We propose the first GKE protocol that requires only one round of communication and is proven secure in the standard model. Our protocol is generically constructed from a key encapsulation mechanism (KEM). We also suggest an efficient KEM from the literature, which satisfies the underlying security notion, to instantiate the generic protocol. We then concentrate on enhancing the security of one-round GKE protocols. A new model of security for forward secure GKE protocols is introduced and a generic one-round GKE protocol with forward security is then presented. The security of this protocol is also proven in the standard model. We also propose an efficient forward secure encryption scheme that can be used to instantiate the generic GKE protocol. Our next contributions are to the security models of GKE protocols. We observe that the analysis of GKE protocols has not been as extensive as that of two-party key exchange protocols. Particularly, the security attribute of key compromise impersonation (KCI) resilience has so far been ignored for GKE protocols. We model the security of GKE protocols addressing KCI attacks by both outsider and insider adversaries. We then show that a few existing protocols are not secure against KCI attacks. A new proof of security for an existing GKE protocol is given under the revised model assuming random oracles. Subsequently, we treat the security of GKE protocols in the universal composability (UC) framework. We present a new UC ideal functionality for GKE protocols capturing the security attribute of contributiveness. An existing protocol with minor revisions is then shown to realize our functionality in the random oracle model. Finally, we explore the possibility of constructing GKE protocols in the attribute-based setting. We introduce the concept of attribute-based group key exchange (AB-GKE). A security model for AB-GKE and a one-round AB-GKE protocol satisfying our security notion are presented. The protocol is generically constructed from a new cryptographic primitive called encapsulation policy attribute-based KEM (EP-AB-KEM), which we introduce in this thesis. We also present a new EP-AB-KEM with a proof of security assuming generic groups and random oracles. The EP-AB-KEM can be used to instantiate our generic AB-GKE protocol.

Automated proof for formal indistinguishability and its applications

Bana et al. proposed the relation formal indistinguishability (FIR), i.e. an equivalence between two terms built from an abstract algebra. Later Ene et al. extended it to cover active adversaries and random oracles. This notion enables a framework to verify computational indistinguishability while still offering the simplicity and formality of symbolic methods. We are in the process of making an automated tool for checking FIR between two terms. First, we extend the work by Ene et al. further, by covering ordered sorts and simplifying the way to cope with random oracles. Second, we investigate the possibility of combining algebras together, since it makes the tool scalable and able to cover a wide class of cryptographic schemes. Specially, we show that the combined algebra is still computationally sound, as long as each algebra is sound. Third, we design some proving strategies and implement the tool. Basically, the strategies allow us to find a sequence of intermediate terms, which are formally indistinguishable, between two given terms. FIR between the two given terms is then guaranteed by the transitivity of FIR. Finally, we show applications of the work, e.g. on key exchanges and encryption schemes. In the future, the tool should be extended easily to cover many schemes. This work continues previous research of ours on use of compilers to aid in automated proofs for key exchange.

Modeling key compromise impersonation attacks on group key exchange protocols

Two-party key exchange (2PKE) protocols have been rigorously analyzed under various models considering different adversarial actions. However, the analysis of group key exchange (GKE) protocols has not been as extensive as that of 2PKE protocols. Particularly, an important security attribute called key compromise impersonation (KCI) resilience has been completely ignored for the case of GKE protocols. Informally, a protocol is said to provide KCI resilience if the compromise of the long-term secret key of a protocol participant A does not allow the adversary to impersonate an honest participant B to A. In this paper, we argue that KCI resilience for GKE protocols is at least as important as it is for 2PKE protocols. Our first contribution is revised definitions of security for GKE protocols considering KCI attacks by both outsider and insider adversaries. We also give a new proof of security for an existing two-round GKE protocol under the revised security definitions assuming random oracles. We then show how to achieve insider KCIR in a generic way using a known compiler in the literature. As one may expect, this additional security assurance comes at the cost of an extra round of communication. Finally, we show that a few existing protocols are not secure against outsider KCI attacks. The attacks on these protocols illustrate the necessity of considering KCI resilience for GKE protocols.

Lattice basis delegation in fixed dimension and shorter-ciphertext hierarchical IBE

We present a technique for delegating a short lattice basis that has the advantage of keeping the lattice dimension unchanged upon delegation. Building on this result, we construct two new hierarchical identity-based encryption (HIBE) schemes, with and without random oracles. The resulting systems are very different from earlier lattice-based HIBEs and in some cases result in shorter ciphertexts and private keys. We prove security from classic lattice hardness assumptions.

Parallel authentication and public-key encryption

A parallel authentication and public-key encryption is introduced and exemplified on joint encryption and signing which compares favorably with sequential Encrypt-then-Sign (ɛtS) or Sign-then-Encrypt (Stɛ) schemes as far as both efficiency and security are concerned. A security model for signcryption, and thus joint encryption and signing, has been recently defined which considers possible attacks and security goals. Such a scheme is considered secure if the encryption part guarantees indistinguishability and the signature part prevents existential forgeries, for outsider but also insider adversaries. We propose two schemes of parallel signcryption, which are efficient alternative to Commit-then-Sign-and- Encrypt (Ct&G3&S). They are both provably secure in the random oracle model. The first one, called generic parallel encrypt and sign, is secure if the encryption scheme is semantically secure against chosen-ciphertext attacks and the signature scheme prevents existential forgeries against random-message attacks. The second scheme, called optimal parallel encrypt. and sign, applies random oracles similar to the OAEP technique in order to achieve security using encryption and signature components with very weak security requirements — encryption is expected to be one-way under chosen-plaintext attacks while signature needs to be secure against universal forgeries under random-plaintext attack, that is actually the case for both the plain-RSA encryption and signature under the usual RSA assumption. Both proposals are generic in the sense that any suitable encryption and signature schemes (i.e. which simply achieve required security) can be used. Furthermore they allow both parallel encryption and signing, as well as parallel decryption and verification. Properties of parallel encrypt and sign schemes are considered and a new security standard for parallel signcryption is proposed.

A Closer Look at Multiple Forking: Leveraging (In)Dependence for a Tighter Bound

Boldyreva, Palacio and Warinschi introduced a multiple forking game as an extension of general forking. The notion of (multiple) forking is a useful abstraction from the actual simulation of cryptographic scheme to the adversary in a security reduction, and is achieved through the intermediary of a so-called wrapper algorithm. Multiple forking has turned out to be a useful tool in the security argument of several cryptographic protocols. However, a reduction employing multiple forking incurs a significant degradation of , where denotes the upper bound on the underlying random oracle calls and , the number of forkings. In this work we take a closer look at the reasons for the degradation with a tighter security bound in mind. We nail down the exact set of conditions for success in the multiple forking game. A careful analysis of the cryptographic schemes and corresponding security reduction employing multiple forking leads to the formulation of `dependence' and `independence' conditions pertaining to the output of the wrapper in different rounds. Based on the (in)dependence conditions we propose a general framework of multiple forking and a General Multiple Forking Lemma. Leveraging (in)dependence to the full allows us to improve the degradation factor in the multiple forking game by a factor of . By implication, the cost of a single forking involving two random oracles (augmented forking) matches that involving a single random oracle (elementary forking). Finally, we study the effect of these observations on the concrete security of existing schemes employing multiple forking. We conclude that by careful design of the protocol (and the wrapper in the security reduction) it is possible to harness our observations to the full extent.

“¿No les corresponde conocer el derecho?” : estudio de Miqueas 3, 1-12

Resumen: El autor se propone estudiar desde una perspectiva literaria, crítica y retórica el capítulo 3 del profeta Miqueas. Para esto, en primer término plantea una estructura a partir de los oráculos de condena que el discurso posee. Luego intenta aproximarse al texto desde una perspectiva poético–literaria que intente explicar la fuerza discursiva de las figuras retóricas y del movimiento de la trama del texto. También se integra en el análisis la perspectiva teológica de las expresiones, sobre todo evaluando su alcance a partir de su relación con la tradición veterotestamentaria. Finalmente, se evalúa la intencionalidad del texto a partir de la composición redaccional y de lo que el análisis anterior fue brindando para poder imaginar un camino de actualización del mismo.

Filozofia antyczna wobec problemu interpretacji. Rozwój alegorezy od przedsokratyków do Arystotelesa

The present work examines the beginnings of ancient hermeneutics. More specifically, it discusses the connection between the rise of the practice of allegoresis, on the one hand, and the emergence of the first theory of figurative language, on the other. Thus, this book investigates the specific historical and cultural circumstances that enabled the ancient Greeks not only to discover the possibility of allegorical interpretation, but also to treat figurative language as a philosophical problem. By posing difficulties in understanding the enigmatic sense of various esoteric doctrines, poems, oracles and riddles, figurative language created the context for theoretical reflection on the meaning of these “messages”. Hence, ancient interpreters began to ponder over the nature and functions of figurative (“enigmatic”) language as well as over the techniques of its proper use and interpretation. Although the practice of allegorical interpretation was closely linked to the development of the whole of ancient philosophy, the present work covers only the period from the 6th to the 4th century B.C. It concentrates, then, on the philosophical and cultural consequences of allegoresis in the classical age. The main thesis advocated here has it that the ancient Greeks were in-clined to regard allegory as a cognitive problem rather than merely as a stylistic or a literary one. When searching for the hidden meanings of various esoteric doc-trines, poems, oracles and riddles, ancient interpreters of these “messages” assumed allegory to be the only tool suitable for articulating certain matters. In other words, it was their belief that the use of figurative language resulted from the necessity of expressing things that were otherwise inexpressible. The present work has been organized in the following manner. The first part contains historical and philological discussions that provide the point of departure for more philosophical considerations. This part consists of two introductory chapters. Chapter one situates the practice of allegorical interpretation at the borderline of two different traditions: the rhetorical-grammatical and the hermeneutical. In order to clearly differentiate between the two, chapter one distinguishes between allegory and allegoresis, on the one hand, and allegoresis and exegesis, on the other. While pointing to the conventionality (and even arbitrariness) of such distinctions, the chapter argues, nevertheless, for their heuristic usefulness. The remaining part of chapter one focuses on a historical and philological reconstruction of the most important conceptual tools of ancient hermeneutics. Discussing the semantics of such terms as allēgoría, hypónoia, ainigma and symbolon proves important for at least two crucial reasons. Firstly, it reveals the mutual affinity between allegoresis and divination, i.e., practices that are inherently connected with the need to discover the latent meaning of the “message” in question (whether poem or oracle). Secondly, these philological analyses bring to light the specificity of the ancient understanding of such concepts as allegory or symbol. It goes without saying that antiquity employed these terms in a manner quite disparate from modernity. Chapter one concludes with a discussion of ancient views on the cognitive value of figurative (“enigmatic”) language. Chapter two focuses on the role that allegoresis played in the process of transforming mythos into logos. It is suggested here that it was the practice of allegorical interpretation that made it possible to preserve the traditional myths as an important point of reference for the whole of ancient philosophy. Thus, chapter two argues that the existence of a clear opposition between mythos into logos in Preplatonic philosophy is highly questionable in light of the indisputable fact that the Presocratics, Sophists and Cynics were profoundly convinced about the cognitive value of mythos (this conviction was also shared by Plato and Aristotle, but their attitude towards myth was more complex). Consequently, chapter two argues that in Preplatonic philosophy, myth played a function analogous to the concepts discussed in chapter one (i.e., hidden meanings, enigmas and symbols), for in all these cases, ancient interpreters found tools for conveying issues that were otherwise difficult to convey. Chapter two concludes with a classification of various types of allegoresis. Whilst chapters one and two serve as a historical and philological introduction, the second part of this book concentrates on the close relationship between the development of allegoresis, on the one hand, and the flowering of philosophy, on the other. Thus, chapter three discusses the crucial role that allegorical interpretation came to play in Preplatonic philosophy, chapter four deals with Plato’s highly complex and ambivalent attitude to allegoresis, and chapter five has been devoted to Aristotle’s original approach to the practice of allegorical interpretation. It is evident that allegoresis was of paramount importance for the ancient thinkers, irrespective of whether they would value it positively (Preplatonic philosophers and Aristotle) or negatively (Plato). Beginning with the 6th century B.C., the ancient practice of allegorical interpretation is motivated by two distinct interests. On the one hand, the practice of allegorical interpretation reflects the more or less “conservative” attachment to the authority of the poet (whether Homer, Hesiod or Orpheus). The purpose of this apologetic allegoresis is to exonerate poetry from the charges leveled at it by the first philosophers and, though to a lesser degree, historians. Generally, these allegorists seek to save the traditional paideia that builds on the works of the poets. On the other hand, the practice of allegorical interpretation reflects also the more or less “progressive” desire to make original use of the authority of the poet (whether Homer, Hesiod or Orpheus) so as to promote a given philosophical doctrine. The objective of this instrumental allegoresis is to exculpate philosophy from the accusations brought against it by the more conservative circles. Needless to say, these allegorists significantly contribute to the process of the gradual replacing of the mythical view of the world with its more philosophical explanation. The present book suggests that it is the philosophy of Aristotle that should be regarded as a sort of acme in the development of ancient hermeneutics. The reasons for this are twofold. On the one hand, the Stagirite positively values the practice of allegoresis, rehabilitating, thus, the tradition of Preplatonic philosophy against Plato. And, on the other hand, Aristotle initiates the theoretical reflection on figurative (“enigmatic”) language. Hence, in Aristotle we encounter not only the practice of allegoresis, but also the theory of allegory (although the philosopher does not use the term allēgoría). With the situation being as it is, the significance of Aristotle’s work cannot be overestimated. First of all, the Stagirite introduces the concept of metaphor into the then philosophical considerations. From that moment onwards, the phenomenon of figurative language becomes an important philosophical issue. After Aristo-tle, the preponderance of thinkers would feel obliged to specify the rules for the appropriate use of figurative language and the techniques of its correct interpretation. Furthermore, Aristotle ascribes to metaphor (and to various other “excellent” sayings) the function of increasing and enhancing our knowledge. Thus, according to the Stagirite, figurative language is not only an ornamental device, but it can also have a significant explanatory power. Finally, Aristotle observes that figurative expressions cause words to become ambiguous. In this context, the philosopher notices that ambiguity can enrich the language of a poet, but it can also hinder a dialectical discussion. Accordingly, Aristotle is inclined to value polysemy either positively or negatively. Importantly, however, the Stagirite is perfectly aware of the fact that in natural languages ambiguity is unavoidable. This is why Aristotle initiates a syste-matic reflection on the phenomenon of ambiguity and distinguishes its various kinds. In Aristotle, ambiguity is, then, both a problem that needs to be identified and a tool that can help in elucidating intricate philosophical issues. This unique approach to ambiguity and figurative (“enigmatic”) language enabled Aristotle to formulate invaluable intuitions that still await appropriate recognition.

Cryptographic Tamper Evidence

We propose a new notion of cryptographic tamper evidence. A tamper-evident signature scheme provides an additional procedure Div which detects tampering: given two signatures, Div can determine whether one of them was generated by the forger. Surprisingly, this is possible even after the adversary has inconspicuously learned (exposed) some-or even all-the secrets in the system. In this case, it might be impossible to tell which signature is generated by the legitimate signer and which by the forger. But at least the fact of the tampering will be made evident. We define several variants of tamper-evidence, differing in their power to detect tampering. In all of these, we assume an equally powerful adversary: she adaptively controls all the inputs to the legitimate signer (i.e., all messages to be signed and their timing), and observes all his outputs; she can also adaptively expose all the secrets at arbitrary times. We provide tamper-evident schemes for all the variants and prove their optimality. Achieving the strongest tamper evidence turns out to be provably expensive. However, we define a somewhat weaker, but still practical, variant: α-synchronous tamper-evidence (α-te) and provide α-te schemes with logarithmic cost. Our α-te schemes use a combinatorial construction of α-separating sets, which might be of independent interest. We stress that our mechanisms are purely cryptographic: the tamper-detection algorithm Div is stateless and takes no inputs except the two signatures (in particular, it keeps no logs), we use no infrastructure (or other ways to conceal additional secrets), and we use no hardware properties (except those implied by the standard cryptographic assumptions, such as random number generators). Our constructions are based on arbitrary ordinary signature schemes and do not require random oracles.

Amphilochos : étude sur la légende du héros grec et le sanctuaire oraculaire de Mallos

Le héros grec Amphilochos, descendant mythique de la célèbre famille des hérosprophètes Mélampodides, était, comme son père Amphiaraos, un devin reconnu et un soldat aux aptitudes militaires formidables. Après avoir participé à la seconde expédition contre Thèbes et à la guerre de Troie, celui-ci aurait pérégriné dans bon nombre de contrées en fondant plusieurs cités situées entre l’Espagne et la Syrie. Quelque temps après sa mort brutale en combat singulier contre un autre devin nommé Mopsos, Amphilochos fut élevé au rang de divinité oraculaire à Mallos de Cilicie, une cité dont il avait été lui-même le fondateur. À l’époque romaine, Amphilochos avait acquit, en plus d’un statut ontologique supérieur, une très grande réputation dans cette région où il rendait des oracles à des pèlerins qui venaient eux-mêmes le visiter dans son antre. Cette recherche, qui vise d’une part à étudier de façon exhaustive la légende d’Amphilochos, tente surtout de déterminer, malgré un nombre restreint d’indices, les modalités de la révélation oraculaire dans le sanctuaire de Mallos de Cilicie.