-
PDF
- Split View
-
Views
-
Cite
Cite
Simon Kramer, Rajeev Goré, Eiji Okamoto, Computer-aided decision-making with trust relations and trust domains (cryptographic applications), Journal of Logic and Computation, Volume 24, Issue 1, February 2014, Pages 19–54, https://doi.org/10.1093/logcom/exs013
Close - Share Icon Share
Abstract
We propose generic declarative definitions of individual and collective trust relations between interacting agents and agent collections, and trust domains of trust-related agents in distributed systems. Our definitions yield (1) (in)compatibility, implicational and transitivity results for trust relationships, including a Datalog-implementability result for their logical structure; (2) computational complexity results for deciding potential and actual trust relationships and membership in trust domains; (3) a positive (negative) compositionality result for strong (weak) trust domains; (4) a computational design pattern for building up strong trust domains; and (5) a negative scalability result for trust domains in general. We instantiate our generic trust concepts in five major cryptographic applications of trust, namely: Access Control, Trusted Third Parties, the Web of Trust, Public-Key Infrastructures and Identity-Based Cryptography. We also show that accountability induces trust. Our defining principle for weak and strong trust (domains) is (common) belief in and (common) knowledge of agent correctness, respectively.
*Cf. [41] for an early technical-report, [41a] for the version published in Cryptology ePrint Archive and [40] for a workshop version of this article.
References
[2]. ,
Anderson
R.
Security Engineering: A Guide to Building Dependable Distributed Systems
, 2008
2ndWiley
[3], , , , , . ,
Anderson
R.
Crispo
B.
Lee
J.-H.
Manifavas
C.
Matyas
V.
Petitcolas
F.
The Global Internet Trust Register.
, 1999
The MIT Press
[4], .
Areces
C.
ten Cate
B.
Hybrid Logics
, Handbook of Modal Logic
, 2007
, vol. 3
Elsevier
of Blackburn et al. [9]
[5], , .
Arenas
A.
Wilson
M.
Matthews
B.
On trust management in grids
, Proceedings of the ACM Conference on Autonomic Computing and Communication Systems
, 2007
[6], , , , , .
Bauland
M.
Mundhenk
M.
Schneider
T.
Schnoor
H.
Schnoor
I.
Vollmer
H.
The tractability of model checking for LTL: the good, the bad, and the ugly fragments
, ACM Transactions on Computational Logic
, 2011
, vol. 12
(pg. 1529
-3785
)[7]. ,
Binmore
K.
Game Theory: A Very Short Introduction.
, 2007
Oxford University Press
[8], .
Blackburn
P.
van Benthem
J.
Modal logic: a semantic perspective
, Handbook of Modal Logic
, 2007
, vol. 3
Elsevier
of Blackburn et al. [9]
[9], , .
Blackburn
P.
van Benthem
J.
Wolter
F.
Handbook of Modal Logic
, Studies in Logic and Practical Reasoning.
, 2007
, vol. 3
Elsevier
[10], . ,
Boyd
C.
Mathuria
A.
Protocols for Authentication and Key Establishment.
, 2003
Springer
[11], .
Bradfield
J.
Stirling
C.
Modal Mu-Calculi
, Handbook of Modal Logic
, 2007
, vol. 3
Elsevier
of Blackburn et al. [9]
[12], , . ,
Cachin
C.
Keidar
I.
Shraer
A.
Trusting the cloud.
, 2009
Technical Column of ACM SIGACT News
June
[13], , .
Carbone
M.
Nielsen
M.
Sassone
V.
A formal model for trust in dynamic networks
, Proceedings of the IEEE Conference on Software Engineering and Formal Methods
, 2003
[14].
Cerf
V. G.
Trust and the Internet
, IEEE Internet Computing
, 2010
, vol. 14
(pg. 14
-22
)[15].
Chuvakin
A.
Beautiful log handling
, Beautiful Security: Leading Security Experts Explain How They Think
, 2009
O'Reilly
In Oram and Viega [59]
[16], , , .
Dantsin
E.
Eiter
T.
Gottlob
G.
Voronkov
A.
Complexity and expressive power of logic programming
, ACM Computing Surveys
, 2001
, vol. 33
3
(pg. 374
-425
)[17], . ,
Davey
B. A.
Priestley
H. A.
Introduction to Lattices and Order.
, 2002
Cambridge University Press
1990
[18].
Demolombe
R.
Reasoning about trust: a formal logical framework
, LNCS.
, 2004
, vol. 2995
Springer
[19]. ,
Desmedt
Y. G.
Secure Public Key Infrastructure.
, 2012
Springer
To appear
[20], .
Dolev
D.
Yao
A.
On the security of public key protocols
, IEEE Transactions on Information Theory
, 1983
, vol. 29
2
(pg. 198
-208
)[21], .
Ellison
C.
Schneier
B.
Ten risks of PKI: what you're not being told about public key infrastructure
, Computer Security Journal
, 2000
, vol. 16
1
(pg. 1
-7
)[22]
EuroPKI. http://www.europki.org/
[23]
European Research Consortium for Informatics and Mathematics. Cloud computing: Platforms, software and applications. ERCIM News, 83, 47–48, 2010
[24], , , . ,
Fagin
R.
Halpern
J. Y.
Moses
Y.
Vardi
M. Y.
Reasoning about Knowledge.
, 1995
MIT Press
[25]
[26], , . ,
Ferguson
N.
Schneier
B.
Kohno
T.
Cryptography Engineering: Design Principles and Practical Applications.
, 2010
Wiley
[27], , .
Gabbay
D. M.
Finger
M.
Reynolds
M.
Temporal Logic: Mathematical Foundations and Computational Aspects
, Oxford Logic Guides.
, 2000
, vol. 2
Oxford University Press
[28], , .
Gabbay
D. M.
Hodkinson
I.
Reynolds
M.
Temporal Logic: Mathematical Foundations and Computational Aspects
, Oxford Logic Guides.
, 1994
, vol. 1
Oxford University Press
[29], .
Gallery
E.
Mitchell
C. J.
Trusted computing: security and applications
, Cryptologia
, 2009
, vol. 33
(pg. 217
-245
)[30], .
Haenni
R.
Jonczy
J.
A new approach to PGP's web of trust
, Proceedings of the European e-Identity Conference
, 2007
[31], .
Halpern
J. Y.
Moses
Y.
Knowledge and common knowledge in a distributed environment
, Journal of the ACM
, 1990
, vol. 37
3
(pg. 549
-587
)[32], .
Halpern
J. Y.
Moses
Y.
A guide to completeness and complexity for modal logics of knowledge and belief
, Artificial Intelligence
, 1992
, vol. 54
(pg. 319
-379
)[33], .
Halpern
J. Y.
Moses
Y.
The effect of bounding the number of primitive propositions and the depth of nesting on the complexity of modal logic
, Artificial Intelligence
, 1995
, vol. 75
(pg. 361
-372
)[34], .
Huang
J.
Fox
M. S.
An ontology of trust—formal semantics and transitivity
, Proceedings of the ACM Conference on Electronic Commerce
, 2006
[35], .
Huang
J.
Nicol
D.
A calculus of trust and its application to PKI and identity management
, Proceedings of the ACM Symposium on Identity and Trust on the Internet
, 2009
[36], . ,
Joye
M.
Neven
G.
Identity-Based Cryptography.
, 2009
IOS Press
[37].
Kaufman
L. M.
Data security in the world of cloud computing
, IEEE Security & Privacy
, 2009
, vol. 7
(pg. 61
-64
)[38], .
Khan
K. M.
Malluhi
Q.
Establishing trust in cloud computing
, IEEE IT Professional
, 2010
, vol. 12
5
(pg. 20
-27
)[39]. ,
Kramer
S.
A logic of interactive proofs (formal theory of knowledge transfer).
, 2012
Technical Report 1201.3667, arXiv http://arxiv.org/ab/1201.3667
[40], , .
Kramer
S.
Goré
R.
Okamoto
E.
Formal definitions and complexity results for trust relations and trust domains
, Proceedings of the ESSLLI-affiliated Workshop on Logics in Security
, 2010
[41], , . ,
Kramer
S.
Goré
R.
Okamoto
E.
Formal definitions and complexity results for trust relations and trust domains fit for TTPs, the Web of Trust, PKIs, and ID-Based Cryptography.
, 2010
Logic Column of ACM SIGACT News
March
[41a], , .
Kramer
S.
Goré
R.
Okamoto
E.
Computer-Aided Decision-Making with Trust Relations and Trust Domains (Cryptographic Applications)
, Cryptology ePrint Archive
, 2011
Report 2011/235http://eprint.iacr.org/
[42], , , , .
Kramer
S.
Palamidessi
C.
Segala
R.
Turrini
A.
Braun
C.
A quantitative doxastic logic for probabilistic processes and applications to information-hiding
, Journal of Applied Non-Classical Logic
, 2009
, vol. 19
4
(pg. 489
-516
)[43], .
Kramer
S.
Rybalchenko
A.
A multi-modal framework for achieving accountability in multi-agent systems
, Proceedings of the ESSLLI-affiliated Workshop on Logics in Security
, 2010
[44], .
Krukowa
K.
Twigg
A.
The complexity of fixed point models of trust in distributed networks
, Theoretical Computer Science
, 2007
, vol. 389
3
pg. 26
[45], .
Lekkas
D.
Gritzalis
D.
e-Passports as a means towards a globally interoperable public key infrastructure
, Journal of Computer Security
, 2010
, vol. 18
(pg. 379
-396
)[46].
Liau
C. -J.
Belief, information acquisition, and trust in multi-agent systems—a modal logic formulation
, Artificial Intelligence
, 2003
, vol. 149
1
(pg. 31
-60
)[47], , , .
Lioy
A.
Marian
M.
Moltchanova
N.
Pala
M.
PKI past, present, and future
, Journal of Information Security
, 2006
, vol. 5
(pg. 18
-29
)[48], .
Lioy
A.
Ramunno
G.
Trusted Computing
, Handbook of Information and Communication Security
, 2010
Springer
[49], , .
Liu
Ch.
Ozols
M.
Cant
T.
An axiomatic basis for reasoning about trust in PKIs
, LNCS.
, 2001
, vol. 2119
Springer
[50]. ,
Lynch
N. A.
Distributed Algorithms.
, 1996
Morgan Kaufmann Publishers
[51], .
Marsh
S.
Dibben
M. R.
Trust, untrust, distrust and mistrust—an exploration of the dark(er) side
, LNCS.
, 2005
, vol. 3477/2005
Springer
[52].
Maurer
U.
Modelling a public-key infrastructure
, LNCS.
, 1996
, vol. 1146
Springer
[53], .
Meyer
J. -J.
Veltnam
F.
Intelligent agents and common sense reasoning
, Handbook of Modal Logic
, 2007
, vol. 3
Elsevier
of Blackburn et al. [11]
[54].
Michael
B.
In clouds shall we trust?
, IEEE Security & Privacy
, 2009
, vol. 7
5
pg. 3
[55], , .
Miller
K. W.
Voas
J.
Laplante
P.
In trust we trust
, IEEE Computer
, 2010
, vol. 43
(pg. 85
-87
)[56].
Minker
J.
Logic and databases: a 20 year retrospective
, LNCS.
, 1996
, vol. 1154/1996
Springer
[57].
Muller
T.
Semantics of trust
, LNCS.
, 2011
, vol. 6561
Springer
[58], . ,
Nickel
P. J.
Vaesen
K.
Handbook of Risk Theory: Epistemology, Decision Theory, Ethics, and Social Implications of Risk
, 2012
Springer
chapter Risk and Trust
[59], . ,
Oram
A.
Viega
J.
Beautiful Security: Leading Security Experts Explain How They Think.
, 2009
O'Reilly
[60].
Parikh
R.
Social software
, Synthese
, 2002
, vol. 132
(pg. 187
-211
)[61].
Paulson
L. C.
The inductive approach to verifying cryptographic protocols
, Journal of Computer Security
, 1998
, vol. 6
(pg. 85
-128
)[62].
Perlman
R.
An overview of PKI trust models
, IEEE Network
, 1999
, vol. 13
6
(pg. 38
-43
) November/December
[63], .
Primiero
G.
Taddeo
M.
A modal type theory for formalizing trusted communications
, Journal of Applied Logic
, 2012
, vol. 10
(pg. 92
-114
)[64].
Rangan
P. V.
An axiomatic basis of trust in distributed systems
, Proceedings of the IEEE Symposium on Security and Privacy
, 1988
[65], .
Ruohomaa
S.
Kutvonen
L.
Trust management survey
, LNCS.
, 2005
, vol. 3477
Springer
[66], , .
Jøsang
A.
Ismail
R.
Boyd
C.
A survey of trust and reputation systems for online service provision
, Decision Support Systems
, 2007
, vol. 43
2
(pg. 618
-644
)[67]. ,
Schneider
F. B.
Trust in Cyberspace.
, 1998
The National Academic Press
[68].
Schneier
B.
Security, group size, and the human brain
, IEEE Security & Privacy
, 2009
, vol. 7
[69]. ,
Schneier
B.
Liars and Outliers: Enabling the Trust That Society Needs to Thrive.
, 2012
Wiley
[70].
Schnoebelen
Ph.
The complexity of temporal logic model checking
, Proceedings of Advances in Modal Logic
, 2003
, vol. 4
[71], , .
Seligman
J.
Liu
F.
Girard
P.
Logic in the community
, LNAI.
, 2011
, vol. 6521
Springer
[72], , .
Tiu
A.
Goré
R.
Dawson
J.
A proof theoretic analysis of intruder theories
, Logical Methods in Computer Science
, 2010
, vol. 6
3
(pg. 1
-37
)[73], , .
van Ditmarsch
H.
van der Hoek
W.
Kooi
B.
Dynamic Epistemic Logic
, Synthese Library.
, 2007
, vol. 337
Springer
[74]. ,
van Tilborg
H. C. A.
Encyclopedia of Cryptography and Security
, 2005
Springer
(pg. 398
-400
)[75].
Woleński
J.
Applications of squares of oppositions and their generalizations in philosophical analysis
, Logica Universalis
, 2007
, vol. 2
1
pg. 37
[76], .
Xiu
D.
Liu
Z.
A formal definition for trust in distributed systems
, LNCS.
, 2005
, vol. 3650
Springer
[77].
Yao
A.
Protocols for secure computations
, Proceedings of the IEEE Symposium on Foundations of Computer Science
, 1982
[78], , .
Yu
H.
Jin
C.
Che
H.
A description logic for PKI trust domain modeling
, Proceedings of the IEEE Conference on Information Technology and Applications
, 2005
[79], , .
Zhao
W.
Varadharajan
V.
Bryan
G.
Analysis and modelling of trust in distributed information systems
, LNCS.
, 2005
, vol. 3803
Springer
[80], .
Zimmermann
Ph.
Callas
J.
The Evolution of PGP's Web of Trust
, Beautiful Security: Leading Security Experts Explain How They Think
, 2009
O'Reilly
In Oram and Viega [59]
PDF
This content is only available as a PDF.
© The Author, 2012. Published by Oxford University Press. All rights reserved. For Permissions, please email: journals.permissions@oup.com
Issue Section:
Original Articles
