Multi-Party Secure Computation of Multi-variable Polynomials

The goal of decentralizing the calculations performed by participants in information interaction protocols is usually to improve the reliability and security of information systems. Decentralized computing is based on multi-party secure computing protocols (MSCP), which are usually not universal, but are built for pre-specific functions calculated by participants. In this work, an MSCP is constructed to calculate polynomial values from several variables over a finite field. The constructed protocol is based on linear secret separation schemes, and its characteristics, such as the power of valid and unauthorized coalitions, can be described in terms of the characteristics of linear codes and their SchurHadamard degrees. Some codes and code constructs for which such characteristics can be determined analytically are described.

Keywords

secure computation; linear codes.

References

1. Yao A. Protocols for Secure Computations. IEEE Computer Society, 1982, pp. 160-164.
2. Archer D.W., Bogdanov D., Lindell Y. et al. From Keys to Databases-Real-World Applications of Secure Multi-Party Computation. The Computer Journal, 2018, vol. 61, no. 12, pp. 1749-1771.
3. Garg S., Ghodsi Z., Hazay C. et al. Outsourcing Private Machine Learning via Lightweight Secure Arithmetic Computation. Available at: https://arxiv.org/abs/1812.01372 (accessed 04.05.2022)
4. Jintai Ding, Bo-Yin Yang. Multivariate Public Key Cryptography. Post-Quantum Cryptography, New York, Springer, 2009, pp. 193-241.
5. Bruneau N., Guilley S., Heuser A. Optimal Side-Channel Attacks for Multivariate Leakages and Multiple Models. Journal of Cryptographic Engineering, 2017, no. 7, pp. 331-341.
6. Aesun Park, Kyung-Ah Shim, Namhun Koo et al. Side-Channel Attacks on Post-Quantum Signature Schemes Based on Multivariate Quadratic Equations. IACR Transactions on Cryptographic Hardware and Embedded Systems, 2018, no. 3, pp. 500-523.
7. Weijian Li, Xian Huang, Huimin Zhao et al. Fuzzy Matching Template Attacks on Multivariate Cryptography: A Case Study. Discrete Dynamics in Nature and Society, 2020, vol. 2020, pp. 1-11. DOI: 10.1155/2020/9475782
8. Haibo Yi, Weijian Li. On the Importance of Checking Multivariate Public Key Cryptography for Side-Channel Attacks: the Case of enTTS Scheme. The Computer Journal, 2017, vol. 60, no. 8, pp. 1-13. DOI: 10.1093/comjnl/bxx010
9. Carlet C., Prouff E. Polynomial Evaluation and Side Channel Analysis. The New Codebreakers, 2016, vol. 9100, pp. 315-341.
10. Kosolapov Yu.V. [Blakley Type Secret Sharing Scheme Based on the Intersection of Subspaces]. Mathematical Aspects of Cryptography, 2017, vol. 8, no. 1, pp. 13-30. (in Russian)
11. MacWilliams F.J., Sloane N.J.A. The Theory of Error-Correcting Codes. North Holland, North Holland Publishing, 1977.
12. Randriambololon H. On Products and Powers of Linear Codes under Componentwise Multiplication. Available at: http://arxiv.org/abs/1312.0022 (accessed 04.05.2022)
13. Deundayk V.M., Kosolapov Yu.V. [On Some Properties of the Schur-Hadamard Product for Linear Codes and their Applications]. Applied Discrete Mathematics, 2020, no. 50, pp. 72-86. (in Russian)
14. Chizhov I.V., Borodin M.A. Effective Attack on the McEliece Cryptosystem Based on Reed-Muller Codes. Discrete Mathematics and Applications, 2014, vol. 24, no. 5, pp. 273-280.
15. Roumaissa M., Pierre L.C., Sedat A. et al. A Novel Niederreiter-Like Cryptosystem Based on the (u|u+v)-construction Codes. RAIRO - Theoretical Informatics and Applications, 2021, no. 55, pp. 1-16.