4
$\begingroup$

For calculating accumulated values for set of elements chosen randomly from, say, $\{e_1 ,e_2,...e_n\}\subseteq X$ we use the formula $acc= g^{f(e,s)}$ where $f(e,s)= (e_1+s)(e_2+s).....(e_n+s)$.

Then, the witness for $e_k$ is calculated as $wit_{e_k} = g^{\prod(e_i+s)} $ where $i \ne k $ (i.e., accumulating all values except $e_k$).

This can be calculated by dividing $f(e,s)/(e_k+s)$ (assuming all $e_i$'s and $s$ are known to me) and raising $g$ to it.

My question is not about the application or purpose of cryptographic accumulators but about some mathematical clarifications:

  1. While computing $f(e,s)$, do I have to do modular arithmetic on $P$ where $P$ is a prime number representing the order of group $\mathbb{G}$?

  2. Also, one paper stated that it is impossible to create a witness for an element which is not accumulated into it. Will anybody please elaborate on it?

  3. By dividing $f(e,s)$ by $(e_k+s)$ one can calculate a witness value. Is there any way to distinguish between the witness (let me call it) values that where computed when $e_k$ is accumulated in $f(e,s)$ and when it is not accumulated $f(e,s)$?

$\endgroup$
  • $\begingroup$ Yes, assuming P is the order of group G, then operations with exponents should be done modulo P. $\endgroup$ – cygnusv May 26 '15 at 7:19
  • $\begingroup$ The whole point with a construction like accumulator introduced is how one would verify a statement about values accumulated. To be useful, there should be a hard problem and maybe a trapdoor. For example, there could be a group of a hidden order (that is, like RSA, not of some prime order) so "dividing in the exponent" is not possible without the order. Alternatively, $s$ could be a secret. Or, one could sign such an accumulator with a private key. I'd expect rather creative verification relation/technique/protocol. $\endgroup$ – Vadym Fedyukovych May 26 '15 at 11:08
5
$\begingroup$

This can be calculated by dividing $f(e,s)/(e_k+s)$ (assuming all $e_i$'s and $s$ are known to me) and raising $g$ to it.

First, if the prover knows $s$, it doesn't need to know the $e_i$'s to create membership witnesses. It can simply raise the accumulator $\mathsf{acc}$ to $1/(e_k + s)$: \begin{align*} \mathsf{wit}_{e_k} &= \mathsf{acc}^{\frac{1}{e_k + s}} = {g^{f(e,s)/{(e_k + s)}}} = g^{\prod_{i\ne k}{(e_i+s)}} \end{align*}

This brings me to my second point: knowledge of $s$ allows the prover to create fake membership witnesses for any $e$ that was not accumulated. This is because the prover can compute $\frac{1}{e + s}$ for any $e$.

So, yes, computing $f(e,s)/(e_k+s)$ and then raising $g$ to it is one way to calculate the witness, but it's a bad idea: the prover can easily create fake witnesses for any non-accumulated $e$ if it knows $s$. Computing witnesses in this way only makes sense when there's a trusted party that knows $s$. This trusted party computes and outsources witnesses to an untrusted "prover" who merely relays these witnesses to verifiers (i.e., the 2- or 3- party models of authenticated data structures).

Requiring a trusted party that knows $s$ is unreasonable in many applications. In practice, we want to prevent the (untrusted) prover from faking witnesses, by ensuring it does not know $s$. We can do this via a trusted setup phase that gives the prover public parameters $\left(g^{s^i}\right)_{0\le i\le q}$ but does not give him $s$. This trusted setup phase is run by some trusted "guy in the sky," which in practice can be implemented via MPC protocols (see Scalable Multi-party Computation for zk-SNARK Parameters in the Random Beacon Model). Here $q$ is a strict upper bound on the number of elements you will ever accumulate.

Now, in order to commit to a set $A = \{e_1, \dots, e_n\}, n\le q$ of items, you first have to compute the coefficients of the polynomial $f(e, x)$ using Lagrange interpolation in $O(n^2)$ time, Newton interpolation in $O(n^2)$ time or FFT interpolation in $O(n\log^2{n})$ time.

Note that you don't need to know $s$ to interpolate. Consider $A = \{1,2,3\}$. Its polynomial $f_A(x) = (x-1)(x-2)(x-3) = x^3 - 6 x^2 + 11 x - 6$, so its coefficients are $(1, -6, 11, -6)$.

Once you have the coefficients $\{c_1, \dots, c_n\}$ you can compute the accumulator $acc$ by raising the $\left(g^{s^i}\right)_{0\le i\le n}$ public parameters to the coefficients: \begin{align*} acc &= \left(g^{s^n}\right)^{c_n} \left(g^{s^{n-1}}\right)^{c_{n-1}} \dots (g^s)^{c_1} \left(g\right)^{c_0}\\ &= g^{c_n s^n} g^{c_{n-1} s^{n-1}} \dots g^{c_1 s} g^{c_0}\\ &= g^{c_n s^n+ c_{n-1} s^{n-1} + \dots + c_1 s + c_0}\\ &= g^{f(e,s)} \end{align*}

For example, for our set $A$ above, the prover computes its accumulator as $(g^{s^3})^1 (g^{s^2})^{-6} (g^{s})^{11} g^{-6} = g^{s^3 - 6 s^2 + 11 s - 6} = g^{f_A(s)}$. Note that the prover does not need $s$ to compute $g^{f_A(s)}$ as long as it has the public parameters. In my experience, most accumulator papers do not explain this step, partly because they only look at the two- or three-party models of authenticated data structures where there actually exists a trusted party that knows $s$. (In other words, the "Hey, let's play with fire!" model.)

To answer your other questions,

  1. While computing $f(e,s)$, do I have to do modular arithmetic on $P$ where $P$ is a prime number representing the order of group $\mathbb{G}$?

If you know the trapdoor $s$ (i.e., insecure mode), then yes, computing $f(e,s)$ involves adding and multiplying things modulo $P$ as per its definition.

If you don't know the trapdoor $s$, then computing $f(e,s)$ involves adding, multiplying and inverting numbers (for Lagrange and Newton) modulo $P$. If you're using FFT interpolation, it also involves roots of unity in the field of order $P$ (i.e., the field "in the exponent").

  1. Also, one paper stated that it is impossible to create a witness for an element which is not accumulated into it. Will anybody please elaborate on it?

As I described before, the prover cannot fake witnesses only when the prover does not know the trapdoor $s$. I can't find the security proof in Lan Nguyen's original paper on accumulators, but it's a reduction to $q$-Strong Diffie-Hellman ($q$-SDH). The intuition behind why membership witnesses are secure is that without the trapdoor, nobody can compute any pair of the form $(e, g^\frac{1}{e + s})$.

  1. By dividing $f(e,s)$ by $(e_k+s)$ one can calculate a witness value.

Yes, but remember that this requires the prover to know the trapdoor, which is not secure (unless you're in the "Hey, let's play with fire!" model).

Is there any way to distinguish between the witness (let me call it) values that where computed when $e_k$ is accumulated in $f(e,s)$ and when it is not accumulated $f(e,s)$?

Before I can answer this question, you have to clarify what element(s) these witnesses are for and what does the adversary know? Do they know the elements accumulated in the two accumulators?

$\endgroup$
  • $\begingroup$ How can you compute the coefficients for f(e, x) if you don't know the trapdoor? Even in Nguyen's paper adding to the accumulator seems to require knowing s? $\endgroup$ – Matthew Jul 20 '18 at 10:03
  • 2
    $\begingroup$ Updated my answer to address this. Excerpt: "Note that you don't need to know $s$ to interpolate. Consider $A = \{1,2,3\}$. Its polynomial $f_A(x) = (x-1)(x-2)(x-3) = x^3 - 6 x^2 + 11 x - 6$, so its coefficients are $(1, -6, 11, -6)$." Also, "the prover computes A's accumulator as $(g^{s^3})^1 (g^{s^2})^{-6} (g^{s})^{11} g^{-6} = g^{s^3 - 6 s^2 + 11 s - 6} = g^{f_A(s)}$. Note that the prover does not need $s$ to compute $g^{f_A(s)}$ as long as it has the public parameters." (i.e., the $g^{s^i}$'s) $\endgroup$ – Alin Tomescu Jul 20 '18 at 16:41

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.