Deriving concrete parameters from DARK

12 June 2026

Cryptography Computational Mathematics

For a recent project, I had to derive concrete parameters from the follow-up paper (Bünz and Fisch 2023) on the DARK polynomial commitment scheme. I wrote up the methodology notes in this post in case this is helpful to others.

Overview

The idea for the binding proof in DARK is simple from the following steps (for more, see Corollary 5):

1. For a multi-linear polynomial with bounded coefficients, evaluating at a fixed sufficiently large positive integer is injective. (Fact 1)
2. Commitment in DARK is basically evaluating rational polynomials with rational coefficients at a large point.
3. Combined with Fact 1, breaking binding amounts to breaking the hidden order assumption. This is formalized in Lemma 7.

As in the paper, we use \(W(\beta_n, \beta_d)\) to denote the set of vectors, which we can identify with their corresponding multi-linear polynomials, with the \(\ell_2\)-norm of the numerator vector bounded by \(\beta_n\) and the \(\ell_{\infty}\)-norm of the denominators bounded by \(\beta_d\).¹ Notice that we talk about the numerators and denominators informally, but this doesn’t matter for the proof, as the upper bound on the absolute value is achieved trivially if one reduces the denominator and numerator by their common factors. Similarly, we use \(W(\beta)\) to denote the set of integer multi-linear polynomials.

DARK shows that we can parameterize \(\beta_n\) and \(\beta_d\) to construct an upper bound \(\beta\), such that the DARK protocol is binding for rational multi-linear polynomials in \(W(\beta_n, \beta_d)\) and integer multi-linear polynomials in \(W(\beta)\). This is the content of Corollary 5.

Parameterization

We have the following parameterization: \[\begin{aligned} \beta_n &= 2^{\lambda\mu}\sqrt{\xi}\,\beta,\\ \beta_d &= \frac{\sqrt{\xi}}{2^{\lambda\mu}}, \end{aligned}\] where \(\mu = \log n\) is the number of interactive rounds in the DARK protocol, \(\lambda\) is the security bit parameter, and the parameter \(\xi\) is given by

\[\xi = 2^{(16+2\mu)\lambda+6\mathrm{CSZ}_{\mu,\lambda}+2\mu+6}.\]

The above is the parameterization used in the first paragraph of section 7.1, page 23. To make it more confusingly still, in Theorem 5 on page 25, \(\xi\) is parameterized by \(\log \xi = (14+2\mu)\lambda+6\text{CSZ}_{\mu,\lambda}+2(\mu+4)\), where the constant term is 8 instead of 6 and one factor of the \(\lambda\) term differs (16 vs 14). The value \(\text{CSZ}_{\mu,\lambda}\) is the associated bound in the composite Schwartz-Zippel lemma. In Theorem 5 on page 25, a looser analytic bound is used, but a footnote in the paper suggests that the values can be replaced with concrete values produced in Table 1 from Theorem 3.

Instantiation

We reproduced the computation of \(\mathrm{CSZ}\) and compare with the values in the paper for parameters \(\mu = 32\) and \(\lambda = 50\). We can compute the value of \(\mathrm{CSZ}\) to derive²

\[\begin{aligned} \log \beta_d &= 1422,\\ \log \beta_n &= 4622 + \log \beta. \end{aligned}\]

For the DARK protocol, we work with \(q = \lceil 2\sqrt{n}\beta \rceil\) as in Corollary 5 on page 22, so in particular \(\log q = 17 + \log \beta\) for \(\mu = 32\). The binding soundness bound is given by \(\frac{3\mu}{2^{\lambda}}\), which is given in the almost-special-soundness expression in the paragraph immediately following Theorem 5 on page 25. This gives about \(2^{-43.42}\) for \(\mu = 32\) and \(\lambda = 50\). We include the table showing computations for \(\mathrm{CSZ}\). We additionally highlight the value corresponding to 32 rounds in the interactive proof protocol at security level 50-bit.

The code below was used to produce the table.

import heapq
import math
from mpmath import mp, betainc, log, mpf
from sympy import nextprime

mp.dps = 40

def log2_I(p: int, r: int, mu: int):
    """log2 of I_{1/p}(r, mu); convention I(0, mu) = 1."""
    if r == 0:
        return mpf(0)
    return log(betainc(r, mu, 0, mpf(1) / p, regularized=True), 2)

def t_upper(mu: int, lam: int) -> int:
    """ceil of the greedy upper bound on log2 t(lambda, mu) -- Algorithm 1."""
    def item(p, r):
        w = log2_I(p, r - 1, mu) - log2_I(p, r, mu)
        return (-log(p, 2) / w, p, r, w)          # max-heap by density
    heap = [item(2, 1)]
    pmax = 2
    total_w, total_v = mpf(0), mpf(0)
    while total_w < lam:
        _, p, r, w = heapq.heappop(heap)
        total_v += log(p, 2)
        total_w += w
        heapq.heappush(heap, item(p, r + 1))
        if p == pmax:
            pmax = nextprime(p)
            heapq.heappush(heap, item(pmax, 1))
    return math.ceil(total_v)

References

• Bünz, Benedikt, and Ben Fisch. 2023. “Multilinear Schwartz-Zippel Mod N and Lattice-Based Succinct Arguments.” In Theory of Cryptography – TCC 2023, Part III, edited by Guy N. Rothblum and Hoeteck Wee, vol. 14371. Lecture Notes in Computer Science. Springer. https://doi.org/10.1007/978-3-031-48621-0_14.