Secure Distributed Computation in the Exponent

Abstract:

A secure multi-party computation problem deals with computing a function on any input, in a distributed network, ensuring that no more information is revealed to a player in the computation. New protocols are developed for the following interesting variation on a typical problem of secure multi-party computation: Given secrets shared among a group of players, compute the function value of basic computations, such as interpolation, addition, multiplication or inversion, in the exponent. The protocols can be proven robust and secure in standard computation models.

• Periodical: Advanced Materials Research (Volumes 217-218)
• Pages: 994-1000
• DOI: https://doi.org/10.4028/www.scientific.net/AMR.217-218.994
• Online since: March 2011
• Authors: Hong Wang, Shi Min Wei
• Keywords: Distributed Cryptography, Secure Multiparty Computation, Static Adversary, Verifiable Secret Sharing

References

[1] A. C. Yao, Protocols for secure computations, in Proc. 23rd Annual Symp. Foundations of Computer Science, pp.160-164, IEEE Press, New York. (1982).

[2] R. Cramer, I. Damgård, S. Dziembowski, M. Hirt, and T. Rabin, Efficient Multiparty Computations Secure against an Adaptive Adversary, in Proc. Advances in Cryptology – EUROCRYPT '99, LNCS 1592, pp.311-326, Springer-Verlag, Berlin/New York. (1999).

DOI: 10.1007/3-540-48910-x_22

[3] K. Srinathan, and C. P. Rangan, Efficient Asynchronous Secure Multiparty Distributed Computation, in Proc. INDOCRYPT 2000, LNCS 1977, pp.117-129, Springer-Verlag, Berlin/New York. (2000).

DOI: 10.1007/3-540-44495-5_11

[4] R. Cramer, I. Damgård, and U. Maurer, General Secure Multi-party Computation from any Linear Secret-sharing Scheme, in Proc. Advances in Cryptology – EUROCRYPT 2000, LNCS 1807, pp.316-334, Springer-Verlag, Berlin/New York. (2000).

DOI: 10.1007/3-540-45539-6_22

[5] M. Hirt, U. Maurer, and B. Przydatek, Efficient Secure Multi-party Computation, in Proc. Advances in Cryptology – ASIACRYPT 2000, LNCS 1976, pp.143-161, Springer-Verlag, Berlin/New York. (2000).

DOI: 10.1007/3-540-44448-3_12

[6] W. Du, and M. Atallah, Secure Multi-Party Computation Problems and Their Applications: A Review and Open Problems, in Proc. New Security Paradigms Workshop, pp.11-20, ACM Press, New York. (2001).

DOI: 10.1145/508171.508174

[7] R. Cramer, S. Fehr, Y. Ishai, and E. Kushilevitz, Efficient Multi-party Computation over Rings, in Proc. Advances in Cryptology – EUROCRYPT 2003, LNCS 2656, pp.596-613, Springer-Verlag, Berlin/New York. (2003).

DOI: 10.1007/3-540-39200-9_37

[8] P. Feldman, A Practical Scheme for Non-Interactive Verifiable Secret Sharing, in Proc. 28th Annual Symp. Foundations of Computer Science, pp.427-437, IEEE Press, New York. (1987).

DOI: 10.1109/sfcs.1987.4

[9] R. Gennaro, and M. Di Raimondo, Secure Multiplication of Shared Secrets in the Exponent, Information Processing Letters, vol. 96, pp.71-79. (2005).

DOI: 10.1016/j.ipl.2005.01.015

[10] M. Abe, Robust Distributed Multiplication without Interaction, in Proc. Advances in Cryptology – CRYPTO '99, LNCS 1666, pp.130-147, Springer-Verlag, Berlin/New York. (2000).

DOI: 10.1007/3-540-48405-1_9

[11] T. P. Pedersen, Non-Interactive and Information-Theoretic Secure Verifiable Secret Sharing, in Proc. Advances in Cryptology – CRYPTO '91, LNCS 576, pp.129-140, Springer-Verlag, Berlin/New York. (1992).

DOI: 10.1007/3-540-46766-1_9

[12] R. Gennaro, S. Jarecki, H. Krawczyk, and T. Rabin, Robust Threshold DSS Signatures, Information and Computation, vol. 164, no. 1, pp.54-84. An earlier version appeared in Eurocrypt '96. (2001).

DOI: 10.1006/inco.2000.2881

[13] L. R. Welch, and E. R. Berlekamp, Error Correction of Algebraic Block Codes, U. S. Patent 4 633 470. (1983).

[14] C. Peikert, On Error Correction in the Exponent, in Proc. Theory of Cryptography Conference (TCC 2006), LNCS 3876, pp.167-183, Springer-Verlag, Berlin/New York. (2006).

[15] A. Herzberg, S. Jarecki, H. Krawczyk, and M. Yung, Proactive Secret Sharing or: How to Cope with Perpetual Leakage, in Proc. Advances in Cryptology – CRYPTO '95, LNCS 963, pp.339-352, Springer-Verlag, Berlin/New York. (1995).

DOI: 10.1007/3-540-44750-4_27

[16] T. Pedersen, A Threshold Cryptosystem without a Trusted Party, in Proc. Advances in Cryptology – EUROCRYPT '91, LNCS 547, pp.522-526, Springer-Verlag, Berlin/New York. (1991).

DOI: 10.1007/3-540-46416-6_47

[17] R. Gennaro, S. Jarecki, H. Krawczyk, and T. Rabin, Secure Distributed Key Generation for Discrete-log Based Cryptosystems, in Proc. Advances in Cryptology – EUROCRYPT '99, LNCS 1592, pp.295-310, Springer-Verlag, Berlin/New York. (1999).

DOI: 10.1007/3-540-48910-x_21

[18] R. Canetti, Security and Composition of Multi-party Cryptographic Protocols, Journal of Cryptology, vol. 13, no. 1, pp.143-202. (2000).

DOI: 10.1007/s001459910006

[19] H. Wang, Y. Q. Zhang, and D. G. Feng, Short Threshold Signature Schemes without Random Oracles, in Proc. Progress in Cryptology – INDOCRYPT 2005, LNCS 3797, pp.297-310, Springer-Verlag, Berlin/New York. (2005).

DOI: 10.1007/11596219_24

[20] E. Modiano, and A. Ephremides, Communication Protocols for Secure Distributed Computation of Binary Functions, Information and Computation, vol. 158, no. 2, pp.71-97. (2000).

DOI: 10.1006/inco.2000.2865