Top

Wireless Networks

Published in:

05-07-2022 | Original Paper

Optimal-round preprocessing-MPC of polynomials over non-zero inputs via distributed random matrix

Authors: Dor Bitan, Shlomi Dolev

Published in: Wireless Networks | Issue 7/2022

Activate our intelligent search to find suitable subject content or patents.

search-config

AI-assisted search

Off

Abstract

Secure multiparty computation (MPC) is an extensively studied research field in cryptography. It considers two main models—the plain model and the preprocessing model. The latter enables achieving objectives known to be unachievable for the plain model. One prominent example of such an objective is the perfectly secure evaluation of functions over private inputs, with the majority of the parties being dishonest. Recent results have shown that this objective can even be achieved in an optimal number of rounds of communication—two rounds. However, when the function to be evaluated is a polynomial with a possibly high degree over inputs taken from a large domain, existing solutions require an exponential amount of memory in the size of the domain. This paper presents preprocessing-MPC protocols for high-degree polynomials over non-zero inputs. These protocols are the first to have optimal round complexity, perfect security against coalitions of up to \(N-1\) out of N parties, and communication and space complexities that grow linearly with the number of monomials in the polynomial (independent of its degree). Furthermore, the results are extended to the client-server model. Namely, this paper presents a scheme that enables a user to outsource the storage of non-zero secrets to N distrusted servers and have the servers obliviously evaluate polynomials over the secrets in a single round of communication, perfectly secure against coalitions of up to \(N-1\) servers. These schemes are based on a novel secret sharing scheme, Distributed Random Matrix (DRM), first presented here. The DRM secret sharing scheme supports homomorphic multiplications and, after a single round of communication, supports homomorphic additions.

previous article On the outage performance of decode-and-forward based relay ordering in cognitive wireless sensor networks

next article A new fuzzy logic approach for reliable communications in wireless underground sensor networks

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Available only for authorised users

The term active security refers to security against malicious parties. These parties might deviate from the protocol in an attempt to sabotage the computation process. Handling malicious parties is out of the scope of this work.

If every two-party functionality had a protocol with polynomial space complexity, this would imply an unexpected answer to a longstanding open question on the complexity of information-theoretic private information retrieval. See [10, 37].

Note that [34] suggests a specific example for a specific technique to cope with possible zeros, which is a special case for our techniques.

Applebaum, B., Brakerski, Z., & Tsabary R. (2018). Perfect secure computation in two rounds. In Theory of cryptography conference (pp. 152–174). Springer.

Beaver, D., Micali, S., & Rogaway, P. (1990). The round complexity of secure protocols. In Proceedings of the twenty-second annual ACM symposium on theory of computing (pp. 503–513). ACM.

Ben-Or, M., Goldwasser, S., & Wigderson, A. (1988). Completeness theorems for non-cryptographic fault-tolerant distributed computation. In Proceedings of the twentieth annual ACM symposium on theory of computing (pp. 1–10). ACM.

Chaum, D., Crépeau, C., Damgard, I. (1988). Multiparty unconditionally secure protocols. In Proceedings of the twentieth annual ACM symposium on theory of computing (pp. 11–19). ACM.

Damgård, I., & Nielsen, J. B. (2003). Universally composable efficient multiparty computation from threshold homomorphic encryption. In Annual international cryptology conference (pp. 247–264). Springer.

Goldreich, O., Micali, S., & Wigderson, A. (1987). How to play any mental game. In Proceedings of the nineteenth annual ACM symposium on theory of computing (pp. 218–229). ACM.

Rivest, R. (1999). Unconditionally secure commitment and oblivious transfer schemes using private channels and a trusted initializer.

Yao, A. C.-C. (1982). Protocols for secure computations. FOCS, 82, 160–164.MathSciNet

Beaver, D. (1997). Commodity-based cryptography. In Proceedings of the twenty-ninth annual ACM symposium on Theory of computing (pp. 446–455). ACM.

10.

Ishai, Y., Kushilevitz, E., Meldgaard, S., Orlandi, C., & Paskin-Cherniavsky, A. (2013). On the power of correlated randomness in secure computation. In Theory of cryptography conference (pp. 600–620). Springer.

11.

Kushilevitz, E., & Nisan, N. (2006). Communication complexity. Cambridge University Press.MATH

12.

Shamir, A. (1979). How to share a secret. Communications of the ACM, 22(11), 612–613.MathSciNetCrossRef

13.

Bar-Ilan, J., & Beaver, D. (1989). Non-cryptographic fault-tolerant computing in constant number of rounds of interaction. In Proceedings of the eighth annual ACM symposium on principles of distributed computing (pp. 201–209). ACM.

14.

Damgård, I., Larsen, K. G., & Nielsen, J. B. (2019). Communication lower bounds for statistically secure MPC, with or without preprocessing. IACR Cryptology, 2019, 220.

15.

Patra, A., & Ravi, D. (2018). On the exact round complexity of secure three-party computation. In Annual international cryptology conference (pp. 425–458). Springer.

16.

Ananth, P., Choudhuri, A. R., Goel, A., & Jain, A. (2018). Round-optimal secure multiparty computation with honest majority. In Annual international cryptology conference (pp. 395–424). Springer.

17.

Garg, S., Ishai, Y., & Srinivasan, A. (2018) Two-round MPC: information-theoretic and black-box. In Theory of cryptography conference (pp. 123–151). Springer.

18.

Couteau, G. (2019). A note on the communication complexity of multiparty computation in the correlated randomness model. In Advances in cryptology—EUROCRYPT 2019—38th annual international conference on the theory and applications of cryptographic techniques, Darmstadt, Germany, 2019, proceedings, part II (pp. 473–503).

19.

Damgård, I., Nielsen, J. B., Nielsen, M., & Ranellucci, S. (2017). The tinytable protocol for 2-party secure computation, or: Gate-scrambling revisited. In Advances in cryptology—CRYPTO 2017—37th annual international cryptology conference, Santa Barbara, CA, 2017, proceedings, part I (pp. 167–187).

20.

Ametepe, A. F.-X., Ahouandjinou, A. S. R. M., & Ezin, E. C. (2022). Robust encryption method based on AES-CBC using elliptic curves Diffie–Hellman to secure data in wireless sensor networks. Wireless Networks, 28(3), 991–1001.CrossRef

21.

Akbari, M. R., Barati, H., & Barati, A. (2022). An overlapping routing approach for sending data from things to the cloud inspired by fog technology in the large-scale IoT ecosystem. Wireless Networks, 28(2), 521–538.CrossRef

22.

Chen, X., Jiao, L., Li, W., & Xiaoming, F. (2016). Efficient multi-user computation offloading for mobile-edge cloud computing. IEEE/ACM Transactions on Networking, 24(5), 2795–2808.CrossRef

23.

Derbeko, P., Dolev, S., & Gudes, E. (2021). Wavelet-based dynamic and privacy-preserving similitude data models for edge computing. Wireless Networks, 27(1), 351–366.CrossRef

24.

Ganesan, S., & Muthuswamy, V. (2021). Ensuring reliability of high-priority data transport using expected congestion shortfall prediction in wireless sensor networks. Wireless Networks, 27(8), 5125–5143.CrossRef

25.

Li, X., Shuo, X., Zhao, H., Han, S., & Yan, L. (2022). An adaptive multi-zone geographic routing protocol for underwater acoustic sensor networks. Wireless Networks, 28(1), 209–223.CrossRef

26.

Liu, J., & Yang, W. (2022). Secure UAV communication against cooperative adaptive eavesdroppers. Wireless Networks, 28(3), 1113–1128.CrossRef

27.

Rao, F.-Y., & Bertino, E. (2019). Privacy techniques for edge computing systems. Proceedings of the IEEE, 107(8), 1632–1654.CrossRef

28.

Srinivas, M., & Amgoth, T. (2022). Data acquisition in large-scale wireless sensor networks using multiple mobile sinks: A hierarchical clustering approach. Wireless Networks, 28(2), 603–619.

29.

Saida, R., Hadj Kacem, Y., BenSaleh, M. S., & Abid, M. (2022). A model based process for reconfigurable wireless sensor network development. Wireless Networks, 28(2), 567–585.CrossRef

30.

Santhosh Kumar, S. V. N., Palanichamy, Y., Selvi, M., Ganapathy, S., Kannan, A., & Pariserum Perumal, S. (2021). Energy efficient secured k means based unequal fuzzy clustering algorithm for efficient reprogramming in wireless sensor networks. Wireless Networks, 27(6), 3873–3894.CrossRef

31.

Wang, K., XiaoYi, Y., Lin, W. L., Deng, Z. L., & Liu, X. (2021). Computing aware scheduling in mobile edge computing system. Wireless Networks, 27(6), 4229–4245.CrossRef

32.

Wigderson, A. (2017). Technical perspective: Low-depth arithmetic circuits. Communications of the ACM, 60(6), 91–91.CrossRef

33.

Damgård, I., & Zakarias, S. (2013). Constant-overhead secure computation of Boolean circuits using preprocessing. In Proceedings of theory of cryptography 2013—The 10th theory of cryptography conference TCC (pp. 621–641).

34.

Ghodosi, H., Pieprzyk, J., & Steinfeld, R. (2012). Multi-party computation with conversion of secret sharing. Designs, Codes and Cryptography, 62(3), 259–272.MathSciNetCrossRef

35.

Halevi, S., Ishai, Y., Kushilevitz, E., & Rabin, T. (2018). Best possible information-theoretic MPC. In Theory of cryptography conference (pp. 255–281). Springer.

36.

Valiant, L. G. (1979). Completeness classes in algebra. In Proceedings of the eleventh annual ACM symposium on theory of computing (pp. 249–261). ACM.

37.

Chor, B., Goldreich, O., Kushilevitz, E., & Sudan, M. (1995). Private information retrieval. In Proceedings of IEEE 36th annual foundations of computer science (pp. 41–50). IEEE.

Title: Optimal-round preprocessing-MPC of polynomials over non-zero inputs via distributed random matrix
Authors: Dor Bitan
Shlomi Dolev
Publication date: 05-07-2022
Publisher: Springer US
Published in: Wireless Networks / Issue 7/2022
Print ISSN: 1022-0038
Electronic ISSN: 1572-8196
DOI: https://doi.org/10.1007/s11276-022-03040-7

Springer Professional

Abstract

Please log in to get access to your license.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"

Other articles of this Issue 7/2022

Secure and efficient cache-based authentication scheme for vehicular ad-hoc networks

Joint optimization of energy harvesting and information transmission for trapped user

Mitigating peak side-lobe levels in pulse compression radar using classical orthogonal polynomials

Secure transmission in one-bit cell-free massive MIMO system with multiple non-colluding eavesdroppers

An improved traffic flow forecasting based control logic using parametrical doped learning and truncated dual flow optimization model

Distributed multi-tenant RAN slicing in 5G networks