Argo MAC: Garbling with Elliptic Curve MACs

Argo MAC is a new garbling primitive that efficiently translates the bit decomposition of an elliptic curve point into a homomorphic MAC of that point, enabling over 1000x more efficient garbled SNARK verifiers for pairing-based SNARKs.

Argo MAC Garbling with Elliptic Curve MACs Liam Eagen∗ Ying Tong Lai † { ideal }

January 18, 2026

Off-chain cryptography enables more expressive smart contracts for Bitcoin [1]. Recent work, including BitVM [2, 3, 4] and Glock [5], use SNARKs to prove arbitrary computation, and garbled circuits to verifiably move proof verification off-chain. In this note, we define a new garbling primitive, Argo MAC, that enables over 1000× more efficient garbled SNARK verifiers. Argo MAC efficiently translates from an encoding of the bit decomposition of a curve point to a homomorphic MAC of that point. These homomorphic MACs enable much more efficient garbling. In subsequent work, we will describe how to use Argo MAC to construct garbled SNARK verifiers for pairing-based SNARKs.

1 Introduction

Garbling schemes [6] are a powerful technique that underlie many higher-level cryptographic protocols like Secure Function Evaluation (SFE), Conditional Disclosure of Secrets (CDS), and Multiparty Computation (MPC). A garbling scheme is a two-party protocol between a Garbler and an Evaluator. In the first phase, the Garbler “garbles” a function and sends the garbling to the Evaluator. In the second phase, the Garbler shares some encoding of an input with the Evaluator, which allows them to compute the function on that, and only that, particular input. Many of the earliest, and most practical, garbling schemes rely on some variant of Yao’s protocol [7]. This protocol takes a circuit, consisting of a DAG of gates connected by wires. Each gate takes several wires as input and produces some number of output wires. In the original scheme, the wires are binary and each gate encodes a binary logic gate. Subsequent work has extended this notion to a larger class of circuits [8, 9, 10, 11]. To garble the circuit, the Garbler assigns each wire a Message Authentication Code (MAC) key or randomized encoding scheme. They “garble” the value of that wire by encoding it under this scheme. The Garbler assigns to each gate some additional cryptographic information such that, given input wire encodings, the Evaluator can compute the encoding of the output wires. Crucially, this is the only way the Evaluator can compute valid encodings of the output wires. In Yao’s scheme, each gate is encoded as an encrypted truth table. The input wire MACs for each row are used as the key to encrypt the output wire. Starting with the free XOR technique [12], some garbling schemes [13, 14, 15, 16, 17, 18] exploited the fact that for certain types of gates there exist encoding schemes that allow the Evaluator to evaluate the gate with no, or very little, additional information. This reduces the size of the garbled circuit and the complexity of evaluation. For XOR , this family of techniques exploits “homomorphic MACs” (HMACs) that are linear with respect to the XOR operation. Other techniques, like information theoretic partial garbling (ITPG) [11], exploit a similar trick over the additive group of general finite fields. More recent work has even demonstrated the existence of fully homomorphic MACs which allow evaluating both addition and multiplication in 𝔽2 , yielding constant-sized garbling tables [16, 17, 18].

1.1 BitVM and Glock

A recent line of work has shown how to use garbling schemes to augment Bitcoin with SNARK verification. Bitcoin is not capable of directly verifying complex programs, which limits its ability to build complex smart contracts, in particular SNARK verifiers. However, Bitcoin can verify the correct encoding of wires in a garbled circuit for certain encoding schemes. For example, in Yao’s garbled circuits, each input bit can have one of two possible encodings, and Bitcoin can verify that each bit is a valid encoding by checking hash pre-images. More sophisticated techniques [5, 19] are able to verify encodings of wires over larger, but still small, alphabets (e.g. byte values). We call such encodings that can be decomposed as strings over a small alphabet “projective.” We can couple this functionality with an off-chain garbled circuit to reveal a secret conditional on a predicate. During setup, the Garbler constructs a circuit for a predicate 𝒞, and during Evaluation reveals an encoding of an input 𝑥. The validity of this encoding can be verified by Bitcoin. The Evaluator uses this encoding to derive an encoding of the output of 𝒞(𝑥) = 𝑦. Bitcoin can also verify the correctness of the encoding of 𝑦. Suppose 𝑥 is a SNARK proof, and 𝒞 is the SNARK verification circuit. If the SNARK is invalid, then 𝑦 = 0. In an interactive BitVM-style protocol (e.g. Glock), the Evaluator can present the encoding of 𝑦 = 0 as a “fraud proof” that 𝑥 is not valid. This can be used to condition the release of funds on SNARK validity, which enables a kind of “optimistic” [20] SNARK verification on Bitcoin. Many projects are using variants of this technique to build sophisticated protocols on top of Bitcoin, which were previously believed to be impossible.

1.2 Rich Wire Encodings

The SNARK used by most Glock-like protocols is Groth16 [21], chosen for its small proof size. Some also use variants of other elliptic curve based SNARKs like Pari [22]. These SNARK verifier circuits are all naturally expressed as elliptic curve pairing 1 equations. These can in turn be expressed as simple formulae or circuits, where wire values take on elliptic curve points or other elements of large groups. We might hope that there is some way to combine the free XOR technique with this circuit and encode curve points in a way that respects curve operations. This might allow us to very efficiently garble SNARK verifiers. However, we need this encoding to be projective with respect to a small alphabet in order to use it with Bitcoin. To encode elliptic curve points in a projective way, we decompose the curve point into some string over a small alphabet. Unfortunately, this destroys the structure of the curve point as an element of an algebraic group. Note that this is not the case for all groups. For example, the additive group of a field admits a simple projective encoding that respects the additive structure: bit decomposition. Since bit recomposition is 𝔽linear, everything just works. Unfortunately, this is likely impossible for elliptic curves. If we could find a homomorphic, projective encoding of points then we could mount an index calculus attack on the curve group, which is believed to be hard and is the basis for their unique efficiency compared to other discrete log-hard groups.

1.3 Argo MAC

Argo MAC is a technique to bridge this gap: that is, to efficiently transform a projective encoding of an elliptic curve point into a HMAC over an elliptic curve group. Of course, this is possible using generic garbling schemes for binary circuits by garbling the encoding function for a HMAC over elliptic curves, but this yields unacceptably large garbling tables. In particular, this is not (much) more efficient than simply garbling the SNARK verifier. In a nutshell, Argo MAC uses ITPG [11] to evaluate the encoding function for a HMAC over elliptic curve groups. Recall ITPG has complexity dependent on the size of the Arithmetic Branching Program (ABP) for the garbled polynomial, which places strict limits on the complexity of the encoding function. To make this work, we use a HMAC scheme over EC groups whose encoding function is a sparse degree-3 polynomial. Argo MAC uses well-understood, existing techniques based on Yao garbling and ITPG, and only relies on conservative security assumptions about symmetric key cryptography.

1 Designated verifier versions like that described in Glock are able to avoid pairings, with other tradeoffs.

First, we accept the bits of the coordinates of the curve point encoded using standard, Yao-based encoding. Then, we use standard garbling techniques to map this encoding to one compatible with ITPG. Since elliptic curves are algebraic groups, their group law can be expressed using low-degree polynomials. We use ITPG to evaluate the degree-3 encoding function on the input point. Finally, the output of ITPG is a secure MAC of an elliptic curve point that respects the group law. This technique yields over 3 orders of magnitude performance improvement compared to Yao-based approaches, both in terms of garbling table size, as well as garbler and evaluator speed. Intuitively, this speedup comes from performing as much of the garbling operations natively, i.e. in the group where the objects naturally live, as possible. This avoids the arithmetization overhead of converting high-level operations, like field multiplication, into binary circuits. For example, when computing elliptic curve addition formulae, working with MACs over the base field allows addition operations for free, and multiplication operations much more cheaply, than if they were carried out by a binary circuit.

1.4 Related Work

It is challenging to directly compare Argo MAC to existing work by itself. Most work that would be directly comparable focuses on garbling SNARK verifiers, which we defer. If one were to directly replicate the functionality of Argo MAC using other garbling techniques, the overall protocol would typically be less efficient than directly garbling the verifier. However, assuming that it is possible to construct a garbled SNARK verifier whose table size and garbling time are dominated by Argo MAC, we can estimate what a garbled SNARK verifier would look like using Argo MAC. There are many garbling schemes for generic boolean circuits [7, 12, 23], which can be used to implement SNARK verifiers. In fact, the most mature approach to this in the context of BitVM/Glock style protocols on Bitcoin is based on privacy-free half gate garbling [24]. This approach incurs large arithmetization overhead when converting operations to binary circuits. This increases garbling and evaluation time by many orders of magnitude compared to the cost of Argo MAC. Some approaches, such as BitGC [15] or those based on AHMACs [16, 17, 18], are able to avoid increasing the garbling table size, even in the case of AHMAC keeping table size dependent only on input and output size and not circuit complexity. However, they are still not able to avoid increasing garbling time, which for a SNARK verifier circuit can be very large [25]. These schemes also have concretely large garbling tables and require additional cryptographic assumptions. There are also approaches to garbling arithmetic circuits [8, 9, 10]. These come in a number of flavors, but generally require additional heavy cryptographic assumptions or decompose integer wires using the Chinese Remainder Theorem. These schemes can be concretely efficient, and have been applied to BitVM style protocols [26]. While implementation is still ongoing, the resulting tables and garbling times will be larger than Argo MAC. In forthcoming work, we will show how to build a garbling scheme for pairing-based SNARK verifiers that respects this MAC structure. In different forthcoming work, Babylon Labs [27] will use our technique in a different way to build a SNARK verifier based on linear pairing witness encryption [28]. In both cases, the key enabling technology that makes these schemes over 1000× more efficient than existing approaches is Argo MAC.

2 Preliminaries

We will use 𝔽 to denote fields and 𝔾, ℍ to denote groups. We write the set of group homomorphisms as Hom(𝔾, ℍ), the set of functions as 𝔾 → ℍ, and the set of partial functions as 𝔾 ⇀ ℍ. These partial functions can also be interpreted as functions which may return ⊥. When ℍ = 𝔾 we denote the integer multiplication homomorphisms by integers, i.e. 𝑛 ∈ ℤ is the function 𝑛 ∶ 𝐺 ↦ 𝑛𝐺. When ℍ = 𝔾𝑛 we denote by vectors 𝑣 ∈ ℤ𝑛 the homomorphisms 𝑣 ∶ 𝐺 ↦ (𝑣𝑖 𝐺)𝑖∈[𝑛] . We adopt the same convention for larger endomorphism rings, for example in curves with complex multiplication (CM). We will use lowercase letters to refer to field elements and uppercase to curve points. We use both the terms “randomized encodings”, as well as “MAC”/“GC”, where they are more natural, recognizing their equivalence. Throughout 𝐸 denotes an elliptic curve over base field 𝔽𝑞 with characteristic 𝑝 and subgroup of size 𝑟. We write the cofactor of 𝐸/𝔽𝑞 as ℎ, which by construction satisfies (𝑟, ℎ) = 1. We do not assume

anything else about 𝐸, but in practice it will typically be one of the groups associated with a pairing-friendly curve from a family like BN [29] or BLS [30]. The scheme is parameterized over the security parameter 𝜆, and a replication factor for the iterated MAC 𝜅. This value is always less than 𝜆 and is determined by the CM discriminant and the cofactor of the curve. We denote the number of bits in 𝑝 by 𝜌 = ⌈log2 𝑞⌉ > 2𝜆. For a given MAC scheme we denote the MAC of a value 𝑥 under the key k using square brackets, i.e. [𝑥]k . When the key is clear from context, we drop the key subscript. We adopt the same notation for garbling schemes. For a given garbling scheme we denote the garbling of a function 𝑓 under the garbling key k also as [𝑓]k .

2.1 Elliptic Curves

We briefly review the properties of elliptic curves relevant to Argo MAC, and defer a more complete treatment to [31]. An elliptic curve is an algebraic group over a field. We will work with curves in Weierstrass form and make use of their algebraic group laws in a non-blackbox way. The curve is parameterized by two field elements 𝐴, 𝐵 ∈ 𝔽𝑞 and consists of all the solutions to the equation

𝐸/𝔽𝑞 ∶ 𝑦2 = 𝑥3 + 𝐴𝑥𝑧 4 + 𝐵𝑧 6 . This is the Jacobian form of the curve, and points are defined to be equivalent if there exists a non-zero 𝑟 such that (𝑥 ∶ 𝑦 ∶ 𝑧) ∼ (𝑟2 𝑥 ∶ 𝑟3 𝑦 ∶ 𝑟𝑧). The identity element in this form is 𝒪 = (1 ∶ 1 ∶ 0). We say a point is “affine” if 𝑧 = 1. For a point 𝑃 we write its coordinates as 𝑃 = (𝑥(𝑃 ) ∶ 𝑦(𝑃 ) ∶ 𝑧(𝑃 )). The inverse of a point has inverted 𝑦-coordinate, i.e. 𝑦(−𝑃 ) = −𝑦(𝑃 ). The curve group law can be derived using the divisor class group of the curve. There are many different formulae for computing the sum of two points, but we will use the following. These formulae are not complete and are not well-defined if 𝑃 , 𝑄 = 𝒪 or 𝑃 = ±𝑄. We also assume 𝑧(𝑃 ) = 𝑧(𝑄) = 1, and the full formulae can be obtained by substituting 𝑥 ↦ 𝑥/𝑧 2 and 𝑦 ↦ 𝑦/𝑧 3 , scaling by 𝑧(𝑃 )𝑧(𝑄) subject to Jacobian equivalence. 𝑥(𝑃 + 𝑄) = 𝑥(𝑃 )2 𝑥(𝑄) + 𝑥(𝑃 )𝑥(𝑄)2 − 2𝑦(𝑃 )𝑦(𝑄) + 2𝐵, 𝑦(𝑃 + 𝑄) = 3𝑥(𝑃 )2 𝑦(𝑄)𝑥(𝑄) − 3𝑦(𝑃 )𝑥(𝑃 )𝑥(𝑄)2 + 𝑦(𝑃 )2 𝑦(𝑄), − 𝑦(𝑃 )𝑦(𝑄)2 − 3𝑦(𝑃 )𝐵 + 3𝑦(𝑄)𝐵 𝑧(𝑃 + 𝑄) = 𝑥(𝑃 ) − 𝑥(𝑄). Notice these formulae are biquadratic in (𝑥(𝑃 ), 𝑦(𝑃 )) and (𝑥(𝑄), 𝑦(𝑄)). This allows us to define quadratic equations that add a fixed point to their input.

2.1.1 Complex Multiplication

Since elliptic curves are abelian groups, they admit multiplication by integers. In general, this is the full endomorphism ring of the curve. However, in some cases curves can have larger endomorphism rings which include multiplication by imaginary quadratic integers. For our purposes, the full theory of complex multiplication is not necessary. It is sufficient to observe that in two cases, there are non-trivial linear endomorphisms of a curve. In the first, when 𝐴 = 0 and 𝔽𝑞 has a third root of unity 𝜔, the mapping 𝑃 ↦ (𝜔𝑥(𝑃 ) ∶ 𝑦(𝑃 ) ∶ 𝑧(𝑃 )) is a point on the curve. In the second, when 𝐵 = 0 and 𝔽𝑞 has a fourth root of unity 𝑖, the mapping 𝑃 ↦ (−𝑥(𝑃 ) ∶ 𝑖𝑦(𝑃 ) ∶ 𝑧(𝑃 )) is a point on the curve. Remarkably, these mappings are respect the group law.

2.2 Message Authentication Codes

A MAC is a randomized encoding of some message 𝑚 under randomness consisting of a key k. A MAC Scheme is defined over a message space ℳ, a key space 𝒦, and a MAC space 𝒞. It has a function KeyGen(1𝜆 ) ∈ 𝒦, a function En ∶ 𝒦 × ℳ → 𝒞, and a partial decoding function De ∶ 𝒦 × 𝒞 ⇀ ℳ. For all key ∈ 𝒦, De is the inverse of En on its image: En ∶ 𝒦 × ℳ → 𝒞, De ∶ 𝒦 × 𝒞 ⇀ ℳ, De(key, En(key, 𝑚)) = 𝑚.

Therefore, MACs must be unique per message. A MAC has 𝑡-unforgeability if: given a fixed key key = KeyGen(1𝜆 ), on input 𝑡 valid MACs, all PPT adversaries 𝒜 have at most negligible advantage in 𝜆 of constructing a pair (𝑚, 𝑐) ∈ ℳ × 𝒞 such that 𝑐 = En(key, 𝑚). We say a MAC is hiding if no PPT adversary can distinguish (𝑚0 , 𝑐) and (𝑚1 , 𝑐).

2.2.1 Homomorphic MACs

A homomorphic MAC (HMAC) scheme with security parameter 𝜆 is parameterized over a pair of groups 𝔾, ℍ and two subsets Φ ⊆ Hom(𝔾, ℍ), 𝐾 ⊆ ℍ of size at least 2𝜆 . The message space ℳ = 𝔾, the key space 𝒦 = Φ × 𝐾, and the output space 𝒞 = ℍ. Key generation simply samples uniformly random 𝜙 and 𝑘. We define encoding and decoding to be:

KeyGen(1𝜆 ) ∶= (𝜙, 𝑘) ← 𝒦, En((𝜙, 𝑘), 𝑚) ∶= 𝜙(𝑚) + 𝑘, De((𝜙, 𝑘), 𝑐) ∶= 𝜙−1 (𝑐 − 𝑘).

For 𝔾 = ℍ = 𝔽+ 2𝜆 and natural homomorphisms, this yields the free XOR MAC of free XOR garbling. Similarly, using 𝔾 = ℍ = 𝔽+ we find a MAC that appears implicitly in the randomized encodings of ITPG. We call these MACs homomorphic (indeed they are bilinear) because of the following group homomorphisms:

𝜙 ↦ 𝜙(𝑚) + 𝑘 ∈ Hom(Hom(𝔾, ℍ), ℍ), (𝑚, 𝑘) ↦ 𝜙(𝑚) + 𝑘 ∈ Hom(𝔾 × ℍ, ℍ).

In privacy-free schemes, it is convenient to include the message itself in the MAC, which we do implicitly. Except for the key information passed to the ITPG of the encoding function, all our schemes are privacy-free, and we assume all our MACs also carry the message with them.

2.2.2 Iterated MACs

The simplest variant of homomorphic MACs simply lets Φ = Hom(𝔾, ℍ). For many groups, e.g. of order greater than 2𝜆 , this yields a secure scheme. However, in some cases it is convenient to use a smaller set of homomorphisms. In Argo MAC, this is necessary because we need a set of group homomorphisms that can be evaluated by low-degree polynomials. Using a common trick, found for example in [16], we can decompose a high-entropy 𝜙 into a vector of low-entropy 𝜙𝑖 ’s. Let ℍ = ℍ′𝜅 and using Φ = {𝜙 ∶ 𝜙𝑖 ∈ 𝑆} where 𝑆 ⊂ Hom(𝔾, ℍ′ ) is a small subset of size 𝑑. If we have 𝑑𝜅 ≥ 2𝜆 then |Φ| ≥ 2𝜆 then the set of endomorphisms is still large enough. Generically, given multiple MACs with security levels 𝜆𝑖 over the same value with independent keys, we can concatenate the MACs to construct a MAC with security level ∑𝑖 𝜆𝑖 .

2.3 Garbled Circuits

We use substantially the same syntax as [6], where MACs are randomized encodings of values, and garbled circuits are randomized encodings of functions. We define a garbling scheme with respect to a space of functions ℱ ⊆ 𝒳 → 𝒴 and two MAC schemes In, Out whose message spaces are 𝒳 and 𝒴 respectively. A garbling scheme is parameterized over a key space 𝒦, which includes input and output MAC keys, and a space 𝒢 of garblings. It has three functions:

• KeyGen. This may either be parameterized over the input and output MAC schemes, or generate the input and output MAC keys. • Gb ∶ 𝒦 × ℱ → 𝒢. This accepts a function and a garbling key and returns an element GC ∈ 𝒢. • Ev ∶ 𝒢 × 𝒞In → 𝒞Out . This accepts a garbling and an input MAC and returns an output MAC of the evaluation of 𝐹 on that input: Ev(Gb(𝐾, 𝐹 ), [𝑥]In ) = [𝑦]Out .

When the input and output MAC schemes of two garbling schemes are the same, we can compose these schemes if they use the same keys. However, the security of the resulting scheme is not immediate. In a privacy-free scheme, all the MACs also include the message, which is the case for our garbling schemes.

When ℱ = {id} we call the scheme an “adaptor garbled circuit (scheme)”. These allow switching the key while keeping the message the same, which can be useful when moving between different group representations, and in conjunction with the homomorphic properties of HMACs. This is closely related in free XOR MACs with the notion of half gates, and to the construction of ITPG. A garbling scheme has correctness if Ev always returns a valid MAC of 𝑦 on a valid input MAC. A garbling scheme has authenticity if no PPT adversary can forge an output MAC for a value 𝑦′ ≠ 𝐹 (𝑥) given a garbling GC and a MAC of 𝑥 under the input key. A scheme has privacy if no PPT adversary can, for a garbling of 𝐹0 GC, distinguish (GC, [𝑥], 𝐹0 ) and (GC, [𝑥], 𝐹1 ) where 𝐹0 (𝑥) = 𝐹1 (𝑥). We prove these properties by simulation arguments, i.e. by showing that there exists a simulator that can produce (at least) two views of the evaluator without knowledge of the garbling key, and that distinguishing these distributions is hard.

2.3.1 Randomized Encodings

The notion of randomized encodings is closely to garbling schemes. It transforms a function 𝑓 of inputs 𝑥 ̂ 𝑧; 𝑟). The scheme includes a reconstruction and 𝑧, using some randomness 𝑟, into a randomized encoding 𝑓(𝑥, function Rec which allows the Evaluator to compute 𝑓(𝑥, 𝑧) from this encoding and 𝑥.

̂ 𝑧; 𝑟), 𝑥) = 𝑓(𝑥, 𝑧). Rec(𝑓(𝑥,

Given the randomized encoding and 𝑥, the garbler should not learn any information about 𝑧 apart from ̂ 𝑧; 𝑟) and 𝑓(𝑥, 𝑓(𝑥, 𝑧). Informally, any adversary should not be able to distinguish encodings 𝑓(𝑥, ̂ 𝑧 ′ ; 𝑟′ ) where ′ 𝑓(𝑥, 𝑧) = 𝑓(𝑥, 𝑧 ). We call 𝑥 the “public” input and 𝑧 the “private” input. There is a natural relationship with garbling schemes here. Suppose we split the encoding into offline and online parts: ̂ 𝑧; 𝑟) = (𝑓 ̂ (𝑟), 𝑓 ̂ (𝑥, 𝑧; 𝑟)). 𝑓(𝑥, off on

The first part looks like a garbling table, the second part like the input encoding, and the reconstruction function like Ev. If the function 𝑓 returns a MAC, then this randomized encoding is equivalent to a (partial) garbling scheme. In the language of [11], it is partial because 𝑥 is public to the evaluator. In the case of randomized encodings, purely privacy-free schemes are not interesting since there is only one possible 𝑧. However, if 𝑧 only contains key information about an output MAC, then we recover something like a privacy-free garbling scheme.

2.4 Information Theoretic Partial Garbling

The ITPG protocol [11] is the core component of Argo, so we review it here. The presentation in the paper is general, and in our case we need only a simplification of the protocol for secret evaluation of bivariate, quadratic polynomials. Consider the general bivariate, quadratic polynomial

𝐹 (𝑧; 𝑥, 𝑦) = 𝑧0 + 𝑧1 𝑥 + 𝑧2 𝑦 + 𝑧3 𝑥2 + 𝑧4 𝑥𝑦 + 𝑧5 𝑦2 .

We would like to construct a randomized encoding of this polynomial and reconstruction algorithm which given the encoding and (𝑥, 𝑦) can compute 𝐹 (𝑥, 𝑦) without revealing any information about 𝑧. To do this, we implicitly construct an ABP with edges for the 5 multiplications by 𝑥 or 𝑦 in 𝐹 . We write the encoding as 𝑒 = 𝐹 ̂ (𝑟; 𝑧, 𝑥, 𝑦). We begin by defining the affine encoding of the 𝑧 input as 𝑒𝑖 = 𝑧𝑖 + 𝑟𝑖 for 𝑖 ∈ [0, 5]. Our reconstruction algorithm will multiply each of these values by the corresponding 𝑋, 𝑌 monomial, leaving 𝐹 (𝑧; 𝑥, 𝑦) plus a polynomial in 𝑋, 𝑌 , 𝑟. 𝐹 (𝑒0∶5 ; 𝑥, 𝑦) = 𝐹 (𝑧; 𝑥, 𝑦) + 𝐹 (𝑟0∶5 ; 𝑥, 𝑦). Now, we will start adding encodings of 𝑋 and 𝑌 to cancel this randomness. For example, adding 𝑒6 ∶= −𝑟3 𝑥 + 𝑟6 allows the reconstruction algorithm to cancel the 𝑥2 term, 𝑒7 ∶= −𝑟4 𝑦 + 𝑟7 the 𝑥𝑦 term, and 𝑒8 ∶= −𝑟5 𝑦 + 𝑟8 the 𝑦2 term:

𝐹 (𝑒0∶5 ; 𝑥, 𝑦) − 𝑒6 𝑥 − 𝑒7 𝑥 − 𝑒8 𝑦 = 𝐹 (𝑧; 𝑥, 𝑦) + 𝑟0 + (𝑟1 + 𝑟6 )𝑥 + (𝑟2 + 𝑟7 + 𝑟8 )𝑦.

Adding two more encodings 𝑒9 ∶= −(𝑟1 + 𝑟6 + 𝑟7 )𝑥 + 𝑟9 and 𝑒10 ∶= −(𝑟2 + 𝑟8 )𝑦 − (𝑟0 + 𝑟9 ) allows us to cancel the remaining terms and define the reconstruction function

Rec(𝑒, 𝑥, 𝑦) ∶= 𝐹 (𝑒0∶5 ; 𝑥, 𝑦) − 𝑒6 𝑥 − 𝑒7 𝑦 − 𝑒8 𝑦 − 𝑒9 − 𝑒10 = 𝐹 (𝑧; 𝑥, 𝑦).

It is easy to see, since each term except for the last has a new random value, that the vector 𝑒 is uniformly randomly distributed among vectors such that reconstruction succeeds. In particular, it is independent of 𝑧. For polynomials with fewer non-zero coefficients, like those that occur in our protocol, it is possible to eliminate some of the terms in this reconstruction procedure, like 𝑒5 and 𝑒8 if the polynomial does not have a 𝑦-coordinate. We can interpret this as a garbling scheme and as an input MAC scheme. The input MAC scheme takes the message (𝑥, 𝑦) and outputs the encodings (𝑒6 , ..., 𝑒10 ) and the garble function returns (𝑒0 , ..., 𝑒5 ). These are the offline and online parts of the encoding respectively.

2.4.1 Non-Linear Reconstruction

For our application, we can apply a simplification of this entirely linear reconstruction algorithm since the private inputs are all fixed in advance. We can eliminate the MACs 𝑒0 , ..., 𝑒5 and incoporate the 𝑧 values into the encoding keys:

𝑒5 = 𝑧 5 𝑦 + 𝑟 5 𝑒4 = 𝑧 4 𝑦 + 𝑟 4 𝑒3 = 𝑧 3 𝑥 + 𝑟 3 𝑒2 = (𝑧2 − 𝑟5 )𝑦 + 𝑟2 𝑒1 = (𝑧1 − 𝑟3 − 𝑟4 )𝑥 + 𝑟1 𝑒0 = 𝑧 0 − 𝑟 1 − 𝑟 2

This allows for the simpler reconstruction procedure

Rec(𝑒, 𝑥, 𝑦) = 𝑒1 + 𝑒2 + 𝑒3 𝑥 + 𝑒4 𝑥 + 𝑒5 𝑦.

Again, we see that 𝑒 is uniformly random among vectors that reconstruct the correct value, therefore it is independent of 𝑧. Disappointingly, this does not affect the size of the garbling table very much, since the number of elements in the encoding that depend on 𝑥 and 𝑦 is the same. In this variant, the input MAC scheme simply returns (𝑒1 , ..., 𝑒5 ) and the garble function returns the empty string.

2.5 Half Gates

We adapt the half gate technique [23] to reduce the size of adaptor tables for bits. The simplest construction of an adaptor table using the Yao style technique is constructed from a symmetric encryption algorithm ℰ. Given an input MAC scheme and an output MAC scheme, the garbling table simply stores encryptions of the outputs under the input MACs as keys

GC = (ℰ([0]In , [0]Out ), ℰ([1]In , [1]Out )).

The half gate technique modifies the output MAC by replacing one of these ciphertexts with a hash. We define [0]Out = ℋ([0]In ) and just store the encryption of 1, GC = (ℰ([1]In , [1]Out )). In the privacy-free setting, the Evaluator knows the message, and so can choose whether to hash or decrypt

ℋ([𝑥]In ) 𝑥=0 Ev(GC, [𝑥]In ) = { 𝒟([𝑥]In , GC1 ) 𝑥 = 1.

Proving the security of this scheme with different input MAC schemes is non-trivial, in particular when used with free XOR [12]. In our application, we can choose the input MAC values to be independently, uniformly random, simplifying the security analysis. We only require that ℋ([𝑥]In ) be suitable for use with ITPG: that is, its output should be indistinguishable from random by any PPT adversary.

3 Argo MAC

The Argo MAC protocol is a garbling scheme for the function that takes as input the bits of two field elements (𝑥, 𝑦), and returns a curve point 𝑃 = (𝑥, 𝑦) ∈ 𝔾 if they are its affine Weierstrass coordinates, but fails otherwise. While both the input and output are encodings of the same curve point, they are different objects living in different groups.

𝑓argo ∶ 𝔽𝜌2 × 𝔽𝜌2 ⇀ 𝔾 (𝑥, 𝑦) (𝑥, 𝑦) ∈ 𝔾 𝑓argo (bits(𝑥), bits(𝑦)) = { . ⊥ otherwise

Note that the input may be poorly formed: for example, the coordinates may not be a curve point, in which case the function returns ⊥. We can also perform additional input validation, testing that 𝑥 and 𝑦 are valid field elements and that 𝑃 ∈ 𝔾. As we will see later, this is not strictly necessary. The input MAC scheme is constructed from any MAC scheme for bits, where each bit is encoded under a different, unrelated key. The output MAC scheme is an HMAC where 𝔾 = 𝐸/𝔽𝑝 and ℍ = 𝔾𝜅 . We choose our set Φ such that 𝜙 ∈ Φ if 𝜙𝑖 (𝑃 ) is a degree 1 endomorphism of 𝐸. In general this means 𝜙𝑖 (𝑃 ) = 𝒪 or 𝜙𝑖 (𝑃 ) = 𝑃 , but when 𝐸 has CM discriminant −3 or −4 this can include more functions, resp. 7 and 5. Let the number of degree 1 endomorphisms be 𝑑 and let 𝜅 > 𝜆/ log2 𝑑. This ensures |Φ| = 𝑑𝜅 > 2𝜆 . To implement this garbling scheme, we split the function into two parts: the output MAC encode function, and input validation.

3.1 Encode

The HMAC encode function naturally splits as 𝜅 many independent functions, each computing [𝑃 ]𝑖 = 𝜙𝑖 (𝑃 ) + 𝐾𝑖 . Let 𝕂 = 𝔽𝑝 (𝐸) be the function field of the curve. We drop the 𝑖 subscript for now and consider a single component of the MAC. Recall that for Weierstrass curves, this function can be written using three quadratic polynomials 𝑓𝑥 , 𝑓𝑦 , 𝑓𝑧 ∈ 𝕂[𝑋, 𝑌 ] such that for all 𝐾 and any 𝑃 ∉ {𝐾, 𝒪},

𝑓𝑥 (𝑥(𝑃 ), 𝑦(𝑃 )) 𝑓𝑦 (𝑥(𝑃 ), 𝑦(𝑃 )) 𝜙(𝑃 ) + 𝐾 = ( , ). 𝑓𝑧 (𝑥(𝑃 ), 𝑦(𝑃 ))2 𝑓𝑧 (𝑥(𝑃 ), 𝑦(𝑃 ))3

These polynomials return the Jacobian coordinates of the result, so for any 𝑟 ∈ 𝔽× 𝑝 the polynomials (𝑟 𝑓𝑥 , 𝑟3 𝑓𝑦 , 𝑟𝑓𝑧 ) yield the same point up to equivalence. For each of 𝑣 ∈ {𝑥, 𝑦, 𝑧} we can decompose 𝑓𝑣 into a 2 (𝜙) sum of at most 𝑛𝑣 products of coefficients 𝑐𝑣,𝑗 ⃗ ∈ 𝕂[𝑟] and monomials 𝑚⃗ 𝑣,𝑗 ∈ 𝔽[𝑋, 𝑌 ], where 𝑗 ∈ [𝑛𝑣 ]. Define ⃗ ⃗ (𝜙) the generic 𝐹 (𝐶 ; 𝑋, 𝑌 ) ∈ 𝔽 [𝐶 , 𝑋, 𝑌 ] such that 𝑓 (𝑋, 𝑌 ) = 𝐹 (𝑐𝑣⃗ (𝑟, 𝐾); 𝑋, 𝑌 ). Concretely 𝑣 𝑣 𝑝 𝑣 𝑣 𝑣

𝐹𝑥 (𝐶𝑥⃗ , 𝑋, 𝑌 ) = 𝐶𝑥,0 + 𝐶𝑥,1 𝑋 + 𝐶𝑥,2 𝑌 + 𝐶𝑥,3 𝑋 2 𝐹 (𝐶 ⃗ , 𝑋, 𝑌 ) = 𝐶 + 𝐶 𝑌 + 𝐶 𝑋 2 + 𝐶 𝑋𝑌 + 𝐶 𝑦 𝑦 𝑦,0 𝑦,1 𝑦,2 𝑦,3 𝑥,4 𝑌 2

𝐹𝑧 (𝐶𝑧⃗ , 𝑋, 𝑌 ) = 𝐶𝑧,0 + 𝐶𝑧,1 𝑋.

Because the endomorphisms are always linear, this is the same degree and shape of polynomials as Jacobian point addition. The key observation is that 𝐹𝑣 is linear in the coefficient variables and that all the secret information about the key is encoded into these variables. Therefore, we can apply ITPG to the function 𝐹𝑣 to construct (𝜙) (𝜙) a randomized encoding 𝐹𝑣̂ (𝑐𝑣⃗ (𝑟, 𝐾), 𝑥(𝑃 ), 𝑦(𝑃 )) that hides the 𝑐𝑣⃗ (𝑟, 𝐾) and still allows the evaluator to compute [𝑃 ]. For curves in Weierstrass form, the total number of edges in the ABPs for 𝑓𝑥 , 𝑓𝑦 , 𝑓𝑧 is 9. Using the same technique as in the original paper, we can lift 𝐹𝑣 from polynomials in the coordinates of the curve points to polynomials in the bits of the coordinates as follows: 𝜌−1 𝜌−1 𝐺𝑣 (𝐶𝑣⃗ ; 𝑋,⃗ 𝑌 ⃗ ) = 𝐹𝑣 (𝐶𝑣⃗ , ∑ 𝑋𝑗 2𝑗 , ∑ 𝑌𝑗 2𝑗 ). 𝑗=0 𝑖=0

The scheme then yields a randomized encoding of 𝐺𝑣 that consists entirely of affine functions of the variables 𝑋⃗ and 𝑌 ⃗ , which is equivalently an HMAC where 𝔾 = (𝔽+ 𝑝) 2𝜌 and ℍ = (𝔽+ 9𝜌 𝑝 ) . For a suitably defined MAC key and input 𝑃 ∈ 𝐸 we therefore have (𝜙 ) 𝐺𝑣̂ (𝑐𝑣⃗ 𝑖 (𝑟𝑖 , 𝐾𝑖 ); bits(𝑥(𝑃 )), bits(𝑦(𝑃 ))) = 𝑣([𝑃 ]𝑖 ).

We can further concatenate all these HMACs across all 𝑖 ∈ [𝜅] to construct a single HMAC from 𝔾 to ℍ = (𝔽𝑝 )9𝜌𝜅 . Equivalently, we have 2𝜌 HMACs, one for each bit of input. The HMACs for the bits of 𝑥 map to 5𝜌𝜅 field elements and the HMACs for the bits of 𝑦 to 4𝜌𝜅.

3.1.1 Using Half Gates

To complete the GC, we simply need an adaptor table from the input MAC to this HMAC for the message space ℳ = {0, 1}. Using the half-gate technique, this requires one ciphertext per component of ℍ, or 9𝜌2 𝜅 bits. For a curve over a 256-bit field with CM discriminant −3 and security level 128, this comes to about 3.6MB. This yields a correct protocol because for each encoding of a value, the constant term in the affine function is of the form 𝑟𝑖 , that is an independent random value. Thus, we can use ℋ to generate these values. One term in the reconstruction does not have a constant term of this form, but that element of the encoding does not depend on the input.

3.2 Validation

There are three components to input validation: (1) checking that the coordinates of the curve point are valid field elements, (2) checking that the coordinates form a valid curve point, and (3) checking that the curve point lies in 𝔾. All of these need only be done once, not replicated 𝜅 times like the encode function, and therefore contribute very little to the overall cost of the scheme. There is an interesting subtlety in (1) and (3) since it is not a priori defined what it means to be an invalid field element or element of the subgroup. We can define both of these as equivalence classes over a larger set, and we could choose to define all elements of the larger set as valid and simply quotient by the equivalence class. Alternatively, and more commonly, we could require that the input be a canonical representative of the equivalence class. In either case, there is no sensible way to quotient an arbitrary pair of field elements to a curve point, so condition (2) can always fail.

3.2.1 Field Element Validity

Normalization. The 𝔽+ 𝑝 MACs naturally quotient alternative bit representations for the same field element, so this happens for free. We simply compute a power of 2 linear combination of MACs, which always yields the same result since the MACs are 𝔽 linear.

Canonicity. We can use an existing garbling scheme to evaluate a LessThan circuit on the input and the field characteristic. This is a very small circuit with one AND gate per bit. There are many candidates, but privacy-free half gates with free XOR yields the smallest circuit. If the circuit fails we reveal the MAC of ⊥.

3.2.2 Curve Point Validity

A curve point is valid if and only if it is a solution to the curve equation, which in Weierstrass form is 𝑦2 = 𝑥3 + 𝐴𝑥 + 𝐵. To check curve point validity, we can reuse the ITPG scheme for leaking a secret if a polynomial equation is not satisfied. That is, for a secret 𝑠 apply the scheme to the polynomial

𝑓curve (𝑋, 𝑌 ) = (𝑋 3 + 𝐴𝑋 + 𝐵 − 𝑌 2 )𝑠.

After using ITPG, we divide the result by 𝑋 3 + 𝐴𝑋 + 𝐵 − 𝑌 2 if the curve point is non-zero. We can let 𝑠 = [⊥] or use an adaptor table to reveal the MAC of ⊥ given 𝑠.

3.2.3 Subgroup Membership

Normalization. Let ℎ be the cofactor of the elliptic curve: that is, #𝐸/𝔽𝑝 = 𝑟ℎ. Every curve point decomposes uniquely as 𝑃 = 𝑅 + 𝐻 where 𝑟𝑅 = ℎ𝐻 = 𝒪. Let 𝑅 be the unique representative of the equivalence class 𝐸 quotiented by the ℎ order subgroup. Let 𝑐 be the unique integer in [0, 𝑟ℎ − 1] such that 𝑐 = 0 mod ℎ and 𝑐 = 1 mod 𝑟. Multiplying, 𝑐𝑃 = 𝑅. Therefore, if 𝐾 is in 𝔾, we can compute a MAC of the normalized point 𝑃 by multiplying by 𝑐,

𝑐[𝑃 ] = 𝜙(𝑅) + 𝐾.

Canonicity. To efficiently test whether 𝑃 ∈ 𝔾, let 𝔾′ = 𝐸[ℎ] be the cofactor group not including 𝒪. We must choose Φ such that for 𝑄 ∈ 𝔾′ /𝒪, 𝜙 ↦ 𝜙(𝑄) is injective. This constrains the possible Φ based on the factors of the cofactor. For example, if 2 ∣ ℎ then Φ = {0, 1}𝜅 is the only possible choice. If gcd(ℎ, 12) = 1 then we can always use the full CM endomorphism set. Observe that if 𝑃 ∉ 𝔾, then 𝑃 = 𝑅 + 𝐻 for non-zero 𝐻, and that [𝑃 ]𝑖 = [𝑅]𝑖 + 𝜙(𝐻). Multiplying by 𝑟, we find 𝑟[𝑃 ]𝑖 = 𝜙𝑖 (𝑟𝐻). Since evaluation by 𝜙𝑖 is invertible in the cofactor group, except on zero, we can solve the discrete log and compute 𝜙 if and only if 𝐻 ≠ 𝒪. Therefore, if 𝑃 ∉ 𝔾 we leak 𝜙 and if 𝑃 ∈ 𝔾 we do not leak 𝜙. This does not require any modifications to the garbling table. Again, we can use an adaptor table to leak [⊥] given 𝜙.

3.3 Incomplete Addition Formulas

Recall that Jacobian point addition formulae are incomplete. When we evaluate 𝑃 + 𝑃 , the formulae will return the non-curve point value (0 ∶ 0 ∶ 0). They are also incomplete for the point at infinity, but it is not possible to encode this as an affine point. So, if 𝜙(𝑃 ) = 𝐾, simply evaluating the polynomials will fail to return a valid curve point, so the MAC is not well defined. In applications related to BitVM and Glock, the Garbler is able to freely choose the input point. This means a malicious Garbler could maliciously cause the scheme to output an invalid curve point. To solve this, we augment the Jacobian addition formulae with an additional term 𝑢𝑖 𝑥(2𝑃 ). The value 𝑢𝑖 is 1 if 𝑃 = 𝜙−1 (𝐾) and zero otherwise. We can compute this using an equality circuit between 𝑥(𝑃 ) = 𝑥(𝜙−1 (𝐾)) and the top bits of 𝑦(𝑃 ) and 𝑦(𝜙−1 (𝐾)). If the points are equal, we learn a secret that allows us to learn an ITPG encoding of 𝑔 = 1. Otherwise, we learn a secret that allows us to learn the encoding of 𝑔 = 0. We can use a simple Yao-style garbling scheme for this step. The updated functions to garble are

𝑓𝑣′ (𝑃 ) = 𝑓𝑣 (𝑃 ) + 𝑔𝑣(2𝑃 ).

In many applications the Garbler has freedom to choose which points to MAC. For example, in a SNARK verifier the points are likely distributed uniformly at random, so the probability of a failure occurring is negligible. In that case, it may be sufficient to simply leak a secret directly if a failure occurs, as it can only happen with a malicious Garbler. This does not even require a Yao-style garbling table for equality. We can leak a secret directly by hashing the input labels and computing their XOR . If points are equal, then the resulting value can be used to decrypt a secret. Otherwise, the Evaluator learns nothing.

3.4 Protocol

Argo MAC Output MAC Scheme 1. Let 𝐸 be an elliptic curve and 𝑆 the set of 𝑑 endomorphisms of degree 1

2. Let 𝜅 = 2𝜆 / log2 𝑑 3. 𝔾 = 𝐸 ℍ = 𝔾𝜅 4. 𝐾 = ℍ Φ = {𝜙 ≠ 0 ∶ 𝑖 ∈ [𝜅], 𝜙𝑖 ∈ 𝑆} ⊂ Hom(𝔾, ℍ) 5. En((𝜙, 𝐾), 𝑃 ) = 𝜙(𝑃 ) + 𝐾

3. Note since 𝜙 ≠ 0 the decode function will always have at least one entry 𝑗 where 𝜙𝑗 ≠ 0

𝜙−1 ([𝑃 ]𝑗 − 𝐾𝑗 ) ∀𝑖 ∶ [𝑃 ]𝑖 = 𝜙𝑖 (𝑃 ) + 𝐾𝑖 De((𝜙, 𝐾), [𝑃 ]) = { 𝑗 ⊥ otherwise.

Argo MAC Garbling Scheme 1. Let PRG be a pseudorandom generator 2. Let ℋ(𝑥) = PRG(𝑥) and ℰ(𝑘, 𝑚) = 𝑚 + PRG(𝑘) 3. Let LT𝑥 be a garbling scheme for the function 𝑦 ↦ 𝑦 < 𝑥 4. In the case of extension fields, let LT𝑥 apply component-wise 5. Let EQ𝑥 be a garbling scheme for the function 𝑦 ↦ 𝑦 = 𝑥 6. Let the garbling key be: a) All the input MAC keys b) All the GC keys for EQ and LT c) (𝑟𝑖 , 𝜙𝑖 , 𝐾𝑖 ) for all 𝑖 ∈ 𝜅. d) The value [⊥]. Garble 1. Construct a GC for LT𝑞 for each input scalar. 2. Construct a GC for EQ for each 𝑥(𝐾𝑖 ), bit𝜌−1 (𝑦(𝐾𝑖 )).

3. Adaptor tables from input bits and outputs of EQ𝑥 to (𝔽+ 𝑝) (9𝜌+1)𝜅

4. Use the output MAC scheme from the adaptor tables in the ITPG encoding for the encoding function and 𝑓curve 5. Use [⊥] as 𝑠 in 𝑓curve 6. The garbled circuit includes a) The tables for EQ and LT b) Adaptor table from LT to [⊥] c) Adaptor tables from EQ to the encoding for 𝑓argo d) Adaptor tables from input to the encoding for 𝑓argo e) Adaptor tables from input to the encoding for 𝑓curve Evaluate 1. Evaluate the LT circuits and if any return 0 use the associated adaptor table to derive [⊥] 2. Evaluate the EQ circuits to derive encodings of 𝑔𝑖 for 𝑖 ∈ 𝜅. 3. Use the appropriate adaptor tables to derive the input encoding for 𝑓argo and 𝑓curve . 4. If the input point is not a valid curve point, reconstruct the output of 𝑓curve which is [⊥]. 5. Reconstruct all the [𝑃 ]𝑖 . 6. If 𝑃 ∉ 𝔾 clear the 𝔾 part and find 𝜙. Use the appropriate adaptor table to derive [⊥]. 7. Otherwise, return [𝑃 ].

3.5 Security

Essentially all of the components of Argo MAC already have security proofs. In fact, the ITPG paper has a verifiable computation protocol very similar to ours. The only non-trivial things to prove are that randomizing the Jacobian equivalence class is secure, and that using ITPG with half gates is secure. We would like to use the randomness generated by a hash function ℋ in the half gates as the randomness for ITPG. The security of this follows almost immediately by assumption that the output of ℋ is indistinguishable from pseudorandom if we do not know the input to the function. For practical efficiency, we use AES to instantiate this function. In practice, we also assume that the garbler has given a commitment to the input labels to the Evaluator. This is necessary for BitVM-style protocols on Bitcoin and can be instantiated with a collision-resistant, one-way function. However, this is outside the scope of this paper.

3.5.1 Jacobian Coordinates Proof

While the ITPG scheme ensures that an adversary cannot learn any information about 𝑧 from the encoding, it is important to show that the function itself does not reveal any information about the MAC key. As a strawman, observe that if we do not randomize up to Jacobian equivalence, the output can leak information about the key. Suppose 𝜙 = 0, in which case if 𝑓𝑧 (𝑃 ) = 1. Now suppose 𝜙 ≠ 0, in which case 𝑓𝑧 (𝑃 ) = 𝑥(𝑃 ) − 𝑥(𝐾) ≠ 0 with high probability. Therefore, naively applying the ITPG protocol to this function would leak 𝜙 with high probability. To show security, we show that for any non-zero input 𝑃 , output triple (𝑥 ∶ 𝑦 ∶ 𝑧), and any 𝜙, there exists a pair (𝑟, 𝐾) such that 𝑥 = 𝑟2 𝑓𝑥 (𝑃 ) 𝑦 = 𝑟3 𝑓𝑦 (𝑃 ) 𝑧 = 𝑟𝑓𝑧 (𝑃 ). Take the point 𝑅 = (𝑥 ∶ 𝑦 ∶ 𝑧). Now, let 𝐾 = 𝑅 − 𝜙(𝑃 ) and compute the non-randomized coefficients using (𝜙, 𝐾) 𝑥′ = 𝑓𝑥 (𝑃 ) 𝑦′ = 𝑓𝑦 (𝑃 ) 𝑧 ′ = 𝑓𝑧 (𝑃 ). Because of the group law, we know that (𝑥′ ∶ 𝑦′ ∶ 𝑧 ′ ) ∼ (𝑥, 𝑦, 𝑧) and therefore there exists some 𝑟 ≠ 0 such that 𝑥 = 𝑟2 𝑥′ , 𝑦 = 𝑟3 𝑦′ , 𝑧 = 𝑟𝑧 ′ . Therefore, there exists exactly one (𝑟, 𝐾) for each ((𝑥 ∶ 𝑦 ∶ 𝑧), 𝑃 , 𝜙). Symmetrically, for uniformly random (𝑟, 𝜙, 𝐾) the value [𝑃 ] is uniformly randomly distributed among (𝑥 ∶ 𝑦 ∶ 𝑧) satisfying the curve equation. Equivalently, it is a random element of a random equivalence class and therefore [𝑃 ] is independent of the key.

3.5.2 Overall Proof

We prove security of the overall protocol using a simulation-based argument for authenticity, in the syntax of [6]. This is the only property we care about because the scheme is privacy-free. The simulator will take as input a curve point 𝑃 and a randomness oracle RNG, and it will output an input encoding and a garbled circuit. The simulator will execute the garbling procedure as specified, but will generate the unopened branch using RNG. If RNG = PRG, then the resulting GC will be from the same distribution as valid garbled circuits. If RNG ≠ PRG is a true random number generator, then the resulting distribution will be uniformly random among all circuits. This is because the adaptor tables consist only of PRG(ℓ𝑏 ) + RNG(ℓ1−𝑏 ). Suppose there exists a PPT adversary that can distinguish these two cases with non-negligible advantage. Then, we can build a distinguisher for PRG from real randomness using the adversary. This distinguisher will succeed with advantage equal to that of the adversary, which is non-negligible. This is impossible by assumption on the PRG and therefore 𝒜 cannot exist. Therefore, the distribution of real ([𝑥], GC) is indistinguishable from uniformly random and is independent of the garbling key. We apply the same argument to show that all adaptor tables generated during garbling are independent of the garbling key. Note that the tables we use for gluing the LessThan circuit and secret revelation are half-gate tables, so the proof is simpler. To argue for the overall security of the scheme, we only need to invoke the authenticity property of the LessThan circuit used for input validation. If this scheme allows setting the output MAC key during garbling, we can sample it ourselves and we are done. If it does not, we can use the output MAC key chosen by the LessThan scheme and let [⊥]argo = [0]lt .

4 Performance

We implemented Argo MAC in under 2500 lines of code, using finite field and elliptic curve primitives from the popular arkworks [32] Rust cryptography library. In Table 1, we report garbling times, evaluation times, and table sizes for Argo MAC instantiated over both 𝔾1 and 𝔾2 groups of the BN254 curve. 𝜅𝐴 and 𝜅𝐵 are defined as 𝜅𝐴 = 𝜌/ log2 (𝑑), 𝜅𝐵 = 𝜆/ log2 (𝑑). Our implementation uses 𝜆 = 128, 𝜌 = 256, 𝑑 = 7.

Group 𝜅 Garbling (ms) Evaluation (ms) Table size (MB) 𝔾1 𝜅𝐴 45 22 7.1 𝔾2 𝜅𝐵 72 37 13.9 𝔾1 𝜅𝐵 23 11 3.6

Table 1: Garbling times, evaluation times, and table sizes for 𝔾1 and 𝔾2 elements. These benchmarks were run single-threaded, on a machine with an Apple M4 chip and 24GB RAM. Since Argo MAC is the dominant cost in the table size of the full Groth16 verifier garbling scheme, these benchmarks allow us to make a preliminary estimate of the full scheme’s table size. Recall that a Groth16 proof consists of (𝐴, 𝐵, 𝐶, 𝑥) ∈ (𝔾1 , 𝔾2 , 𝔾1 , 𝔽𝑞 ). Due to the structure of the pairing gadget in the full scheme, we will use 𝜅𝐴 for 𝐴, and 𝜅𝐵 for 𝐵, 𝐶, giving us a Groth16 verifier garbling table of size roughly 25MB.

Acknowledgements Thanks to Alpen Labs for supporting the first author’s research on precursors to this scheme. Thanks to the Babylon Labs team for conversations about the scheme.

References [1] Satoshi Nakamoto. Bitcoin: A Peer-to-Peer Electronic Cash System. 2008. url: https://bitcoin. org/bitcoin.pdf. [2] Robin Linus. BitVM: Compute Anything on Bitcoin. 2023. url: https://bitvm.org/bitvm.pdf. [3] Lukas Aumayr et al. BitVM: Quasi-Turing Complete Computation on Bitcoin. Cryptology ePrint Archive, Report 2024/1995. 2024. url: https://eprint.iacr.org/2024/1995. [4] Robin Linus et al. Bridging Bitcoin to Second Layers via BitVM2. Cryptology ePrint Archive, Report 2025/1158. 2025. url: https://eprint.iacr.org/2025/1158. [5] Liam Eagen. Glock: Garbled Locks for Bitcoin. Cryptology ePrint Archive, Report 2025/1485. 2025. url: https://eprint.iacr.org/2025/1485. [6] Mihir Bellare, Viet Tung Hoang, and Phillip Rogaway. Foundations of Garbled Circuits. Cryptology ePrint Archive, Report 2012/265. 2012. url: https://eprint.iacr.org/2012/265. [7] Andrew C. Yao. “How to Generate and Exchange Secrets”. In: 27th Annual Symposium on Foundations of Computer Science (FOCS). doi: 10.1109/SFCS.1986.25. [8] Benny Applebaum, Yuval Ishai, and Eyal Kushilevitz. How to Garble Arithmetic Circuits. Cryptology ePrint Archive, Report 2012/255. 2012. url: https://eprint.iacr.org/2012/255. [9] Marshall Ball et al. New Ways to Garble Arithmetic Circuits. Cryptology ePrint Archive, Report 2023/501. 2023. url: https://eprint.iacr.org/2023/501. [10] David Heath. Efficient Arithmetic in Garbled Circuits. Cryptology ePrint Archive, Report 2024/139. 2024. url: https://eprint.iacr.org/2024/139. [11] Yuval Ishai and Hoeteck Wee. Partial Garbling Schemes and Their Applications. Cryptology ePrint Archive, Report 2014/995. 2014. url: https://eprint.iacr.org/2014/995. [12] Vladimir Kolesnikov and Thomas Schneider. “Improved Garbled Circuit: Free XOR Gates and Applications”. In: Automata, Languages and Programming, 35th International Colloquium, ICALP 2008. doi: 10.1007/978-3-540-70583-3_40.

[13] Jae Hyun Ahn et al. Computing on Authenticated Data. Cryptology ePrint Archive, Report 2011/096. 2011. url: https://eprint.iacr.org/2011/096. [14] Rosario Gennaro and Daniel Wichs. Fully Homomorphic Message Authenticators. Cryptology ePrint Archive, Report 2012/290. 2012. url: https://eprint.iacr.org/2012/290. [15] Hanlin Liu et al. BitGC: Garbled Circuits with 1 Bit per Gate. Cryptology ePrint Archive, Report 2024/1988. 2024. url: https://eprint.iacr.org/2024/1988. [16] Yuval Ishai, Hanjun Li, and Huijia Lin. Succinct Homomorphic MACs from Groups and Applications. Cryptology ePrint Archive, Report 2024/2073. 2024. url: https://eprint.iacr.org/2024/2073. [17] Yuval Ishai, Hanjun Li, and Huijia Lin. A Unified Framework for Succinct Garbling from Homomorphic Secret Sharing. Cryptology ePrint Archive, Report 2025/442. 2025. url: https://eprint.iacr.org/ 2025/442. [18] Hanjun Li, Huijia Lin, and George Lu. Succinct Garbled Circuits with Low-Depth Garbling Algorithms. Cryptology ePrint Archive, Report 2025/2308. 2025. url: https://eprint.iacr.org/2025/2308. [19] Robin Linus. Optimizing On-Chain Costs for Publishing Proofs in BitVM-Style Bridges. 2025. url: https://gist.github.com/RobinLinus/0fc7405ad7485c35465efb7996a7b014. [20] Harry A. Kalodner et al. “Arbitrum: Scalable, private smart contracts”. In: USENIX Security 2018. url: https://www.usenix.org/conference/usenixsecurity18/presentation/kalodner. [21] Jens Groth. On the Size of Pairing-based Non-interactive Arguments. Cryptology ePrint Archive, Report 2016/260. 2016. url: https://eprint.iacr.org/2016/260. [22] Michel Dellepere, Pratyush Mishra, and Alireza Shirzad. Garuda and Pari: Faster and Smaller SNARKs via Equifficient Polynomial Commitments. Cryptology ePrint Archive, Report 2024/1245. 2024. url: https://eprint.iacr.org/2024/1245. [23] Samee Zahur, Mike Rosulek, and David Evans. Two Halves Make a Whole: Reducing Data Transfer in Garbled Circuits using Half Gates. Cryptology ePrint Archive, Report 2014/756. 2014. url: https: //eprint.iacr.org/2014/756. [24] BitVM Alliance. Garbled SNARK Verifier (BitVM). 2025. url: https://github.com/BitVM/garbledsnark-verifier. [25] Andrew Ong. ZeroGC: A Garbled Circuit Scheme for BitVM3 with Zero Ciphertext per Gate. 2025. url: https://hackmd.io/@bitlayer/BJEieeTSeg. [26] Ariel Futoransky et al. OHMG: One hot modular garbling. Cryptology ePrint Archive, Paper 2025/2338. 2025. url: https://eprint.iacr.org/2025/2338. [27] Babylon Labs. url: https://babylonlabs.io. [28] Sanjam Garg et al. A Framework for Witness Encryption from Linearly Verifiable SNARKs and Applications. Cryptology ePrint Archive, Report 2025/1364. 2025. url: https://eprint.iacr.org/ 2025/1364. [29] Paulo S. L. M. Barreto and Michael Naehrig. Pairing-Friendly Elliptic Curves of Prime Order. Cryptology ePrint Archive, Report 2005/133. 2005. url: https://eprint.iacr.org/2005/133. [30] Paulo S. L. M. Barreto, Ben Lynn, and Michael Scott. Constructing Elliptic Curves with Prescribed Embedding Degrees. Cryptology ePrint Archive, Report 2002/088. 2002. url: https://eprint.iacr. org/2002/088. [31] Lawrence C. Washington. Elliptic Curves: Number Theory and Cryptography. 2nd. Chapman and Hall/CRC, 2008. [32] arkworks contributors. arkworks zkSNARK ecosystem. url: https://github.com/arkworks-rs/.