1. On Asymmetric Unification for the Theory of XOR with a Homomorphism
- Author
-
Lynch, Christopher, Marshall, Andrew M., Meadows, Catherine, Narendran, Paliath, and Ravishankar, Veena
- Subjects
FOS: Computer and information sciences ,Computer Science - Computational Complexity ,Physics::General Physics ,Computer Science - Cryptography and Security ,TheoryofComputation_MATHEMATICALLOGICANDFORMALLANGUAGES ,TheoryofComputation_LOGICSANDMEANINGSOFPROGRAMS ,High Energy Physics::Phenomenology ,Computer Science::Programming Languages ,Computer Science::Computation and Language (Computational Linguistics and Natural Language and Speech Processing) ,Computational Complexity (cs.CC) ,Cryptography and Security (cs.CR) - Abstract
Asymmetric unification, or unification with irreducibility constraints, is a newly developed paradigm that arose out of the automated analysis of cryptographic protocols. However, there are still relatively few asymmetric unification algorithms. In this paper we address this lack by exploring the application of automata-based unification methods. We examine the theory of xor with a homomorphism, ACUNh, from the point of view of asymmetric unification, and develop a new automata-based decision procedure. Then, we adapt a recently developed asymmetric combination procedure to produce a general asymmetric- ACUNh decision procedure. Finally, we present a new approach for obtaining a solution-generating asymmetric-ACUNh unification automaton. We also compare our approach to the most commonly used form of asymmetric unification available today, variant unification.
- Published
- 2019
- Full Text
- View/download PDF