Stack Exchange Network

Stack Exchange network consists of 174 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

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.

2
votes
1answer
49 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 ...
0
votes
0answers
23 views

Efficient accumulator with constant witnesses

I'm looking for a data structure similar to a dynamic accumulator that has the following properties: Small size: ideally under 100 bytes for the accumulator, and also under 100 bytes for witnesses ...
2
votes
0answers
40 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 ...
9
votes
5answers
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 ...
4
votes
2answers
53 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 ...
3
votes
0answers
53 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 ...
4
votes
0answers
93 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 * ...
1
vote
1answer
147 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 ...
3
votes
1answer
324 views

Accumulators with batch additions

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 ...
5
votes
0answers
164 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 ...
3
votes
0answers
177 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 ...
3
votes
2answers
387 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 ...
4
votes
1answer
102 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 ...
1
vote
0answers
131 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 ...
2
votes
1answer
144 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?
4
votes
1answer
630 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 ...
7
votes
1answer
157 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/...
4
votes
1answer
448 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 ...
2
votes
1answer
109 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.
3
votes
1answer
257 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)$. ...
4
votes
2answers
176 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 ...
0
votes
1answer
251 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$ ...
3
votes
4answers
126 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 ...
3
votes
1answer
164 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 ...
-1
votes
1answer
792 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 ...
8
votes
1answer
2k views

Disadvantages of one-way accumulators?

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) ...
2
votes
0answers
248 views

Does a strong dynamic accumulator exist yet? [closed]

I’m looking for a one-way accumulator which can safely add new members (deletion is not necessary) and does not rely on a trusted party in any way. Unfortunately it appears that it does not exist yet. ...
7
votes
3answers
708 views

Can one use a Cryptographic Accumulator to efficiently store Lamport public keys without the need of a Merkle Tree?

One of the problems of one-time Lamport signatures is that public keys are disposed after use, so you must generate many keys and store them in a Merkle tree. The root is the "real" public key and ...