Hostname: page-component-74656f9884-8r8nv Total loading time: 0 Render date: 2026-11-08T04:05:27.399Z Has data issue: false hasContentIssue false
  • English
  • Français

Bounded ACh unification

Published online by Cambridge University Press:  16 September 2020

Ajay Kumar Eeralla Open the ORCID record for Ajay Kumar Eeralla [Opens in a new window]  and
Christopher Lynch
Ajay Kumar Eeralla*
Affiliation:
Galois Inc, Portland, Oregon, 97204
Christopher Lynch
Affiliation:
Department of Computer Science, Clarkson University, Potsdam, NY 13699, USA
*
*Corresponding author. Email: aeeralla@galois.com
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the 'Save PDF' action button.

We consider the problem of the unification modulo an equational theory associativity and commutativity (ACh), which consists of a function symbol h that is homomorphic over an associative–commutative operator +. Since the unification modulo ACh theory is undecidable, we define a variant of the problem called bounded ACh unification. In this bounded version of ACh unification, we essentially bound the number of times h can be applied to a term recursively and only allow solutions that satisfy this bound. There is no bound on the number of occurrences of h in a term, and the + symbol can be applied an unlimited number of times. We give inference rules for solving the bounded version of the problem and prove that the rules are sound, complete, and terminating. We have implemented the algorithm in Maude and give experimental results. We argue that this algorithm is useful in cryptographic protocol analysis.

Keywords

Equational unificationcryptographic protocol analysisrewritinghomomorphismcommutativityMaude

Information

Type
Paper
Information
Mathematical Structures in Computer Science , Volume 30 , Special Issue 6: Special Issue: Unification , June 2020 , pp. 664 - 682
Copyright
© The Author(s), 2020. Published by Cambridge University Press

References

Anantharaman, S., Lin, H., Lynch, C., Narendran, P. and Rusinowitch, M. (2010). Cap unification: application to protocol security modulo homomorphic encryption. In: Proceedings of the 5th ACM Symposium on Information, Computer and Communications Security, ACM, 192–203.CrossRefGoogle Scholar
Anantharaman, S., Lin, H., Lynch, C., Narendran, P. and Rusinowitch, M. (2012). Unification modulo homomorphic encryption. In: Journal of Automated Reasoning, Springer, 135–158.Google Scholar
Baader, F. and Nipkow, T. (1998). Term Rewriting and All that, Cambridge University Press, Cambridge, UK.10.1017/CBO9781139172752CrossRefGoogle Scholar
Baader, F. and Snyder, W. (2001). Unification theory. In: Handbook of Automated Reasoning, Elsevier, 447–533.Google Scholar
Clavel, M., Durán, F., Eker, S., Lincoln, P., Martí-Oliet, N., Meseguer, J. and Talcott, C. L. (2007). All About Maude - A High-Performance Logical Framework, How to Specify, Program and Verify Systems in Rewriting Logic, Springer, Berlin, Heidelberg.Google Scholar
Escobar, S., Kapur, D., Lynch, C., Meadows, C., Meseguer, J., Narendran, P. and Sasse, R. (2011). Protocol analysis in Maude-NPA using unification modulo homomorphic encryption. In: Proceedings of the 13th International ACM SIGPLAN Symposium on Principles and Practices of Declarative Programming, ACM, 65–76.CrossRefGoogle Scholar
Escobar, S., Meadows, C. and Meseguer, J. (2007). Maude-Npa: cryptographic protocol analysis modulo equational properties. In: Foundations of Security Analysis and Design V: FOSAD 2007/2008/2009 Tutorial Lectures, 1–50, Springer.Google Scholar
Fages, F. (1984). Associative-commutative unification. In: 7th International Conference on Automated Deduction, Springer, 194–208.Google Scholar
Kapur, D., Narendran, P. and Wang, L. (2003). An E-unification algorithm for analyzing protocols that use modular exponentiation. In: Rewriting Techniques and Applications, Springer, 165–179.CrossRefGoogle Scholar
Kremer, S., Ryan, M. and Smyth, B. (2010). Election verifiability in electronic voting protocols. In: Computer Security – ESORICS, Springer, 389–404.CrossRefGoogle Scholar
Liu, Z. and Lynch, C. (2011). Efficient general unification for XOR with homomorphism. In: 23rd International Conference on Automated Deduction, CADE-23, Springer, 407–421.CrossRefGoogle Scholar
Liu, Z. and Lynch, C. (2014). Efficient general AGH-unification. In: Information and Computation, vol. 238, Elsevier, 128–156.Google Scholar
Marshall, A. M., Meadows, C. A. and Narendran, P. (2015). On unification modulo one-sided distributivity: algorithms, variants and asymmetry. Logical Methods in Computer Science 11 (2) 1–39.CrossRefGoogle Scholar
Narendran, P. (1996). Solving linear equations over polynomial semirings. In: Proceedings 11th Annual IEEE Symposium on Logic in Computer Science, IEEE Computer Society, 466–472.CrossRefGoogle Scholar
Schmidt-Schauß, M. (1998). A decision algorithm for distributive unification. In: Journal of Theoretical Computer Science, Elsevier, 111–148.Google Scholar
Tidén, E. and Arnborg, S. (1987). Unification problems with one-sided distributivity. In: Journal of Symbolic Computation, Springer, 183–202.Google Scholar