Abstract
In the context of modeling cryptographic tools like blind signatures and homomorphic encryption, the Dolev-Yao model is typically extended with an operator over which encryption is distributive. The intruder deduction problem has a non-elementary upper bound when the extended operator is an Abelian group operator. Here we show that the intruder deduction problem is DEXPTIME-complete when we restrict the operator to satisfy only the associative property. We propose an automata-based analysis for the upper bound and use the reachability problem for alternating pushdown systems to show the lower bound.
S. P. Suresh—Partially supported by an Infosys Grant.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Abadi, M., Cortier, V.: Deciding knowledge in security protocols under equational theories. Theor. Comput. Sci. 367(1–2), 2–32 (2006). https://doi.org/10.1016/j.tcs.2006.08.032
Avanesov, T., Chevalier, Y., Rusinowitch, M., Turuani, M.: Satisfiability of general intruder constraints with and without a set constructor. J. Symbolic Comput. 80, 27–61 (2017). https://doi.org/10.1016/j.jsc.2016.07.009
Baskar, A.: Decidability results for extended Dolev-Yao theories. Ph.D. thesis, Chennai Mathematical Institute (2011)
Baskar, A., Ramanujam, R., Suresh, S.: Dolev-Yao theory with associative blindpair operators, Technical report (2019). http://www.cmi.ac.in/~spsuresh/pdfs/ciaa19-tr.pdf
Baskar, A., Ramanujam, R., Suresh, S.P.: Knowledge-based modelling of voting protocols. In: Samet, D. (ed.) TARK 2007, pp. 62–71 (2007). https://doi.org/10.1145/1324249.1324261
Baskar, A., Ramanujam, R., Suresh, S.P.: A dexptime-complete Dolev-Yao theory with distributive encryption. In: Hliněný, P., Kučera, A. (eds.) MFCS 2010. LNCS, vol. 6281, pp. 102–113. Springer, Heidelberg (2010). https://doi.org/10.1007/978-3-642-15155-2_11
Ciobâca, S., Delaune, S., Kremer, S.: Computing knowledge in security protocols under convergent equational theories. J. Autom. Reason. 48(2), 219–262 (2012). https://doi.org/10.1007/s10817-010-9197-7
Comon-Lundh, H., Shmatikov, V.: Intruder deductions, constraint solving and insecurity decision in presence of exclusive or. In: LICS 2003, pp. 271–280. IEEE Computer Society (2003). https://doi.org/10.1109/LICS.2003.1210067
Cortier, V., Delaune, S.: Decidability and combination results for two notions of knowledge in security protocols. J. Autom. Reason. 48(4), 441–487 (2012). https://doi.org/10.1007/s10817-010-9208-8
Cortier, V., Delaune, S., Lafourcade, P.: A survey of algebraic properties used in cryptographic protocols. J. Comput. Secur. 14(1), 1–43 (2006). http://content.iospress.com/articles/journal-of-computer-security/jcs244
Dolev, D., Yao, A.: On the security of public-key protocols. IEEE Trans. Inf. Theory 29(2), 198–207 (1983). https://doi.org/10.1109/TIT.1983.1056650
Lafourcade, P., Lugiez, D., Treinen, R.: Intruder deduction for the equational theory of Abelian groups with distributive encryption. Inf. Comput. 205(4), 581–623 (2007). https://doi.org/10.1016/j.ic.2006.10.008
Rusinowitch, M., Turuani, M.: Protocol insecurity with a finite number of sessions and composed keys is NP-complete. Theor. Comput. Sci. 299(1–3), 451–475 (2003). https://doi.org/10.1016/S0304-3975(02)00490-5
Suwimonteerabuth, D., Schwoon, S., Esparza, J.: Efficient algorithms for alternating pushdown systems with an application to the computation of certificate chains. In: Graf, S., Zhang, W. (eds.) ATVA 2006. LNCS, vol. 4218, pp. 141–153. Springer, Heidelberg (2006). https://doi.org/10.1007/11901914_13
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2019 Springer Nature Switzerland AG
About this paper
Cite this paper
Baskar, A., Ramanujam, R., Suresh, S.P. (2019). Dolev-Yao Theory with Associative Blindpair Operators. In: Hospodár, M., Jirásková, G. (eds) Implementation and Application of Automata. CIAA 2019. Lecture Notes in Computer Science(), vol 11601. Springer, Cham. https://doi.org/10.1007/978-3-030-23679-3_5
Download citation
DOI: https://doi.org/10.1007/978-3-030-23679-3_5
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-030-23678-6
Online ISBN: 978-3-030-23679-3
eBook Packages: Computer ScienceComputer Science (R0)