Ari Biswas
Current Organizations / Institutes
The organizations/institutes from the scholar's latest article
Ari Biswas has a total of 9 co-authors. Here are the top co-authors by number of shared publications:
- Graham Cormode
University of Warwick University of Warwick
2 shared publications Andrew Milson
Attestable
1 shared publication- Divesh Srivastava
AT&T Chief Data Office, Bedminster, USA
1 shared publication - Justin Thaler
A16z Crypto Research
1 shared publication Liam Eagen
Ideal Group
1 shared publication- Quang Dao
Carnegie Mellon University, Pittsburgh, Pennsylvania, USA
1 shared publication
Latest Publications
- Open Access
- 26 October 2026
- Published by International Association for Cryptologic Research in IACR Communications in Cryptology
- Vol. 3 (3)
The Sum-Check Protocol over the Monomial Basis, and Other Optimizations
The sum-check protocol underpins SNARKs with the fastest known provers. For an n -variate polynomial g over a finite field ???? , it enables an untrusted prover to convince a verifier of the sum of all evaluations of g over a product set H n with H ⊂ ???? . The standard choice for H n is the Boolean hypercube { 0 , 1 } n , whose points double as the natural interpolation points for multilinear polynomials. We propose a projective variant of the sum-check protocol, obtained by changing this interpolating set from { 0 , 1 } n to the infinity hypercube { 0 , ∞ } n . Under a suitable notion of evaluation at ∞ , evaluating a multilinear polynomial at a point of { 0 , ∞ } n directly reads off one of its monomial coefficients. The values a prover stores are therefore already monomial coefficients, and no change of basis is needed. This makes the variant a near-drop-in replacement, requiring only local changes to how polynomials are stored and how each round's consistency check is written, and leaving the number of rounds, the proof size, and the verifier's work unchanged. It removes every field subtraction from the prover's per-round update, gives structured polynomials such as equality and less-than shorter formulas that evaluate in fewer field operations, and matches the coefficient representation used by commitment schemes such as WHIR, removing a basis mismatch those schemes otherwise work around. Against a baseline carrying all known optimizations, it yields a 6–12% speedup of the sum-check prover on BN254 and on a pseudo-Mersenne 128-bit prime field. Finally, we describe an optimization specific to approximately 256-bit prime fields, and hence to provers built on elliptic-curve commitments. When targeting approximately 128 bits of security, it suffices to draw challenges from a subset of size close to 2 128 . We choose that subset to be the values whose Montgomery representation occupies only the upper machine words, which makes field multiplication 1.94 × faster and the prover's per-round update 1.82 × faster in combination with the projective formula.
- 26 October 2026
- Published by International Association for Cryptologic Research in IACR Communications in Cryptology
- Vol. 3 (3)
Open AccessThe Sum-Check Protocol over the Monomial Basis, and Other Optimizations
The sum-check protocol underpins SNARKs with the fastest known provers. For an n -variate polynomial g over a finite field ???? , it enables an untrusted prover to convince a verifier of the sum of all evaluations of g over a product set H n with H ⊂ ???? . The standard choice for H n is the Boolean hypercube { 0 , 1 } n , whose points double as the natural interpolation points for multilinear polynomials. We propose a projective variant of the sum-check protocol, obtained by changing this interpolating set from { 0 , 1 } n to the infinity hypercube { 0 , ∞ } n . Under a suitable notion of evaluation at ∞ , evaluating a multilinear polynomial at a point of { 0 , ∞ } n directly reads off one of its monomial coefficients. The values a prover stores are therefore already monomial coefficients, and no change of basis is needed. This makes the variant a near-drop-in replacement, requiring only local changes to how polynomials are stored and how each round's consistency check is written, and leaving the number of rounds, the proof size, and the verifier's work unchanged. It removes every field subtraction from the prover's per-round update, gives structured polynomials such as equality and less-than shorter formulas that evaluate in fewer field operations, and matches the coefficient representation used by commitment schemes such as WHIR, removing a basis mismatch those schemes otherwise work around. Against a baseline carrying all known optimizations, it yields a 6–12% speedup of the sum-check prover on BN254 and on a pseudo-Mersenne 128-bit prime field. Finally, we describe an optimization specific to approximately 256-bit prime fields, and hence to provers built on elliptic-curve commitments. When targeting approximately 128 bits of security, it suffices to draw challenges from a subset of size close to 2 128 . We choose that subset to be the values whose Montgomery representation occupies only the upper machine words, which makes field multiplication 1.94 × faster and the prover's per-round update 1.82 × faster in combination with the projective formula.
- Open Access
- 4 November 2024
- Published by Association for Computing Machinery (ACM) in Proceedings of the ACM on Management of Data
- Vol. 2 (5) , 1-25
Differentially Private Hierarchical Heavy Hitters
The task of finding Hierarchical Heavy Hitters (HHH) was introduced by Cormode et al. [12] as a generalisation of the heavy hitter problem. While finding HHH in data streams has been studied extensively, the question of releasing HHH when the underlying data is private remains unexplored. In this paper, we formalise and study the notion of differentially private HHH, in both the streaming and non-streaming setting. In the non-streaming setting, we show the surprising result that the relative error in estimating the count for any prefix is independent of the height of the hierarchy and the number of heavy hitters in the stream. Additionally, our algorithms also improve the error guarantees of Ghazi et al. [24] for the problem of counting over trees. Meanwhile, in the streaming setting, the main issue is that although the exact version of HHH has low global sensitivity (as counting queries are 1-sensitive), the approximation functions due to streaming have high global sensitivity, linear in the available space. Despite this obstacle, we show that the absolute error for estimating frequencies in the streaming setting is independent of the available space.
- 4 November 2024
- Published by Association for Computing Machinery (ACM) in Proceedings of the ACM on Management of Data
- Vol. 2 (5) , 1-25
Open AccessDifferentially Private Hierarchical Heavy Hitters
The task of finding Hierarchical Heavy Hitters (HHH) was introduced by Cormode et al. [12] as a generalisation of the heavy hitter problem. While finding HHH in data streams has been studied extensively, the question of releasing HHH when the underlying data is private remains unexplored. In this paper, we formalise and study the notion of differentially private HHH, in both the streaming and non-streaming setting. In the non-streaming setting, we show the surprising result that the relative error in estimating the count for any prefix is independent of the height of the hierarchy and the number of heavy hitters in the stream. Additionally, our algorithms also improve the error guarantees of Ghazi et al. [24] for the problem of counting over trees. Meanwhile, in the streaming setting, the main issue is that although the exact version of HHH has low global sensitivity (as counting queries are 1-sensitive), the approximation functions due to streaming have high global sensitivity, linear in the available space. Despite this obstacle, we show that the absolute error for estimating frequencies in the streaming setting is independent of the available space.
- Open Access
- 15 November 2023
- Published by Association for Computing Machinery (ACM)
- p. 1919-1933
Interactive Proofs For Differentially Private Counting
Differential Privacy (DP) is often presented as a strong privacy-enhancing technology with broad applicability and advocated as a de facto standard for releasing aggregate statistics on sensitive data. However, in many embodiments, DP introduces a new attack surface: a malicious entity entrusted with releasing statistics could manipulate the results and use the randomness of DP as a convenient smokescreen to mask its nefariousness. Since revealing the random noise would obviate the purpose of introducing it, the miscreant may have a perfect alibi. To close this loophole, we introduce the idea of Interactive Proofs For Differential Privacy, which requires the publishing entity to output a zero knowledge proof that convinces an efficient verifier that the output is both DP and reliable. Such a definition might seem unachievable, as a verifier must validate that DP randomness was generated faithfully without learning anything about the randomness itself. We resolve this paradox by carefully mixing private and public randomness to compute verifiable DP counting queries with theoretical guarantees and show that it is also practical for real-world deployment. We also demonstrate that computational assumptions are necessary by showing a separation between information-theoretic DP and computational DP under our definition of verifiability.
- 15 November 2023
- Published by Association for Computing Machinery (ACM)
- p. 1919-1933
Open AccessInteractive Proofs For Differentially Private Counting
Differential Privacy (DP) is often presented as a strong privacy-enhancing technology with broad applicability and advocated as a de facto standard for releasing aggregate statistics on sensitive data. However, in many embodiments, DP introduces a new attack surface: a malicious entity entrusted with releasing statistics could manipulate the results and use the randomness of DP as a convenient smokescreen to mask its nefariousness. Since revealing the random noise would obviate the purpose of introducing it, the miscreant may have a perfect alibi. To close this loophole, we introduce the idea of Interactive Proofs For Differential Privacy, which requires the publishing entity to output a zero knowledge proof that convinces an efficient verifier that the output is both DP and reliable. Such a definition might seem unachievable, as a verifier must validate that DP randomness was generated faithfully without learning anything about the randomness itself. We resolve this paradox by carefully mixing private and public randomness to compute verifiable DP counting queries with theoretical guarantees and show that it is also practical for real-world deployment. We also demonstrate that computational assumptions are necessary by showing a separation between information-theoretic DP and computational DP under our definition of verifiability.