Pith. sign in

REVIEW 2 major objections 4 minor 31 references

AG codes from the Hermitian curve for Cross-Subspace Alignment in Private Information Retrieval

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

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

Pith's one-line read The paper constructs X-secure T-private PIR schemes from AG codes on Hermitian curves, with rate 1−(X+T+3q^2−q−2)/N, and proves these out-perform earlier genus-0, genus-1, and hyperelliptic constructions at fixed field size.

desk verdict The Hermitian CSA-PIR construction is sound and the custom basis trick is real, but the paper's own rate tables use deg(Dfull) instead of the code length, understating the Hermitian rates; fix that and the comparison claims get stronger. read the letter →

arxiv 2508.19459 v1 pith:SSHBWPBR submitted 2025-08-26 math.AG cs.ITmath.IT

Francesco Ghiandoni , Massimo Giulietti , Enrico Mezzano , Marco Timpanella This is my paper · ORCID
classification math.AGcs.ITmath.IT MSC 11G2094B05
keywords privateinformationretrievalcross-subspacealignmentalgebraicgeometrycodesHermitiancurvemaximalcurvesX-secureT-privatePIRRiemann-Rochspacesfinitefields
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 constructs a private information retrieval (PIR) scheme whose code comes from the Hermitian curve H_q, a maximal curve over F_{q^2} with q^3+1 rational points. The construction fits the cross-subspace alignment (CSA) framework: Riemann–Roch spaces on H_q supply the encrypted, query, security, and privacy subspaces, and the curve's many rational points let the evaluation code be long, pushing the PIR rate to 1 − (X+T+3q^2−q−2)/N for X-secure, T-private retrieval. The authors derive the largest rate their method can reach and show that, for fixed field size and sufficiently large X+T, it exceeds the rates of earlier CSA schemes built from rational, elliptic, and hyperelliptic curves. A reader should care because PIR capacity is limited by download overhead, and this is a concrete family where more rational points on the underlying curve translate directly into less overhead.

What carries the argument

The load-bearing object is the divisor Dinfo = −(h) + (L+g(H_q)−1)P∞ on H_q, where h = ∏_{i=1}^m 1/(x−α_i) has poles at the mq selected points P_{i,z}. The paper constructs an explicit F_{q^2}-basis of L(Dinfo) from functions h_i^{(z)} = y^{z−1}∏(x−α_{i′}) and uses the divisors Dnoise = (X+T+4g(H_q)+q−2)P∞ + (q^2−1)P0 and Dfull = Dinfo's support plus Dnoise to satisfy the subspace conditions of Theorem 2.2. The evaluation map on a set of deg(Dfull)+1 rational points is injective, giving an information set of size N; the security and privacy parameters are controlled by the minimum distances of the dual codes of the corresponding evaluation codes. The point count q^3+1 of the Hermitian curve

What would settle it

Take q=11 with X=T=5, fix the mq points P_{i,z} in the construction, and count the distinct F_{121}-rational points of H_q outside {P∞,P0}∪{P_{i,z}}. The construction needs 1330 distinct points and H_q has 1332, leaving only two spare points; if any selected α_i or β_{i,z} causes a collision, the hypothesis of Theorem 3.3 fails and the maximum rate 429/789 is not attained for those parameters.

Watch

Extended reading notes

Core claim

On its own terms, the paper establishes Theorem 3.3: for the Hermitian curve H_q of genus q(q−1)/2, if L = mq − q(q−1)/2 with m chosen so that L + g(H_q) ≡ 0 (mod q), and if enough F_{q^2}-rational points of H_q remain after excluding P∞, P0, and mq selected affine points, then there exists an X-secure and T-private PIR scheme with rate R = L/N = 1 − (X+T+3q^2−q−2)/N, where N = L+X+T+3q^2−q−2. It then gives the maximum rate: L = mq − g(H_q) with m = floor((q^3−3q^2+q+1−(X+T))/(2q)). The improvement over earlier genus-0, genus-1, and hyperelliptic CSA schemes comes from H_q being F_{q^2}-maximal: its q^3+1 rational points allow longer evaluation sets, hence a larger L for the same security an

Load-bearing premise

The construction's advertised rates are only reachable if, after setting aside the Hermitian curve's point at infinity, the point P0, and the mq chosen affine points, enough distinct F_{q^2}-rational points remain to form the evaluation set; any collision or shortage of those points makes the maximum-rate formula unattainable.

Editorial extensions

If this is right

  • For fixed field size and sufficiently large X+T, the Hermitian scheme out-rates the genus-0 construction from Theorem 2.3, the elliptic construction from Theorem 2.4, and the hyperelliptic construction from Theorem 2.5.
  • The scheme answers the open direction in [20] of building CSA-based PIR from maximal curves; Hermitian curves are the first maximal family used this way.
  • Because the overhead term X+T+3q^2−q−2 does not grow with L, longer codes are strictly better: the rate approaches 1 as the curve supplies more usable rational points.
  • The explicit maximum-rate formula lets a designer choose q, X, T and immediately read off the best L and N for the Hermitian construction, without searching over divisors.

Reading between the lines

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

  • The comparison results depend on asymptotic conditions such as X+T ≥ 3(q+2); for small X+T, the Hermitian scheme may not beat elliptic or hyperelliptic ones, so the 'best curve' question is parameter-dependent rather than settled by maximality alone.
  • One could test whether other maximal curves, such as Suzuki or Ree curves, fit the same divisor template; the Hermitian construction uses an explicit basis of L(mP∞), so a similar basis for other Deligne–Lusztig curves would be the main obstacle.
  • The rate formula assumes the full set of q^3+1 rational points is available; in practice, the selected α_i and β_{i,z} must be checked for collisions, so a small-q implementation would reveal whether the advertised maximum is actually reachable.
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.

Referee Report

2 major / 4 minor

Summary. The paper constructs X-secure T-private PIR schemes using algebraic-geometry codes on the Hermitian curve H_q over F_{q^2}. The construction instantiates the CSA framework of [19] with Riemann-Roch spaces on H_q. Theorem 3.3 states that, under a point-count condition, there is an XSTPIR scheme with rate R = L/N and N = L + X + T + 3q^2 - q - 2, where L = mq - g(H_q). Proposition 3.5 optimizes L from the Hasse-Weil point count and gives a formula for the maximum rate; Section 4 compares these rates with the rational, elliptic, and hyperelliptic constructions from [19,20].

Significance. If the technical issues are repaired, the paper makes a solid contribution: it gives a new family of CSA-PIR schemes from a maximal curve, with a proof of Theorem 3.3 that is largely sound. Equations (19)-(21) correctly place Vnoise inside L(Dnoise), the intersection argument L(Dinfo)∩L(Dnoise)={0} is valid, and the dual-distance bounds yielding X+1 and T+1 are standard. The rates are not fitted; they are derived from Riemann-Roch and from the exact point count of the Hermitian curve. The main weakness is an internally inconsistent denominator in the rate-optimization statement and in Table 3, which understates the Hermitian scheme's rate. The qualitative comparison with other curve families appears robust, but the numerical claims must be corrected.

major comments (2)
  1. [Proposition 3.5 and Section 3] The maximum-rate formula in Proposition 3.5 uses the wrong N. Theorem 3.3 defines N = ℓ(Dfull) = deg(Dfull) - g(H_q) + 1 = L + X + T + 3q^2 - q - 2. In contrast, Proposition 3.5 states 'N = L + X + T + (7q^2 - 3q - 6)/2', which is deg(Dfull), not the code length/number of servers. This is not a harmless typo: the proof of Proposition 3.5 maximizes L with respect to this deg-based N, and Table 3 is computed accordingly. The errors understate the achievable rate. For q=11, X=T=5, Proposition 3.5 gives m=44, L=429, deg(Dfull)=843, but the correct N is 843-55+1=789, so the rate is 429/789≈0.5437, not 429/843≈0.5089 as listed. The same correction applies to every entry of the last row of Table 3. The point-count optimization itself is correct, but the rate formula and all numerical values depending on it must be recomputed with N=deg(Dfull)-g+1.
  2. [Table 3 and internal consistency] Table 3's last row, labelled q(q-1)/2, reports rates L/deg(Dfull) rather than L/N from Theorem 3.3. This makes the table inconsistent with the theorem it is supposed to illustrate. It also creates tension with Propositions 4.8 and 4.9, which (correctly) use N = L + X + T + 3q^2 - q - 2 in the denominators of the bounds. The manuscript should reconcile these: either Proposition 3.5 and Table 3 should be corrected to the Theorem 3.3 definition of N, or the theorem's N should be used everywhere. Until this is done, the numerical comparison between the Hermitian construction and the hyperelliptic constructions is not reliable as stated.
minor comments (4)
  1. [Proposition 4.8] The displayed derivative after the definition of P(q,M) is incorrect: ∂P/∂M = q^3 - 2q^2 - 3q + 1, not 2q^3 - 4q^2 - 4q - 4. The positivity conclusion still holds for q≥3, so this is a typographical error, but it should be fixed.
  2. [Proposition 4.9] The hyperelliptic equation is displayed as 'y2−x2q+1−a2gx2g+···+a0=0'; this appears to be a typo for 'y^2 - x^{2g+1} - a_{2g}x^{2g} - ... - a_0 = 0'. Please correct the exponent.
  3. [Theorem 3.3] The congruence condition is written as 'L+g(H_q)≡q 0'; this should be 'L+g(H_q) ≡ 0 (mod q)'.
  4. [Abstract and Section 4] The abstract claims the Hermitian construction achieves 'higher retrieval rates' than the other families without qualification. Section 4 shows this only for sufficiently large X+T (Propositions 4.8 and 4.9). Consider adding the qualifying regime to the abstract or conclusions.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the Hermitian PIR construction is derived from explicit Riemann–Roch computations and an external AG-code-to-PIR framework, not from its own conclusion.

full rationale

The central claim, Theorem 3.3, is a constructive existence statement. The paper defines the divisors Dinfo, Dnoise, Dfull explicitly (Eqs. (3), (16), (17)), proves an explicit basis of L(Dinfo) (Proposition 3.1 and Corollary 3.2), verifies the inclusions needed for Theorem 2.2, and computes the code length N = ℓ(Dfull) = deg(Dfull) − g(Hq) + 1 directly. The rate L/N is then obtained algebraically from that dimension count. No parameter is fitted to data, no prediction is renamed from an input, and no uniqueness theorem is imported from the authors' own prior work. The cited framework [19] is by a different research group, and the self-citations that do appear (e.g., background on Hermitian AG codes) are not load-bearing for the new construction. Proposition 3.5 maximizes L subject to the explicit point-count condition q^3+1 ≥ 2L + X + T + 4q^2 − 2q, which is a stated numerical existence requirement rather than a circular one. The comparisons in Section 4 are ordinary inequalities derived from the same formulas. I do flag one non-circular mathematical/notational error: in the proof of Proposition 3.5 and in Table 3, N is written as deg(Dfull) = L + X + T + (7q^2 − 3q − 6)/2, whereas Theorem 3.3 defines the number of servers as N = ℓ(Dfull) = deg(Dfull) − g + 1 = L + X + T + 3q^2 − q − 2. For example, q=11, X=T=5 gives L=429, deg(Dfull)=843, but ℓ(Dfull)=789, so the rate should be 429/789≈0.544, not 429/843≈0.509 as listed. This affects the reported numerical values, but it is an error of formula, not circularity: the erroneous expression is not equivalent to the input by construction. Hence the circularity score is 0.

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

No free parameters are fitted to data; X,T,L,q,g are inputs. The construction relies on standard results: Riemann-Roch, the Hasse-Weil bound, the maximality of H_q, the dual AG code distance bound, and the PIR-algebra framework from [19] as a black box. No invented entities are introduced.

assumptions (6)
  • standard math Riemann-Roch theorem
    Used to compute dimensions of L(Dinfo), L(Dsec), L(Dpriv), L(Dfull), and the dual distance bounds; invoked throughout Section 3.
  • standard math Hasse-Weil bound and maximal curve property
    Used to assert |H_q(F_{q^2})| = q^3+1 and the maximality of the Hermitian curve; Section 2.1.
  • standard math Known structure of Hermitian curves: genus q(q-1)/2, basis of L(mP∞)
    Proposition 2.1 and the point-count facts for H_q; needed for the construction of the basis in Proposition 3.1.
  • domain assumption Theorem 2.2 from [19], the CSA-PIR algebraic framework
    The entire scheme is built on this black-box theorem; the paper verifies its hypotheses rather than reproving it.
  • standard math Dual AG code minimum distance bound d⊥(C(D,G)) ≥ deg(G) - 2g + 2
    Used to derive X-security and T-privacy from the dimensions of L(Dsec_l) and L(Dpriv_l) in Theorem 3.3.
  • standard math Trace-map property: for every α ∈ F_{q^2}, the equation y^q+y = α^{q+1} has q distinct solutions in F_{q^2}
    Ensures the mq points P_{i,z} exist with distinct y-coordinates, as required in Proposition 3.1.

how reviews work

0 comments
Cite this review

Pith. "Pith review of AG codes from the Hermitian curve for Cross-Subspace Alignment in Private Information Retrieval." pith.science (2026). https://pith.science/paper/SSHBWPBR

@misc{pith2026250819459,
  author       = {Pith},
  title        = {Pith review of: AG codes from the Hermitian curve for Cross-Subspace Alignment in Private Information Retrieval},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/SSHBWPBR}},
  note         = {Machine review of arXiv:2508.19459}
}
abstract

Private information retrieval (PIR) addresses the problem of retrieving a desired message from distributed databases without revealing which message is being requested. Recent works have shown that cross-subspace alignment (CSA) codes constructed from algebraic geometry (AG) codes on high-genus curves can improve PIR rates over classical constructions. In this paper, we propose a new PIR scheme based on AG codes from the Hermitian curve, a well-known example of an $F_\ell$-maximal curve, that is, a curve defined over the finite field with $\ell$ elements which attains the Hasse-Weil upper bound on the number of its $F_\ell$-rational points. The large number of rational points enables longer code constructions, leading to higher retrieval rates than schemes based on genus 0, genus 1, and hyperelliptic curves of arbitrary genus. Our results highlight the potential of maximal curves as a natural source of efficient PIR constructions.

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

31 extracted references · 29 canonical work pages

  1. [19]

    Karpuk, and Camilla Hollanti

    Okko Makkonen, David A. Karpuk, and Camilla Hollanti. Algebraic geometry codes for cross- subspace alignment in private information retrieval. In2024 IEEE International Symposium on Information Theory (ISIT), pages 2874–2879. IEEE, 2024

    work page 2024

  2. [1]

    On hiding information from an oracle

    Martin Abadi, Joan Feigenbaum, and Joe Kilian. On hiding information from an oracle. In Proceedings of the nineteenth annual ACM symposium on Theory of computing, pages195–203, 1987. 15

    work page 1987

  3. [2]

    Adam and John C

    Nabil R. Adam and John C. Worthmann. Security-control methods for statistical databases: a comparative study.ACM Computing Surveys (CSUR), 21(4):515–556, 1989

    work page 1989

  4. [3]

    Upper bound on the communication complexity of private information retrieval

    Andris Ambainis. Upper bound on the communication complexity of private information retrieval. In International Colloquium on Automata, Languages, and Programming, pages 401–407. Springer, 1997

    work page 1997

  5. [4]

    Hiding instances in multioracle queries

    Donald Beaver and Joan Feigenbaum. Hiding instances in multioracle queries. In Annual symposium on theoretical aspects of computer science, pages 37–48. Springer, 1990

    work page 1990

  6. [5]

    Share conversion and private information retrieval

    Amos Beimel, Yuval Ishai, Eyal Kushilevitz, and Ilan Orlov. Share conversion and private information retrieval. InProceedings - 2012 IEEE 27th Conference on Computational Com- plexity, CCC 2012, Proceedings of the Annual IEEE Conference on Computational Com- plexity, pages 258–268, September 2012. IEEE Computer Society Technical Committee on Mathematical ...

    work page 2012

  7. [6]

    GCSA codes with noise alignment for secure coded multi-party batch matrix multiplication.IEEE Journal on Selected Areas in Information Theory, 2(1):306–316, 2021

    Zhen Chen, Zhuqing Jia, Zhiying Wang, and Syed Ali Jafar. GCSA codes with noise alignment for secure coded multi-party batch matrix multiplication.IEEE Journal on Selected Areas in Information Theory, 2(1):306–316, 2021

    work page 2021

  8. [7]

    Private information retrieval

    Benny Chor, Eyal Kushilevitz, Oded Goldreich, and Madhu Sudan. Private information retrieval. In Proceedings of IEEE 36th Annual Foundations of Computer Science, pages 41–

    work page

Show all 31 references
  1. [8]

    Private information retrieval

    Benny Chor, Eyal Kushilevitz, Oded Goldreich, and Madhu Sudan. Private information retrieval. Journal of the ACM (JACM), 45(6):965–981, 1998

    1998

  2. [9]

    Jones, and Richard J

    David Dobkin, Anita K. Jones, and Richard J. Lipton. Secure databases: Protection against user influence. ACM Transactions on Database systems (TODS), 4(1):97–106, 1979

    1979

  3. [10]

    Codes for distributed PIR with low storage overhead

    Arman Fazeli, Alexander Vardy, and Eitan Yaakobi. Codes for distributed PIR with low storage overhead. In 2015 IEEE International Symposium on Information Theory (ISIT), pages 2852–2856. IEEE, 2015

    2015

  4. [11]

    Protecting data privacy in private information retrieval schemes

    Yael Gertner, Yuval Ishai, Eyal Kushilevitz, and Tal Malkin. Protecting data privacy in private information retrieval schemes. InProceedings of the thirtieth annual ACM symposium on Theory of computing, pages 151–160, 1998

    1998

  5. [12]

    PIR codes from combinatorial structures

    Massimo Giulietti, Arianna Sabatini, and Marco Timpanella. PIR codes from combinatorial structures. In International Workshop on the Arithmetic of Finite Fields, pages 169–182. Springer, 2022

    2022

  6. [13]

    Princeton University Press, 2008

    James William Peter Hirschfeld, Gábor Korchmáros, and Fernando Torres.Algebraic curves over a finite field, volume 20. Princeton University Press, 2008

    2008

  7. [14]

    Van Lint, and Ruud Pellikaan

    Tom Høholdt, Jacobus H. Van Lint, and Ruud Pellikaan. Algebraic geometry codes.Handbook of coding theory, 1(Part 1):871–961, 1998

    1998

  8. [15]

    X-secure T-private information retrieval from MDS coded storage with Byzantine and unresponsive servers.IEEE Transactions on Information Theory, 66(12):7427–7438, 2020

    Zhuqing Jia and Syed Ali Jafar. X-secure T-private information retrieval from MDS coded storage with Byzantine and unresponsive servers.IEEE Transactions on Information Theory, 66(12):7427–7438, 2020. 16

    2020

  9. [16]

    Cross subspace alignment and the asymptotic capacity of X-secure T-private information retrieval

    Zhuqing Jia, Hua Sun, and Syed Ali Jafar. Cross subspace alignment and the asymptotic capacity of X-secure T-private information retrieval. IEEE Transactions on Information Theory, 65(9):5783–5798, 2019

    2019

  10. [17]

    Nagy, and Marco Timpanella

    Gábor Korchmáros, Gábor P. Nagy, and Marco Timpanella. Codes and gap sequences of Hermitian curves. IEEE Transactions on Information Theory, 66(6):3547–3554, 2019

    2019

  11. [18]

    Two-point AG codes from one of the Skabelund maximal curves

    Leonardo Landi, Marco Timpanella, and Lara Vicino. Two-point AG codes from one of the Skabelund maximal curves. IEEE Transactions on Information Theory, 70(7):4792–4798, 2024

    2024

  12. [20]

    Karpuk, and Camilla Hollanti

    Okko Makkonen, David A. Karpuk, and Camilla Hollanti. Secret Sharing for Secure and Pri- vate Information Retrieval: A Construction Using Algebraic Geometry Codes.arXiv preprint arXiv:2408.00542, 2024

    2024 arXiv

  13. [21]

    Matthews

    Gretchen L. Matthews. Codes from the Suzuki function field.IEEE Transactions on Infor- mation Theory, 50(12):3298–3302, 2004

    2004

  14. [22]

    Shah, KV Rashmi, and Kannan Ramchandran

    Nihar B. Shah, KV Rashmi, and Kannan Ramchandran. One extra bit of download ensures perfectlyprivateinformationretrieval. In 2014 IEEE International Symposium on Information Theory, pages 856–860. IEEE, 2014

    2014

  15. [23]

    How to share a secret.Communications of the ACM, 22(11):612–613, 1979

    Adi Shamir. How to share a secret.Communications of the ACM, 22(11):612–613, 1979

    1979

  16. [24]

    Algebraic function fields and codes, volume 254

    Henning Stichtenoth. Algebraic function fields and codes, volume 254. Springer Science & Business Media, 2009

    2009

  17. [25]

    Blind interference alignment for private information retrieval

    Hua Sun and Syed Ali Jafar. Blind interference alignment for private information retrieval. In 2016 IEEE International Symposium on Information Theory (ISIT), pages 560–564. IEEE, 2016

    2016

  18. [26]

    The capacity of private information retrieval.IEEE Transactions on Information Theory, 63(7):4075–4088, 2017

    Hua Sun and Syed Ali Jafar. The capacity of private information retrieval.IEEE Transactions on Information Theory, 63(7):4075–4088, 2017

    2017

  19. [27]

    On the capacity of locally decodable codes.IEEE Transactions on Information Theory, 66(10):6566–6579, 2020

    Hua Sun and Syed Ali Jafar. On the capacity of locally decodable codes.IEEE Transactions on Information Theory, 66(10):6566–6579, 2020

    2020

  20. [28]

    A note on certain maximal hyperelliptic curves.Finite Fields Their Appl., 18(5):1013–1016, 2012

    Saeed Tafazolian. A note on certain maximal hyperelliptic curves.Finite Fields Their Appl., 18(5):1013–1016, 2012

    2012

  21. [29]

    On a generalization of the Deligne–Lusztig curve of Suzuki type and application to AG codes.Journal of Mathematical Cryptology, 18(1):20230024, 2024

    Marco Timpanella. On a generalization of the Deligne–Lusztig curve of Suzuki type and application to AG codes.Journal of Mathematical Cryptology, 18(1):20230024, 2024

    2024

  22. [30]

    Washington

    Lawrence C. Washington. Elliptic curves: number theory and cryptography. Chapman and Hall/CRC, 2008. 17

    2008

  23. [41]

    IEEE Computer Society, 1995

    1995

Pith tools

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