{"id":"0fb76319-5ccd-45d5-a7e9-82f1aef04848","arxiv_id":"1908.06891","paper_version":3,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"high","formal_verification":"none","parameter_count":4,"one_line_summary":"A candidate construction of trilinear maps from Weil descents of abelian varieties, whose third group hides a discrete logarithm behind a secret descent basis and quadratic relations.","lead":"This paper proposes a way to build cryptographic trilinear maps using Weil descent of abelian varieties over finite fields, including Jacobians of hyperelliptic curves and elliptic curves. If the proposed trapdoor discrete logarithm assumptions hold, such maps could support indistinguishability obfuscation.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Public blinding matrices are commuting projections; simultaneous diagonalization recovers the secret basis and breaks the trapdoor.","rationale":"The paper's central claim is a candidate cryptographic trilinear map whose security rests entirely on the secrecy of the descent basis u and the blinded matrices Γ, W, Ψ_i. The reader's weakest assumption identified exactly this: if u can be recovered from the published data, the construction collapses. My stress-test sharpens that concern into a concrete attack. The published matrices Ω_{a,b} are not arbitrary matrices with hidden subsets; they are Γ^{-1}E_IΓ, i.e., projections that are simultaneously diagonalizable. Because W=Γ^{-1}, the common eigenbasis is the set of columns of W, which is the secret data itself. Recovering this eigenbasis is standard linear algebra over k and is polynomial-time. The paper's own §8 lists the problem of recovering u from W_IΓ_I as open; the simultaneous-diagonalization observation shows the abstracted subproblem is easy for the stated parameter regime. This is not a matter of unproven but plausible hardness: it is a structural algebraic weakness in the blinding mechanism. I therefore recommend REJECT rather than CONDITIONAL. The paper is otherwise clearly written and honestly flags its open problems, but the specific security mechanism at the heart of the construction does not withstand this linear-algebraic analysis.","tokens_in":36756,"tokens_out":20389,"duration_ms":226475,"concrete_test":"Run a small instance (d=8 or 16, k=F_q with q=101): choose a random basis u, build Γ and W=Γ^{-1}, choose N=d^2 random subsets I_i of size d^{1/2}, and publish A_i=Γ^{-1}E_{I_i}Γ. Compute images and kernels of the A_i and take intersections (or diagonalize a random linear combination). Check whether the recovered one-dimensional spans equal the columns of W up to scaling. If yes, the projection subproblem of §8 is solvable in polynomial time. Then, to confirm the full break, reconstruct the candidate Γ and verify against the published descent equations \\hat V and \\hat m that the remaining k^* scalar is uniquely determined.","verdict_should_be":"REJECT","load_bearing_attack":"The construction's security collapses at the public blinding data. In §3 and §4.1, each blinded map Ψ_i is specified by publishing the matrices Ω_{a,b}=W_{I_{a,b}}Γ_{I_{a,b}} for the partition I_{a,b} of {0,...,d-1} (Proposition 11). Since W=Γ^{-1}, each Ω is Γ^{-1}E_IΓ: an idempotent projection onto the coordinate subspace I in the eigenbasis given by the columns of W=Γ^{-1}. All published Ω therefore commute, and within one Ψ_i they form an orthogonal resolution of I_d. The adversary can compute the image and kernel of each projection and intersect them across the O(d^2) public matrices. For the random subsets I_{a,b} required in §3, the incidence pattern separates coordinates, so each one-dimensional span k·col_j(W) is recovered. This gives W up to column scaling, hence Γ up to row scaling; the Frobenius relation row_{i+1}=σ(row_i) fixes the row scaling and order up to a single k^* scalar, and the published descent equations \\hat V and \\hat m, which depend on u, fix that scalar. This is a polynomial-time linear-algebra attack, not the quadratic-system or exhaustive-subset analysis considered in §2.8. It affirmatively answers Open Problem 2 of §8 and invalidates the core security premise of §1 and §3 that the secret descent basis cannot be uncovered.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","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.","tokens_in":37070,"tokens_out":17212,"duration_ms":194702,"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":[{"comment":"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.","section":"§2.8 (Prop. 11), §3, §4.1"},{"comment":"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.","section":"§2.4–§2.6, Theorems 1 and 2"}],"minor_comments":[{"comment":"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}}.","section":"§2.8"},{"comment":"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.","section":"§3 and §8"},{"comment":"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.","section":"Throughout"},{"comment":"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.","section":"§3–§4"}],"recommendation":"reject","confidential_remarks":"The manuscript is honest and the algebraic core is competently developed, but the public data are vulnerable to a standard simultaneous-diagonalization attack. This is not a fixable local issue: the construction itself publishes the projections. I recommend rejection. If the authors pursue a revision, they would need a fundamentally different blinding mechanism."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","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.\n\nThe 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.\n\nOther 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.\n\nWho 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.\n\nRecommendation: send it to peer review. The central security claim fails, but the algebraic machinery is substantive and worth separating from the broken claim.","headline":"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.","tokens_in":37557,"tokens_out":5515,"would_cite":false,"duration_ms":56463,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["11T71","94A60","14G50","11G20","14H40"],"pacs":[],"model":"deepseek-v4-flash","headline":"Weil descent builds trilinear maps with a hidden trapdoor.","keywords":["trilinear maps","multilinear maps","Weil descent","Weil restriction","trapdoor discrete logarithm","indistinguishability obfuscation","pairings","hyperelliptic Jacobians"],"falsifier":"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.","tokens_in":36540,"feed_emoji":"🔐","tokens_out":15073,"duration_ms":137463,"temperature":0.7,"pith_summary":"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.","feed_headline":"Weil descent builds trilinear maps with a hidden trapdoor","feed_subtitle":"A secret field basis hides the third group's discrete log; if it holds, these maps lead toward program obfuscation.","key_machinery":"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.","core_discovery":"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.","pith_inferences":["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."],"forward_implications":["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."],"supporting_citations":[{"why":"Supplies the Weil-restriction formalism used to define descent varieties and descent maps from a variety over an extension field.","marker":"[1]"},{"why":"Gives the necessary conditions that make Galois-equivariant multilinear maps to $\\mu_\\ell$ difficult, framing why a descent-based construction is needed.","marker":"[3]"},{"why":"Provides the addition-and-reduction arithmetic for hyperelliptic Jacobians on which Theorem 1's efficient pairing specification is built.","marker":"[4]"},{"why":"Introduces hidden pairings and trapdoor DDH groups by disguising elliptic curves, the idea this paper carries over to Weil descent.","marker":"[5]"},{"why":"Gives the standard background on Weil descent that the blinding construction adopts and extends.","marker":"[7]"},{"why":"Previous trilinear map constructed from torsion pairings and the map $\\phi_L$, which this paper adapts and blinds through descent.","marker":"[8]"},{"why":"Shows trilinear maps are sufficient for indistinguishability obfuscation, the motivating application that makes the construction worth pursuing.","marker":"[11]"},{"why":"Supplies the efficient Weil pairing and squaring trick used to compute the blinded pairing on torsion points.","marker":"[13]"},{"why":"The attack on disguised elliptic curves that this paper's affine, descent-based specification is designed to avoid.","marker":"[16]"}],"fun_headline_variants":["Weil descent yields trilinear maps with a hidden trapdoor","Trilinear maps from Weil descent with a secret basis","Weil descent trapdoor enables trilinear map construction","Secret basis on Weil descent hides trilinear map's discrete log","Trapdoor discrete log in Weil descent for trilinear maps"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"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.","fun_headline_variants_meta":{"raw":{"variants":["Weil descent yields trilinear maps with a hidden trapdoor","Trilinear maps from Weil descent with a secret basis","Weil descent trapdoor enables trilinear map construction","Secret basis on Weil descent hides trilinear map's discrete log","Trapdoor discrete log in Weil descent for trilinear maps"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000342,"raw_usage":{"total_tokens":1887,"prompt_tokens":958,"completion_tokens":929,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":574,"completion_tokens_details":{"reasoning_tokens":847}},"tokens_in":574,"tokens_out":929,"duration_ms":8152,"temperature":1.0,"reasoning_tokens":847,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-14T12:31:56.503660+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"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.","supporting_citations":[{"cited_title":"Weil, Adeles and Algebraic Groups, Progress in Math","cited_arxiv_id":null,"evidence_quote":"Supplies the Weil-restriction formalism used to define descent varieties and descent maps from a variety over an extension field."},{"cited_title":"Boneh and A","cited_arxiv_id":null,"evidence_quote":"Gives the necessary conditions that make Galois-equivariant multilinear maps to $\\mu_\\ell$ difficult, framing why a descent-based construction is needed."},{"cited_title":"Cantor, Computing in the jacobian of a hyperelliptic cu rve, Mathematics of computation V","cited_arxiv_id":null,"evidence_quote":"Provides the addition-and-reduction arithmetic for hyperelliptic Jacobians on which Theorem 1's efficient pairing specification is built."},{"cited_title":"Dent and S","cited_arxiv_id":null,"evidence_quote":"Introduces hidden pairings and trapdoor DDH groups by disguising elliptic curves, the idea this paper carries over to Weil descent."},{"cited_title":"Frey and T","cited_arxiv_id":null,"evidence_quote":"Gives the standard background on Weil descent that the blinding construction adopts and extends."},{"cited_title":"Huang, Trilinear maps for cryptography, arXiv:180 3.10325, 2018","cited_arxiv_id":null,"evidence_quote":"Previous trilinear map constructed from torsion pairings and the map $\\phi_L$, which this paper adapts and blinds through descent."},{"cited_title":"Lin and S","cited_arxiv_id":null,"evidence_quote":"Shows trilinear maps are sufficient for indistinguishability obfuscation, the motivating application that makes the construction worth pursuing."},{"cited_title":"Miller, The Weil pairing, and its efficient calculation , J","cited_arxiv_id":null,"evidence_quote":"Supplies the efficient Weil pairing and squaring trick used to compute the blinded pairing on torsion points."},{"cited_title":"Morales, An Attack on Disguised Elliptic Curves, Ma nuscript","cited_arxiv_id":null,"evidence_quote":"The attack on disguised elliptic curves that this paper's affine, descent-based specification is designed to avoid."}],"review_version":1}