On asymmetric unification for the theory of XOR with a homomorphism

DOI10.1007/978-3-030-29007-8_17zbMATH Open1435.68373arXiv1907.00227OpenAlexW2970093241WikidataQ118190331 ScholiaQ118190331MaRDI QIDQ2180236FDOQ2180236

Authors: Christopher Lynch, Andrew M. Marshall, Paliath Narendran, Catherine Meadows, V. Ravishankar

Publication date: 13 May 2020

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.

Full work available at URL: https://arxiv.org/abs/1907.00227

Recommendations

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Cryptography (94A60) Grammars and rewriting systems (68Q42) Mechanization of proofs and logical operations (03B35) Theorem proving (automated and interactive theorem provers, deduction, resolution, etc.) (68V15)

Cited In (3)

This page was built for publication: On asymmetric unification for the theory of XOR with a homomorphism

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2180236)