3
$\begingroup$

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?

$\endgroup$

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.