@vbuterin suggested an n-party setup where each party provides a prime to create a modulus N = p_1 * p_2 * ... * p_n. I thought it would be better to have each party provide a large semiprime s_i = p_{i1} * p_{i2} as its own modulus, and use each modulus as its own accumulator, running in parallel. Here’s my reasoning:
Pros:
-
No multiparty computation ceremony is needed to multiply the numbers without anyone learning them.
-
Proofs can be verified in parallel.
-
Furthermore, updating an accumulator/verifying a witness requires mod N exponentiation, which requires us to multiply N-bit numbers O(\log a) times (using the repeated squaring method). Using the Karatsuba algorithm, this takes O(\log a)(2048n)^{1.58} time for a product of n 2048 bit primes, but only O(\log a) \cdot n (4096)^{1.58} for n products of pairs of 2048-bit primes, so the latter method is faster by a factor of (n^{0.58})/2^{1.58}. The speedup is (n^{1.58})/2^{1.58} if the multiplications are parallel, and potentially more if the decrease in size of the multiplicands allows us to take advantage of hardware speedups for multiplication.
-
Since the semiprimes are just standard RSA-2048 keys, they don’t have to be created specifically for the purpose of this accumulator. They can come from a variety of sources. For example:
-
we can use famous semiprimes like those from the RSA factoring challenge.
-
We can use expired public keys from defunct organizations as suggested in Bunz’s talk
-
We can generate several large random “nothing-up-my-sleeve” numbers and hope they have large prime factors. As Theorem 1 of the paper on page 262 of this document linked by @JustinDrake proves, a 6144-bit (6KiB) random number has a 0.5 * (\ln^2(3/2) + O(1/(6144\ln2))) \approx 0.08 probability of having at least 2 >2048 bit prime factors (not sure, but it may be possible to improve this guarantee by squeezing). As Justin says, this paper sees the benefit of choosing multiple small numbers over one big number, but as far as I can tell, it misses the fact that it is not necessary to multiply these to get an accumulator. Indeed, efficiency was the main problem with this scheme, so getting the (n^{0.58})/2^{1.58} speedup may be important for this approach.
-
Trusted individuals in the cryptocurrency community can supply public keys they generate.
-
-
(Minor point) The single prime way is insecure against n-1 parties being dishonest, since n-1 parties can factor their primes out of the modulus to find the last prime, the semiprime setup is secure unless all n parties are dishonest.
Cons:
- Obviously, the size of the accumulator and witnesses is doubled.
Are there any problems with this scheme I’ve missed?