Multivariate Cryptography

This article introduces Multivariate Cryptography, by referring this paper as the main technical reference.

1. Introduction

One of the main goals of modern public-key cryptography is to claim that an attacker has no possible way to recover a secret, from designated cryptosystem. However, there are something more.

Game theory, which is a great tool to model a realistic environment into a set of theoretical rules in which each party tries one’s best to achieve a specific goal. In the context of modern cryptography, what we call attack model. They define what primitives attackers/defenders have, and we deduce some statements from them.

Here are some examples of attack models:

• IND-CPA : Indistinguishability under Chosen-Plaintext Attack
• IND-CCA : Indistinguishability under Chosen-Ciphertext Attack
• EUF-CMA : Existential Unforgeability under Chosen-Message Attack

Terms in front of the dash show what the goal of attackers is, and terms after it represent attackers’ primitives. For example, attackers can choose an arbitrary plaintext and encrypt it by using the target service as an oracle.

The main purpose of modern public-key cryptography is to claim that specific cryptosystem has, or doesn’t have, a resistance against some attack models by assuming computational infeasibility. This methodology is powerful, but it has a dependency: the underlying hardness assumption must remain hard for the attacker model being considered.

Classical RSA relies on the difficulty of factoring large integers. Diffie-Hellman, DSA, ECDH, and ECDSA rely on variants of the discrete logarithm problem.

Those assumptions are credible against classical computers at well-chosen parameter sizes, but they are not credible against a sufficiently large, fault-tolerant quantum computer because Shor’s algorithm solves factoring and discrete logarithms in polynomial time.

Post-quantum cryptography (PQC) is the attempt to build public-key encryption, key establishment, and digital signatures from problems for which no efficient classical or quantum algorithms are known. The dominant PQC families are:

• Hash-based cryptography, especially for signatures.
• Lattice-based cryptography, especially for KEMs and signatures.
• Code-based cryptography, especially for encryption/KEMs.
• Isogeny-based cryptography, an active but delicate research direction.
• Multivariate-based cryptography, based on solving systems of multivariate polynomial equations over finite fields.

As of 2026, the first finalized NIST PQC standards are not multivariate schemes. The three principal finalized FIPS standards are:

1. ML-KEM : a lattice-based key-encapsulation mechanism derived from CRYSTALS-Kyber, standardized as FIPS 203.
2. ML-DSA : a lattice-based digital signature scheme derived from CRYSTALS-Dilithium, standardized as FIPS 204.
3. SLH-DSA : a stateless hash-based digital signature scheme derived from SPHINCS+, standardized as FIPS 205.

NIST also selected HQC, a code-based KEM, in 2025 for future standardization as an additional encryption mechanism. Multivariate cryptography remains important because its algebraic structure is different from lattices and hashes, and some multivariate signatures offer attractive speed and size tradeoffs.

NIST’s additional signature process has continued to evaluate non-lattice signatures; in May 2026, NIST advanced nine third-round candidates, including multivariate designs such as UOV, MAYO, QR-UOV, and SNOVA.

This article focuses on the multivariate branch.

---

2. Quantum Computing Background

A classical bit is either 0 or 1. A qubit can be in a superposition

$$\alpha\lvert 0\rangle + \beta\lvert 1\rangle, \qquad |\alpha|^2 + |\beta|^2 = 1.$$

A quantum computation applies unitary transformations to a quantum state, then measures the state to obtain classical information. Because unitary transformations are reversible, quantum circuit design often uses reversible versions of classical computations. Irreversible classical logic can be embedded into reversible logic by preserving enough auxiliary information.

2.1 Toffoli gates and circuit-cost metrics

The Toffoli gate, also called the controlled-controlled-NOT gate, maps

$$(a,b,c) \mapsto (a,b,c \oplus ab).$$

By fixing or post-processing the third wire, Toffoli can implement classical AND and NAND-like behavior inside a reversible computation. Since NAND is universal for classical Boolean circuits, Toffoli is a central tool for compiling classical computations into reversible circuits.

Strictly speaking, Toffoli alone is not a universal set for arbitrary quantum computation because it does not create arbitrary quantum superpositions or phases. Universal quantum circuit sets typically include gates such as Hadamard, phase rotations, CNOT, and T gates. Still, Toffoli count, T-count, T-depth, total qubit count, and circuit depth are important resource metrics when estimating quantum attacks on cryptographic algorithms.

2.2 Shor’s algorithm

Shor’s algorithm reduces factoring and discrete logarithms to order finding or period finding. At a high level, if a group operation can be implemented as a quantum circuit, then quantum Fourier sampling can reveal the hidden period of a function derived from that group operation.

For RSA, this means that integer factorization can be solved in polynomial time in the bit length of the RSA modulus. For finite-field or elliptic-curve Diffie-Hellman, it means that the relevant discrete logarithm can be recovered in polynomial time in the group-size parameter.

In the idealized model of a large, error-corrected quantum computer, this is a qualitative break: increasing RSA or ECC key sizes does not restore the same security relationship, because the asymptotic attack becomes polynomial.

2.3 Grover search

Grover’s algorithm gives a quadratic speedup for unstructured search. A classical brute-force search over a space of size $2^k$ costs about $2^k$ evaluations. Grover search can find a marked item using about $2^{k/2}$ quantum oracle queries.

This matters for symmetric cryptography, but it is not usually a complete break. To attack AES with Grover search, for example, one must implement AES as a reversible quantum circuit, pay the cost of repeated oracle calls, and tolerate the overhead of quantum error correction.

The usual high-level mitigation is to choose symmetric parameters with a sufficient security margin, such as using 256-bit keys when a 128-bit post-quantum brute-force margin is desired.

---

3. Why Classical Public-Key Crypto Fails Against Large Quantum Computers

3.1 RSA and the general number field sieve

Classically, the best general-purpose factoring algorithm for large RSA-style integers is the General Number Field Sieve (GNFS). Its heuristic running time for factoring an integer $N$ is commonly written using $L$-notation:

$$L_N\left[\frac13,\left(\frac{64}{9}\right)^{1/3}\right] = \exp\left(\left(\left(\frac{64}{9}\right)^{1/3}+o(1)\right)(\ln N)^{1/3}(\ln\ln N)^{2/3}\right).$$

This is sub-exponential but still super-polynomial. That gap is exactly why RSA can be parameterized securely against classical machines: key sizes can be chosen so that the best known attack is far outside the feasible range.

Shor’s algorithm changes the asymptotic situation. Factoring becomes polynomial-time in the bit length of $N$, assuming a sufficiently capable quantum computer. Therefore, RSA’s classical hardness assumption collapses under that attacker model.

3.2 Discrete logarithms and elliptic curves

For an elliptic curve group generated by a point $P$ of order $r$, the elliptic-curve discrete logarithm problem (ECDLP) asks for $d$ given

$$Q = dP.$$

Shor’s algorithm can solve this through a two-dimensional hidden-period formulation. Define

$$f(a,b) = aP + bQ = (a + bd)P, \qquad (a,b) \in \mathbb{Z}_r^2.$$

Then

$$f(a,b)=f(a',b') \iff (a-a') + d(b-b') \equiv 0 \pmod r.$$

The period lattice is therefore

$$\Lambda = \{(u,v) \in \mathbb{Z}_r^2 : u + dv \equiv 0 \pmod r\}.$$

Finding this lattice reveals $d$. This is why ECDSA and ECDH are considered quantum-vulnerable even though they are efficient and widely deployed in classical systems.

3.3 Why this motivates PQC

A PQC design should avoid relying on factoring or discrete logarithms. It does not need to be immune to all quantum speedups; Grover-type speedups can often be handled by parameter selection. The critical requirement is that no Shor-like polynomial-time quantum algorithm is known for the underlying problem.

For multivariate cryptography, that underlying problem is solving systems of multivariate polynomial equations over finite fields, especially quadratic systems.

---

4. What Is Multivariate Public-Key Cryptography?

Multivariate public-key cryptography builds public-key primitives from polynomial maps over finite fields. The public key is usually a list of multivariate quadratic polynomials. The private key is a hidden decomposition that makes inversion feasible for the legitimate user.

Let $\mathbb{F}_q$ be a finite field. A public map

$$P: \mathbb{F}_q^n \to \mathbb{F}_q^m$$

is represented by $m$ coordinate polynomials:

$$P(x_1,\dots,x_n) = (p_1(x),\dots,p_m(x)).$$

In the MQ setting, each $p_k$ has degree at most two:

$$p_k(x_1,\dots,x_n) = \sum_{1\le i\le j\le n} a^{(k)}_{ij}x_i x_j + \sum_{i=1}^{n} b^{(k)}_i x_i +c^{(k)}, \qquad k=1,\dots,m.$$

The MQ problem is: given $p_1,\dots,p_m$, find

$$x=(x_1,\dots,x_n)\in \mathbb{F}_q^n$$

such that

$$p_1(x)=p_2(x)=\cdots=p_m(x)=0.$$

The problem is NP-hard in general, and decision variants are NP-complete under standard formulations. This does not automatically make every MPKC scheme secure, because real schemes publish structured polynomial systems, not uniformly random hard instances. The central engineering problem is therefore:

• Make the public system easy to evaluate,
• hard to invert without the trapdoor,
• and resistant to attacks that detect the hidden structure.

A common construction hides an easily invertible central map $F$ by composing it with two invertible affine maps:

$$P = S \circ F \circ T.$$

Here:

• $T:\mathbb{F}_q^n\to\mathbb{F}_q^n$ hides the input coordinates.
• $F:\mathbb{F}_q^n\to\mathbb{F}_q^m$ is the central trapdoor map.
• $S:\mathbb{F}_q^m\to\mathbb{F}_q^m$ hides the output coordinates.
• $P$ is the public key.
• $(S,F,T)$, or enough data to invert them, is the secret key.

The survey by Dey and Dutta describes this as the standard shape of many MPKC encryption and signature schemes: the public key is a composition of affine maps and a central MQ map, while the secret key stores the maps needed to invert the composition.

---

5. Encryption and Signature Patterns

5.1 Public-key encryption

For encryption, the public map should be efficiently computable. A simplified encryption flow is:

$$\textsf{Enc}_{pk}(x) = P(x) = c.$$

If $P=S\circ F\circ T$, then decryption uses the secret decomposition:

$$\begin{aligned} y &= S^{-1}(c),\\ z &\in F^{-1}(y),\\ x &= T^{-1}(z). \end{aligned}$$

The public operation is just polynomial evaluation. The private operation may require solving linear systems, factoring low-degree univariate polynomials, or using a specialized inversion procedure for $F$.

In practice, MPKC encryption has been difficult to make robust. The review paper emphasizes that no MQ encryption scheme has had the same durability as the stronger signature-line candidates. Encryption schemes such as Simple Matrix, ZHFE, HFERP, and EFLASH illustrate the design space, but many proposed systems have later been weakened or broken by structural attacks.

5.2 Digital signatures

For signatures, the direction is reversed. The signer must invert the public map using the secret key, while the verifier only evaluates the public map.

A simplified signature flow is:

1. Encode or hash a message $M$ to a target vector $d \in \mathbb{F}_q^m$.
2. Use the secret key to find $z$ such that $P(z)=d$.
3. Publish $z$ as the signature.
4. Verify by checking whether $P(z)=d$.

This asymmetry is attractive. Signature verification is typically fast because it is only public polynomial evaluation. Some multivariate signatures also have compact signatures.

The tradeoff is that public keys can be very large, and many designs have been vulnerable to structural cryptanalysis.

---

6. Major MPKC Design Families

6.1 Matsumoto-Imai and hidden-field ideas

The modern MPKC line begins with the Matsumoto-Imai scheme. The core idea is to define a simple-looking map over an extension field and then express it as multivariate polynomials over the base field. This creates a public multivariate map whose trapdoor lives in the hidden extension-field representation.

That first design was broken by algebraic attacks, but it introduced a template that influenced many later schemes.

The Hidden Field Equations (HFE) family generalizes the hidden-field idea. An HFE central polynomial over an extension field $K:=\mathbb{F}_q[y]/g(y)$, where $g(y)$ is an irreducible polynomial, has the form

$$F(X)= \sum_{0\le j\le i<n} a_{ij}X^{q^i+q^j} + \sum_{i=0}^{n-1} b_iX^{q^i}+c.$$

When represented over the base field, this becomes a system of quadratic equations. HFE variants add modifiers such as vinegar variables, minus equations, or projection techniques to improve security and efficiency. Examples include HFEv-, QUARTZ, GeMSS, and HMFEv.

6.2 Oil and Vinegar, UOV, and Rainbow

The Oil and Vinegar (OV) design splits variables into two classes:

• Vinegar variables, which are assigned random values during signing.
• Oil variables, which become solvable through a linear system after the vinegar variables are fixed.

In a simple OV central map, oil-oil quadratic terms are omitted. Once the vinegar variables are chosen, each equation is linear in the oil variables. The signer solves this linear system to produce a signature.

Unbalanced Oil and Vinegar (UOV) uses more vinegar variables than oil variables to improve security. UOV has been influential because its structure is simple, its signing and verification can be fast, and it has survived longer than many other multivariate ideas when parameters are carefully selected.

Rainbow stacks several UOV-like layers. Each layer treats variables from previous layers as vinegar variables for the next layer. This improves efficiency but creates more exploitable structure. Rainbow became a NIST third-round finalist, but later key-recovery attacks made it unsuitable for standardization.

6.3 Matrix and hybrid constructions

Some MPKC encryption schemes use matrix algebra or combine several trapdoor ideas. The review paper discusses examples such as:

• Simple Matrix, which uses a matrix-algebra central structure.
• ZHFE, which modifies HFE to avoid some low-rank weaknesses but was later attacked.
• HFERP, which combines HFE, Rainbow-like structure, and plus techniques.
• EFLASH, which uses an efficient decryption strategy but has known security concerns.

These systems show that the design space is broad, but they also show the main danger: structure added for efficient inversion often becomes the attacker’s handle.

---

7. “MQ Is Hard” Is Not Enough

It is true that random MQ solving is computationally hard in general. But MPKC public keys are not arbitrary random systems.

They are deliberately generated so that the owner can invert them. The security question is therefore not only whether MQ is hard; it is whether the published polynomial system leaks enough structure to reconstruct or bypass the secret key.

Here are three broad categories of the attacks on MPKC families:

• direct algebraic attacks
• rank attacks (including MinRank)
• and differential attacks.

7.1 Direct algebraic attacks

A direct attack ignores the intended trapdoor and solves the public system directly. For encryption, an attacker given $c=P(x)$ can solve

$$P(x)-c=0.$$

For signatures, an attacker trying to forge a signature for digest $d$ can solve

$$P(z)-d=0.$$

Important direct-attack tools include:

• Gröbner basis algorithms, such as Buchberger’s algorithm and the faster F4/F5 families.
• Relinearization, which introduces new variables for products such as $x_i x_j$.
• XL-type algorithms, which multiply equations by monomials and linearize the resulting higher-degree system.

The practical cost depends on the degree of regularity, number of variables, number of equations, field size, and special structure. A parameter set that looks large by raw variable count can still fail if its algebraic structure gives low-degree relations.

7.2 MinRank and rank attacks

A quadratic form can be represented by a matrix. In many MPKC schemes, the hidden central map has lower-rank structure than a random public system would suggest. The attacker looks for a nontrivial linear combination of public quadratic forms whose associated matrix has small rank.

A simplified MinRank problem is:

Given matrices $M_1,\dots,M_\ell \in \mathbb{F}^{n\times n}$ and a rank bound $r$, find coefficients $\lambda_1,\dots,\lambda_\ell$, not all zero, such that

$$> \operatorname{rank}\left(\sum_{i=1}^{\ell}\lambda_iM_i\right)\le r. >$$

MinRank itself is hard in general, but special MPKC instances can be easier than random instances. Several HFE-style and Rainbow-style systems have been weakened by attacks that exploit low-rank or rectangular-rank structure.

7.3 Differential attacks

For a quadratic public map $P$, the expression

$$B_P(x,a)=P(x+a)-P(x)-P(a)+P(0)$$

is bilinear in $x$ and $a$. Differential attacks study this bilinear map to find invariants, kernels, symmetries, or subspaces that reveal information about the hidden central map. If the private construction leaves a recognizable differential footprint, the attacker may reconstruct an equivalent key or forge signatures without solving a random MQ instance.

7.4 Quantum attacks against MPKC

No Shor-like polynomial-time quantum algorithm is known for solving arbitrary MQ systems. That is the core reason MPKC belongs to PQC. However, quantum attackers still matter:

• Grover search can speed up exhaustive search over guessed variables or keys.
• Quantum versions of algebraic subroutines can change constant factors or search exponents.
• Security levels must be estimated against both classical and quantum costs.

A conservative design should not simply quote NP-hardness. It must analyze the best known structural, algebraic, and hybrid attacks under the intended parameter set.

---

8. Efficiency Tradeoffs

MPKC has several attractive efficiency properties:

• Fast public operations. Evaluation of quadratic polynomials is straightforward and can be optimized over small finite fields.
• Fast signature verification. Verification is often just a hash plus public polynomial evaluation.
• Simple arithmetic. Many schemes use operations over small finite fields, which can be implemented without heavy big-integer arithmetic.
• Potential usefulness for constrained devices. RFID tags, smart cards, and embedded verifiers may benefit from fast verification.

The drawbacks are equally important:

• Large public keys. A public key contains many quadratic coefficients. Naively, $m$ quadratic polynomials in $n$ variables require on the order of

  $$m\cdot \frac{(n+1)(n+2)}{2}$$

  field elements.

• Fragile structure. The more structure is added to make signing or decryption efficient, the more structure an attacker can try to detect.
• Limited formal security proofs. Many practical MPKC schemes are analyzed by resistance to known attacks rather than reduced tightly to a standard hard problem.
• History of breaks. Many early and even some advanced multivariate schemes were later broken or substantially weakened.

This explains why MPKC is simultaneously promising and risky: it can be very fast, but its security depends heavily on subtle algebraic design choices.

---

9. Case Studies

9.1 Rainbow

Rainbow is one of the best-known multivariate signature schemes. It generalizes UOV into multiple layers. Verification is fast, and signing uses structured linear algebra over small finite fields. These properties made Rainbow attractive in the NIST PQC process, where it reached the third round as a finalist.

However, Rainbow’s layered structure created exploitable algebraic relationships. Beullens’ attacks, including the breaking Rainbow takes a weekend on a laptop line of work, demonstrated practical key recovery for important parameter sets. The main lesson is not merely that Rainbow failed, but that MPKC schemes can fail because of structure recovery, not because random MQ solving became easy.

9.2 UOV and modern UOV-like signatures

UOV removes the multilayer structure of Rainbow and retains a simpler oil-vinegar trapdoor. It is still not automatically secure; parameter choices must resist intersection attacks, rank attacks, and hybrid solving. But UOV-like schemes remain relevant because the design is efficient and comparatively well studied.

Modern multivariate signature candidates such as UOV, MAYO, QR-UOV, and SNOVA show that the oil-vinegar design space remains active. Their evaluation focuses on whether variants can reduce key sizes, preserve fast signing and verification, and avoid the structural weaknesses that affected Rainbow.

9.3 HFE-style signatures

HFE-style systems use hidden extension-field polynomials. Their advantage is that the central equation can be inverted using univariate polynomial techniques. Their weakness is that the hidden-field representation can create rank or algebraic patterns. Variants such as QUARTZ, HFEv-, GeMSS, and HMFEv modify the basic design with vinegar variables, removed equations, or other transformations.

The historical record is mixed. Some schemes offered short signatures or fast verification, but many suffered from large keys, slow signing, or later rank attacks. The main lesson is that HFE is a fertile idea, but its security is highly sensitive to parameterization and modifiers.

9.4 MPKC encryption schemes

Multivariate encryption has been more difficult than multivariate signatures. Schemes such as Simple Matrix, ZHFE, HFERP, and EFLASH attempted to provide efficient encryption/decryption structures, but many have known disadvantages or attacks. The review paper’s overall assessment is that MQ-based encryption has not yet produced as durable a candidate class as MPKC signatures.

---

10. How to Read MPKC Security Claims

When reading a paper or specification for a multivariate scheme, do not stop at the statement “MQ is NP-hard.” Check at least the following points.

10.1 What is the exact public map shape?

Ask whether the public polynomials are close to random MQ instances or whether they preserve visible traces of a central map. Look for hidden subspaces, rank defects, missing monomial classes, field-representation artifacts, or layer boundaries.

10.2 What are the best direct-solving estimates?

A parameter set should estimate the cost of Gröbner basis attacks, XL-style attacks, hybrid attacks, and field-equation effects. It should state the assumed linear-algebra exponent, field size, memory cost, and quantum-search adjustments.

10.3 What structural attacks were considered?

For MPKC, this is often more important than generic solving. A serious analysis should address MinRank, differential attacks, intersection attacks, rectangular MinRank attacks, key-recovery attacks, and any family-specific attacks.

10.4 What is the deployment tradeoff?

Large public keys may be acceptable in some settings and unacceptable in others. Fast verification may matter more than key size for firmware signatures, but less for bandwidth-constrained protocols. MPKC is not a universal replacement; it is a design family with specific strengths.

---

11. Current Position of Multivariate Cryptography

Multivariate cryptography did not dominate the first wave of finalized PQC standards. Lattice-based and hash-based schemes are currently the primary standardized choices. Code-based KEMs are also important, especially with HQC selected for additional KEM standardization.

Still, MPKC remains active for three reasons.

First, it provides assumption diversity. A cryptographic ecosystem based entirely on one mathematical family is fragile. Multivariate schemes rely on algebraic solving rather than lattice reduction or hash-function assumptions.

Second, MPKC can offer high-speed public operations. For signatures, fast verification can be attractive in constrained verification environments.

Third, newer designs can learn from past failures. The breaks of Rainbow, HFE variants, and encryption schemes are not only setbacks; they are information about which algebraic structures leak too much.

As of May 2026, NIST’s additional signature process keeps several multivariate signatures under evaluation. This does not mean they are standardized or safe for immediate deployment. It means the family still has enough potential to justify serious analysis.

---

12. Conclusion

Multivariate public-key cryptography is based on a simple hard problem: solving systems of multivariate polynomial equations over finite fields. The quadratic case, MQ, is especially attractive because quadratic maps are efficient to evaluate while still hard to solve in general.

The core MPKC trapdoor pattern is also simple:

$$P = S \circ F \circ T.$$

The public key is a list of quadratic polynomials. The private key is the hidden decomposition that makes inversion feasible. This pattern can produce fast encryption operations and very fast signature verification, but it also creates the central risk of MPKC: the hidden structure may leak.

Quantum computing motivates MPKC because Shor’s algorithm breaks RSA and ECC but does not appear to solve MQ efficiently. However, post-quantum status is not a proof of security. MPKC schemes must survive direct algebraic solving, MinRank and other rank attacks, differential attacks, intersection attacks, and family-specific cryptanalysis.

The right way to view MPKC is therefore balanced. It is not merely a broken historical branch, because UOV-like and other multivariate signatures remain under active evaluation. It is also not a mature drop-in replacement for current standardized PQC. It is a powerful algebraic design area whose future depends on building trapdoors that are efficient for honest users and genuinely invisible to attackers.

---

References and Further Reading

1. Jayashree Dey and Ratna Dutta, Progress in Multivariate Cryptography: Systematic Review, Challenges, and Research Directions, ACM Computing Surveys, Vol. 55, No. 12, Article 246, 2023. DOI: https://doi.org/10.1145/3571071.
2. NIST, Post-Quantum Cryptography Project: https://csrc.nist.gov/projects/post-quantum-cryptography.
3. NIST FIPS 203, Module-Lattice-Based Key-Encapsulation Mechanism Standard (ML-KEM): https://csrc.nist.gov/pubs/fips/203/final.
4. NIST FIPS 204, Module-Lattice-Based Digital Signature Standard (ML-DSA): https://csrc.nist.gov/pubs/fips/204/final.
5. NIST FIPS 205, Stateless Hash-Based Digital Signature Standard (SLH-DSA): https://csrc.nist.gov/pubs/fips/205/final.
6. NIST, NIST Selects HQC as Fifth Algorithm for Post-Quantum Encryption, 2025: https://www.nist.gov/news-events/news/2025/03/nist-selects-hqc-fifth-algorithm-post-quantum-encryption.
7. NIST IR 8610, Status Report on the Second Round of the Additional Digital Signature Schemes for the NIST Post-Quantum Cryptography Standardization Process, 2026: https://doi.org/10.6028/NIST.IR.8610.
8. Peter W. Shor, Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer, 1994: https://arxiv.org/abs/quant-ph/9508027
9. Lov K. Grover, A Fast Quantum Mechanical Algorithm for Database Search, 1996: https://arxiv.org/abs/quant-ph/9605043
10. Ward Beullens, Breaking Rainbow Takes a Weekend on a Laptop, 2022: https://eprint.iacr.org/2022/214.pdf