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 group of squares (quadratic residues) modulo $n$ that are relatively prime to $n$ has the property that it has size $n' = \frac{p-1}{2}\frac{q-1}{2}$ and the function $e_{n,y}(x) = x^y \mod n$ is a permutation of this group whenever $y$ and $n'$ are relatively prime. Thus, if the factorization of $n$ is hidden, "random" exponentiations of an element of this group are extremely unlikely to produce elements of any proper subgroup. This means that repeated applications of $e_{n,y}(x)$ are extremely unlikely to reduce the size of the domain or produce random collisions.

This section of the paper leaves me with a few questions.

  1. What is the significance of working in the group of quadratic residues?

  2. When $y$ and $n'$ are relatively prime and used in $e_{n,y}$ how is it that "random exponentiations of an element of this group" are unlikely to produce elements of insecure (at least this is what I assume "proper" means here) subgroups?


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.