# Questions tagged [accumulators]

A cryptographic accumulator is a one way membership function. It answers a query as to whether a potential candidate is a member of a set without revealing the individual members of the set.

31 questions
34 views

### What's the difference among Vector Commitment, Zero-knowledge Set, Zero-knowledge Accumulator, and Zero-knowledge Elementary Database?

Vector commitment allows to commit to an ordered sequence of $q$ value ($m_1,\cdots,m_q$) in such a way that one can later open the commitment at specific positions(e.g., prove that $m_i$ is the $i$-...
50 views

### Accumulator-like data structure with publicly-computable witness

I'm looking for a data structure that would allow anyone to compute a witness for an element without knowing all other elements within the accumulator/set. Specifically: Suppose there is a set of ...
30 views

### Dynamic accumulator with only non-membership witness

Goal: Construct a dynamic accumulator which can add elements and provide non-membership witnesses. I wanted to know if my construction is correct. Consider a group $Z_p$ where $p$ is prime number. ...
204 views

### cryptographic accumulators: accumulator size vs. max. number of set members?

Here's a basic question about cryptographic accumulators, or at least ones based on fixed-size accumulator values (such as RSA ones based on modulo arithmetic), that is strangely not even mentioned in ...
76 views

### Proof of membership in an aggregated BLS signature

Is it possible to prove that a given signature is a part of an aggregated BLS signature? Specifically, given: $m_1...m_n$ are $n$ distinct messages $p_1...p_n$ are private keys with $P_1...P_n$ being ...
129 views

### Inclusion and Exclusion proofs in RSA accumulators

I am reading about RSA accumulators from this video and few other sources. I had a confusion whether the complete set is needed to construct a proof of inclusion/exclusion in an RSA accumulator or is ...
2k views

### Hash to prime numbers?

Is there some provably secure hash function to prime numbers? Say, a function $H: \{0, 1\}^* \rightarrow \{e: e \in \{0, 1\}^\lambda \land e$ is prime$\}$ I'm asking because there are some ...
77 views

### Feasible to find two sets with the same RSA accumulator value if a prime representative hash function is used?

Consider the RSA accumulator scheme with random oracle as proposed by Barić and Pfitzmann, with the random oracle replaced by a secure hash function $H$ as follows. For a set $S$, the accumulator ...
60 views

### Why do one-way accumulators use rigid integers as the modulus?

In the paper that introduced one-way accumulators, the author's justify their use of rigid integers as the modulus with the following: The advantage of using a rigid integer $n = pq$ is that the ...
100 views

### can a quantum or classical computer perform “MATRIX factorisation”?

I know that thanks to Shor's algorithm, integer factorisation is easy on quantum computers, yet hard on classical computers. But what if I have two MATRICES, A and B, and compute the product N = A * ...
179 views

### Transparent, publicly updatable accumulator with constant-sized witnesses

I am looking for an accumulator with the following properties: Transparent: No trusted setup (rules out RSA and pairing-based accumulators) Publicly updatable: No central authority (rules out digital ...
381 views

It was shown by Camacho that in batch deletions in accumulators, the information to update all witnesses is at least linear in the number of elements deleted. I am wondering if there are accumulators ...
183 views

### Is there an efficient way to verify the union of two RSA accumulators?

More specifically, say we have one RSA accumulator $A_{S_1}$ accumulating set $S_1$ and another RSA accumulator $A_{S_2}$ accumulating set $S_2$. Does there exist a sublinear method to securely verify ...
299 views

### How CL-signature can act as positive & additive accumulator?

A paper (http://ieeexplore.ieee.org/abstract/document/7961987/) proposes a Braavos (adaptively sound dynamic positive accumulator). Braavos uses two other accumulators. One is adaptively sound ...
452 views

### A Zero knowledge proof for set membership?

Essentially, I am trying to build up a list of authorised public keys that will be stored in a database P by a verifier V. A public key will be considered authorised if belongs to a user in a database ...
110 views

### Public Key Encryption scheme with small messages among many parties

Question Is it possible to create a public key encryption scheme, with $n$ parties, where a party can send all other parties a bit unique to each party in less than $n$ bits? Assume we can set up a ...
139 views

### Is there a flaw in this ring signature scheme? [closed]

Having read some papers about RSA accumulators applied to ring signatures schemes, I ended up thinking why would we need to accumulate all the members public keys for our specific use case. So I came ...
165 views

### Deletion complexity in a RSA accumulator

My question is about the existence of a dynamic RSA accumulator with deletion of an element in O(1) time. Do you know some practical implementation?
767 views

### Deletion in RSA Accumulator

I am studying RSA Dynamic Accumulators and I have a question: why is it simpler to calculate the new accumulator value after a deletion if the secret $\phi(N)$ is known? Is possible to calculate the ...
165 views

### Can a one-way accumulator be used in place of a digital signature?

Could a one-way accumulator be used in a manner to replace a digital signature? Can it provide a way to: verify that the data has not been tampered with, and verify that the message is in fact sent/...
489 views

### Proving membership of a group without revealing identity?

I have an interesting problem for which I've failed, so far, to find an elegant solution. Imagine that a user needs to repeatedly prove to public observers that they are a member of a trusted set ...
112 views

### Type of values that can be accumulated in bilinear map (multiplicative) accumulator reg

Is there any restriction that the members to be accumulated in bilinear map (multiplicative) accumulator need to be relatively prime to $P$, where $P$ is the order of the group.
335 views

### Bilinear pairing arithmetic - cryptographic accumulators

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)$. ...
211 views

### Discrete log accumulator without pairings?

Here $g$ is some fixed generator of a discrete log group. I don't want the group to be bilinear for efficiency and BDH-skepticism reasons. Is anyone aware of a discrete log accumulator? What I mean ...
270 views

### How to compute accumulated values in bilinear map accumulators

How to compute $g^{1/(e_1+s)}$, where $g$ is the generator of group $\mathbb G$, and $e_1$ and $s$ are keys? I know only $s$ and $g^{e_1}$, not $e_1$. $\mathbb G$ has prime order for some prime $p$ ...
129 views

### Possible to use an accumulator to “license” or restrict the qty of certificates being used?

Suppose in a future version of x509 PKI, it is possible to limit the quantity of certificates being used, what would that look like? Here is a concept that won't work in the real world, but ...
190 views

### Can I publish the accumulator trapdoor and still keep it secure?

I'm implementing the Camenish-Lysyanskaya dynamic accumulator. It seems to me that the accumulator is provably secure because the trapdoor is unknown to the attacker. The risks should be the fact ...
868 views

### How can I convert numbers into prime numbers?

I'm working with one-way accumulators, but I'm not knowledgable in cryptography. Is there an easy peasy way to hash numbers (or whatever) into prime numbers? Obviously I'd like it to be collision ...
2k views

One-way accumulators are built upon a (quasi)-commutative one-way function. With quasi-commutativity, I refer to the following property: For $f : X \times Y \to X$, it is true that \$f(f(x, y_1), y_2) ...