cfrg/draft-irtf-cfrg-vdaf

Apply parallel sum gadget optimization to Prio3Histogram

Closed this issue · 0 comments

The range check portion of the Prio3Histogram circuit could be rewritten to use the parallel sum gadget. This would result in more wire polynomials, each of smaller degree, smaller proofs ($O(\sqrt{n})$ instead of $O(n)$), faster proving, and larger preparation message shares ($O(\sqrt{n})$ instead of $O(1)$). See #124 (comment).