An asynchronous protocol for distributed computation of RSA inverses and its applications

ABSTRACT

This paper presents an efficient asynchronous protocol to compute RSA inverses with respect to a public RSA modulus N whose factorization is secret and shared among a group of parties. Given two numbers x and e, the protocol computes y such that y^e≡x (mod N). A synchronous protocol for this task has been presented by Catalano, Gennaro, and Halevi (Eurocrypt 2000), but the standard approach for turning this into an asynchronous protocol would require a Byzantine-agreement sub-protocol. Our protocol adopts their approach, but exploits a feature of the problem in order to avoid the use of a Byzantine agreement primitive. Hence, it leads to efficient asynchronous protocols for threshold signatures and for Byzantine agreement based on the strong RSA assumption, without the use of random oracles.

REFERENCES

• 1: N. Barić and B. Pfitzmann, "Collision-free accumulators and fail-stop signature schemes without trees," in Proc. EUROCRYPT '97, pp. 480--494, 1997.
• 2: Michael Ben-Or , Ran Canetti , Oded Goldreich, Asynchronous secure computation, Proceedings of the twenty-fifth annual ACM symposium on Theory of computing, p.52-61, May 16-18, 1993, San Diego, California, United States [doi>10.1145/167088.167109]
• 3: Michael Ben-Or , Boaz Kelmer , Tal Rabin, Asynchronous secure computations with optimal resilience (extended abstract), Proceedings of the thirteenth annual ACM symposium on Principles of distributed computing, p.183-192, August 14-17, 1994, Los Angeles, California, United States [doi>10.1145/197917.198088]
• 4: Christian Cachin , Klaus Kursawe , Anna Lysyanskaya , Reto Strobl, Asynchronous verifiable secret sharing and proactive cryptosystems, Proceedings of the 9th ACM conference on Computer and communications security, November 18-22, 2002, Washington, DC, USA [doi>10.1145/586110.586124]
• 5: Christian Cachin , Klaus Kursawe , Frank Petzold , Victor Shoup, Secure and Efficient Asynchronous Broadcast Protocols, Proceedings of the 21st Annual International Cryptology Conference on Advances in Cryptology, p.524-541, August 19-23, 2001
• 6: Christian Cachin , Klaus Kursawe , Victor Shoup, Random oracles in constantipole: practical asynchronous Byzantine agreement using cryptography (extended abstract), Proceedings of the nineteenth annual ACM symposium on Principles of distributed computing, p.123-132, July 16-19, 2000, Portland, Oregon, United States [doi>10.1145/343477.343531]
• 7: R. Canetti, R. Gennaro, A. Herzberg, and D. Naor, "Proactive security: Long-term protection against break-ins," RSA Laboratories' CryptoBytes, vol. 3, no. 1, 1997.
• 8: Ran Canetti , Tal Rabin, Fast asynchronous Byzantine agreement with optimal resilience, Proceedings of the twenty-fifth annual ACM symposium on Theory of computing, p.42-51, May 16-18, 1993, San Diego, California, United States [doi>10.1145/167088.167105]
• 9: D. Catalano, R. Gennaro, and S. Halevi, "Computing inverses over a shared secret modulus," in Proc. EUROCRYPT 2000, pp. 190--206, Springer, 2000.
• 10: B. Chor and C. Dwork, "Randomization in Byzantine agreement," in Randomness and Computation (S. Micali, ed.), vol. 5 of Advances in Computing Research, pp. 443--497, JAI Press, 1989.
• 11: B. Chor, S. Goldwasser, S. Micali, and B. Awerbuch, "Verifiable secret sharing and achieving simultaneity in the presence of faults," in Proc. 26th IEEE Symposium on Foundations of Computer Science (FOCS), pp. 383--395, 1985.
• 12: Ronald Cramer , Victor Shoup, Signature schemes based on the strong RSA assumption, ACM Transactions on Information and System Security (TISSEC), v.3 n.3, p.161-185, Aug. 2000 [doi>10.1145/357830.357847]
• 13: Y. Desmedt, "Threshold cryptography," European Transactions on Telecommunications, vol. 5, no. 4, pp. 449--457, 1994.
• 14: Yvo Desmedt , Yair Frankel, Shared Generation of Authenticators and Signatures (Extended Abstract), Proceedings of the 11th Annual International Cryptology Conference on Advances in Cryptology, p.457-469, August 11-15, 1991
• 15: Y. Frankel , P. Gemmell , P. D. MacKenzie , Moti Yung, Optimal-resilience proactive public-key cryptosystems, Proceedings of the 38th Annual Symposium on Foundations of Computer Science (FOCS '97), p.384, October 19-22, 1997
• 16: Eiichiro Fujisaki , Tatsuaki Okamoto, Statistical Zero Knowledge Protocols to Prove Modular Polynomial Relations, Proceedings of the 17th Annual International Cryptology Conference on Advances in Cryptology, p.16-30, August 17-21, 1997
• 17: R. Gennaro, S. Halevi, and T. Rabin, "Secure hash-and-sign signatures without the random oracle," in Proc. EUROCRYPT '99, pp. 123--139, Springer, 1999.
• 18: R. Gennaro, T. Rabin, S. Jarecki, and H. Krawczyk, "Robust and efficient sharing of RSA functions," Journal of Cryptology, vol. 13, pp. 273--300, 2000.
• 19: Oded Goldreich , Shafi Goldwasser , Silvio Micali, How to construct random functions, Journal of the ACM (JACM), v.33 n.4, p.792-807, Oct. 1986 [doi>10.1145/6490.6503]
• 20: S. Goldwasser , S. Micali , C. Rackoff, The knowledge complexity of interactive proof systems, SIAM Journal on Computing, v.18 n.1, p.186-208, Feb. 1989 [doi>10.1137/0218012]
• 21: Silvio Micali , Salil Vadhan , Michael Rabin, Verifiable Random Functions, Proceedings of the 40th Annual Symposium on Foundations of Computer Science, p.120, October 17-18, 1999
• 22: M. Naor , O. Reingold, Number-theoretic constructions of efficient pseudo-random functions, Proceedings of the 38th Annual Symposium on Foundations of Computer Science (FOCS '97), p.458, October 19-22, 1997
• 23: Jesper Buus Nielsen, A Threshold Pseudorandom Function Construction and Its Applications, Proceedings of the 22nd Annual International Cryptology Conference on Advances in Cryptology, p.401-416, August 18-22, 2002
• 24: Torben P. Pedersen, Non-Interactive and Information-Theoretic Secure Verifiable Secret Sharing, Proceedings of the 11th Annual International Cryptology Conference on Advances in Cryptology, p.129-140, August 11-15, 1991
• 25: M. O. Rabin, "Randomized Byzantine generals," in Proc. 24th IEEE Symposium on Foundations of Computer Science (FOCS), pp. 403--409, 1983.
• 26: Tal Rabin, A Simplified Approach to Threshold and Proactive RSA, Proceedings of the 18th Annual International Cryptology Conference on Advances in Cryptology, p.89-104, August 23-27, 1998
• 27: Michael K. Reiter, Secure agreement protocols: reliable and atomic group multicast in rampart, Proceedings of the 2nd ACM Conference on Computer and communications security, p.68-80, November 1994, Fairfax, Virginia, United States [doi>10.1145/191177.191194]
• 28: R. L. Rivest , A. Shamir , L. Adleman, A method for obtaining digital signatures and public-key cryptosystems, Communications of the ACM, v.21 n.2, p.120-126, Feb. 1978 [doi>10.1145/359340.359342]
• 29: V. Shoup, "Practical threshold signatures," in Proc. EUROCRYPT 2000, pp. 207--220, Springer, 2000.

INDEX TERMS

Primary Classification:
  D. Software
  D.4 OPERATING SYSTEMS
      D.4.6 Security and Protection
          Subjects: Cryptographic controls

Additional Classification:
  E. Data
  E.3 DATA ENCRYPTION
      Subjects: Public key cryptosystems

  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.2 Modes of Computation
          Subjects: Probabilistic computation

General Terms:
Algorithms, Design, Performance, Security

Keywords:
Byzantine agreement, Cryptography, threshold signatures, verifiable random functions, verifiable secret sharing