Weil descent and cryptographic trilinear maps

Ming-Deh A. Huang

REVIEW 2 major objections 4 minor 17 references

Weil descent and cryptographic trilinear maps

T0 review · 2 major / 4 minor · reviewed 2026-08-14 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read Weil descent builds trilinear maps with a hidden trapdoor.

desk verdict A serious and explicit construction, but the stress-test attack is right: the public blinding matrices are commuting projections, so the secret descent basis falls to linear algebra and the trapdoor is broken. read the letter →

arxiv 1908.06891 v3 pith:BCPDR3IF submitted 2019-08-19 cs.CR math.NT

Ming-Deh A. Huang This is my paper · ORCID

classification cs.CRmath.NT MSC 11T7194A6014G5011G2014H40

keywords trilinearmapsmultilinearWeildescentrestrictiontrapdoordiscretelogarithmindistinguishabilityobfuscationpairingshyperellipticJacobians

verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

This paper develops a concrete method for constructing cryptographic trilinear maps—maps $G_1\times G_2\times G_3\to\mu_\ell$ in which discrete logarithms stay hard—on the Weil descent of abelian varieties over finite fields. The central trick is to work on the descent of a hyperelliptic Jacobian or an elliptic curve with respect to a secret basis of the field extension; the descent looks like a harmless affine variety to the public, while the secret basis hides the linear-algebra actions that make the third pairing group hard to crack. The paper proves that the blinded pairing needed for the map can be specified efficiently and without global-descent leaks, and it reduces the security question to a trapdoor discrete logarithm problem that it leaves open. If the construction is sound, it gives a candidate route to trilinear maps, which prior work has shown would be enough for indistinguishability obfuscation.

What carries the argument

The load-bearing object is the secret-basis Weil descent: a secret basis $u$ of $K/k$ defines the maps $\delta_{\sigma^i}(\hat x)=\langle\hat x,u^{\sigma^i}\rangle$ and $\rho(\hat x)=(\delta_{\sigma^i}(\hat x))_i$, with secret matrix $\Gamma=(u^{\sigma_i}_j)$ and $W=\Gamma^{-1}$. Descent varieties and maps are specified in a public basis $\theta$ while avoiding 'global descents'—d-tuples of polynomials, or $K$-linear combinations, that would reveal $u$. Onto this scaffolding the construction blinds the action of $\mathrm{Mat}_d(\mathbb{F}_\ell)$: sparse $(0,1)$-matrices $M_i$ become public maps $\Psi_i$ whose coefficients are sums $\langle\hat m(\hat X^{q^a},\hat X^{q^b}),\Omega_{r,a,b}\rangle$ with $\Omega_{a,b}=W_{I_{a,b}}\Gamma_{I_{a,b}}$, so recovering $u$ is one route to breaking the trapdoor. The third group is the quotient of the noncommutative algebra $\Lambda=\mathbb{F}_\ell\langle z_1,\ldots,z_N\rangle$ by the exponentially large submodule $J_N$, which makes the discrete logarithm hard while a sparse representative keeps pairing evaluation efficient.

What would settle it

Exhibit a polynomial-time algorithm that, given the published data (the descent variety $\hat V$, the specified $\hat m$ and $\hat\tau$, $\phi\circ\delta$, the matrices $\Omega_{a,b}$, and the relations $R$), either determines the secret basis $u$ or finds the scalar $a$ for a random sparse representative $g\in a+J_N$; either computation would collapse the trilinear map.

Watch

Extended reading notes

Core claim

The paper's central claim is that a trilinear map $G_1\times G_2\times G_3\to\mu_\ell$ can be built on the Weil descent of an abelian variety. Concretely, for an abelian variety $A$ over a degree-$d$ extension $K/k$, with two secret bases $u,u'$, one forms descents $\hat A,\hat A'$ and chooses torsion points $D_\alpha,D_\beta$ that are not descent points. Pick $N=O(d^2)$ sparse $(0,1)$-matrices $M_i$ which together with the identity span $\mathrm{Mat}_d(\mathbb{F}_\ell)$, hide them as endomorphism maps $\Psi_i$ on the descent, and publish quadratic relations $R$ on the corresponding noncommutative variables. With $J$ the ideal generated by $R$ and $U=J_N$, the third group is $G_3=(\mathbb{F}_\ell+U)/U$; a sparse representative of $z+U$ acts on $D_\beta$, and the pairing satisfies $\hat e(xD_\alpha,\Psi(g)(yD_\beta))=\zeta^{xyz}$ for $\zeta=\hat e(D_\alpha,D_\beta)$. To stop self-pairings on $G_1$ and $G_2$, the final construction uses two independent secret bases. Theorems 1 and 2 assert that the blinded pairing $\hat e$ can be specified efficiently—with $O(g^2d)$ descent functions for hyperelliptic Jacobians and $O(d)$ for elliptic curves—with no global descent and safe from the linear attack described in Section 2.4.

Load-bearing premise

The load-bearing premise is that the secret basis $u$—together with the blinding matrices $\Gamma$ and $W$, the maps $\Psi_i$, and the relations $R$—cannot be efficiently recovered from the published descent variety, specified maps, pairings, and sparse encodings; the paper states in Section 8 that this recovery problem is open.

Editorial extensions

If this is right

The blinded pairing $\hat e$ can be specified by polynomially many rational descent functions with blinded constants: $O(g^2d)$ functions for hyperelliptic Jacobians and $O(d)$ for elliptic curves, by Theorems 1 and 2.
Given that specification, the trilinear map is efficiently computable via $\hat e(xD_\alpha,\Psi(g)(yD_\beta))=\zeta^{xyz}$ for any sparse representative $g$ of $z+U$.
The discrete logarithm on $G_3$ is hard only while the secret descent basis stays hidden; the paper's generic version reduces it to solving quadratic systems in $d^{O(1)}$ variables, so the map is a candidate, not a proven secure scheme.
If an adversary recovers $u$, the trapdoor map $\omega$ reduces the discrete logarithm on $G_3$ to linear algebra in $\mathrm{Mat}_d(\mathbb{F}_\ell)$, so the entire construction collapses.
Because trilinear maps are known to suffice for indistinguishability obfuscation, a sound instance of this construction would provide a concrete candidate obfuscator through the known reduction.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

If the trapdoor discrete-logarithm problem resists algebraic attacks, the same secret-basis blinding could plausibly be adapted to other hiding tasks such as graded encodings, though the paper only claims a trilinear map.
A direct way to test the security premise is to instantiate the construction with small $d$ and small genus and check whether the linear-analysis conditions of Section 2.4 are actually met on random sampled points; the paper argues they can be satisfied but reports no implementation.
The two-secret-basis version is designed to block self-pairings on $G_1$ and $G_2$; one could try to build a self-pairing from the natural isomorphism between the two descents, which would break the claimed hardness of the first group.
Because the trapdoor is a hidden algebra morphism $\omega:\Lambda\to\mathrm{Mat}_d(\mathbb{F}_\ell)$, the quadratic relations $R$ can be viewed as a hidden-linear-algebra instance; the paper does not analyze quantum algorithms for this trapdoor.

Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Desk Editor's Note

read the letter

Two things you should know. First, the reader's conditional verdict is fair if you view the paper as an algebraic framework; the construction is coherent and the pairing computations are explicit. Second, the stress-test note is correct, and it is more serious than the paper's own open problems suggest. The matrices Omega_{a,b} published to specify each Psi_i are idempotent projections W_I Gamma_I with W = Gamma^{-1}; they commute and satisfy Omega_I Omega_J = Omega_{I cap J}. With O(d^2) such projections coming from random subsets I, the family separates coordinates, so a generic linear combination of the Omega's has distinct eigenvalues and its eigenvectors are the columns of W. That recovers the secret descent basis up to column scaling; the Frobenius relations and published descent equations fix the remaining ambiguity. This is polynomial-time linear algebra, not the quadratic-system difficulty assumed in Section 2.8 and Section 3. The trapdoor discrete logarithm problem is not merely unproven; it is broken as stated.

The paper still has real value. The idea of using Weil descent to blind the Mat_d(F_ell) action on A[ell]^d is new, and the descent-map specification in Propositions 6-10 is a systematic treatment of what can be safely published. The pairing computation on hyperelliptic Jacobians (Sections 5-6) is explicit and appears technically sound; the elliptic curve case in Section 7 gives concrete rational functions with degree counts. The paper is also honest: Section 8 lists the key security assumptions as open problems, which makes it easier to identify the flaw.

Other soft spots are secondary. The construction is heuristic: random birational models are assumed dense, sampled points are treated as random, and no concrete parameter set is proposed. The key claim that the ideal quotient has exponential dimension does not help once the secret basis is recovered. None of this matters as much as the attack: after u is recovered, the trapdoor map lambda is computed and the DLP on G3 reduces to a vector space.

Who should read this: researchers working on multilinear maps and Weil descent cryptanalysis. The paper will be a useful record of an attempted construction and a caution about publishing matrix projections. It deserves a serious referee; the attack should be documented alongside the construction.

Recommendation: send it to peer review. The central security claim fails, but the algebraic machinery is substantive and worth separating from the broken claim.

Referee Report

2 major / 4 minor

Summary. The paper proposes a method for constructing cryptographic trilinear maps from Weil descent. A secret basis u of a finite extension K/k is used to form a descent \hat A of an abelian variety A; the addition law and pairings on \hat A are published through specially blinded specifications. The third group G3 is defined as F_l + J_N modulo J_N in a noncommutative algebra generated by d^{O(1)} maps, and security is claimed to rest on the difficulty of recovering u or on a conjectured trapdoor discrete-logarithm problem. Explicit treatments are given for hyperelliptic Jacobians (§5–§6) and elliptic curves (§7). Theorems 1 and 2 assert that the blinded pairing can be specified efficiently and safely from the linear attacks defined in §2.4.

Significance. If the construction worked, it would provide a concrete algebraic trilinear map, a recognized goal because of Lin–Tessaro's result that trilinear maps imply indistinguishability obfuscation. The manuscript contains substantial explicit algebra: the Cantor arithmetic for hyperelliptic Jacobians, the blinding formulas of Proposition 11, and the pairing-evaluation lemmas are worked out in detail, and the paper is candid in listing its security questions as open. However, the security core is broken by a polynomial-time linear-algebra attack on the public blinding matrices, so the proposed construction does not achieve its stated goal. The algebraic machinery may still be useful, but the paper as a secure construction is not viable.

major comments (2)

[§2.8 (Prop. 11), §3, §4.1] Each published Ω_{a,b} is W_{I_{a,b}}Γ^{I_{a,b}}; since W=Γ^{-1}, this equals Γ^{-1}E_{I_{a,b}}Γ, an idempotent projection. Any two such projections commute, because P_I P_J = P_{I∩J}, and the family of O(d^2) projections published in §3 separates the coordinate directions. By polynomial-time simultaneous diagonalization over k, an adversary recovers the common eigenbasis, i.e. the columns of W up to scaling and permutation. Conjugating the public Ψ_i into this basis gives N_i = P^{-1}D M_i D^{-1}P with D diagonal and P a permutation. The M_i are (0,1)-matrices with two ones per row, so their supports (and hence the trapdoor action) are revealed up to a harmless conjugation; scalar matrices are invariant under this conjugation. Consequently, given a sparse representative g∈Λ, evaluating g in the N_i determines the unique a with g∈a+J_N, solving the discrete-log problem of §3.2 in polynomial time. This is a negative answer to Open Problem 2 of §8 and removes the central security premise of §1 and §3.
[§2.4–§2.6, Theorems 1 and 2] The claimed safety against 'linear attacks' is heuristic. The paper assumes, without proof or quantified probability, that random birational transformations make all relevant polynomials dense in some degree at least 2 (p. 16), and that polynomially many sampled descent points behave as random for interpolation (p. 13). Proposition 7 concludes that a K-global descent is 'unlikely' or that probability is 'negligible' without giving a bound in terms of the random Γ. Thus Theorems 1 and 2 are conditional statements; even apart from the attack above, they do not by themselves establish a secure scheme.

minor comments (4)

[§2.8] The notation Ω_{a,b}=W_I Γ_I is inconsistent with the A_I/A^I definitions given earlier in the section; it should read W_{I_{a,b}} Γ^{I_{a,b}}.
[§3 and §8] Section 3 publishes Ω_{a,b} for O(d^2) maps Ψ_i, each contributing about d^{1-ε} projections, so the number of public projections is O(d^{3-ε}); Open Problem 2 instead considers only O(d^2) subsets. The relationship between the two counts should be clarified.
[Throughout] There are small textual errors, e.g. 'defined by by a' in §1.1, 'U/u0' in §2.8, and some incomplete sentences in the site description in §5; these do not affect the mathematics.
[§3–§4] The paper would benefit from a small worked example, such as d=2 or d=3, illustrating Proposition 11 and the structure of G3; currently the construction is quite difficult to verify by hand.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the construction is self-contained and explicitly leaves its security assumptions as open problems.

full rationale

The paper's central contribution is a candidate construction, not a prediction from fitted inputs. The trilinear map is defined explicitly: G3 is formed as U1/U with U a submodule of E0 = {lambda in EndV : e(alpha, lambda beta)=1}, so the factorization e(a alpha, c+lambda(b beta)) = e(alpha,beta)^{abc} is the intended definition of the quotient, not a circular derivation of one input from another. The Weil-descent blinding, the matrices W and Gamma, the morphisms Psi_i, the relations R, and the encoding of G3 are all introduced as construction data; no quantity is fitted to a dataset and then renamed a prediction. Theorems 1 and 2 claim efficient, 'properly specified' programs for the blinded pairing, built from the standard Weil pairing via Miller's algorithm and from explicit rational-function identities (Propositions 12 and 13, Lemmas 9-13); these are independent algebraic correctness statements, even though their security against linear attacks relies on heuristic density assumptions. The paper does not invoke a self-authored uniqueness theorem to force a choice, and its self-citations ([8], [9], [10]) are contextual background rather than load-bearing support. Section 8 is explicit that recovering the secret descent basis u and solving the trapdoor discrete-logarithm problem are open; the hardness of the quadratic-system route is presented as a conjecture about computational cost, not as a derived theorem. Any cryptanalytic vulnerability, such as the public matrices Omega_{a,b}=W_I Gamma_I being commuting projections that might reveal W, would be an attack on the construction's security, not circularity in its derivation. Accordingly, no circular step is exhibited and the appropriate score is 0.

Assumptions & free parameters 4 free parameters · 6 assumptions · 0 invented entities

The construction rests on standard algebraic geometry for pairings and Jacobian computations, but the security-relevant claims rest on several heuristic and unproven assumptions. No numerical data are fitted; the free parameters listed are construction and security choices. No new physical or mathematical entity is postulated beyond the free algebra Lambda used as an algebraic platform.

free parameters (4)

descent degree d = [K:k]
Chosen by the construction as a security parameter. Hardness statements scale with d, but no concrete value is specified.
torsion prime ell
A prime not equal to the field characteristic; discrete logarithms on mu_ell and on ell-torsion are assumed hard. No concrete bit length is given.
sparsity constants c and epsilon
Used in sections 3.3 and 4.1 to control support sizes and row-column set sizes. They are chosen by hand, not fitted to data.
random blinding scalars a and r in K*
Used in Proposition 8 and section 2.7 to blind descent functions. They are sampled randomly rather than fitted.

assumptions (6)

standard math Weil descent gives an invertible linear map rho and correct descent varieties.
Used throughout sections 2 and 4 as standard theory from [1] and [7].
domain assumption Weil reciprocity defines a nondegenerate, efficiently computable pairing on J[ell].
Used in section 6 and Lemmas 9 through 13, assuming the hyperelliptic curve has odd-degree monic f.
standard math Cantor's composition and reduction algorithm for hyperelliptic Jacobians is correct and polynomial-time.
The entire addition and doubling computation in section 5 relies on [4].
ad hoc to paper Random birational transformations make relevant polynomials dense in some degree at least 2.
This is the key step that is claimed to prevent linear attacks in section 2.5. It is stated as 'likely' without an explicit probability bound.
ad hoc to paper Polynomially many sampled descent points can be treated as random for interpolation attacks.
Assumed in section 2.4 with the phrase 'Heuristically speaking' before the definitions of ell_S(A) and omega_S(A).
domain assumption Solving systems of quadratic polynomials in d^{O(1)} variables requires exponential time.
The security of the trapdoor discrete logarithm in sections 3 and 8 rests on this complexity heuristic rather than on a proof.

how reviews work

0 comments

Cite this review

Pith. "Pith review of Weil descent and cryptographic trilinear maps." pith.science (2026). https://pith.science/paper/BCPDR3IF

@misc{pith2026190806891,
  author       = {Pith},
  title        = {Pith review of: Weil descent and cryptographic trilinear maps},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/BCPDR3IF}},
  note         = {Machine review of arXiv:1908.06891}
}

read the original abstract

It has recently been shown that cryptographic trilinear maps are sufficient for achieving indistinguishability obfuscation. In this paper we develop a method for constructing such maps on the Weil descent (restriction) of abelian varieties over finite fields, including the Jacobian varieties of hyperelliptic curves and elliptic curves. The security of these candidate cryptographic trilinear maps raises several interesting questions, including the computational complexity of a trapdoor discrete logarithm problem.

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

17 extracted references · 17 canonical work pages

[1]

Weil, Adeles and Algebraic Groups, Progress in Math

A. Weil, Adeles and Algebraic Groups, Progress in Math. 23 , Birkhuser 1982. (Notes of Lectures given 1959-1960.)

work page 1982
[2]

Barak, O

B. Barak, O. Goldreich, R. Impagliazzo, S. Rudich, A. Saha i, S. Vadhan, and K. Yang, On the (im)possibility of obfuscating programs. In Advances in Cryptology , CRYPTO 2001, pp. 118. Springer, 2001

work page 2001
[3]

Boneh and A

D. Boneh and A. Silverberg, Applications of Multilinear F orms to Cryptography, Contemporary Mathematics Vol. 324, American Mathematical Society, pp. 71-90, 2003

work page 2003
[4]

Cantor, Computing in the jacobian of a hyperelliptic cu rve, Mathematics of computation V

D. Cantor, Computing in the jacobian of a hyperelliptic cu rve, Mathematics of computation V. 48. No. 177, pp. 95-101, 1987

work page 1987
[5]

Dent and S

A. Dent and S. Galbraith, Hidden pairings and trapdoor DDH groups. In ANTS (2006), F. Hess, S. Pauli, and M. E. Pohst, Eds., vol. 4076 of L ecture Notes in Computer Science, Springer, pp. 436451, 2006

work page 2006
[6]

Frey, How to disguise an elliptic curve (Weil descent)

G. Frey, How to disguise an elliptic curve (Weil descent). The 2nd El- liptic Curve Cryptography Workshop (ECC 98) (1998). Availa ble from http://www.cacr.math.uwaterloo.ca/conferences/1998/ecc98.frey.ps

work page 1998
[7]

Frey and T

G. Frey and T. Lange, Background on Weildescent, Chapter 7 in Handbook of elliptic curve and hyperelliptic curve cryptography , CRC Press 2006

work page 2006
[8]

Huang, Trilinear maps for cryptography, arXiv:180 3.10325, 2018

M.-D. Huang, Trilinear maps for cryptography, arXiv:180 3.10325, 2018

work page 2018

Show all 17 references

[9]

Huang, Trilinear maps for cryptography II, arXiv:1 810.03646, 2019

M.-D. Huang, Trilinear maps for cryptography II, arXiv:1 810.03646, 2019

2019
[10]

Huang and W

M.-D. Huang and W. Raskind, A Multilinedar Generalizati on of the Tate Pairing, with Wayne Raskind, Proc. 9th Int’l Conf. on Finite Fields and their Application s (Fq 9), AMS Contemporary Mathematics Series Vol 518 , ed. by G. Mullen, 255- 263, 2010

2010
[11]

Lin and S

H. Lin and S. Tessaro, Indistinguishability Obfuscatio n from Trilinear Maps and Block-Wise Local PRGs, in CRYPTO 2017

2017
[12]

Miller, Short programs for functions on curves, unpub lished manuscript, 1986

V. Miller, Short programs for functions on curves, unpub lished manuscript, 1986

1986
[13]

Miller, The Weil pairing, and its eﬃcient calculation , J

V. Miller, The Weil pairing, and its eﬃcient calculation , J. Cryptology 17 (2004) 235-261

2004
[14]

Cornell and J

J.S Milne, Abelian varieties, in Arithmetic Geometry G. Cornell and J. Silverman editors, Spring Verlag 1986

1986
[15]

Cornell and J

J.S Milne, Jacobian varieties, in Arithmetic Geometry G. Cornell and J. Silverman editors, Spring Verlag 1986

1986
[16]

Morales, An Attack on Disguised Elliptic Curves, Ma nuscript

D.M. Morales, An Attack on Disguised Elliptic Curves, Ma nuscript
[17]

Silverman, The arithmetic of elliptic curves , 2nd ed., Springer, 2009

J.H. Silverman, The arithmetic of elliptic curves , 2nd ed., Springer, 2009. 41

2009

Pith tools

Reviewed August 14, 2026 · model on record in the stance chip above.

[1] [1]

Weil, Adeles and Algebraic Groups, Progress in Math

A. Weil, Adeles and Algebraic Groups, Progress in Math. 23 , Birkhuser 1982. (Notes of Lectures given 1959-1960.)

work page 1982

[2] [2]

Barak, O

B. Barak, O. Goldreich, R. Impagliazzo, S. Rudich, A. Saha i, S. Vadhan, and K. Yang, On the (im)possibility of obfuscating programs. In Advances in Cryptology , CRYPTO 2001, pp. 118. Springer, 2001

work page 2001

[3] [3]

Boneh and A

D. Boneh and A. Silverberg, Applications of Multilinear F orms to Cryptography, Contemporary Mathematics Vol. 324, American Mathematical Society, pp. 71-90, 2003

work page 2003

[4] [4]

Cantor, Computing in the jacobian of a hyperelliptic cu rve, Mathematics of computation V

D. Cantor, Computing in the jacobian of a hyperelliptic cu rve, Mathematics of computation V. 48. No. 177, pp. 95-101, 1987

work page 1987

[5] [5]

Dent and S

A. Dent and S. Galbraith, Hidden pairings and trapdoor DDH groups. In ANTS (2006), F. Hess, S. Pauli, and M. E. Pohst, Eds., vol. 4076 of L ecture Notes in Computer Science, Springer, pp. 436451, 2006

work page 2006

[6] [6]

Frey, How to disguise an elliptic curve (Weil descent)

G. Frey, How to disguise an elliptic curve (Weil descent). The 2nd El- liptic Curve Cryptography Workshop (ECC 98) (1998). Availa ble from http://www.cacr.math.uwaterloo.ca/conferences/1998/ecc98.frey.ps

work page 1998

[7] [7]

Frey and T

G. Frey and T. Lange, Background on Weildescent, Chapter 7 in Handbook of elliptic curve and hyperelliptic curve cryptography , CRC Press 2006

work page 2006

[8] [8]

Huang, Trilinear maps for cryptography, arXiv:180 3.10325, 2018

M.-D. Huang, Trilinear maps for cryptography, arXiv:180 3.10325, 2018

work page 2018