I am looking for an alternative to RSA accumulators, and I am wondering if the following option based on function composition might fit the bill. It seems like an obvious tweak on RSA accumulators, which makes me think I'm probably missing something important though.

So I understand that RSA is based on modular exponentiation over a hidden-order group where the Strong RSA Problem is hard. So for a set $S = \{x_1, x_2, \dots, x_n \}$, let $g$ be a generator of our hidden order group $G$, and let $e_i = \mathsf{H}(x_i)$ be the prime representative of $x_i$, where $\mathsf{H}$ is a collision-resistant hash function that maps its input to prime numbers, also let $N = pq$ be a large composite number obtained by multiplying two large prime numbers. We would say that the accumulator $A$ of $S$ is something like: $A = g^{\prod_{i \in |n|} e_i} \bmod N$.

This description borrows from https://alinush.github.io/2020/11/24/RSA-accumulators.html. Again, from my understanding an RSA accumulator relies on the Strong RSA assumption for its security. It assumes that finding roots modulo a large composite number (like $N$) is computationally infeasible.This obviously requires a trusted setup of some kind.

Is it possible to tweak this to a degree, to instead rely on the difficulty of the discrete logarithm problem (DLP) for our security assumptions? Here's where my brain goes: we'll assume that $N$ is a (public) large (safe) prime number (of at least 2048 bits) for all the reasons that safe primes are useful. Then, we'll restructure our hashing function so that the assumption would be that given $y = x^a \bmod N$, it is hard to find $x$ given $y$, $a$, and $N$. My mind goes to function composition, such that the accumulator uses a set of functions, each with a fixed exponent drawn from $Z_N^*$. The semigroup operation here then becomes function composition.

The functions are of the form $f_a(x) = x^a \bmod N$. The accumulator for a set of exponents $S = \{a_1, a_2, \dots, a_n\}$ can be represented by the composed function $A = f_{a_1} \circ f_{a_2} \circ \dots \circ f_{a_n}(x)$ (which could be interpreted as the hash of $x$ given $S$ I guess). The set of functions forms a semigroup under composition since it's closed and associative but is not invertible (if we assume that $f_1$ is our identity element, then I guess this is actually a monoid).

It is relatively efficient to compute, because it can be done incrementally, and leverage efficient modular exponentiation routines. It should also be commutative due to the nature of modular exponentiation and multiplication. I guess care has to be taken to ensure that the exponents are random. The standard assumption of a cryptographically secure function $\mathsf{H}$ modeled as a random oracle seems sufficient? In terms of size, I don't think they need to be as big as $N$ here (correct me if I'm wrong). So something like SHA256 is probably fine? I guess it would also be beneficial for the exponents to be co-prime with $N - 1$, but since we already know that $N$ is a safe prime, $N - 1$ is going to be even, so choosing large random exponents will likely result in them being co-prime with $N-1$ anyway?

Ok, so with all of that in mind, is this scheme going to work? Or am I missing something obvious? I guess technically, if we choose and fix $x$ to be some known generator for the set, this then is essentially an RSA accumulator? But otherwise, we could start with the identity $f_1(x)$ and then compose over that to produce the full accumulation. The reason I'm interested in this approach, is pretty much because I need an add-only (wrong term?) accumulator with short membership commitments that doesn't require a trusted setup. So I am open to other options as well!



Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.