The Experts below are selected from a list of 327 Experts worldwide ranked by ideXlab platform
Martha Sideri - One of the best experts on this subject based on the ideXlab platform.
-
Designing secure communication protocols from trust specifications
Algorithmica, 1994Co-Authors: Christos H. Papadimitriou, P. Venkat Rangan, Martha SideriAbstract:In a very large distributed system, entities may trust and mistrust others with respect to communication security in arbitrarily complex ways. We formulate the problem of designing a secure communication protocol, given a network interconnection and a Ternary Relation which captures trust between the entities. We didentify several important ways of synthesizing secure channels, and study the algorithmic problem of designing a secure communication protocol connecting the entities, given the connectivity of the network and the trust Relationship between the nodes. We show that whether secure communication is possible can be decided easily in polynomial time. If we also require that channel synthesis proceed along unambiguous paths (in which case the protocol is defined on a spanning tree of the network), we show that the design problem is NP-complete, and we give a linear-time algorithm for an interesting special case of the problem.
-
FSTTCS - Designing Secure Communication Protocols from Trust Specifications
Lecture Notes in Computer Science, 1991Co-Authors: Christos H. Papadimitriou, P. Venkat Rangan, Martha SideriAbstract:In a very large distributed system, entities may trust and mistrust others with respect to communication security in arbitrarily complex ways. We formulate the problem of designing a secure communication protocol, given a network interconnection and a Ternary Relation which captures trust between the entities. We identify several important ways of synthesizing secure channels, and study the algorithmic problem of designing a secure communication protocol connecting the entities, given the connectivity of the network and the trust Relationship between the nodes. We show that whether secure communication is possible can be decided easily in polynomial time. If we also require that channel synthesis proceed along unambiguous paths (in which case the protocol is defined on a spanning tree of the netowrk), we show that the design problem is NP-complete, and we give a linear-time algorithsibly grm for an interesting special case of the problem.
Christos H. Papadimitriou - One of the best experts on this subject based on the ideXlab platform.
-
Designing secure communication protocols from trust specifications
Algorithmica, 1994Co-Authors: Christos H. Papadimitriou, P. Venkat Rangan, Martha SideriAbstract:In a very large distributed system, entities may trust and mistrust others with respect to communication security in arbitrarily complex ways. We formulate the problem of designing a secure communication protocol, given a network interconnection and a Ternary Relation which captures trust between the entities. We didentify several important ways of synthesizing secure channels, and study the algorithmic problem of designing a secure communication protocol connecting the entities, given the connectivity of the network and the trust Relationship between the nodes. We show that whether secure communication is possible can be decided easily in polynomial time. If we also require that channel synthesis proceed along unambiguous paths (in which case the protocol is defined on a spanning tree of the network), we show that the design problem is NP-complete, and we give a linear-time algorithm for an interesting special case of the problem.
-
FSTTCS - Designing Secure Communication Protocols from Trust Specifications
Lecture Notes in Computer Science, 1991Co-Authors: Christos H. Papadimitriou, P. Venkat Rangan, Martha SideriAbstract:In a very large distributed system, entities may trust and mistrust others with respect to communication security in arbitrarily complex ways. We formulate the problem of designing a secure communication protocol, given a network interconnection and a Ternary Relation which captures trust between the entities. We identify several important ways of synthesizing secure channels, and study the algorithmic problem of designing a secure communication protocol connecting the entities, given the connectivity of the network and the trust Relationship between the nodes. We show that whether secure communication is possible can be decided easily in polynomial time. If we also require that channel synthesis proceed along unambiguous paths (in which case the protocol is defined on a spanning tree of the netowrk), we show that the design problem is NP-complete, and we give a linear-time algorithsibly grm for an interesting special case of the problem.
Andrew Yang - One of the best experts on this subject based on the ideXlab platform.
-
a Ternary knowledge Relation on secrets
Theoretical Aspects of Rationality and Knowledge, 2011Co-Authors: Sara Miner More, Pavel Naumov, Brittany Nicholls, Andrew YangAbstract:The paper introduces and studies the Ternary Relation "secret a reveals at least as much information about secret c as secret b." In spite of its seeming simplicity, this Relation has many non-trivial properties. The main result is a complete infinite axiomatization of the propositional theory of this Relation.
-
TARK - A Ternary knowledge Relation on secrets
Proceedings of hte 13th Conference on Theoretical Aspects of Rationality and Knowledge - TARK XIII, 2011Co-Authors: Sara Miner More, Pavel Naumov, Brittany Nicholls, Andrew YangAbstract:The paper introduces and studies the Ternary Relation "secret a reveals at least as much information about secret c as secret b." In spite of its seeming simplicity, this Relation has many non-trivial properties. The main result is a complete infinite axiomatization of the propositional theory of this Relation.
P. Venkat Rangan - One of the best experts on this subject based on the ideXlab platform.
-
Designing secure communication protocols from trust specifications
Algorithmica, 1994Co-Authors: Christos H. Papadimitriou, P. Venkat Rangan, Martha SideriAbstract:In a very large distributed system, entities may trust and mistrust others with respect to communication security in arbitrarily complex ways. We formulate the problem of designing a secure communication protocol, given a network interconnection and a Ternary Relation which captures trust between the entities. We didentify several important ways of synthesizing secure channels, and study the algorithmic problem of designing a secure communication protocol connecting the entities, given the connectivity of the network and the trust Relationship between the nodes. We show that whether secure communication is possible can be decided easily in polynomial time. If we also require that channel synthesis proceed along unambiguous paths (in which case the protocol is defined on a spanning tree of the network), we show that the design problem is NP-complete, and we give a linear-time algorithm for an interesting special case of the problem.
-
FSTTCS - Designing Secure Communication Protocols from Trust Specifications
Lecture Notes in Computer Science, 1991Co-Authors: Christos H. Papadimitriou, P. Venkat Rangan, Martha SideriAbstract:In a very large distributed system, entities may trust and mistrust others with respect to communication security in arbitrarily complex ways. We formulate the problem of designing a secure communication protocol, given a network interconnection and a Ternary Relation which captures trust between the entities. We identify several important ways of synthesizing secure channels, and study the algorithmic problem of designing a secure communication protocol connecting the entities, given the connectivity of the network and the trust Relationship between the nodes. We show that whether secure communication is possible can be decided easily in polynomial time. If we also require that channel synthesis proceed along unambiguous paths (in which case the protocol is defined on a spanning tree of the netowrk), we show that the design problem is NP-complete, and we give a linear-time algorithsibly grm for an interesting special case of the problem.
Ladislav Nebeský - One of the best experts on this subject based on the ideXlab platform.
-
The Directed Geodetic Structure of a Strong Digraph
Czechoslovak Mathematical Journal, 2004Co-Authors: Ladislav NebeskýAbstract:By a Ternary structure we mean an ordered pair ( U _0, T _0), where U _0is a finite nonempty set and T _0is a Ternary Relation on U _0. A Ternary structure ( U _0, T _0) is called here a directed geodetic structure if there exists a strong digraph D with the properties that V ( D ) = U _0and T _0 (u,v, w) if and only if d _ D (u,v) + d _ D (v,w) = d _ D (u, w) for all u , v , w ∈ U _0, where d _Ddenotes the (directed) distance function in D . It is proved in this paper that there exists no sentence s of the language of the first-order logic such that a Ternary structure is a directed geodetic structure if and only if it satisfies s .
-
Signpost Systems and Their Underlying Graphs
Electronic Notes in Discrete Mathematics, 2003Co-Authors: Henry Martyn Mulder, Ladislav NebeskýAbstract:A signpost system is an axiomatization of travelling around using signposts. It is a Ternary Relation on a set satisfying three fairly natural axioms. Its underlying graph is introduced. Basic properties and examples are presented. More advanced results involve additional axioms that impose more structure on the signpost system and its underlying graph.
-
Modular and median signpost systems and their underlying graphs
Discussiones Mathematicae Graph Theory, 2003Co-Authors: Henry Martyn Mulder, Ladislav NebeskýAbstract:The concept of a signpost system on a set is introduced. It is a Ternary Relation on the set satisfying three fairly natural axioms. Its underlying graph is introduced. When the underlying graph is disconnected some unexpected things may happen. The main focus are signpost systems satisfying some extra axioms. Their underlying graphs have lots of structure: the components are modular graphs or median graphs. Yet another axiom guarantees that the underlying graph is also connected. The main results of this paper concern if-and-only-if characterizations involving signpost systems satisfying additional axioms on the one hand and modular, respectively median graphs on the other hand.