Distributed Contingency Logic and Security



Department of Mathematical Sciences, Sharif University of Technology, Tehran, Iran


In information security, ignorance is not bliss. It is always stated that hiding the protocols (let the other be ignorant about it) does not increase the security of organizations. However, there are cases that ignorance creates protocols. In this paper, we propose distributed contingency logic, a proper extension of contingency (ignorance) logic. Intuitively, a formula is distributed contingent in a group of agent if and only if it does not follow from the knowledge of all individual agents put together. We formalize secret sharing scheme (a security property that is built upon ignorance of all agents), and a man in the middle attack to a weak protocol in our logic. We also illustrate a condition where disclose a secret may hide another one forever. Finally we prove the main theorems of every logic, soundness and completeness. We also prove that distributed contingency logic is more expressive than classical contingency logic and epistemic logic.


1] CJF Cremers, S Mauw, and EP De Vink. Formal methods for security protocols: Three examples of the black-box approach. NVTI newsletter,7:21–32, 2003.
[2] Jim Woodcock, Peter Gorm Larsen, Juan Bicarregui, and John Fitzgerald. Formal methods: Practice and experience. ACM computing surveys (CSUR), 41(4):19, 2009.
[3] Susan Older and Shiu-Kai Chin. Formal methods for assuring security of protocols. The Computer Journal, 45(1):46–54, 2002.
[4] Moni Naor and Adi Shamir. Visual cryptography. In Workshop on the Theory and Application of of Cryptographic Techniques, pages 1–12. Springer,1994.
[5] Douglas R Stinson. An explication of secret sharing schemes. Designs, Codes and Cryptography, 2(4):357–390, 1992.
[6] Samaneh Mashhadi. Computationally secure multiple secret sharing: models, schemes, and formal security analysis. The ISC International Journal of Information Security, 7(2):91–99, 2015.
[7] J-J Ch Meyer and Wiebe Van Der Hoek. Epistemic logic for AI and computer science, volume 41. Cambridge University Press, 2004.
[8] Ronald Fagin, Joseph Y Halpern, Yoram Moses, and Moshe Vardi. Reasoning about knowledge. MIT press, 2004.
[9] Floris Roelofsen. Distributed knowledge. Journal of Applied Non-Classical Logics, 17(2):255–273, 2007.
[10] Jelle Gerbrandy. Distributed knowledge. In Twendial, volume 98, pages 111–124, 1998.
[11] IL Humberstone et al. The logic of noncontingency. Notre Dame Journal of Formal Logic, 36(2):214–229, 1995.
[12] Steven T Kuhn et al. Minimal non-contingency logic. Notre Dame Journal of Formal Logic, 36(2):230–234, 1995.
[13] Jie Fan, Yanjing Wang, and Hans van Ditmarsch. Contingency and knowing whether. The Review of Symbolic Logic, 8(01):75–107, 2015.
[14] Jie Fan and Hans Van Ditmarsch. Neighborhood contingency logic. In Indian Conference on Logic and Its Applications, pages 88–99. Springer, 2015.
[15] Christopher Steinsvold. A note on logics of ignorance and borders. Notre Dame Journal of Formal Logic, 49(4):385–392, 2008.
[16] Wiebe Van Der Hoek and Alessio Lomuscio. A logic for ignorance. In Declarative Agent Languages and Technologies, pages 97–108. Springer,2004.
[17] Jelle Douwe Gerbrandy et al. Bisimulations on planet Kripke. ILLC Dissertation Series, 1999.
[18] Jie Fan. Removing your ignorance by announcing group ignorance: A group announcement logic for ignorance. Stud. Log, 9(4):4–33, 2016.
[19] Jie Fan. Distributed knowledge whether. International Workshop on Logic, Rationality and Interaction, 10455, 2017.
[20] Catherine Meadows. Formal methods for cryptographic protocol analysis: Emerging issues and trends. IEEE journal on selected areas in communications, 21(1):44–54, 2003.
[21] Seyit Ahmet Camtepe and Bülent Yener. A formal method for attack modeling and detection. SA Camtepe, B. Yener, 2006.
[22] Nadarajah Asokan, Valtteri Niemi, and Kaisa Nyberg. Man-in-the-middle in tunnelled authentication protocols. In security protocols workshop, volume 3364, pages 28–41. Springer, 2003.
[23] Zhe Chen, Shize Guo, Rong Duan, and Sheng Wang. Security analysis on mutual authentication against man-in-the-middle attack. In Information Science and Engineering (ICISE), 2009 1st International Conference on, pages 1855–1858. IEEE, 2009.
[24] Ratan K Guha, Zeeshan Furqan, and Shahabuddin Muhammad. Discovering man-in-the-middle attacks in authentication protocols. In Military Communications Conference, 2007. MILCOM 2007. IEEE, pages 1–7. Ieee, 2007.
[25] Hans Van Ditmarsch, Wiebe van Der Hoek, and Barteld Kooi. Dynamic epistemic logic, volume  337. Springer Science & Business Media, 2007.

[26] Wiebe Van Der Hoek, Bernd Van Linder, and John-Jules Meyer. Group knowledge is not always distributed (neither is it always implicit). Mathematical social sciences, 38(2):215–240, 1999.
[27] Rahim Ramezanian. Classification of action models which preserve full communication, Master thesis. Shahid Beheshti University, 2010. Persian.
[28] Patrick Blackburn, Maarten De Rijke, and Yde Venema. Modal Logic: Graph. Darst, volume 53. Cambridge University Press, 2002.
[29] Sandra M Hedetniemi, Stephen T Hedetniemi, and Arthur L Liestman. A survey of gossiping and broadcasting in communication networks. Networks, 18(4):319–349, 1988.
[30] Hans van Ditmarsch, Jan van Eijck, Pere Pardo, Rahim Ramezanian, and Fran¸ cois Schwarzentruber. Epistemic protocols for dynamic gossip. Journal of Applied Logic, 20:1–31, 2017.
[31] Hans van Ditmarsch, Jan van Eijck, Pere Pardo, Rahim Ramezanian, and Fran¸ cois Schwarzentruber. Dynamic gossip. arXiv preprint arXiv:1511.00867, 2015.
[32] Maduka Attamah, Hans Van Ditmarsch, Davide Grossi, and Wiebe van der Hoek. Knowledge and gossip. In ECAI, pages 21–26, 2014.
[33] Walter Kn¨ odel. New gossips and telephones. Discrete Mathematics, 13(1):95, 1975.