Modelling Arbitrary Computations in the Symbolic Model using an Equational Theory for Bounded Binary Circuits

Michiel Marcus, Anne Nijsten, Frank Westers · 2025

Read Modelling Arbitrary Computations in the Symbolic Model using an Equational Theory for Bounded Binary Circuits by Michiel Marcus, Anne Nijsten, Frank Westers (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2507-21731.txt.

Introduction

Tools that check the safety of secret codes often reason about programs in an abstract way, away from real hardware. Michiel Marcus, Anne Nijsten, and Frank Westers work on a gap in that approach in this 2025 paper. Real code runs as binary circuits, and the abstract model needs a clean way to stand for any such circuit up to a fixed size.

The authors propose a family of equation sets for bounded binary circuits and show the sets have a handy trait that lets tools list all cases. They prove the equations match plain logic for circuits up to size three, and they measure how fast the work runs in a standard analysis tool. The result is a first step, they note, and larger circuits will need more work on scale.

Catalog record

CREATORMichiel Marcus, Anne Nijsten, Frank Westers
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE44 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2507-21731

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Modelling Arbitrary Computations in the Symbolic Model using an Equational Theory for Bounded Binary Circuits Michiel Marcus, Anne Nijsten, Frank Westers Abstract In this work, we propose a class of equational theories for bounded binary circuits that have the finite variant property. These theories could serve as a building block to specify cryptographic primitive implementations and automatically discover attacks as binary circuits in the symbolic model. We provide proofs of equivalence between this class of equational theories and Boolean logic up to circuit size 3 3 and we provide the variant complexities and performance benchmarks using Maude-NPA. This is the first result in this direction and follow-up research is needed to improve the scalability of the approach. I Introduction As more and more cryptographic protocols are developed to ensure confidentiality, integrity and authenticity of our data, it is vital that these protocols themselves are secure. Numerous tools and techniques have been developed that allow us to formally verify whether these cryptographic protocols work as intended [ blanchet2007cryptoverif , proverif , meier2013tamarin , maude-npa ] . Formal analysis of cryptographic protocols is typically conducted under one of two common models: the computational or the symbolic model. The computational model allows for making strong statements about the investigated system. Specifically, they can prove an upper bound on the probability than an attacker can break the system in terms of the security of the building blocks tools. However, tools in this model generally offer very little automation. The symbolic model makes it possible to reason about security protocols at a higher abstraction level, which allows for a higher degree of automation of the proofs. Common vulnerabilities, such as logical flaws that compromise security properties, can be caught in the symbolic model by automated protocol verification tools [ SoK ] . In contrast with the computational model, the symbolic model does not reason about bit strings, but about arbitrary-length variables and models cryptographic primitives in an idealised manner. The symbolic model is therefore not sound, as an attack on the protocol abusing computational aspects of a cryptographic scheme will not be caught in the symbolic model. However, such attacks are often very complex and are also very hard to discover manually using cryptanalysis. In the symbolic model, we typically consider a Dolev-Yao adversary [ dolev-yoa ] that has complete control over the network. The adversary can intercept messages sent between protocol participants, record the messages and insert messages the attacker has created using their own knowledge. In this work, we are specifically interested in tools that do symbolic verification. In the symbolic model, mathematical properties are modelled using an equational theory. An example is the equational theory with only the rule dec(enc(m,k),k)=m , where dec denotes decryption, enc denotes encryption, m is an arbitrary message and k is an arbitrary key. This equational theory models the mathematical properties of a perfectly secure symmetric encryption scheme - the only way to turn a ciphertext enc(m,k) back into the message is through the rule that requires the knowledge of the key. This is obvious to see in our one-line equational system, but if the system becomes more complex, proving security statements become harder. However, if an equational system has the so-called finite variant property (FVP), which we elaborate on in section II-A5 , then the problem can be solved relatively efficiently. In that case there is a procedure called variant narrowing that can be used for unification during the analysis of the system [ variant-unification ] , a technique that is commonly used by automated protocol verifiers. Hence, it is favourable for an equational system to have the FVP. Examples of equational theories with the FVP are abelian groups, blind signatures, and modular exponentiation. However, several theories, such as associativity (without commutativity), commutativity (without associativity) and the homomorphic property of partially homomorphic encryption do not have the FVP [ homenc-fvp ] . In our work, we consider equational theories for Boolean logic. The theory of Boolean logic is not FVP, because the equation that models the homomorphic property of homomorphic encryption enc(x + y, k) = enc(x, k) + enc(y, k) is similar to the distributivity rule in Boolean logic (x or y) and z = (x and z) or (y and z) and therefore has similar problems with respect to the FVP. Since there is already some literature available on equational theories with FVP for the homomorphic property of homomorphic encryption, but little on equational theories with the FVP for Boolean logic, we will refer to the former when motivating and explaining our work. Since Boolean logic encompasses more rules than just distributivity, previous literature needs to be extended in order to construct an equational theory with the FVP for Boolean logic, which is the goal of our work. When an equational theory does not have the FVP, variant narrowing cannot be used for unification. However, it is possible to devise specific unification algorithms for non-FVP theories, which would enable automatic protocol analysis for protocols with these theories. There is a composition theory that states that variant narrowing yields a unification algorithm for the combination of any number of equational theories with the FVP [ variant-unification ] . If we have a protocol with partially homomorphic encryption, then we have on the one hand decryption and encryption cancellation, which has the FVP, and on the other hand the homomorphic property of the encryption scheme, which does not have the FVP. Even with the dedicated unification algorithm for the homomorphic property of homomorphic encryption as introduced by Anantharaman et al. in [ cap_unification ] , there is no known theorem that explains how it can be combined with variant narrowing to yield a unification algorithm for the combined equational theory of homomorphic encryption. Similarly, a dedicated unification algorithm for the one-sided distributivity rule of Boolean logic was proposed by Tiden and Arnborg in [ boolean_unification ] , but it has the same issue. Additionally, Tiden and Arnborg prove that unification for the two-sided distributivity rule of Boolean logic is NP-hard. The best approach is therefore to construct an equational theory that is an approximation of Boolean logic and has the FVP. I-A Contributions In this work, we build on main ideas in the work by Escobar et al. [ homenc-fvp ] and create an equational theory for bounded binary circuits with the FVP. Concretely, we present the following contributions: • We introduce the first equational theory for bounded binary circuits with the FVP; • We prove that this equational theory models all properties of Boolean algebra. This equational theory serves as a building block for automatic protocol verification tooling based on narrowing to verify protocols with specific implementations. Instead of using abstract encryption schemes and digital signatures schemes, the encryption/decryption and sign/verify functionality can be modelled using binary circuits. This allows the tooling to find more complex attacks on the protocol using implementation details. I-B Outline of the Paper In Section II we provide the necessary background information about symbolic verification and equational theories. Next, we discuss related work in Section III . Further, we present our strategy for modelling arbitrary binary circuits in Section IV . In Section V we formally verify a small circuit

Read the complete text