{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T02:39:16Z","timestamp":1760150356722,"version":"build-2065373602"},"reference-count":58,"publisher":"MDPI AG","issue":"4","license":[{"start":{"date-parts":[[2023,11,9]],"date-time":"2023-11-09T00:00:00Z","timestamp":1699488000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"name":"European Union\u2019s Horizon 2020 research","award":["780477"],"award-info":[{"award-number":["780477"]}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Cryptography"],"abstract":"<jats:p>In this paper, we introduce secure groups as a cryptographic scheme representing finite groups together with a range of operations, including the group operation, inversion, random sampling, and encoding\/decoding maps. We construct secure groups from oblivious group representations combined with cryptographic protocols, implementing the operations securely. We present both generic and specific constructions, in the latter case specifically for number-theoretic groups commonly used in cryptography. These include Schnorr groups (with quadratic residues as a special case), Weierstrass and Edwards elliptic curve groups, and class groups of imaginary quadratic number fields. For concreteness, we develop our protocols in the setting of secure multiparty computation based on Shamir secret sharing over a finite field, abstracted away by formulating our solutions in terms of an arithmetic black box for secure finite field arithmetic or for secure integer arithmetic. Secure finite field arithmetic suffices for many groups, including Schnorr groups and elliptic curve groups. For class groups, we need secure integer arithmetic to implement Shanks\u2019 classical algorithms for the composition of binary quadratic forms, which we will combine with our adaptation of a particular form reduction algorithm due to Agarwal and Frandsen. As a main result of independent interest, we also present an efficient protocol for the secure computation of the extended greatest common divisor. The protocol is based on Bernstein and Yang\u2019s constant-time 2-adic algorithm, which we adapt to work purely over the integers. This yields a much better approach for multiparty computation but raises a new concern about the growth of the B\u00e9zout coefficients. By a careful analysis, we are able to prove that the B\u00e9zout coefficients in our protocol will never exceed 3max(a,b) in absolute value for inputs a and b. We have integrated secure groups in the Python package MPyC and have implemented threshold ElGamal and threshold DSA in terms of secure groups. We also mention how our results support verifiable multiparty computation, allowing parties to jointly create a publicly verifiable proof of correctness for the results accompanying the results of a secure computation.<\/jats:p>","DOI":"10.3390\/cryptography7040056","type":"journal-article","created":{"date-parts":[[2023,11,9]],"date-time":"2023-11-09T10:19:27Z","timestamp":1699525167000},"page":"56","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Secure Groups for Threshold Cryptography and Number-Theoretic Multiparty Computation"],"prefix":"10.3390","volume":"7","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-6273-8930","authenticated-orcid":false,"given":"Berry","family":"Schoenmakers","sequence":"first","affiliation":[{"name":"Department of Mathematics & Computer Science, TU Eindhoven, 5600 MB Eindhoven, The Netherlands"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-5829-9696","authenticated-orcid":false,"given":"Toon","family":"Segers","sequence":"additional","affiliation":[{"name":"Department of Mathematics & Computer Science, TU Eindhoven, 5600 MB Eindhoven, The Netherlands"}]}],"member":"1968","published-online":{"date-parts":[[2023,11,9]]},"reference":[{"key":"ref_1","first-page":"32","article-title":"Efficient Extended GCD and Class Groups from Secure Integer Arithmetic","volume":"Volume 13914","author":"Schoenmakers","year":"2023","journal-title":"Proceedings of the Cyber Security, Cryptology, and Machine Learning\u20147th International Symposium, CSCML 2023"},{"key":"ref_2","doi-asserted-by":"crossref","unstructured":"Bar-Ilan, J., and Beaver, D. (1989, January 14\u201316). Non-Cryptographic Fault-Tolerant Computing in Constant Number of Rounds of Interaction. Proceedings of the Eighth Annual ACM Symposium on Principles of Distributed Computing, Edmonton, AB, Canada.","DOI":"10.1145\/72981.72995"},{"key":"ref_3","first-page":"326","article-title":"Twisted Edwards Curves Revisited","volume":"Volume 5350","author":"Pieprzyk","year":"2008","journal-title":"Proceedings of the Advances in Cryptology\u2014ASIACRYPT 2008, 14th International Conference on the Theory and Application of Cryptology and Information Security"},{"key":"ref_4","doi-asserted-by":"crossref","unstructured":"Buchmann, J.A., and Vollmer, U. (2007). Binary Quadratic Forms\u2014An Algorithmic Approach, Springer. Algorithms and Computation in Mathematics.","DOI":"10.1007\/978-3-540-46368-9_2"},{"key":"ref_5","first-page":"379","article-title":"Efficient Verifiable Delay Functions","volume":"Volume 11478","author":"Ishai","year":"2019","journal-title":"Proceedings of the Advances in Cryptology\u2014EUROCRYPT 2019\u201438th Annual International Conference on the Theory and Applications of Cryptographic Techniques"},{"key":"ref_6","first-page":"123","article-title":"Time- and Space-Efficient Arguments from Groups of Unknown Order","volume":"Volume 12828","author":"Malkin","year":"2021","journal-title":"Proceedings of the Advances in Cryptology\u2014CRYPTO 2021\u201441st Annual International Cryptology Conference, CRYPTO 2021"},{"key":"ref_7","first-page":"25","article-title":"Trustless unknown-order groups","volume":"1","author":"Dobson","year":"2022","journal-title":"Math. Cryptol."},{"key":"ref_8","doi-asserted-by":"crossref","first-page":"340","DOI":"10.46586\/tches.v2019.i3.340-398","article-title":"Fast constant-time gcd computation and modular inversion","volume":"2019","author":"Bernstein","year":"2019","journal-title":"IACR Trans. Cryptogr. Hardw. Embed. Syst."},{"key":"ref_9","unstructured":"Menezes, A., van Oorschot, P.C., and Vanstone, S.A. (1996). Handbook of Applied Cryptography, CRC Press."},{"key":"ref_10","doi-asserted-by":"crossref","first-page":"233","DOI":"10.1016\/0898-1221(87)90130-1","article-title":"A systolic algorithm for extended GCD computation","volume":"14","author":"Bojanczyk","year":"1987","journal-title":"Comput. Math. Appl."},{"key":"ref_11","unstructured":"Knuth, D.E. (1969). The Art of Computer Programming, Volume II: Seminumerical Algorithms, Pearson Education."},{"key":"ref_12","doi-asserted-by":"crossref","first-page":"30","DOI":"10.1007\/11682462_8","article-title":"A New GCD Algorithm for Quadratic Number Rings with Unique Factorization","volume":"Volume 3887","author":"Correa","year":"2006","journal-title":"Proceedings of the LATIN 2006: Theoretical Informatics, 7th Latin American Symposium"},{"key":"ref_13","first-page":"342","article-title":"Distributing Any Elliptic Curve Based Protocol","volume":"Volume 11929","author":"Albrecht","year":"2019","journal-title":"Proceedings of the Cryptography and Coding\u201417th IMA International Conference, IMACC 2019"},{"key":"ref_14","doi-asserted-by":"crossref","first-page":"44","DOI":"10.1007\/s00145-021-09409-9","article-title":"Fast Secure Two-Party ECDSA Signing","volume":"34","author":"Lindell","year":"2021","journal-title":"J. Cryptol."},{"key":"ref_15","first-page":"147","article-title":"Efficient Threshold Zero-Knowledge with Applications to User-Centric Protocols","volume":"Volume 7412","author":"Smith","year":"2012","journal-title":"Proceedings of the Information Theoretic Security\u20146th International Conference, ICITS 2012"},{"key":"ref_16","first-page":"175","article-title":"Publicly Auditable Secure Multi-Party Computation","volume":"Volume 8642","author":"Abdalla","year":"2014","journal-title":"Proceedings of the Security and Cryptography for Networks\u20149th International Conference, SCN 2014"},{"key":"ref_17","doi-asserted-by":"crossref","first-page":"21","DOI":"10.1007\/978-3-319-57339-7_2","article-title":"Pinocchio-Based Adaptive zk-SNARKs and Secure\/Correct Adaptive Function Evaluation","volume":"Volume 10239","author":"Joye","year":"2017","journal-title":"Proceedings of the Progress in Cryptology\u2014AFRICACRYPT 2017\u20149th International Conference on Cryptology in Africa"},{"key":"ref_18","unstructured":"Simon, J. (1988, January 2\u20134). Completeness Theorems for Non-Cryptographic Fault-Tolerant Distributed Computation (Extended Abstract). Proceedings of the 20th Annual ACM Symposium on Theory of Computing, Chicago, IL, USA."},{"key":"ref_19","unstructured":"Coan, B.A., and Afek, Y. (July, January 28). Simplified VSS and Fast-Track Multiparty Computations with Applications to Threshold Cryptography. Proceedings of the Seventeenth Annual ACM Symposium on Principles of Distributed Computing, PODC\u201998, Puerto Vallarta, Mexico."},{"key":"ref_20","unstructured":"de Hoogh, S. (2012). Design of Large Scale Applications of Secure Multiparty Computation: Secure Linear Programming. [Ph.D. Thesis, Department of Mathematics and Computer Science, Technische Universiteit Eindhoven]."},{"key":"ref_21","unstructured":"Toft, T. (2007). Primitives and Applications for Multi-Party Computation. [Ph.D. Thesis, Aarhus University]."},{"key":"ref_22","doi-asserted-by":"crossref","unstructured":"Damg\u00e5rd, I., Fitzi, M., Kiltz, E., Nielsen, J.B., and Toft, T. (2006). Unconditionally Secure Constant-Rounds Multi-Party Computation for Equality, Comparison, Bits and Exponentiation, Springer.","DOI":"10.1007\/11681878_15"},{"key":"ref_23","doi-asserted-by":"crossref","unstructured":"Algesheimer, J., Camenisch, J., and Shoup, V. (2002). Efficient Computation Modulo a Shared Secret with Application to the Generation of Shared Safe-Prime Products, Springer.","DOI":"10.1007\/3-540-45708-9_27"},{"key":"ref_24","unstructured":"Catrina, O., and Saxena, A. (2010, January 25\u201328). Secure Computation with Fixed-Point Numbers. Proceedings of the Financial Cryptography and Data Security, 14th International Conference, FC 2010, Tenerife, Canary Islands, Spain."},{"key":"ref_25","doi-asserted-by":"crossref","unstructured":"Korzilius, S., and Schoenmakers, B. (2023). Divisions and Square Roots with Tight Error Analysis from Newton\u2013Raphson Iteration in Secure Fixed-Point Arithmetic. Cryptography, 7.","DOI":"10.3390\/cryptography7030043"},{"key":"ref_26","doi-asserted-by":"crossref","unstructured":"Brent, R.P., and Kung, H.T. (1985, January 4\u20136). A systolic algorithm for integer GCD computation. Proceedings of the 1985 IEEE 7th Symposium on Computer Arithmetic (ARITH), Urbana, IL, USA.","DOI":"10.1109\/ARITH.1985.6158931"},{"key":"ref_27","doi-asserted-by":"crossref","unstructured":"Buell, D. (2004, January 13\u201318). A Binary Recursive Gcd Algorithm. Proceedings of the Algorithmic Number Theory, Burlington, VT, USA.","DOI":"10.1007\/b98210"},{"key":"ref_28","unstructured":"Serre, J. (1977). Graduate Texts in Mathematics, Springer."},{"key":"ref_29","unstructured":"Holt, D., and Makholm, H. (2020, January 23). What Are Some Group Representation of the Rubik\u2019s Cube Group? StackExchange Mathematics. Available online: https:\/\/math.stackexchange.com\/questions\/1587307\/what-are-some-group-representation-of-the-rubiks-cube-group."},{"key":"ref_30","doi-asserted-by":"crossref","first-page":"R94","DOI":"10.37236\/818","article-title":"Generating Random Elements in Finite Groups","volume":"15","author":"Dixon","year":"2008","journal-title":"Electron. J. Comb."},{"key":"ref_31","doi-asserted-by":"crossref","first-page":"97","DOI":"10.1090\/conm\/298\/05116","article-title":"Variants of product replacement","volume":"298","author":"Murray","year":"2002","journal-title":"Contemp. Math."},{"key":"ref_32","doi-asserted-by":"crossref","first-page":"64","DOI":"10.1016\/j.jsc.2011.08.017","article-title":"The Product Replacement Prospector","volume":"47","year":"2012","journal-title":"J. Symb. Comput."},{"key":"ref_33","unstructured":"Pak, I. (2000, January 12\u201314). The product replacement algorithm is polynomial. Proceedings of the 41st Annual Symposium on Foundations of Computer Science, FOCS 2000, Redondo Beach, CA, USA."},{"key":"ref_34","doi-asserted-by":"crossref","first-page":"167","DOI":"10.1137\/S0097539702403773","article-title":"Design and Analysis of Practical Public-Key Encryption Schemes Secure against Adaptive Chosen Ciphertext Attack","volume":"33","author":"Cramer","year":"2003","journal-title":"SIAM J. Comput."},{"key":"ref_35","doi-asserted-by":"crossref","first-page":"203","DOI":"10.1090\/S0025-5718-1987-0866109-5","article-title":"Elliptic Curve Cryptosystems","volume":"48","author":"Koblitz","year":"1987","journal-title":"Math. Comput."},{"key":"ref_36","doi-asserted-by":"crossref","first-page":"253","DOI":"10.1112\/jlms\/s1-38.1.253","article-title":"A note on the distribution of residues and non-residues","volume":"1","author":"Burgess","year":"1963","journal-title":"J. Lond. Math. Soc."},{"key":"ref_37","doi-asserted-by":"crossref","first-page":"257","DOI":"10.1016\/j.jnt.2003.06.003","article-title":"On consecutive quadratic non-residues: A conjecture of Issai Schur","volume":"103","author":"Hummel","year":"2003","journal-title":"J. Number Theory"},{"key":"ref_38","doi-asserted-by":"crossref","first-page":"65","DOI":"10.2307\/1969420","article-title":"The Least Quadratic Non Residue","volume":"55","author":"Ankeny","year":"1952","journal-title":"Ann. Math."},{"key":"ref_39","doi-asserted-by":"crossref","first-page":"243","DOI":"10.1007\/BF01937490","article-title":"On runs of consecutive quadratic residues and quadratic nonresidues","volume":"24","author":"Buell","year":"1984","journal-title":"BIT Numer. Math."},{"key":"ref_40","doi-asserted-by":"crossref","first-page":"297","DOI":"10.1007\/s00145-004-0314-9","article-title":"Short Signatures from the Weil Pairing","volume":"17","author":"Boneh","year":"2004","journal-title":"J. Cryptol."},{"key":"ref_41","doi-asserted-by":"crossref","unstructured":"Renes, J., Costello, C., and Batina, L. (2016, January 8\u201312). Complete Addition Formulas for Prime Order Elliptic Curves. Proceedings of the Advances in Cryptology\u2013EUROCRYPT 2016: 35th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Vienna, Austria.","DOI":"10.1007\/978-3-662-49890-3_16"},{"key":"ref_42","unstructured":"Bernstein, D.J., and Lange, T. (2007, January 2\u20136). Faster Addition and Doubling on Elliptic Curves. Proceedings of the Advances in Cryptology\u2014ASIACRYPT 2007: 13th International Conference on the Theory and Application of Cryptology and Information Security, Kuching, Malaysia."},{"key":"ref_43","doi-asserted-by":"crossref","unstructured":"Faz-Hernandez, A., Scott, S., Sullivan, N., Wahby, R., and Wood, C. (2022, May 23). IETF Internet Research Taskforce, CFRG Workgroup: Hashing to Elliptic Curves. Available online: https:\/\/www.ietf.org\/archive\/id\/draft-irtf-cfrg-hash-to-curve-10.html.","DOI":"10.17487\/RFC9380"},{"key":"ref_44","unstructured":"Sadeghi, A., Gligor, V.D., and Yung, M. (2013, January 4\u20138). Elligator: Elliptic-curve points indistinguishable from uniform random strings. Proceedings of the 2013 ACM SIGSAC Conference on Computer and Communications Security, CCS\u201913, Berlin, Germany."},{"key":"ref_45","first-page":"41","article-title":"Class number, a theory of factorization, and genera","volume":"20","author":"Shanks","year":"1971","journal-title":"Proc. Symp. Math. Soc."},{"key":"ref_46","unstructured":"Cohen, H. (1993). Graduate Texts in Mathematics, Springer."},{"key":"ref_47","unstructured":"Lejeune Dirichlet, P. (2023, October 20). Vorlesungen \u00fcber Zahlentheorie, Original Published in 1863. 2nd Edition Text Published in 1871. Translation by John Stillwell: Lectures on Number Theory, History of Mathematics Source Series Volume: 16. Available online: http:\/\/www-gdz.sub.uni-goettingen.de\/cgi-bin\/digbib.cgi?PPN30976923X."},{"key":"ref_48","unstructured":"Cox, D.A. (2011). Primes of the Form x2+ny2: Fermat, Class Field Theory, and Complex Multiplication, John Wiley & Sons."},{"key":"ref_49","unstructured":"Long, L., and Binary Quadratic Forms (2020, January 23). GitHub. Available online: https:\/\/github.com\/Chia-Network\/vdf-competition\/blob\/master\/classgroups.pdf."},{"key":"ref_50","unstructured":"David, N., Espitau, T., and Hosoyamada, A. (2022). Quantum binary quadratic form reduction. Cryptol. ePrint Arch."},{"key":"ref_51","unstructured":"Schielzeth, D. (2003). Realisierung der ElGamal-Verschl\u00fcsselung in Quadratischen Z\u00e4hlkorpern. [Master\u2019s Thesis, Technische Universit\u00e4t Berlin]. Available online: https:\/\/page.math.tu-berlin.de\/~kant\/publications\/diplom\/schielzeth.pdf."},{"key":"ref_52","unstructured":"Schaub, J. (1999). Implementiering von Public-Key-Kryptosystemen \u00dcber Imagin\u00e4r-Quadratischen Ordnungen. [Master\u2019s Thesis, Technische Universit\u00e4t Darmstadt, Fachbereich Informatik]."},{"key":"ref_53","doi-asserted-by":"crossref","first-page":"483","DOI":"10.1090\/S0894-0347-1992-1137100-0","article-title":"A rigorous time bound for factoring integers","volume":"5","author":"Lenstra","year":"1992","journal-title":"J. Am. Math. Soc."},{"key":"ref_54","unstructured":"Pedersen, T.P. (1991, January 8\u201311). A Threshold Cryptosystem without a Trusted Party. Proceedings of the Advances in Cryptology\u2014EUROCRYPT\u201991: Workshop on the Theory and Application of Cryptographic Techniques, Brighton, UK."},{"key":"ref_55","unstructured":"Schoenmakers, B. (2023, October 20). MPyC Secure Multiparty Computation in Python. GitHub. Available online: https:\/\/github.com\/lschoe\/mpyc."},{"key":"ref_56","unstructured":"Schoenmakers, B., and Segers, A.J.M. (2023, October 20). Verifiable MPC. GitHub. Available online: https:\/\/github.com\/toonsegers\/verifiable_mpc."},{"key":"ref_57","first-page":"513","article-title":"Compressed \u03a3-Protocol Theory and Practical Application to Plug & Play Secure Algorithmics","volume":"Volume 12172","author":"Micciancio","year":"2020","journal-title":"Proceedings of the Advances in Cryptology\u2014CRYPTO 2020\u201440th Annual International Cryptology Conference, CRYPTO 2020"},{"key":"ref_58","first-page":"346","article-title":"Trinocchio: Privacy-Preserving Outsourcing by Distributed Verifiable Computation","volume":"Volume 9696","author":"Manulis","year":"2016","journal-title":"Proceedings of the Applied Cryptography and Network Security\u201414th International Conference, ACNS 2016"}],"container-title":["Cryptography"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/2410-387X\/7\/4\/56\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,10]],"date-time":"2025-10-10T21:20:40Z","timestamp":1760131240000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/2410-387X\/7\/4\/56"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,11,9]]},"references-count":58,"journal-issue":{"issue":"4","published-online":{"date-parts":[[2023,12]]}},"alternative-id":["cryptography7040056"],"URL":"https:\/\/doi.org\/10.3390\/cryptography7040056","relation":{},"ISSN":["2410-387X"],"issn-type":[{"type":"electronic","value":"2410-387X"}],"subject":[],"published":{"date-parts":[[2023,11,9]]}}}