International Association
for Cryptologic Research

Witness Encryption (WE) is a powerful cryptographic primitive, enabling applications that would otherwise appear infeasible. While general-purpose WE requires strong cryptographic assumptions, and is highly inefficient, recent works have demonstrated that it is possible to design special-purpose WE schemes for targeted applications that can be built from weaker assumptions and can also be concretely efficient. Despite the plethora of constructions in the literature that (implicitly) use witness encryption schemes, there has been no systematic study of special purpose witness encryption schemes.

In this work we make progress towards this goal by designing a modular and extensible framework, which allows us to better understand existing schemes and further enables us to construct new witness encryption schemes. The framework is designed around simple but powerful building blocks that we refer to as "gadgets". Gadgets can be thought of as witness encryption schemes for small targeted relations (induced by linearly verifiable arguments) but they can be composed with each other to build larger, more expressive relations that are useful in applications. To highlight the power of our framework we methodically recover past results, improve upon them and even provide new feasibility results.

The first application of our framework is a Registered Attribute-Based Encryption Scheme [Hohenberger et al. (Eurocrypt 23)] with linear sized common reference string (CRS). Numerous Registered Attribute-Based Encryption (R-ABE) constructions have introduced though a black-box R-ABE construction with a linear--in the number of users--CRS has been a persistent open problem, with the state-of-the-art concretely being N^{1.58} (Garg et al. [GLWW, CRYPTO 24]). Empowered by our Witness Encryption framework we provide the first construction of black-box R-ABE with linear-sized CRS. Our construction is based on a novel realization of encryption for DNF formulas that leverages encryption for set membership.

Our second application is a feasibility result for Registered Threshold Encryption (RTE) with succinct ciphertexts. RTE (Branco et al. [ASIACRYPT 2024] is an analogue of the recently introduced Silent Threshold Encryption (Garg et al. [GKPW, CRYPTO 24]) in the Registered Setting. We revisit Registered Threshold Encryption and provide an efficient construction, with constant-sized encryption key and ciphertexts, that makes use of our WE framework.

Adaptor signatures extend the functionality of digital signatures by enabling the computation of pre-signatures on messages relative to statements in NP relations. Pre-signatures are publicly verifiable objects that simultaneously hide and commit to a standard signature on the same message. Anyone possessing a valid witness for the statement can adapt the pre-signature into a full signature under the underlying signature scheme. Since adaptor signatures are commonly used as building blocks in larger systems—such as blockchain protocols—it is natural to seek a security definition within the Universal Composability (UC) framework. A recent attempt by Tairi et al. (CCS'23) introduced the first UC functionality for adaptor signatures.

This paper makes both negative and positive contributions. On the negative side, we show that the functionality proposed by Tairi et al. suffers from critical limitations: - The functionality fails to guarantee extractability and adaptability—the core security properties of adaptor signatures—to higher-level protocols. - No adaptor signature scheme can realize the functionality.

On the positive side, we propose a new UC functionality that faithfully captures the latest security guarantees of adaptor signatures as formalized via game-based notions by Gerhart et al. (EUROCRYPT'24). - Our functionality guarantees extractability, unique extractability, and pre-signature adaptability in a way that is composable and meaningful for higher-level protocols. - We show that it is realizable by an enhanced Schnorr-based adaptor signature scheme that we construct. Our construction maintains compatibility with existing infrastructure and is efficient enough for practical deployment, particularly in Bitcoin-like environments.

In the last few years, the old idea of internal perturbation for multivariate schemes has been resurrected. A form of this method was proposed with application to HFE and UOV and independently by another team for application to Rainbow. Most recently, a newer and more efficient version of internal perturbation was proposed as an enhanced measure for securing HFE for encryption.

This efficient method, known as the LL' construction, is designed to add little complexity to HFE decryption while increasing the rank of the resulting map to resist the now very effective cryptanalyses powered by MinRank. The basic idea of the construction is to have two small lists of binary linear forms which when multiplied produce rank $1$ quadratic forms. Random linear combinations of these products are then added to each of the HFE equations, resulting in a masked HFE. The main trick to make the scheme usable is to encrypt an send many random messages so that statistically it is likely that the legitimate user can find a ciphertext that is not perturbed by the construction and which may be decrypted as a plain HFE ciphertext.

We show that this approach is not secure. In particular, we present a method to recover the noise support, a collection of quadratic forms spanning the set of LL' quadratic forms. We then are able to filter out the effect of these maps to recover a compatible HFE map. Finally, we are able to complete the key recovery, achieving efficiently an equivalent private key.

We analyze Kaneko's bound to prove that, away from the $j$-invariant $0$, edges of multiplicity at least three can occur in the supersingular $\ell$-isogeny graph $\mathcal{G}_\ell(p)$ only if the base field's characteristic satisfies $p < 4\ell^3$. Further we prove a diameter bound for $\mathcal{G}_\ell(p)$, while also showing that most vertex pairs have a substantially smaller distance, in the directed case; this bound is then used in conjunction with Kaneko's bound to deduce that the distance of $0$ and $1728$ in $\mathcal{G}_\ell(p)$ is at least one fourth of the graph's diameter if $p \equiv 11 \mathrel{\operatorname{mod}} 12$. We also study other phenomena in $\mathcal{G}_\ell(p)$ with Kaneko's bound and provide data to demonstrate that the resulting bounds are optimal; for one of these bounds we investigate the connection between loop multiplicities in isogeny graphs and the factorization of the `diagonal' classical modular polynomial $\Phi_\ell(X,X)$ in positive characteristic.

A private set operation (PSO) scheme [Rafiee, Comput. J. 2020] is a cryptographic primitive that enables a user to securely outsource their dataset to cloud storage, and then when needed, securely issue common set operation queries to the server and receive the results. In [Rafiee, Comput. J. 2020], the only security notion of the PSO schemes, named naSIM, is proposed. This security notion models a weak attacker who is far from the threats of practical environments, and providing stronger security notions has been raised as an open problem. In this paper, we propose a new security notion for the PSO schemes, called aIND, and show that this concept is stronger than naSIM. Furthermore, we propose a new PSO construction that satisfies the security notion aIND. We also show that our construction does not increase the computational and storage overheads compared to other existing constructions, despite covering a much higher level of security.

One of the main guidelines to prevent timing side-channel attacks against cryptographic implementations is to avoid array accesses indexed by secret data. However, alternatives and countermeasures often incur significant performance losses. We propose a novel methodology for secure, constant-time implementation of algorithms that read and write to small arrays with secret-dependent indices, with a constant-factor performance impact compared to timing-unprotected accesses. It is specifically suitable for simple in-order CPUs like those in embedded systems, e.g., the ARM Cortex-M4 core. Although our methodology is general, we illustrate it with secure implementation of permutation operations, such as composition, inversion, and sampling, the latter using the Fisher-Yates shuffle. We apply this methodology to the post-quantum cryptosystems PERK and NTRU, bridging most of the performance gap to unprotected implementations that employ secret-dependent array accesses.

Recent years have witnessed significant progress in composable masked AES designs based on Hardware Private Circuits (HPCs) under the Probe-Isolating Non-Interference (PINI) framework. However, these designs still suffer from substantial randomness requirements and area overhead at higher protection orders. In this work, we revisit Domain-Oriented Masking (DOM), originally proposed by Gross et. al. in 2016, and leverage the DOM-$dep$ and DOM-$indep$ multipliers to construct efficient AES implementations based on the Strong Non-Interference (SNI) framework. Our contributions include: 1. a comprehensive security analysis of DOM-$dep$ and DOM-$indep$, including their compositional security under the SNI framework; 2. more efficient masked AES implementations for arbitrary protection orders, reducing randomness and area overhead while maintaining latency comparable to state-of-the-art HPC3-based designs. Specifically, our masked AES implementations maintain a latency of 41 clock cycles by using the Hadzic's decomposition for $F_2^8$ inverter. When $d <= 4$, they save at least 13% in area (RNG included) and reduce latency by 19.6% compared to the smallest $d$-PINI round-based masked AES implementations provided by Cassiers et.al. (The current version focuses on the core construction and its initial evaluation. Source code has been made publicly available to facilitate verification. Further performance optimizations and theoretical generalizations are underway and will appear in an upcoming revision.)

A quantum copy-protection scheme (Aaronson, CCC’09) encodes a functionality into a quantum state such that given this state, no efficient adversary can create two (possibly entangled) quantum states that are both capable of running the functionality. There has been a recent line of works on constructing provably-secure copy-protection schemes for general classes of schemes in the plain model, and most recently the recent work of Çakan and Goyal (IACR Eprint, 2025) showed how to copy-protect all cryptographically puncturable schemes with pseudorandom puncturing points.

In this work, we show how to copy-protect even a larger class of schemes. We define a class of cryptographic schemes called malleable-puncturable schemes where the only requirement is that one can create a circuit that is capable of answering inputs at points that are unrelated to the challenge in the security game but does not help the adversary answer inputs related to the challenge. This is a flexible generalization of puncturable schemes, and can capture a wide range of primitives that was not known how to copy-protect prior to our work.

Going further, we show that our scheme is secure against arbitrary high min-entropy challenge distributions whereas previous work has only considered schemes that are punctured at pseudorandom points.

Group signatures (GS, Chaum and van Heyst, EUROCRYPT 1991) are digital signatures that allow a signer to anonymously prove the membership and also allow the special authority called the opener can identify the signer. Group signatures with message-dependent opening (GS-MDO, Sakai et al., Pairing 2012) weakened the power of the opener by introducing another authority called the admitter who issues a message-dependent token. It would be a natural research topic to clarify whether cryptographic primitives that are required to construct GS-MDO are stronger than those of GS or not, according to the enhanced functionality of GS-MDO. In this paper, we propose a generic construction of timed-release encryption (TRE) from GS-MDO. Note that Sakai et al. have shown that GS-MDO implies identity-based encryption (IBE), and Nakai et al. (IWSEC 2009) and Matsuda et al. (Pairing 2010) demonstrated generic constructions of TRE from IBE. Thus, we do not show any new result from the viewpoint of feasibility. We show that (1) GS-MDO directly implies TRE without employing the generic constructions of TRE from IBE, and (2) the proposed TRE construction provides public verifiability, that is not usually supported by TRE, because a TRE ciphertext is a group signature in our construction. We also introduce a new security notion which we call token unforgeability where no adversary can forge a token even the adversary has the opener's secret key, and prove that token unforgeability is implied by opener anonymity which is a fundamental security notion of GS-MDO. Our result implies that GS-MDO is a very strong cryptographic primitive.

Quantum computational pseudorandomness has emerged as a fundamental notion that spans connections to complexity theory, cryptography, and fundamental physics. However, all known constructions of efficient quantum-secure pseudorandom objects rely on complexity-theoretic assumptions.

In this work, we establish the first unconditionally secure efficient pseudorandom constructions against shallow-depth quantum circuit classes. We prove the following:

(1) Any quantum state $2$-design yields unconditional pseudorandomness against both $\mathsf{QNC}^0$ circuits with arbitrarily many ancillae and $\mathsf{AC}^0 \circ \mathsf{QNC}^0$ circuits with nearly linear ancillae.

(2) Random phased subspace states, where the phases are picked using a $4$-wise independent function, are unconditionally pseudoentangled against the above circuit classes.

(3) Any unitary $2$-design yields unconditionally secure parallel-query pseudorandom unitaries against geometrically local $\mathsf{QNC}^0$ adversaries, even with limited $\mathsf{AC}^0$ postprocessing.

Our indistinguishability results for $2$-designs stand in stark contrast to the standard setting of quantum pseudorandomness against $\mathsf{BQP}$ circuits, wherein they can be distinguishable from Haar random ensembles using more than two copies or queries. Our work demonstrates that quantum computational pseudorandomness can be achieved unconditionally for natural classes of restricted adversaries, opening new directions in quantum complexity theory.

Polynomial commitment schemes (PCSs) enable verifying evaluations of committed polynomials. Multilinear (ML) PCSs from linear codes are favored for their prover time. Distributed MLPCSs further reduce it by enabling multiple provers to distribute both commitment and proof generation.

We propose $\mathsf{PIP}_\mathsf{FRI}$, an FRI-based MLPCS that unites the linear prover time of PCSs from encodable codes with the compact proofs and fast verification of Reed–Solomon (RS) PCSs. By cutting FFT and hash overhead for both committing and opening, $\mathsf{PIP}_\mathsf{FRI}$ runs $10\times$ faster in prover than the RS-based DeepFold (Usenix Security'25) while retaining competitive proof size and verifier time, and beats Orion (Crypto'22) from linear codes by $3.5$-fold in prover speed while reducing proof size and verification time by $15$-fold.

Its distributed version $\mathsf{DePIP}_\mathsf{FRI}$ delivers the first code-based distributed SNARK for arbitrary circuits over a single polynomial, and further achieves accountability. $\mathsf{DePIP}_\mathsf{FRI}$ outperforms DeVirgo (CCS'22)---the only prior code-based distributed MLPCS, limited to data-parallel circuits and lacking accountability---by $25\times$ in prover time and $7\times$ in communication, with the same number of provers.

A central insight in both constructions is the shred-to-shine technique. It further yields a group-based MLPCS of independent interest, with $16\times$ shorter structured reference string and $10\times$ faster opening time than multilinear KZG (TCC'13).

In 2023, Barreto and Zanon proposed a three-round Schnorr-like blind signature scheme, leveraging zero-knowledge proofs to produce one-time signatures as an intermediate step of the protocol. The resulting scheme, called BZ, is proven secure in the discrete-logarithm setting under the one-more discrete logarithm assumption with (allegedly) resistance to the Random inhomogeneities in a Overdetermined Solvable system of linear equations modulo a prime number $p$ attack, commonly referred to as ROS attack. The authors argue that the scheme is resistant against a ROS-based attack by building an adversary whose success depends on extracting the discrete logarithm of the intermediate signing key. In this paper, however, we describe a distinct ROS attack on the BZ scheme, in which a probabilistic polynomial-time attacker can bypass the zero-knowledge proof step to break the one-more unforgeability of the scheme. We also built a BZ variant that, by using one secure hash function instead of two, can prevent this particular attack. Unfortunately, though, we show yet another ROS attack that leverages the BZ scheme's structure to break the one-more unforgeability principle again, thus revealing that this variant is also vulnerable. These results indicate that, like other Schnorr-based strategies, it is hard to build a secure blind signature scheme using BZ's underlying structure.

We present InsPIRe that is the first private information retrieval (PIR) construction simultaneously obtaining both high-throughput and low query communication while using silent preprocessing (meaning no offline communication). Prior PIR schemes with both high-throughput and low query communication required substantial offline communication of either downloading a database hint that is 10-100x larger than the communication cost of a single query (such as SimplePIR and DoublePIR [Henzinger et al., USENIX Security 2023]) or streaming the entire database (such as Piano [Zhou et al., S&P 2024]). In contrast, recent works such as YPIR [Menon and Wu, USENIX Security 2024] avoid offline communication at the cost of increasing the query size by 1.8-2x, up to 1-2 MB per query. Our new PIR protocol, InsPIRe, obtains the best of both worlds by obtaining high-throughput and low communication without requiring any offline communication. Compared to YPIR, InsPIRe requires 5x smaller cryptographic keys, requires up to 50% less online query communication while obtaining up to 25% higher throughput. We show that InsPIRe enables improvements across a wide range of applications and database shapes including the InterPlanetary File System and private device enrollment.

At the core of InsPIRe, we develop a novel ring packing algorithm, InspiRING, for transforming LWE ciphertexts into RLWE ciphertexts. InspiRING is more amenable to the silent preprocessing setting that allows moving the majority of the necessary operations to offline preprocessing. InspiRING only requires two key-switching matrices whereas prior approaches needed logarithmic key-switching matrices. We also show that InspiRING has smaller noise growth and faster packing times than prior works in the setting when the total key-switching material sizes must be small. To further reduce communication costs in the PIR protocol, InsPIRe performs the second level of PIR using homomorphic polynomial evaluation, which only requires one additional ciphertext from the client.

The Generalized Birthday Problem ($\textsf{GBP}$), which seeks $k$ hash values from $k$ lists whose XOR is zero, is a fundamental problem across multiple cryptographic domains. Wagner's \(k\)-list algorithm (Crypto'02) for $\textsf{GBP}$ has advanced the optimization of solving the syndrome decoding problem and established new cryptanalytic benchmarks for incremental cryptography and blind signatures. $\textsf{Equihash}$ (NDSS'16) underscores the critical advantages of $\textsf{GBP}$ in proof-of-work design, particularly its ASIC-resistance in blockchain. While the k-list $\textsf{GBP}$ has been extensively studied, many schemes including $\textsf{Equihash}$ utilize a single-list variant (selecting hash values from a single list) without clear theoretical grounding. In this work, we revisit these two long-conflated problems and fill in theoretical gaps in solving the single-list $\textsf{GBP}$.

In the realm of $\textsf{Equihash}$, the index-pointer technique has significantly weakened its ASIC-resistance. Our trade-off optimization to Wagner's algorithmic framework further diminishes this resistance by reducing peak memory by at least 50% across most $\textsf{Equihash}$ parameters. To address this, we propose $\textsf{Sequihash}$, a PoW with enhanced ASIC-resistance, rigorously aligned with the $k$-list $\textsf{GBP}$. Furthermore, we explore the implications of $\textsf{GBP}$ in the field of incremental hash and propose a new collision attack on ID-based incremental hash (Eurocrypt'97). Our attack achieves an asymptotic time complexity of $\mathcal{O}(\sqrt{n} \cdot 2^{\sqrt{2n}})$, significantly improving upon the previous Wagner's bound of $\mathcal{O}(2^{\sqrt{4n}})$. Applying our attack to $\textsf{iSHAKE256}$, we reduce its security lower bound from \( 2^{256} \) to \( 2^{189} \).

In this paper, we propose a new postquantum lattice-based digital signature named Rhyme. The scheme is based on the Fiat-Shamir structure and does not rely on flooding, rejection sampling, or Gaussian convolution as previous methods. Instead, its security is based on a variant of LWE combined with a new sampling method (3C sampling). We prove its security in ROM/QROM and provide concrete parameters as well as reference implementation to show that our scheme enjoys high efficiency and very compact signature size compared with former results.

Recent years have witnessed the surge of academic researches and industrial implementations of succinct non-interactive arguments of knowledge (SNARKs). However, proving time remains a bottleneck for applying SNARKs to large-scale circuits. To accelerate the proof generation process, a promising way is to distribute the workload to several machines running in parallel, the SNARKs with which feature are called distributed SNARKs. Nevertheless, most existing works either require a trusted setup, or rely on quantum-insecure assumptions, or suffer from linear communication costs.

In this paper, we introduce $\mathsf{HyperFond}$, the first distributed SNARK that enjoys a transparent setup, post-quantum security and polylogarithmic communication cost, as well as the field-agnostic property (no reliance on specific choices of fields). To this end, we first propose a distributed proof system based on HyperPlonk (by Chen et al. in EUROCRYPT 2023). To instantiate the system, we then put forward a novel approach to distribute the multilinear polynomial commitment scheme in BaseFold (by Zeilberger et al. in CRYPTO 2024), and also present a trade-off between communication cost and proof size. In $\mathsf{HyperFond}$, after committing to polynomial coefficients with quasilinear complexity, each sub-prover generates proofs with time linear in subcircuit size.

We implement $\mathsf{HyperFond}$ using up to 16 machines. Experimental results demonstrate that the proving time of $\mathsf{HyperFond}$ is 14.3 $\times$ faster than HyperPlonk instantiated with BaseFold. We also compare to deVirgo (by Xie et al. in CCS 2022), so far the only post-quantum distributed SNARK, and achieve a 1.89 $\times$ speedup.

This work establishes the CRO Trilemma: no post-quantum proof system can simultaneously satisfy the following three properties beyond negligible failure probability: (i) Confidentiality, quantified by Priv > 1 - negl(lambda); (ii) Reliability, with Rel > 1 - negl(lambda); and (iii) Legal Opposability, measured by contextual entropy H_Opp ≈ log |V_J|, where V_J denotes the validation space of a polynomial-time institutional verifier J.

The result formalizes the Invisible Authenticity Paradox through contextual entropy H(C) and quantum interpretability loss eta_q(C). Under standard quantum assumptions, we prove the following impossibility bound against QPT adversaries:

H_Opp <= (Priv * Rel) / (epsilon_eff * 2^H(C)) + eta_q(C) + negl(lambda)

A composable framework is introduced, including a composable model with verifier J (Algorithm 1), and an optimal entropy decomposition theorem (Theorem 2.3). Theoretical predictions are supported by empirical evidence indicating consistent violation of the bound (Gamma_CRO > 0.8) across NIST PQC finalists (e.g., Dilithium) and structured ZKPs (e.g., STARKs, Groth16).

Tracing techniques have been used to identify users who have leaked their decryption keys in a secure multi-receiver encryption system. Very recently, in the field of distributed cryptography, where trust is distributed, Boneh et al. extended traitor tracing to the framework of threshold decryption, where a single user doesn't hold the whole secret to decrypt but needs to collaborate with others. However, the tracing capacity in their collusion-secure codes-based schemes is still centralized: only the authority holding the secret tracing key can perform tracing. We continue in the direction of not relying on a single entity and propose decentralizing tracing in this context so that the tracing procedure does not need to rely on any secret key and can be done by anyone. Technically, as binary collusion-secure codes only support secret tracing, we switch to robust $q$-ary IPP codes supporting public tracing. This requires us to generalize the bipartite threshold KEM for two users in Boneh et al.'s paper to $q$-partite KEM for q users. In terms of security, their static one-sided security in the binary case is not appropriate, which requires us to define an adaptive one-sided security notion for $q$-partite KEM to be compatible with $q$-ary IPP codes. Finally, we generalize the Boneh et al. construction to achieve this security notion and achieve public traceability for threshold decryption without degrading efficiency.

FRAST is a TFHE-friendly stream cipher that was published at FSE 2025. The cipher is defined over $\mathbb{Z}_{16}$, and makes extensive use of negacyclic S-boxes over $\mathbb Z_{16}$ as they are less costly in TFHE. Like many FHE-friendly ciphers, FRAST randomizes some of its components to increase its security against statistical attacks. In the case of FRAST, some S-boxes are randomized using an XOF that takes a nonce as input.

In this work, we point out a strong structural property of the full FRAST permutation, which leads to a much simpler alternative representation of the primitive. We study the consequences of this representation and find a weak key space of non-negligible size (i.e., much larger than $2^{128}$) on which every ciphertext leaks one bit of plaintext. This corresponds to a distinguishing attack on the full FRAST in the weak-key setting. In particular, we emphasize that, apart from the structural property, the usage of negacyclic S-boxes further leads to a much larger weak-key space for our attack.

Finally, we provide a general framework to mount a linear attack on FRAST in the average key setting. We briefly describe our approach in the end of the paper, and observe that standard assumptions expected to work in the context of linear cryptanalysis do not hold in the case of FRAST: our experiment indicate that a linear attack in the average key setting does not work as expected.

In Zero Knowledge Proofs of Elliptic Curve Inner Products from Principal Divisors and Weil Reciprocity, Eagen proposes a method for checking whether a sum of points in an elliptic curve group have been computed correctly. Eagen's method verifiably checks elliptic curve group operations only with linear combinations in the base field, allowing very general proofs to be encoded in inner product argument systems and rank-1 constraint systems (R1CS). We call this method "straight-line verification,'' due to how it utilizes straight lines in the verification procedure. In FCMP++ by Parker, the author uses Eagen's method in a R1CS to verify scalar multiplication of group elements, proposing a protocol based on Eagen's arguments. Although the iterative witness construction algorithm proposed by Eagen is correct, the arguments are rather informal, lacking precise protocol descriptions, claims, proofs, or efficiency analyses. We present a method based on Eagen's technique for straight-line verification of cryptographic protocols, offloading the bulk of the computational costs faced by verifiers onto the prover, which is useful for light-weight devices or when verification must be performed repeatedly. Computational improvements are largely due to replacing expensive division operations with lower-cost arithmetic by applying logarithmic derivatives.

Our work, while not fully novel, is a healthy expansion of previous work. In Soundness Proof for an Interactive Protocol for the Discrete Logarithm Relation, Bassa contributed towards formalizing Eagen's method, explicitly describing Parker's proof of scalar multiplication and sketching arguments towards proofs of soundness. However, the soundness arguments in Bassa's work are not without obstacles. Per Eagen, rational solutions to certain systems of polynomial equations are assumed to exist. We point out that these equations do not, in fact, admit rational solutions in general. Bassa lifts to the surface of pairs of elliptic curve group points to avoid this problem, but the verification equations proposed by Eagen and studied by Bassa are not sufficiently justified in those documents.

The verification equations described by Bassa reduce to our verification equations, and therefore they are equivalent. In particular, given a variable choice of a line in the affine plane with three distinct, non-identity, and collinear points on an elliptic curve $\mathcal{E}$, say $P, Q, R$ with interpolating slope $\lambda$ and $x$-coordinates $X_P$, $X_Q$, and $X_R$, these points are necessarily dependent: $\lambda^2 = X_P + X_Q + X_R$. Thus, given any derivation $d$ on the function field $K(\mathcal{E})$ over $K$, we have $dX_R = -dX_P - dX_Q$, allowing computations to reduce further than presented in Bassa's work.

Nonetheless, Bassa's amended approach results in formal arguments, if not proofs, of security. We fully justify the verification equations presented by Bassa, show they reduce further, and reconsider the security of Eagen's approach under the reduced verification equations. We encourage the reader to keep in mind that our verification equations are equivalent reduced versions of those presented by Bassa. Along the way, we exploit the techniques utilized by Eagen to further reduce the total number of field divisions required by prover to just a single one. Our framework is easily applied to generically speed up verification in discrete-logarithm-based protocols.

We present our protocol, and explicitly compute the completeness and soundness errors. We remark on how to complete the scheme, and our soundness error supersedes the previous estimates in the literature. We also show how the corrected scheme can be used to verify scalar multiplication as in Parker's proposed protocol. We then apply this approach to zero-knowledge proof systems such as the Schnorr identification scheme and Bulletproofs to illustrate the generic computational advantage offered by divisors. Because these protocols are simple, secure, and popular, we demonstrate that this work is readily applicable to improve verifier computation in cryptocurrencies such as Monero or Salvium.