ABAri Biswas

Ari Biswas

*This is an algorithmically generated author record based on publicly available information.

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:


Latest Publications

  • Open Access

    The Sum-Check Protocol over the Monomial Basis, and Other Optimizations

    by Quang Dao, Ari Biswas, Liam Eagen, Andrew Milson, Shahar Papini, Justin Thaler

    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

    Differentially Private Hierarchical Heavy Hitters

    by Ari Biswas, Graham Cormode, Yaron Kanza, Divesh Srivastava, Zhengyi Zhou

    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

    Interactive Proofs For Differentially Private Counting

    by Ari Biswas, Graham Cormode

    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.