The Experts below are selected from a list of 5067 Experts worldwide ranked by ideXlab platform
Ugo Montanari - One of the best experts on this subject based on the ideXlab platform.
-
CONCUR - A First Order Coalgebraic Model of pi-Calculus Early Observational Equivalence
CONCUR 2002 — Concurrency Theory, 2002Co-Authors: Maria Grazia Buscemi, Ugo MontanariAbstract:In this paper, we propose a compositional coalgebraic semantics of the ?-calculus based on a novel approach for lifting calculi with structural axioms to coalgebraic models. We equip the transition system of the calculus with permutations, parallel composition and restriction operations, thus obtaining a bialgebra. No prefix operation is introduced, relying instead on a clause format defining the transitions of recursively defined processes. The unique morphism to the final bialgebra induces a bisimilarity relation which coincides with Observational Equivalence and which is a congruence with respect to the operations. The permutation algebra is enriched with a name extrusion operator ? a la De Brujin, that shifts any name to the successor and generates a new name in the first variable x0. As a consequence, in the axioms and in the SOS rules there is no need to refer to the support, i.e., the set of significant names, and, thus, the model turns out to be first order.
-
a first order coalgebraic model of pi calculus early Observational Equivalence
International Conference on Concurrency Theory, 2002Co-Authors: Maria Grazia Buscemi, Ugo MontanariAbstract:In this paper, we propose a compositional coalgebraic semantics of the ?-calculus based on a novel approach for lifting calculi with structural axioms to coalgebraic models. We equip the transition system of the calculus with permutations, parallel composition and restriction operations, thus obtaining a bialgebra. No prefix operation is introduced, relying instead on a clause format defining the transitions of recursively defined processes. The unique morphism to the final bialgebra induces a bisimilarity relation which coincides with Observational Equivalence and which is a congruence with respect to the operations. The permutation algebra is enriched with a name extrusion operator ? a la De Brujin, that shifts any name to the successor and generates a new name in the first variable x0. As a consequence, in the axioms and in the SOS rules there is no need to refer to the support, i.e., the set of significant names, and, thus, the model turns out to be first order.
-
Pi-Calculus Early Observational Equivalence: A First Order Coalgebraic Model
2002Co-Authors: Maria Grazia Buscemi, Ugo MontanariAbstract:In this paper, we propose a compositional coalgebraic semantics of the pi-calculus based on a novel approach for lifting calculi with structural axioms to coalgebraic models. We equip the transition system of the calculus with permutations, parallel composition and restriction operations, thus obtaining a bialgebra. No prefix operation is introduced, relying instead on a clause format defining the transitions of recursively defined processes. The unique morphism to the final bialgebra induces a bisimilarity relation which coincides with Observational Equivalence and which is a congruence with respect to the operations. The permutation algebra is enriched with a name extrusion operator delta a' la De Brujin, that shifts any name to the successor and generates a new name in the first variable. As a consequence, in the axioms and in the SOS rules there is no need to refer to the support, i.e., the set of significant names, and, thus, the model turns out to be first order.
-
A first order coalgebraic model of π-calculus early Observational Equivalence
Lecture Notes in Computer Science, 2002Co-Authors: Maria Grazia Buscemi, Ugo MontanariAbstract:In this paper, we propose a compositional coalgebraic semantics of the π-calculus based on a novel approach for lifting calculi with structural axioms to coalgebraic models. We equip the transition system of the calculus with permutations, parallel composition and restriction operations, thus obtaining a bialgebra. No prefix operation is introduced, relying instead on a clause format defining the transitions of recursively defined processes. The unique morphism to the final bialgebra induces a bisimilarity relation which coincides with Observational Equivalence and which is a congruence with respect to the operations. The permutation algebra is enriched with a name extrusion operator 6 a la De Brujin, that shifts any name to the successor and generates a new name in the first variable x 0 . As a consequence, in the axioms and in the SOS rules there is no need to refer to the support, i.e., the set of significant names, and, thus, the model turns out to be first order.
-
Observational Equivalence for synchronized graph rewriting with mobility
International Symposium on Theoretical Aspects of Computer Software, 2001Co-Authors: Barbara Konig, Ugo MontanariAbstract:We introduce a notion of bisimulation for graph rewriting systems, allowing us to prove Observational Equivalence for dynamically evolving graphs and networks.We use the framework of synchronized graph rewriting with mobility which we describe in two different, but operationally equivalent ways: on graphs defined as syntactic judgements and by using tile logic. One of the main results of the paper says that bisimilarity for synchronized graph rewriting is a congruence whenever the rewriting rules satisfy the basic source property. Furthermore we introduce an up-to technique simplifying bisimilarity proofs and use it in an example to show the Equivalence of a communication network and its specification.
Barbara Konig - One of the best experts on this subject based on the ideXlab platform.
-
Observational Equivalence for synchronized graph rewriting with mobility
International Symposium on Theoretical Aspects of Computer Software, 2001Co-Authors: Barbara Konig, Ugo MontanariAbstract:We introduce a notion of bisimulation for graph rewriting systems, allowing us to prove Observational Equivalence for dynamically evolving graphs and networks.We use the framework of synchronized graph rewriting with mobility which we describe in two different, but operationally equivalent ways: on graphs defined as syntactic judgements and by using tile logic. One of the main results of the paper says that bisimilarity for synchronized graph rewriting is a congruence whenever the rewriting rules satisfy the basic source property. Furthermore we introduce an up-to technique simplifying bisimilarity proofs and use it in an example to show the Equivalence of a communication network and its specification.
-
TACS - Observational Equivalence for Synchronized Graph Rewriting with Mobility
Lecture Notes in Computer Science, 2001Co-Authors: Barbara Konig, Ugo MontanariAbstract:We introduce a notion of bisimulation for graph rewriting systems, allowing us to prove Observational Equivalence for dynamically evolving graphs and networks.We use the framework of synchronized graph rewriting with mobility which we describe in two different, but operationally equivalent ways: on graphs defined as syntactic judgements and by using tile logic. One of the main results of the paper says that bisimilarity for synchronized graph rewriting is a congruence whenever the rewriting rules satisfy the basic source property. Furthermore we introduce an up-to technique simplifying bisimilarity proofs and use it in an example to show the Equivalence of a communication network and its specification.
Nicolas Oury - One of the best experts on this subject based on the ideXlab platform.
-
TLCA - Observational Equivalence and program extraction in the Coq proof assistant
Lecture Notes in Computer Science, 2003Co-Authors: Nicolas OuryAbstract:The Coq proof assistant allows one to specify and certify programs. Then, code can be extracted from proofs to different programming languages. The goal of this article is to substitute, at extraction time, some complex and fast data structures for the structures used for specification and proof. This is made under two principal constraints: (1) this substitution must be correct: the optimized data structures in the extracted program must have the same properties as the original ones, (2) on the proof side, the structure must keep a computable nature. If the framework described here is general, we focus on the case of functional arrays. This work leads us to formalize the notion of Observational Equivalence in the Coq system. We conclude with benchmarks.
-
Observational Equivalence and program extraction in the Coq proof assistant
Lecture Notes in Computer Science, 2003Co-Authors: Nicolas OuryAbstract:The Coq proof assistant allows one to specify and certify programs. Then, code can be extracted from proofs to different programming languages. The goal of this article is to substitute, at extraction time, some complex and fast data structures for the structures used for specification and proof. This is made under two principal constraints: (1) this substitution must be correct: the optimized data structures in the extracted program must have the same properties as the original ones, (2) on the proof side, the structure must keep a computable nature. If the framework described here is general, we focus on the case of functional arrays. This work leads us to formalize the notion of Observational Equivalence in the Coq system. We conclude with benchmarks.
Ralf Sasse - One of the best experts on this subject based on the ideXlab platform.
-
Automated Symbolic Proofs of Observational Equivalence
2015Co-Authors: David Basin, Jannik Dreier, Ralf SasseAbstract:Many cryptographic security definitions can be naturally formulated as Observational Equivalence properties. However, existing automated tools for verifying the Observational Equivalence of cryptographic protocols are limited: they do not handle protocols with mutable state and an unbounded number of sessions. We propose a novel definition of Observational Equivalence for multiset rewriting systems. We then extend the Tamarin prover, based on multiset rewriting, to prove the Observational Equivalence of protocols with mutable state, an unbounded number of sessions, and equational theories such as Diffie-Hellman exponentiation. We demonstrate its effectiveness on case studies, including a stateful TPM protocol.
-
ACM Conference on Computer and Communications Security - Automated Symbolic Proofs of Observational Equivalence
Proceedings of the 22nd ACM SIGSAC Conference on Computer and Communications Security, 2015Co-Authors: David Basin, Jannik Dreier, Ralf SasseAbstract:Many cryptographic security definitions can be naturally formulated as Observational Equivalence properties. However, existing automated tools for verifying the Observational Equivalence of cryptographic protocols are limited: they do not handle protocols with mutable state and an unbounded number of sessions. We propose a novel definition of Observational Equivalence for multiset rewriting systems. We then extend the Tamarin prover, based on multiset rewriting, to prove the Observational Equivalence of protocols with mutable state, an unbounded number of sessions, and equational theories such as Diffie-Hellman exponentiation. We demonstrate its effectiveness on case studies, including a stateful TPM protocol.
Véronique Cortier - One of the best experts on this subject based on the ideXlab platform.
-
Deciding Equivalence-based properties using constraint solving
Theoretical Computer Science, 2013Co-Authors: Vincent Cheval, Véronique Cortier, Stéphanie DelauneAbstract:Formal methods have proved their usefulness for analyzing the security of protocols. Most existing results focus on trace properties like secrecy or authentication. There are however several security properties, which cannot be defined (or cannot be naturally defined) as trace properties and require a notion of behavioral Equivalence. Typical examples are anonymity, privacy related properties or statements closer to security properties used in cryptography. In this paper, we consider three notions of Equivalence defined in the applied pi calculus: Observational Equivalence, may-testing Equivalence, and trace Equivalence. First, we study the relationship between these three notions. We show that for determinate processes, Observational Equivalence actually coincides with trace Equivalence, a notion simpler to reason with. We exhibit a large class of determinate processes, called simple processes, that capture most existing protocols and cryptographic primitives. While trace Equivalence and may-testing Equivalence seem very similar, we show that may-testing Equivalence is actually strictly stronger than trace Equivalence. We prove that the two notions coincide for image-finite processes, such as processes without replication. Second, we reduce the decidability of trace Equivalence (for finite processes) to deciding symbolic Equivalence between sets of constraint systems. For simple processes without replication and with trivial else branches, it turns out that it is actually sufficient to decide symbolic Equivalence between pairs of positive constraint systems. Thanks to this reduction and relying on a result first proved by M. Baudet, this yields the first decidability result of Observational Equivalence for a general class of equational theories (for processes without else branch nor replication). Moreover, based on another decidability result for deciding Equivalence between sets of constraint systems, we get decidability of trace Equivalence for processes with else branch for standard primitives.
-
A method for proving Observational Equivalence
2009Co-Authors: Véronique Cortier, Stéphanie DelauneAbstract:Formal methods have proved their usefulness for analyzing the security of protocols. Most existing results focus on trace properties like secrecy (expressed as a reachability property) or authentication. There are however several security properties, which cannot be defined (or cannot be naturally defined) as trace properties and require the notion of Observational Equivalence. Typical examples are anonymity, privacy related properties or statements closer to security properties used in cryptography. In this paper, we consider the applied pi calculus and we show that for determinate processes, Observational Equivalence actually coincides with trace Equivalence, a notion simpler to reason with. We exhibit a large class of determinate processes, called simple processes, that capture most existing protocols and cryptographic primitives. Then, for simple processes without replication nor else branch, we reduce the decidability of trace Equivalence to deciding an Equivalence relation introduced by M. Baudet. Altogether, this yields the first decidability result of Observational Equivalence for a general class of equational theories.
-
CSF - A Method for Proving Observational Equivalence
2009 22nd IEEE Computer Security Foundations Symposium, 2009Co-Authors: Véronique Cortier, Stéphanie DelauneAbstract:Formal methods have proved their usefulness for analyzing the security of protocols. Most existing results focus on trace properties like secrecy (expressed as a reachability property) or authentication. There are however several security properties, which cannot be defined (or cannot be naturally defined) as trace properties and require the notion of Observational Equivalence. Typical examples are anonymity, privacy related properties or statements closer to security properties used in cryptography.In this paper, we consider the applied pi calculus and we show that for determinate processes, Observational Equivalence actually coincides with trace Equivalence, a notion simpler to reason with.We exhibit a large class of determinate processes, called simple processes, that capture most existing protocols and cryptographic primitives. Then, for simple processes without replication nor else branch,we reduce the decidability of trace Equivalence to deciding an Equivalence relation introduced by M. Baudet. Altogether, this yields the first decidability result of Observational Equivalence for a general class of equational theories.
-
computational soundness of Observational Equivalence
Computer and Communications Security, 2008Co-Authors: Hubert Comonlundh, Véronique CortierAbstract:Many security properties are naturally expressed as indistinguishability between two versions of a protocol. In this paper, we show that computational proofs of indistinguishability can be considerably simplified, for a class of processes that covers most existing protocols. More precisely, we show a soundness theorem, following the line of research launched by Abadi and Rogaway in 2000: computational indistinguishability in presence of an active attacker is implied by the Observational Equivalence of the corresponding symbolic processes. We prove our result for symmetric encryption, but the same techniques can be applied to other security primitives such as signatures and public-key encryption. The proof requires the introduction of new concepts, which are general and can be reused in other settings.
-
Computational soundness of Observational Equivalence
2008Co-Authors: Hubert Comon-lundh, Véronique CortierAbstract:Many security properties are naturally expressed as indistinguishability between two versions of a protocol. In this paper, we show that computational proofs of indistinguishability can be considerably simplified, for a class of processes that covers most existing protocols. More precisely, we show a soundness theorem, following the line of research launched by Abadi and Rogaway in 2000: computational indistinguishability in presence of an active attacker is implied by the Observational Equivalence of the corresponding symbolic processes. Up to our knowledge, the only result of this kind is Adao and Fournet, in which, however, cryptographic primitives are not part of the syntax. Otherwise, previous works either considered a passive attacker, or, in case of active attackers, proved a soundness result for properties that can be defined on execution traces of the protocol. Anonymity for instance does not fall in the latter category. We prove our result for symmetric encryption, but the same techniques can be applied to other security primitives such as signatures and public-key encryption. The proof requires the introduction of new concepts, which are general and can be reused in other settings.
