Abstract
Consider a network of processors among which elements in a finite field K can be verifiably shared in a constant number of rounds. Assume furthermore constant-round protocols are available for generating random shared values, for secure multiplication and for addition of shared values. These requirements can be met by known techniques in all standard models of communication.
In this model we construct protocols allowing the network to securely solve standard computational problems in linear algebra. In particular, we show how the network can securely, efficiently and in constant-round compute determinant, characteristic polynomial, rank, and the solution space of linear systems of equations. Constant round solutions follow for all problems which can be solved by direct application of such linear algebraic methods, such as deciding whether a graph contains a perfect match.
If the basic protocols (for shared random values, addition and multiplication) we start from are unconditionally secure, then so are our protocols. Our results offer solutions that are significantly more efficient than previous techniques for secure linear algebra, they work for arbitrary fields and therefore extend the class of functions previously known to be computable in constant round and with unconditional security. In particular, we obtain an unconditionally secure protocol for computing a function f in constant round, where the protocol has complexity polynomial in the span program size of f over an arbitrary finite field.
Chapter PDF
Similar content being viewed by others
Keywords
- Secure Computation
- Oblivious Transfer
- Invertible Matrice
- Unconditional Security
- Secure Multiparty Computation
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
J. Bar-Ilan, D. Beaver: Non-cryptographic fault-tolerant computing in constant number of rounds of interaction, Proc. ACM PODC’ 89, pp. 201–209, 1989.
D. Beaver, S. Micali, P. Rogaway: The Round Complexity of Secure Protocols, Proc. 22nd ACM STOC, pp. 503–513, 1990.
D. Beaver: Minimal Latency Secure Function Evaluation, Proc. EUROCRYPT’ 00, Springer Verlag LNCS, vol. 1807, pp. 335–350.
A. Beimel, A. Gál: On Arithmetic Branching Programs, J. Comp. & Syst. Se, 59, pp. 195–220, 1999.
M. Ben-Or, S. Goldwasser, A. Wigderson: Completeness theorems for non-cryptographic fault-tolerant distributed computation, Proc. ACM STOC’ 88, pp. 1–10, 1988.
R. Canetti, U. Feige, O. Goldreich, M. Naor: Adaptively secure multi-party computation, Proc. ACM STOC’ 96, pp. 639–648, 1996.
D. Chaum, C. Crépeau, I. Damgård: Multi-party unconditionally secure protocols, Proc. ACM STOC’ 88, pp. 11–19, 1988.
R. Cramer, I. Damgård, J. Buus Nielsen: Multiparty Computation from Threshold Homomorphic Encryption, Proc. EUROCRYPT’ 01, Springer Verlag LNCS, vol. 2045, pp. 280–300., 2001.
R. Cramer, I. Damgård, U. Maurer: General Secure Multi-Party Computation from any Linear Secret-Sharing Scheme, Proc. EUROCRYPT’ 00, Springer Verlag LNCS, vol 1807, pp. 316–334. Full version available from IACR eprint archive, 2000.
R. Cramer, I. Damgård, S. Dziembowski, M. Hirt and T. Rabin: Efficient multiparty computations secure against an adaptive adversary, Proc. EUROCRYPT’ 99, Springer Verlag LNCS, vol. 1592, pp. 311–326, 1999.
R. Cramer, I. Damgård, V. Daza: work in progress, 2001.
U. Feige, J. Kilian, M. Naor: A Minimal Model for Secure Computation, Proc. ACM STOC’ 94, pp. 554–563, 1994.
R. Gennaro, M. Rabin, T. Rabin: Simplified VSS and fast-track multi-party computations with applications to threshold cryptography, Proc. ACM PODC’98, pp. 101–111, 1998.
O. Goldreich, S. Micali and A. Wigderson: How to play any mental game or a completeness theorem for protocols with honest majority, Proc. ACM STOC’ 87, pp. 218–229, 1987.
M. Hirt, U. Maurer: Player simulation and general adversary structures in perfect multi-party computation, Journal of Cryptology, vol. 13, no. 1, pp. 31–60, 2000. (Preliminary version in Proc. ACM PODC’97, pp. 25–34, 1997)
Y. Ishai, E. Kushilevitz: Private Simultaneous Messages Protocols with Applications, Proc. 5th Israel Symposium on Theoretical Comp. Sc. (ISTCS’ 97), pp. 174–183, 1997.
Y. Ishai, E. Kushilevitz: Randomizing Polynomials: A New Paradigm for Round-Efficient Secure Computation, Proc. of FOCS’ 00, 2000.
M. Karchmer, A. Wigderson: On span programs, Proc. of Structure in Complexity’ 93, pp. 102–111, 1993.
J. Kilian: Founding Cryptography on Oblivious Transfer, Proc. ACM STOC’ 88, pp. 20–31, 1988.
F. T. Leighton: Introduction to Parallel Algorithms and Architectures: Arrays-Trees-Hypercubes, Morgan Kaufmann Publishers, 1992.
M. Mahajan and V. Vinay: Determinant: combinatorics, algorithms and complexity, Chicago J. Theoret. Comput. Sci., Article 5, 1997.
K. Mulmuley: A Fast Parallel Algorithm to Compute the Rank of a Matrix over an Arbitrary Field, Combinatorica, vol. 7, pp. 101–104, 1987.
T. Rabin, M. Ben-Or: Verifiable secret sharing and multi-party protocols with honest majority, Proc. ACM STOC’ 89, pp. 73–85, 1989.
T. Rabin: Robust sharing of secrets when the dealer is honest or cheating, J. ACM, 41(6):1089–1109, November 1994.
A. Yao: Protocols for Secure Computation, Proc. IEEE FOCS’ 82, pp. 160–164, 1982.
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2001 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Cramer, R., Damgård, I. (2001). Secure Distributed Linear Algebra in a Constant Number of Rounds. In: Kilian, J. (eds) Advances in Cryptology — CRYPTO 2001. CRYPTO 2001. Lecture Notes in Computer Science, vol 2139. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-44647-8_7
Download citation
DOI: https://doi.org/10.1007/3-540-44647-8_7
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-42456-7
Online ISBN: 978-3-540-44647-7
eBook Packages: Springer Book Archive