I've come accross the following expression in a paper:

$$A_i=(C_2 * a_0)^{1/e_i} \bmod n$$

How to calculate $1/e_i$ in modular arithmetic?

Or does it have some different meaning that I do not know?

The paper is "A Practical and Provably Secure Coalition-Resistant Group Signature Scheme" by Giuseppe Ateniese, Jan Camenisch, Marc Joye, and Gene Tsudik", on page no.9, step 4 of JOIN.


In this context $1/e_i$ (more commonly written as $e_i^{-1}$) stands for the multiplicative inverse of $e_i$ modulo the relevant modulus, which in this case is $\lambda(n) = \text{lcm}(p-1,q-1)$. That is, $1/e_i$ is that value $f$ such that $f \cdot e_i = k \cdot \text{lcm}(p-1, q-1) + 1$, for some integer $k$.

Given the factorization of $n$, we can compute $1/e_i$ using the Extended Euclidean method.

We also believe that that $(C_2 \cdot a_0)^{1/e_i} \bmod n$ cannot be computed without knowing the factorization $n = p \cdot q$ (for general $C_2, a_0, e_i$); in fact, this is precisely the RSA problem.


Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.