# Tag Info

## Hot answers tagged accumulators

16

You could use the hash value as seed for a deterministic CSPRNG and then use a prime number generator also used for RSA key pair generation. Note that the size of the prime number must be relatively high (1536 bits for 128 bits of security, e.g. for an RSA key of 3072 bits). The usual caveats of deterministic RSA key pair generation apply. For instance, the ...

8

An advantage of a cryptographic accumulator and actually the reason to use them is that due to the quasi commutativity you can compute witnesses for membership of values in the accumulator where the accumulator and the witnesses are of constant size. Say you have a set $Y=\{y_1,y_2,y_3\}$ and compute the accumulator as $acc=f(f(f(x,y_1),y_2),y_3)$ you ...

6

Look at group signatures (but use one of the more modern schemes; they are proven secure). The signature can be applied to a running counter, or a random challenge. Group signatures also give you a lot of "management" options which can be useful depending on the application. If you don't need them, then you can use ring signatures (but the verifier has to ...

6

Sure. Use the strong RSA assumption. The accumulator of $x_1,\dots,x_k$ is $A = g^{x_1 x_2 \cdots x_k} \bmod n$, where $n$ is a RSA modulus and $g$ is a fixed base. To prove that the accumulator $A$ contains $x$, exhibit a value $h$ such that $h^x=A \pmod n$. This is secure under the strong RSA assumption, and has a discrete log "feel" to it.

6

As D.W. notes, this works for the purpose in question. Actually, relying on number theoretic assumptions for the accumulators will give you no benefit as you have observed. However, here is a construction of accumulators from Nyberg in FSE'96, which does not rely on number theoretic or any computational assumptions. This is the paper of Nyberg and you may ...

6

Yes, they can be used for that purpose. The challenge in practice is exactly what you mentioned: if we're willing to trust number-theoretic assumptions, we usually don't need Lamport signatures. Nonetheless, they can be used in this way.

5

It seems they can be used for that purpose. I found this paper: "Collision-Free Accumulators and Fail-Stop Signature Schemes Without Trees" Niko Baric and Birgit Pfitzmann Eurocrypt '97, LNCS, Springer-Verlag, Berlin 1997.

5

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 ...

5

I think what makes this difficult is the definition of "secure." Clearly $H(m)=2$ always outputs a prime number, but it is not considered secure. For it to be "secure," one would expect every prime number to have an equal probability of being chosen, given a random input. Since you can enumerate the prime numbers below a certain value, the problem is ...

4

Disclaimer: I am not a hard-core cryptographer, and I am only familiar with a subset of the various accumulator implementations. So this is a layman's answer. Accumulators are not attempting to set a bit for every member of the set. The reason they can violate the intuition that they must have at least 1 bit for every potential set member is because they ...

4

I'm assuming you are talking about the typical dynamic RSA accumulator from "Dynamic Accumulators and Application to Efficient Revocation of Anonymous Credentials", by Camenicsh and Lysyanskaya (see PDF here). First, recall that the accumulator over prime elements $x_1, x_2, \dots, x_n$ is computed in $O(n)$ time as: \begin{align*} A &= g^{x_1 x_2 \...

4

I guess you are missing something. If you know that the accumulator value is $a=v^{\prod_i x_i} \bmod n$ to a set of values $x_i$ and you know the factorization of $n$, then it is easy to for any arbitrary $y$ relatively prime to $n$ (in RSA accumulators you accumulate primes) a value $k$ such that $y\cdot k \equiv 1 \pmod{\varphi(n)}$ as the value $\... 4 In your setting this is assumed to be hard. It is exactly the task of producing a forgery for message$s$of the weakly secure Boneh-Boyen signature scheme (Sec. 3.1) under public key$g^{e_1}$(note that the scheme is presented in the asymmetric setting but can equally be instantiated in the symmetric setting under the$q$-SDH assumption). In other words, ... 3 This is actually quite a common problem in cryptographic systems. This can be looked at as proving two different things: Is the server currently storing all of the elements a specific client has given it before in order (is it honest with us)? Is it giving us all of the other client's data (is it honest with others)? Will it continue to act as an append-... 3 If I understand your quantifies (for any given irreducible$f(x)$, there does not exist such an algorithm), then it’s a stronger assumption and one that is unlikely to be true as$n$grows. First, note that if we write$x_i$for$g^{s_i}$then the degree (at most)$n$polynomial$\sum c_is^i$gives $$g^{\sum c_is^i}=\prod x_i^{c_i}$$ as easily calculable. ... 2 In short: The parent CA would sign the public key of an n-time signature scheme, as opposed to the public key of a signature scheme which is valid for an unbounded number of signatures (the current design). n-time signature schemes are usually just constructed by generating n instances of a one-time signature scheme and then accumulating their public keys ... 2 Looks like one of the vector commitment (VC) schemes by Catalano and Fiore comes closest to what you need [1]. Specifically, the one based on Computational Diffie Hellman (CDH) (see Section 3.1 in their paper). You might also be able to verify membership of$x$using$g^x$rather than$x$itself if you can use a discrete log equality proof between the VC's${...

2

Here's an overview of a strong [1], append-only accumulator with your desired properties. This accumulator was originally introduced by Reyzin and Yakoubov in [3]: Supports provable batch additions. Is publicly updatable. The information to update all witnesses is sublinear in the number of elements added. I'll describe this scheme by example, since ...

2

Any signature scheme can work as an accumulator: when elements are signed with the manager's secret key, signature works as a system membership witness (positive acc). It is also additive because you can only add elements in the system by signing them, you cannot cancel a signature in the future (to delete them).

2

I think what you want is a ring signature. This is a signature mechanism that allow you to prove someone signed within a set of actor without revealing which one. You may want to read https://link.springer.com/chapter/10.1007%2F3-540-45682-1_32 and https://github.com/Blockstream/borromean_paper/raw/master/borromean_draft_0.01_34241bb.pdf

2

Given the trapdoor, one would delete an element from RSA accumulator in constant time. In particular, produce an inverse to the element with extended Euclid algorithm and power-to accumulator to the inverse. The element in question would cancel-out from accumulator this way.

2

Another (naive) solution: Take you favourite (cryptographic) hash function $H$. For an element $x \in \{0,1\}^*$, define $H'(x)$ as the first prime number in the $H$-orbit of $x$. That is, \begin{align*} & n_x := \min \{n:\ H^{(n)}(x) \text{ is prime} \} ; \\ & H' (x) := H^{(n_x)}(x), \end{align*} where $H^{(n)}(x)$ is the $n$-fold iteration $(... 2 I've read a little about this area years ago. The naive example of an accumulator is simply multiplying primes together into the accumulator, which can then be checked for their presence simply by division. This obviously results in persistent growth of the accumulator. I looked for an accumulator that addressed the endless growth issue, but I was never ... 2 Yes. More generally, suppose you know the size of the group$\mathbb{G}$you are working in (RSA, class group etc). Let$A = g^n$where$n$is the product of the elements in the committed set. Assuming$n$is co-prime to$|\mathbb{G}|$, you can compute integers$a_1$,$a_2$such that $$a_1 x + a_2 n \equiv 1 \pmod{|\mathbb{G}|}\;\;,\;\; |a_2| < |x|.$$ ... 1 OK posting my own answer, not sure if this is correct, but: The RSA accumulator scheme relies on the lack of knowledge of the totient function, which is used for computing inverse powers. The EC scheme doesn't have this restriction so you're able to prove any value is a member of the set simply by computing its inverse. 1 This is not a correct dynamic accumulator scheme. Your scheme assumes that the following holds: if$a,b$are primes and$0< a,b < p$, then $$(a,b)=1 \implies (ab\mod p,a)\neq1.$$ If this is true, then your scheme is correct, however this is not the case. Toy example:$p=11,a=5,b=7$. Since$ab \mod 11=35 \mod 11=2,$therefore$A=2$. Now, it is ... 1 No and Yes! For the inclusion proof you either need the trapdoor or the accumulated set. However, it is possible to generate exclusion proofs without knowing the trapdoor, i.e. the factorization of the modulus,$N=p\cdot q$, or the size of the group, i.e.$\phi(N)$. Let$A$denote the accumulator's current value,$x$an item,$g$, a generator of the group ... 1 If you are the one to pick$x$and$N$, finding collisions and second preimages is feasible (and it would appear to be possible while not jeopardizing the security of the system). Here is one possible approach: Search for a set of$n$preimages$s_0, s_1, ..., s_{n-1}$such that:$\prod h(s_i) -1 = k r$, for a prime$r\$ between, say, 256 and 512 bits. ...

1

Later edit: Actually, some new Stanford work shows how to obtain transparent RSA accumulators using class groups. This was also discussed in Secure Accumulators from Euclidean Rings without Trusted Setup, by Helger Lipmaa. The Stanford work also shows how to publicly add and remove elements in the accumulator. And the proofs are constant-sized. Original ...

1

No, if you publish an N bit message it can hold at most N bits of information. An N-bit accumulator value doesn't magically hold more than N bits of information in the same way a hash value does not hold the string it is calculated from. Verifying accumulator membership of a given element X requires storing a witness value for that X (essentially ...

Only top voted, non community-wiki answers of a minimum length are eligible