Skip to main content
added 35 characters in body
Source Link
DrLecter
  • 12.6k
  • 3
  • 44
  • 61

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 want to compute a witness for a value say $y_2$, then by quasi commutativity, the value for your witness is $wit_{y_2} = f(f(x,y_1),y_3)$ and you can check given $y_2$ and $wit_{y_2}$ whether $y_2$ is in the accumulator $acc$, you can check whether $acc=f(with_{y_2},y_3)$$acc=f(wit_{y_2},y_3)$ holds.

Furthermore, existing accumulator schemes (CL02, C+09, N05) come with zero-knowledge proofs of accumulator membership (you do not have to reveal the value $y_2$ and the witness $wit_{y_2}$ directly, but you provide a zero-knowledge proof of knowledge of such a pair - which makes them attractive for privacy-preserving applications). Such accumulators are typically also dynamic, i.e., allow update of witnesses in the public if the accumulator is updated. Furthermore, there are also so called universal accumulators, which also allow to produce witnesses for non-membership of a value in the accumulated set (see A+09 or L+07).

All known efficient accumulators are based on number theoretic assumption, but I would not say that they are inefficient. Note that in your last RSA example, the membership check requires one exponentiation, which is not really very expensive.

is the function f weak in terms of eg. collision-resistance, is it not efficient enough...?

For a secure accumulator one requires collssion-freeness, i.e., it is computationally infeasible to find a witness for some value that is not accumulated in the accumulator. For RSA accumulators that requires that you only accumulate primes (so you have to map your values to accumulate to primes with some deterministic algorithm). Otherwise, you could factor your value into two factors and exponentiate one onto your witness and provide the second as value to be checked and the check would work. This is ruled out if you take primes. There are however, other secure pairing based accumulators that do not suffer from this problem.

Accumulators are used for various purposes, such as timestamping (the original application), membership testing, distributed signatures, redactable and sanitizable signatures as well as for revocation in group signatures and anonymous credential systems.

There are constructions for accumulators based on bloom filters (see Nyberg, Fast accumulated hasing, FSE 1996), but they are rather impractical (but do not rely on number theoretic assumptions).

An advantage of a cryptographic accumulator 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 want to compute a witness for a value say $y_2$, then by quasi commutativity, the value for your witness is $wit_{y_2} = f(f(x,y_1),y_3)$ and you can check given $y_2$ and $wit_{y_2}$ whether $y_2$ is in the accumulator $acc$, you can check whether $acc=f(with_{y_2},y_3)$ holds.

Furthermore, existing accumulator schemes (CL02, C+09, N05) come with zero-knowledge proofs of accumulator membership (you do not have to reveal the value $y_2$ and the witness $wit_{y_2}$ directly, but you provide a zero-knowledge proof of knowledge of such a pair - which makes them attractive for privacy-preserving applications). Such accumulators are typically also dynamic, i.e., allow update of witnesses in the public if the accumulator is updated. Furthermore, there are also so called universal accumulators, which also allow to produce witnesses for non-membership of a value in the accumulated set (see A+09 or L+07).

All known efficient accumulators are based on number theoretic assumption, but I would not say that they are inefficient. Note that in your last RSA example, the membership check requires one exponentiation, which is not really very expensive.

is the function f weak in terms of eg. collision-resistance, is it not efficient enough...?

For a secure accumulator one requires collssion-freeness, i.e., it is computationally infeasible to find a witness for some value that is not accumulated in the accumulator. For RSA accumulators that requires that you only accumulate primes (so you have to map your values to accumulate to primes with some deterministic algorithm). Otherwise, you could factor your value into two factors and exponentiate one onto your witness and provide the second as value to be checked and the check would work. This is ruled out if you take primes. There are however, other secure pairing based accumulators that do not suffer from this problem.

Accumulators are used for various purposes, such as timestamping (the original application), membership testing, distributed signatures, redactable and sanitizable signatures as well as for revocation in group signatures and anonymous credential systems.

There are constructions for accumulators based on bloom filters (see Nyberg, Fast accumulated hasing, FSE 1996), but they are rather impractical (but do not rely on number theoretic assumptions).

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 want to compute a witness for a value say $y_2$, then by quasi commutativity, the value for your witness is $wit_{y_2} = f(f(x,y_1),y_3)$ and you can check given $y_2$ and $wit_{y_2}$ whether $y_2$ is in the accumulator $acc$, you can check whether $acc=f(wit_{y_2},y_3)$ holds.

Furthermore, existing accumulator schemes (CL02, C+09, N05) come with zero-knowledge proofs of accumulator membership (you do not have to reveal the value $y_2$ and the witness $wit_{y_2}$ directly, but you provide a zero-knowledge proof of knowledge of such a pair - which makes them attractive for privacy-preserving applications). Such accumulators are typically also dynamic, i.e., allow update of witnesses in the public if the accumulator is updated. Furthermore, there are also so called universal accumulators, which also allow to produce witnesses for non-membership of a value in the accumulated set (see A+09 or L+07).

All known efficient accumulators are based on number theoretic assumption, but I would not say that they are inefficient. Note that in your last RSA example, the membership check requires one exponentiation, which is not really very expensive.

is the function f weak in terms of eg. collision-resistance, is it not efficient enough...?

For a secure accumulator one requires collssion-freeness, i.e., it is computationally infeasible to find a witness for some value that is not accumulated in the accumulator. For RSA accumulators that requires that you only accumulate primes (so you have to map your values to accumulate to primes with some deterministic algorithm). Otherwise, you could factor your value into two factors and exponentiate one onto your witness and provide the second as value to be checked and the check would work. This is ruled out if you take primes. There are however, other secure pairing based accumulators that do not suffer from this problem.

Accumulators are used for various purposes, such as timestamping (the original application), membership testing, distributed signatures, redactable and sanitizable signatures as well as for revocation in group signatures and anonymous credential systems.

There are constructions for accumulators based on bloom filters (see Nyberg, Fast accumulated hasing, FSE 1996), but they are rather impractical (but do not rely on number theoretic assumptions).

Source Link
DrLecter
  • 12.6k
  • 3
  • 44
  • 61

An advantage of a cryptographic accumulator 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 want to compute a witness for a value say $y_2$, then by quasi commutativity, the value for your witness is $wit_{y_2} = f(f(x,y_1),y_3)$ and you can check given $y_2$ and $wit_{y_2}$ whether $y_2$ is in the accumulator $acc$, you can check whether $acc=f(with_{y_2},y_3)$ holds.

Furthermore, existing accumulator schemes (CL02, C+09, N05) come with zero-knowledge proofs of accumulator membership (you do not have to reveal the value $y_2$ and the witness $wit_{y_2}$ directly, but you provide a zero-knowledge proof of knowledge of such a pair - which makes them attractive for privacy-preserving applications). Such accumulators are typically also dynamic, i.e., allow update of witnesses in the public if the accumulator is updated. Furthermore, there are also so called universal accumulators, which also allow to produce witnesses for non-membership of a value in the accumulated set (see A+09 or L+07).

All known efficient accumulators are based on number theoretic assumption, but I would not say that they are inefficient. Note that in your last RSA example, the membership check requires one exponentiation, which is not really very expensive.

is the function f weak in terms of eg. collision-resistance, is it not efficient enough...?

For a secure accumulator one requires collssion-freeness, i.e., it is computationally infeasible to find a witness for some value that is not accumulated in the accumulator. For RSA accumulators that requires that you only accumulate primes (so you have to map your values to accumulate to primes with some deterministic algorithm). Otherwise, you could factor your value into two factors and exponentiate one onto your witness and provide the second as value to be checked and the check would work. This is ruled out if you take primes. There are however, other secure pairing based accumulators that do not suffer from this problem.

Accumulators are used for various purposes, such as timestamping (the original application), membership testing, distributed signatures, redactable and sanitizable signatures as well as for revocation in group signatures and anonymous credential systems.

There are constructions for accumulators based on bloom filters (see Nyberg, Fast accumulated hasing, FSE 1996), but they are rather impractical (but do not rely on number theoretic assumptions).