According to this paper entitled "Using Commutative Encryption to Share a Secret" they define their modulus to be a large prime p, which is public. Both exponents are private in this case.

According to the wikipedia article on RSA link the modulus has to be a product of two primes, and " p, q, and φ(n) must also be kept secret because they can be used to calculate d.", and the exponent can be public.

In the paper both the modulus (p) and φ(p) are known. How is the algorithm in the paper secure? Is it because both keys are private?

Is there a secure way for the same modulus to be used across all parties, and $a_i$ are public for each user?

  • 3
    $\begingroup$ What does RSA have to do with this? $\endgroup$ – fkraiem Feb 9 '15 at 22:22
  • $\begingroup$ Diffie Hellman has a single, public modulus and is still secure. $\endgroup$ – mikeazo Feb 9 '15 at 23:11
  • $\begingroup$ You might be interested in Mental Poker which is similar, and states that the modulus used can be of known factorization, including prime. $\endgroup$ – fgrieu Feb 10 '15 at 8:09

I think the confusion lies in mixing two distinct hard problems.

RSA is related to the difficulty of factoring large numbers. The scheme you link to in the paper is based on the difficulty of solving discrete logarithms. Since they are very different hard problems, you can't really compare the two in terms of what must be kept secret.

For RSA, $\varphi(n)$ must be kept secret since with that you could factor $n$ (and hence make the hard problem easy). With the scheme you link to, you must keep the exponent secret as that is what you are trying to solve for when computing a discrete logarithm.


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.