Secure Multi-Party Linear Algebra with Perfect Correctness
Authors
Jules Maire, Damien Vergnaud
Jules Maire
Sorbonne Université, CNRS, LIP6, Paris, France
jules dot maire at lip6 dot fr
jules dot maire at lip6 dot fr
Damien Vergnaud
Sorbonne Université, CNRS, LIP6, Paris, France
damien dot vergnaud at lip6 dot fr
damien dot vergnaud at lip6 dot fr
Keywords:
Secure Multi-Party Computation
Linear Algebra
Preparata-Sarwate Algorithm
Moore-Penrose Pseudo-Inverse
Abstract
We present new secure multi-party computation protocols for linear algebra over a finite field, which improve the state-of-the-art in terms of security. We look at the case of unconditional security with perfect correctness, i.e., information-theoretic security without errors. We notably propose an expected constant-round protocol for solving systems of m linear equations in n variables over Fq with expected complexity O(k n^2.5 + k m) (where complexity is measured in terms of the number of secure multiplications required) with k > m(m+n)+1. The previous proposals were not error-free: known protocols can indeed fail and thus reveal information with probability Omega(poly(m)/q). Our protocols are simple and rely on existing computer-algebra techniques, notably the Preparata-Sarwate algorithm, a simple but poorly known “baby-step giant-step” method for computing the characteristic polynomial of a matrix, and techniques due to Mulmuley for error-free linear algebra in positive characteristic.
References
[BB89]
Judit Bar-Ilan and Donald Beaver.
Non-cryptographic fault-tolerant computing in constant number of rounds of interaction.
In Piotr Rudnicki, editor, Proceedings of the Eighth Annual ACM Symposium on Principles of Distributed Computing, Edmonton, Alberta, Canada, August 14-16, 1989, 201–209. ACM, 1989.
https://doi.org/10.1145/72981.72995.
[BCH+23]
Ward Beullens, Ming-Shing Chen, Shih-Hao Hung, Matthias J. Kannwischer, Bo-Yuan Peng, Cheng-Jhih Shih, and Bo-Yin Yang.
Oil and vinegar: modern parameters and implementations.
IACR Trans. Cryptogr. Hardw. Embed. Syst., 2023(3):321–365, 2023.
https://doi.org/10.46586/TCHES.V2023.I3.321-365.
[BdV18]
Niek J. Bouman and Niels de Vreede.
New protocols for secure linear algebra: pivoting-free elimination and fast block-recursive matrix decomposition.
2018.
[Beu21]
Ward Beullens.
MAYO: practical post-quantum signatures from oil-and-vinegar maps.
In Riham AlTawy and Andreas Hülsing, editors, Selected Areas in Cryptography - 28th International Conference, SAC 2021, Virtual Event, September 29 - October 1, 2021, Revised Selected Papers, volume 13203 of Lecture Notes in Computer Science, 355–376. Springer, 2021.
https://doi.org/10.1007/978-3-030-99277-4_17.
[BGW88]
Michael Ben-Or, Shafi Goldwasser, and Avi Wigderson.
Completeness theorems for non-cryptographic fault-tolerant distributed computation (extended abstract).
In 20th Annual ACM Symposium on Theory of Computing, 1–10. Chicago, IL, USA, May 2–4, 1988. ACM Press.
https://doi.org/10.1145/62212.62213.
[CD01]
Ronald Cramer and Ivan Damgård.
Secure distributed linear algebra in a constant number of rounds.
In Joe Kilian, editor, Advances in Cryptology – CRYPTO 2001, volume 2139 of Lecture Notes in Computer Science, 119–136. Santa Barbara, CA, USA, August 19–23, 2001. Springer, Heidelberg, Germany.
https://doi.org/10.1007/3-540-44647-8_7.
[CDM00]
Ronald Cramer, Ivan Damgård, and Ueli M. Maurer.
General secure multi-party computation from any linear secret-sharing scheme.
In Bart Preneel, editor, Advances in Cryptology - EUROCRYPT 2000, International Conference on the Theory and Application of Cryptographic Techniques, Bruges, Belgium, May 14-18, 2000, Proceeding, volume 1807 of Lecture Notes in Computer Science, 316–334. Springer, 2000.
https://doi.org/10.1007/3-540-45539-6_22.
[CKP07]
Ronald Cramer, Eike Kiltz, and Carles Padró.
A note on secure computation of the Moore-Penrose pseudoinverse and its application to secure linear algebra.
In Alfred Menezes, editor, Advances in Cryptology – CRYPTO 2007, volume 4622 of Lecture Notes in Computer Science, 613–630. Santa Barbara, CA, USA, August 19–23, 2007. Springer, Heidelberg, Germany.
https://doi.org/10.1007/978-3-540-74143-5_34.
[DFK+06]
Ivan Damgård, Matthias Fitzi, Eike Kiltz, Jesper Buus Nielsen, and Tomas Toft.
Unconditionally secure constant-rounds multi-party computation for equality, comparison, bits and exponentiation.
In Shai Halevi and Tal Rabin, editors, TCC 2006: 3rd Theory of Cryptography Conference, volume 3876 of Lecture Notes in Computer Science, 285–304. New York, NY, USA, March 4–7, 2006. Springer, Heidelberg, Germany.
https://doi.org/10.1007/11681878_15.
[DGL05]
Gema M. Diaz-Toca, Laureano González-Vega, and Henri Lombardi.
Generalizing cramer's rule: solving uniformly linear systems of equations.
SIAM J. Matrix Anal. Appl., 27(3):621–637, 2005.
https://doi.org/10.1137/S0895479802418860.
[DN07]
Ivan Damgård and Jesper Buus Nielsen.
Scalable and unconditionally secure multiparty computation.
In Alfred Menezes, editor, Advances in Cryptology - CRYPTO 2007, 27th Annual International Cryptology Conference, Santa Barbara, CA, USA, August 19-23, 2007, Proceedings, volume 4622 of Lecture Notes in Computer Science, 572–590. Springer, 2007.
https://doi.org/10.1007/978-3-540-74143-5_32.
[DST19]
Thomas Debris-Alazard, Nicolas Sendrier, and Jean-Pierre Tillich.
Wave: A new family of trapdoor one-way preimage sampleable functions based on codes.
In Steven D. Galbraith and Shiho Moriai, editors, Advances in Cryptology – ASIACRYPT 2019, Part I, volume 11921 of Lecture Notes in Computer Science, 21–51. Kobe, Japan, December 8–12, 2019. Springer, Heidelberg, Germany.
https://doi.org/10.1007/978-3-030-34578-5_2.
[jD65]
H. P. jun. Decell.
An application of the Cayley-Hamilton theorem to generalized matrix inversion.
SIAM Rev., 7:526–528, 1965.
[Joh20]
Fredrik Johansson.
On a fast and nearly division-free algorithm for the characteristic polynomial.
CoRR, 2020.
[KLR06]
Eyal Kushilevitz, Yehuda Lindell, and Tal Rabin.
Information-theoretically secure protocols and security under composition.
In Jon M. Kleinberg, editor, 38th Annual ACM Symposium on Theory of Computing, 109–118. Seattle, WA, USA, May 21–23, 2006. ACM Press.
https://doi.org/10.1145/1132516.1132532.
[KMWF07]
Eike Kiltz, Payman Mohassel, Enav Weinreb, and Matthew K. Franklin.
Secure linear algebra using linearly recurrent sequences.
In Salil P. Vadhan, editor, TCC 2007: 4th Theory of Cryptography Conference, volume 4392 of Lecture Notes in Computer Science, 291–310. Amsterdam, The Netherlands, February 21–24, 2007. Springer, Heidelberg, Germany.
https://doi.org/10.1007/978-3-540-70936-7_16.
[KPG99]
Aviad Kipnis, Jacques Patarin, and Louis Goubin.
Unbalanced Oil and Vinegar signature schemes.
In Jacques Stern, editor, Advances in Cryptology – EUROCRYPT'99, volume 1592 of Lecture Notes in Computer Science, 206–222. Prague, Czech Republic, May 2–6, 1999. Springer, Heidelberg, Germany.
https://doi.org/10.1007/3-540-48910-X_15.
[LYKM22]
Donghang Lu, Albert Yu, Aniket Kate, and Hemanta K. Maji.
Polymath: low-latency MPC via secure polynomial evaluations and its applications.
Proc. Priv. Enhancing Technol., 2022(1):396–416, 2022.
https://doi.org/10.2478/popets-2022-0020.
[Mul86]
Ketan Mulmuley.
A fast parallel algorithm to compute the rank of a matrix over an arbitrary field.
In Juris Hartmanis, editor, Proceedings of the 18th Annual ACM Symposium on Theory of Computing, May 28-30, 1986, Berkeley, California, USA, 338–339. ACM, 1986.
https://doi.org/10.1145/12130.12164.
[MW08]
Payman Mohassel and Enav Weinreb.
Efficient secure linear algebra in the presence of covert or computationally unbounded adversaries.
In David Wagner, editor, Advances in Cryptology – CRYPTO 2008, volume 5157 of Lecture Notes in Computer Science, 481–496. Santa Barbara, CA, USA, August 17–21, 2008. Springer, Heidelberg, Germany.
https://doi.org/10.1007/978-3-540-85174-5_27.
[NO07]
Takashi Nishide and Kazuo Ohta.
Multiparty computation for interval, equality, and comparison without bit-decomposition protocol.
In Tatsuaki Okamoto and Xiaoyun Wang, editors, PKC 2007: 10th International Conference on Theory and Practice of Public Key Cryptography, volume 4450 of Lecture Notes in Computer Science, 343–360. Beijing, China, April 16–20, 2007. Springer, Heidelberg, Germany.
https://doi.org/10.1007/978-3-540-71677-8_23.
[NW06]
Kobbi Nissim and Enav Weinreb.
Communication efficient secure linear algebra.
In Shai Halevi and Tal Rabin, editors, TCC 2006: 3rd Theory of Cryptography Conference, volume 3876 of Lecture Notes in Computer Science, 522–541. New York, NY, USA, March 4–7, 2006. Springer, Heidelberg, Germany.
https://doi.org/10.1007/11681878_27.
[{Pen}55]
R. Penrose.
A generalized inverse for matrices.
Proc. Camb. Philos. Soc., 51:406–413, 1955.
[PS73]
Mike Paterson and Larry J. Stockmeyer.
On the number of nonscalar multiplications necessary to evaluate polynomials.
SIAM J. Comput., 2(1):60–66, 1973.
https://doi.org/10.1137/0202007.
[PS78]
Franco P. Preparata and Dilip V. Sarwate.
An improved parallel processor bound in fast matrix inversion.
Inf. Process. Lett., 7(3):148–150, 1978.
https://doi.org/10.1016/0020-0190(78)90079-0.
[Ran93]
Dana Randall.
Efficient generation of random nonsingular matrices.
Random Struct. Algorithms, 4(1):111–118, 1993.
https://doi.org/10.1002/rsa.3240040108.
[Sch93]
Arnold Schönhage.
Fast parallel computation of characteristic polynomials by leverrier's power sum method adapted to fields of finite characteristic.
In Andrzej Lingas, Rolf G. Karlsson, and Svante Carlsson, editors, Automata, Languages and Programming, 20nd International Colloquium, ICALP93, Lund, Sweden, July 5-9, 1993, Proceedings, volume 700 of Lecture Notes in Computer Science, 410–417. Springer, 1993.
https://doi.org/10.1007/3-540-56939-1_90.
[Yao86]
Andrew Chi-Chih Yao.
How to generate and exchange secrets (extended abstract).
In 27th Annual Symposium on Foundations of Computer Science, 162–167. Toronto, Ontario, Canada, October 27–29, 1986. IEEE Computer Society Press.
https://doi.org/10.1109/SFCS.1986.25.
PDF
History
Submitted: 2024-01-09
Accepted: 2024-03-05
Published: 2024-04-09
Accepted: 2024-03-05
Published: 2024-04-09
How to cite
Jules Maire and Damien Vergnaud, Secure Multi-Party Linear Algebra with Perfect Correctness. IACR Communications in Cryptology, vol. 1, no. 1, Apr 09, 2024, doi: 10.62056/avzojbkrz.
License
Copyright is held by the author(s)
This work is licensed under a Creative Commons Attribution (CC BY) license.