{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,23]],"date-time":"2026-04-23T14:50:30Z","timestamp":1776955830774,"version":"3.51.4"},"reference-count":49,"publisher":"MDPI AG","issue":"11","license":[{"start":{"date-parts":[[2021,11,4]],"date-time":"2021-11-04T00:00:00Z","timestamp":1635984000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Entropy"],"abstract":"<jats:p>We consider the secure computation problem in a minimal model, where Alice and Bob each holds an input and wish to securely compute a function of their inputs at Carol without revealing any additional information about the inputs. For this minimal secure computation problem, we propose a novel coding scheme built from two steps. First, the function to be computed is expanded such that it can be recovered while additional information might be leaked. Second, a randomization step is applied to the expanded function such that the leaked information is protected. We implement this expand-and-randomize coding scheme with two algebraic structures\u2014the finite field and the modulo ring of integers, where the expansion step is realized with the addition operation and the randomization step is realized with the multiplication operation over the respective algebraic structures.<\/jats:p>","DOI":"10.3390\/e23111461","type":"journal-article","created":{"date-parts":[[2021,11,4]],"date-time":"2021-11-04T09:11:32Z","timestamp":1636017092000},"page":"1461","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":14,"title":["Expand-and-Randomize: An Algebraic Approach to Secure Computation"],"prefix":"10.3390","volume":"23","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-8659-672X","authenticated-orcid":false,"given":"Yizhou","family":"Zhao","sequence":"first","affiliation":[{"name":"Department of Electrical Engineering, University of North Texas, Denton, TX 76203, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Hua","family":"Sun","sequence":"additional","affiliation":[{"name":"Department of Electrical Engineering, University of North Texas, Denton, TX 76203, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"1968","published-online":{"date-parts":[[2021,11,4]]},"reference":[{"key":"ref_1","doi-asserted-by":"crossref","first-page":"5634","DOI":"10.1109\/TIT.2011.2162183","article-title":"Secret sharing and non-shannon information inequalities","volume":"57","author":"Beimel","year":"2011","journal-title":"IEEE Trans. Inf. Theory"},{"key":"ref_2","doi-asserted-by":"crossref","first-page":"599","DOI":"10.1109\/TIT.2015.2500232","article-title":"Secret sharing, rank inequalities, and information inequalities","volume":"62","author":"Yang","year":"2016","journal-title":"IEEE Trans. Inf. Theory"},{"key":"ref_3","doi-asserted-by":"crossref","first-page":"4075","DOI":"10.1109\/TIT.2017.2689028","article-title":"The Capacity of Private Information Retrieval","volume":"63","author":"Sun","year":"2017","journal-title":"IEEE Trans. Inf. Theory"},{"key":"ref_4","doi-asserted-by":"crossref","first-page":"1945","DOI":"10.1109\/TIT.2018.2791994","article-title":"The Capacity of Private Information Retrieval from Coded Databases","volume":"64","author":"Banawan","year":"2018","journal-title":"IEEE Trans. Inf. Theory"},{"key":"ref_5","unstructured":"Lee, E.J., and Abbe, E. (October, January 30). Two shannon-type problems on secure multi-party computations. Proceedings of the 52nd Annual Allerton Conference on Communication, Control, and Computing (Allerton), Monticello, IL, USA."},{"key":"ref_6","doi-asserted-by":"crossref","first-page":"3901","DOI":"10.1109\/TIT.2016.2568207","article-title":"Communication and randomness lower bounds for secure computation","volume":"62","author":"Data","year":"2016","journal-title":"IEEE Trans. Inf. Theory"},{"key":"ref_7","doi-asserted-by":"crossref","unstructured":"Zhou, Y., Sun, H., and Fu, S. (2019, January 20\u201322). On the Randomness Cost of Linear Secure Computation. Proceedings of the 2019 53rd Annual Conference on Information Sciences and Systems (CISS), Baltimore, MD, USA.","DOI":"10.1109\/CISS.2019.8692860"},{"key":"ref_8","doi-asserted-by":"crossref","unstructured":"Yao, A.C. (1982, January 3\u20135). Protocols for secure computations. Proceedings of the 23rd Annual Symposium on Foundations of Computer Science (Sfcs 1982), Chicago, IL, USA.","DOI":"10.1109\/SFCS.1982.38"},{"key":"ref_9","doi-asserted-by":"crossref","unstructured":"Ben-Or, M., Goldwasser, S., and Wigderson, A. (1988, January 2\u20134). Completeness theorems for non-cryptographic fault-tolerant distributed computation. Proceedings of the Twentieth Annual ACM Symposium on Theory of Computing, Chicago, IL, USA.","DOI":"10.1145\/62212.62213"},{"key":"ref_10","doi-asserted-by":"crossref","unstructured":"Chaum, D., Cr\u00e9peau, C., and Damgard, I. (1988, January 2\u20134). Multiparty unconditionally secure protocols. Proceedings of the Twentieth Annual ACM Symposium on Theory of Computing, Chicago, IL, USA.","DOI":"10.1145\/62212.62214"},{"key":"ref_11","doi-asserted-by":"crossref","unstructured":"Cramer, R., Damgard, I.B., and Nielsen, J.B. (2015). Secure Multiparty Computation and Secret Sharing, Cambridge University Press.","DOI":"10.1017\/CBO9781107337756"},{"key":"ref_12","doi-asserted-by":"crossref","unstructured":"Feige, U., Killian, J., and Naor, M. (1994, January 23\u201325). A minimal model for secure computation. Proceedings of the Twenty-Sixth Annual ACM Symposium on Theory of Computing, Montreal, QC, Canada.","DOI":"10.1145\/195058.195408"},{"key":"ref_13","doi-asserted-by":"crossref","unstructured":"Applebaum, B., Holenstein, T., Mishra, M., and Shayevitz, O. (2018). The communication complexity of private simultaneous messages, revisited. Annual International Conference on the Theory and Applications of Cryptographic Techniques, Springer.","DOI":"10.1007\/978-3-319-78375-8_9"},{"key":"ref_14","unstructured":"Ishai, Y., and Kushilevitz, E. (1997, January 17\u201319). Private simultaneous messages protocols with applications. Proceedings of the Fifth Israeli Symposium on Theory of Computing and Systems, Ramat Gan, Israel."},{"key":"ref_15","doi-asserted-by":"crossref","unstructured":"Beimel, A., Kushilevitz, E., and Nissim, P. (2018). The complexity of multiparty PSM protocols and related models. Annual International Conference on the Theory and Applications of Cryptographic Techniques, Springer.","DOI":"10.1007\/978-3-319-78375-8_10"},{"key":"ref_16","unstructured":"Assouline, L., and Liu, T. (2021, October 03). Multi-Party PSM, Revisited. Cryptology ePrint Archive, Report 2019\/657. Available online: https:\/\/eprint.iacr.org\/2019\/657."},{"key":"ref_17","doi-asserted-by":"crossref","unstructured":"Beimel, A., Gabizon, A., Ishai, Y., Kushilevitz, E., Meldgaard, S., and Paskin-Cherniavsky, A. (2014). Non-interactive secure multiparty computation. Annual Cryptology Conference, Springer.","DOI":"10.1007\/978-3-662-44381-1_22"},{"key":"ref_18","doi-asserted-by":"crossref","unstructured":"Benhamouda, F., Krawczyk, H., and Rabin, T. (2017). Robust non-interactive multiparty computation against constant-size collusion. Annual International Cryptology Conference, Springer.","DOI":"10.1007\/978-3-319-63688-7_13"},{"key":"ref_19","doi-asserted-by":"crossref","first-page":"1793","DOI":"10.1007\/s10623-017-0424-7","article-title":"On the (in) efficiency of non-interactive secure multiparty computation","volume":"86","author":"Yoshida","year":"2018","journal-title":"Des. Codes Cryptogr."},{"key":"ref_20","doi-asserted-by":"crossref","unstructured":"Agarwal, N., Anand, S., and Prabhakaran, M. (2019). Uncovering Algebraic Structures in the MPC Landscape. Annual International Conference on the Theory and Applications of Cryptographic Techniques, Springer.","DOI":"10.1007\/978-3-030-17656-3_14"},{"key":"ref_21","doi-asserted-by":"crossref","unstructured":"Halevi, S., Ishai, Y., Kushilevitz, E., and Rabin, T. (2018). Best possible information-theoretic MPC. Theory of Cryptography Conference, Springer.","DOI":"10.1007\/978-3-030-03810-6_10"},{"key":"ref_22","doi-asserted-by":"crossref","unstructured":"Beimel, A., Ishai, Y., and Kushilevitz, E. (2017). Ad hoc PSM protocols: Secure computation without coordination. Annual International Conference on the Theory and Applications of Cryptographic Techniques, Springer.","DOI":"10.1007\/978-3-319-56617-7_20"},{"key":"ref_23","unstructured":"Dummit, D.S., and Foote, R.M. (2004). Abstract Algebra, John Wiley & Sons."},{"key":"ref_24","unstructured":"Ishai, Y., and Kushilevitz, E. (2000, January 12\u201314). Randomizing polynomials: A new representation with applications to round-efficient secure computation. Proceedings of the 41st Annual Symposium on Foundations of Computer Science, Redondo Beach, CA, USA."},{"key":"ref_25","unstructured":"Yuval, I., and Kushilevitz, E. (2002). Perfect constant-round secure computation via perfect randomizing polynomials. International Colloquium on Automata, Languages, and Programming, Springer."},{"key":"ref_26","doi-asserted-by":"crossref","unstructured":"Lidl, R., and Niederreiter, H. (1997). Finite Fields, Cambridge University Press.","DOI":"10.1017\/CBO9780511525926"},{"key":"ref_27","unstructured":"Shanks, D. (1978). Solved and Unsolved Problems in Number Theory, Chelsea Publishing Company."},{"key":"ref_28","unstructured":"Judson, T. (2014). Abstract Algebra: Theory and Applications, Stephen F. Austin State University."},{"key":"ref_29","doi-asserted-by":"crossref","first-page":"69","DOI":"10.1109\/TIT.1987.1057272","article-title":"A Dichotomy of Functions F(x,y) of Correlated Sources (X,Y) from the Viewpoint of the Achievable Rate Region","volume":"33","author":"Han","year":"1987","journal-title":"IEEE Trans. Inf. Theory"},{"key":"ref_30","doi-asserted-by":"crossref","first-page":"7003","DOI":"10.1109\/TIT.2017.2749234","article-title":"On distributed computing for functions with certain structures","volume":"63","author":"Kuzuoka","year":"2017","journal-title":"IEEE Trans. Inf. Theory"},{"key":"ref_31","doi-asserted-by":"crossref","first-page":"3498","DOI":"10.1109\/TIT.2007.904785","article-title":"Computation over multiple-access channels","volume":"53","author":"Nazer","year":"2007","journal-title":"IEEE Trans. Inf. Theory"},{"key":"ref_32","doi-asserted-by":"crossref","first-page":"1015","DOI":"10.1109\/TIT.2010.2095070","article-title":"Network coding for computing: Cut-set bounds","volume":"57","author":"Appuswamy","year":"2011","journal-title":"IEEE Trans. Inf. Theory"},{"key":"ref_33","doi-asserted-by":"crossref","first-page":"6454","DOI":"10.1109\/TIT.2018.2827405","article-title":"Comments on cut-set bounds on network function computation","volume":"64","author":"Huang","year":"2018","journal-title":"IEEE Trans. Inf. Theory"},{"key":"ref_34","doi-asserted-by":"crossref","first-page":"219","DOI":"10.1109\/TIT.1979.1056022","article-title":"How to encode the modulo-two sum of binary sources","volume":"25","author":"Korner","year":"1979","journal-title":"IEEE Trans. Inf. Theory"},{"key":"ref_35","first-page":"37","article-title":"Coding for noisy channels","volume":"3","author":"Elias","year":"1955","journal-title":"IRE Conv. Rec."},{"key":"ref_36","doi-asserted-by":"crossref","first-page":"2","DOI":"10.1109\/TIT.1974.1055171","article-title":"Recent results in the shannon theory","volume":"20","author":"Wyner","year":"1974","journal-title":"IEEE Trans. Inf. Theory"},{"key":"ref_37","doi-asserted-by":"crossref","first-page":"585","DOI":"10.1109\/TIT.1982.1056524","article-title":"Linear codes for sources and source networks: Error exponents, universal coding","volume":"28","author":"Csiszar","year":"1982","journal-title":"IEEE Trans. Inf. Theory"},{"key":"ref_38","unstructured":"Gamal, A.E., and Kim, Y.-H. (2011). Network Information Theory, Cambridge University Press."},{"key":"ref_39","doi-asserted-by":"crossref","unstructured":"Data, D., Dey, B.K., Mishra, M., and Prabhakaran, V.M. (2014, January 2\u20135). How to securely compute the modulo-two sum of binary sources. Proceedings of the 2014 IEEE Information Theory Workshop (ITW 2014), Hobart, Australia.","DOI":"10.1109\/ITW.2014.6970881"},{"key":"ref_40","doi-asserted-by":"crossref","first-page":"2399","DOI":"10.1109\/TIT.2015.2407874","article-title":"Abelian group codes for channel coding and source coding","volume":"61","author":"Sahebi","year":"2015","journal-title":"IEEE Trans. Inf. Theory"},{"key":"ref_41","doi-asserted-by":"crossref","unstructured":"Heidari, M., and Pradhan, S.S. (2016, January 10\u201315). How to compute modulo prime-power sums. Proceedings of the 2016 IEEE International Symposium on Information Theory (ISIT), Barcelona, Spain.","DOI":"10.1109\/ISIT.2016.7541614"},{"key":"ref_42","doi-asserted-by":"crossref","unstructured":"Katz, J., and Lindell, Y. (2014). Introduction to Modern Cryptography, Chapman and Hall\/CRC.","DOI":"10.1201\/b17668"},{"key":"ref_43","doi-asserted-by":"crossref","unstructured":"Shoup, V. (2009). A Computational Introduction to Number Theory and Algebra, Cambridge University Press.","DOI":"10.1017\/CBO9780511814549"},{"key":"ref_44","unstructured":"Cohen, H. (2013). A Course in Computational Algebraic Number Theory, Springer Science & Business Media."},{"key":"ref_45","first-page":"373","article-title":"An arithmetic method of counting the subgroups of a finite abelian group","volume":"53","year":"2010","journal-title":"Bull. Math. Soc. Sci. Math. Roum."},{"key":"ref_46","first-page":"93","article-title":"Subgroups of finite abelian groups having rank two via Goursat\u2019s lemma","volume":"59","year":"2014","journal-title":"Tatra Mt. Math. Publ."},{"key":"ref_47","unstructured":"Bauer, K., Sen, D., and Zvengrowski, P. (2011). A generalized goursat lemma. arXiv."},{"key":"ref_48","doi-asserted-by":"crossref","first-page":"215","DOI":"10.4169\/college.math.j.42.3.215","article-title":"Counting subgroups in a direct product of finite cyclic groups","volume":"42","author":"Petrillo","year":"2011","journal-title":"Coll. Math. J."},{"key":"ref_49","doi-asserted-by":"crossref","first-page":"46","DOI":"10.1017\/S1446788718000319","article-title":"The distribution of the number of subgroups of the multiplicative group","volume":"108","author":"Martin","year":"2017","journal-title":"J. Aust. Math. Soc."}],"container-title":["Entropy"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1099-4300\/23\/11\/1461\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T07:25:37Z","timestamp":1760167537000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1099-4300\/23\/11\/1461"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,11,4]]},"references-count":49,"journal-issue":{"issue":"11","published-online":{"date-parts":[[2021,11]]}},"alternative-id":["e23111461"],"URL":"https:\/\/doi.org\/10.3390\/e23111461","relation":{},"ISSN":["1099-4300"],"issn-type":[{"value":"1099-4300","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,11,4]]}}}