Automatic verification of finite variant property beyond convergent equational theories

Conference item

Computer-aided analysis of security protocols heavily relies on equational theories to model cryptographic primitives. Most automated verifiers for security protocols focus on equational theories that satisfy the Finite Variant Property (FVP), for which solving unification is decidable. However, they either require to prove FVP by hand or at least to provide a representation as an E-convergent rewrite system, usually E being at most the equational theory for an associative and commutative function symbol (AC). The verifier ProVerif is probably the only exception amongst these tools as it automatically proves FVP without requiring a representation, but on a small class of equational theories. In this work, we propose a novel semi-decision procedure for proving FVP, without the need for a specific representation, and for a class of theories that goes beyond the ones expressed by an E-convergent rewrite system. We implemented a prototype and successfully applied it on several theories from the literature.

Authors: Cheval, V; Fontaine, C

• Publication status: Published
• Peer review status: Peer reviewed
• Publisher: IEEE
• Host title: 2025 IEEE 38th Computer Security Foundations Symposium (CSF)
• Pages: 521-536
• Publication date: 2025-08-11
• Acceptance date: 2025-06-16
• Event title: 38th IEEE Computer Security Foundations Symposium (CSF 2025)
• Event location: Santa Cruz, California, USA
• Event website: https://csf2025.ieee-security.org/
• Event start date: 2025-06-16
• Event end date: 2025-06-20
• DOI: 10.1109/csf64896.2025.00005
• EISSN: 2374-8303
• ISSN: 1940-1434
• EISBN: 9798331510817
• ISBN: 9798331510824
• Language: English
• Keywords: hands; analytical models; computational modeling; symbols; prototypes; mathematical models; cryptography; computer security; cryptographic protocols