Automatic generation of two-party computations

ABSTRACT

We present the design and implementation of a compiler that automatically generates protocols that perform two-party computations. The input to our protocol is the specification of a computation with secret inputs (e.g., a signature algorithm) expressed using operations in the field Zq of integers modulo a prime q and in the multiplicative subgroup of order q in Z^*p for q|p-1 with generator g. The output of our compiler is an implementation of each party in a two-party protocol to perform the same computation securely, i.e., so that both parties can together compute the function but neither can alone. The protocols generated by our compiler are provably secure, in that their strength can be reduced to that of the original cryptographic computation via simulation arguments. Our compiler can be applied to various cryptographic primitives (e.g., signature schemes, encryption schemes, oblivious transfer protocols) and other protocols that employ a trusted party (e.g., key retrieval, key distribution).

REFERENCES

• 1: Boaz Barak , Amir Herzberg , Dalit Naor , Eldad Shai, The proactive security toolkit and applications, Proceedings of the 6th ACM conference on Computer and communications security, p.18-27, November 01-04, 1999, Kent Ridge Digital Labs, Singapore [doi>10.1145/319709.319713]
• 2: Mihir Bellare , Silvio Micali, Non-interactive oblivious transfer and applications, Proceedings on Advances in cryptology, p.547-557, July 1989, Santa Barbara, California, United States
• 3: M. Bellare, R. Sandhu. The security of practical two-party RSA signature schemes. 2001.
• 4: Mihir Bellare , Phillip Rogaway, Random oracles are practical: a paradigm for designing efficient protocols, Proceedings of the 1st ACM conference on Computer and communications security, p.62-73, November 03-05, 1993, Fairfax, Virginia, United States [doi>10.1145/168588.168596]
• 5: J. Benaloh. Dense probabilistic encryption. In Workshop on Selected Areas of Cryptography, pp. 120--128, 1994.
• 6: Manuel Blum , Alfredo De Santis , Silvio Micali , Giuseppe Persiano, Noninteractive zero-knowledge, SIAM Journal on Computing, v.20 n.6, p.1084-1118, Dec. 1991 [doi>10.1137/0220068]
• 7: Mihir Bellare , Anand Desai , David Pointcheval , Phillip Rogaway, Relations Among Notions of Security for Public-Key Encryption Schemes, Proceedings of the 18th Annual International Cryptology Conference on Advances in Cryptology, p.26-45, August 23-27, 1998
• 8: D. Boneh, X. Ding, G. Tsudik, and M. Wong. A method for fast revocation of public key certificates and security capabilities. In Proc. 10th USENIX Security Symposium, Aug. 2001.
• 9: C. Boyd. Digital multisignatures. In H. J. Beker and F. C. Piper, editors, Cryptography and Coding, pp. 241--246. Clarendon Press, 1986.
• 10: Ronald Cramer , Victor Shoup, A Practical Public Key Cryptosystem Provably Secure Against Adaptive Chosen Ciphertext Attack, Proceedings of the 18th Annual International Cryptology Conference on Advances in Cryptology, p.13-25, August 23-27, 1998
• 11: 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]
• 12: Alfredo De Santis , Giovanni Di Crescenzo , Rafail Ostrovsky , Giuseppe Persiano , Amit Sahai, Robust Non-interactive Zero Knowledge, Proceedings of the 21st Annual International Cryptology Conference on Advances in Cryptology, p.566-598, August 19-23, 2001
• 13: Yvo Desmedt, Society and Group Oriented Cryptography: A New Concept, A Conference on the Theory and Applications of Cryptographic Techniques on Advances in Cryptology, p.120-127, August 16-20, 1987
• 14: Yvo G. Desmedt , Yair Frankel, Threshold cryptosystems, Proceedings on Advances in cryptology, p.307-315, July 1989, Santa Barbara, California, United States
• 15: W. Ford, B. Kaliski. Server-assisted generation of a strong secret from a password. In Proc. 5th International Workshop on Enterprise Security, 2000.
• 16: R. Ganesan, Yaksha: augmenting Kerberos with public key cryptography, Proceedings of the 1995 Symposium on Network and Distributed System Security (SNDSS'95), p.132, February 16-17, 1995
• 17: R. Gennaro, S. Jarecki, H. Krawczyk, and T. Rabin. Robust threshold DSS signatures. In Proc. EUROCRYPT '96 (LNCS 1070), pp. 354--371, 1996.
• 18: S. Goldwasser and S. Micali. Probabilistic encryption. Journal of Computer and System Sciences 28:270--299, 1984.
• 19: Shafi Goldwasser , Silvio Micali , Ronald L. Rivest, A digital signature scheme secure against adaptive chosen-message attacks, SIAM Journal on Computing, v.17 n.2, p.281-308, April 1988 [doi>10.1137/0217017]
• 20: Patrick Horster , Holger Petersen , Markus Michels, Meta-ElGamal signature schemes, Proceedings of the 2nd ACM Conference on Computer and communications security, p.96-107, November 1994, Fairfax, Virginia, United States [doi>10.1145/191177.191197]
• 21: Philip MacKenzie , Michael K. Reiter, Networked Cryptographic Devices Resilient to Capture, Proceedings of the 2001 IEEE Symposium on Security and Privacy, p.12, May 14-16, 2001
• 22: Philip D. MacKenzie , Michael K. Reiter, Two-Party Generation of DSA Signatures, Proceedings of the 21st Annual International Cryptology Conference on Advances in Cryptology, p.137-154, August 19-23, 2001
• 23: Alfred J. Menezes , Scott A. Vanstone , Paul C. Van Oorschot, Handbook of Applied Cryptography, CRC Press, Inc., Boca Raton, FL, 1996
• 24: D. Naccache and J. Stern. A new public-key cryptosystem. In Proc. EUROCRYPT '97 (LNCS 1233), pp. 27--36, 1997.
• 25: A. Nicolosi, M. Krohn, Y. Dodis, D. Mazieres. Proactive two-party signatures for user authentication. In Proc. 10th ISOC Network and Distributed System Security Symposium, Feb. 2003.
• 26: Moni Naor , Benny Pinkas, Distributed Oblivious Transfer, Proceedings of the 6th International Conference on the Theory and Application of Cryptology and Information Security: Advances in Cryptology, p.205-219, December 03-07, 2000
• 27: Moni Naor , Benny Pinkas, Efficient oblivious transfer protocols, Proceedings of the twelfth annual ACM-SIAM symposium on Discrete algorithms, p.448-457, January 07-09, 2001, Washington, D.C., United States
• 28: T. Okamoto and S. Uchiyama. A new public-key cryptosystem, as secure as factoring. In Proc. EUROCRYPT '98 (LNCS 1403), pp. 308--318, 1998.
• 29: P. Paillier. Public-key cryptosystems based on composite degree residuosity classes. In Proc. EUROCRYPT '99 (LNCS 1592), pp. 223--238, 1999.
• 30: Michael K. Reiter , Matthew K. Franklin , John B. Lacy , Rebecca N. Wright, The &OHgr; key management service, Journal of Computer Security, v.4 n.4, p.267-287, July 1996
• 31: 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]
• 32: Adi Shamir, How to share a secret, Communications of the ACM, v.22 n.11, p.612-613, Nov. 1979 [doi>10.1145/359168.359176]
• 33: Dawn Xiaodong Song , Adrian Perrig , Doantam Phan, AGVI - Automatic Generation, Verification, and Implementation of Security Protocols, Proceedings of the 13th International Conference on Computer Aided Verification, p.241-245, July 18-22, 2001
• 34: T. Wu, M. Malkin, D. Boneh. Building intrusion tolerant applications. In Proc. 8th USENIX Security Symposium, pp. 79-91, Aug. 1999.
• 35: A. Yao. Protocols for secure computation. In Proc. 23 IEEE Symposium on Foundations of Computer Science, pp. 160--164, 1982.
• 36: Lidong Zhou , Fred B. Schneider , Robbert Van Renesse, COCA: A secure distributed online certification authority, ACM Transactions on Computer Systems (TOCS), v.20 n.4, p.329-368, November 2002 [doi>10.1145/571637.571638]

INDEX TERMS

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

General Terms:
Security

Keywords:
automatic generation of protocols, secure two-party computation, threshold cryptography