{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T03:26:56Z","timestamp":1740108416867,"version":"3.37.3"},"reference-count":27,"publisher":"Springer Science and Business Media LLC","issue":"6","license":[{"start":{"date-parts":[[2021,10,19]],"date-time":"2021-10-19T00:00:00Z","timestamp":1634601600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2021,10,19]],"date-time":"2021-10-19T00:00:00Z","timestamp":1634601600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/100009567","name":"Budapest University of Technology and Economics","doi-asserted-by":"crossref","id":[{"id":"10.13039\/100009567","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["AAECC"],"published-print":{"date-parts":[[2023,11]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>We propose a new identification system based on algorithmic problems related to computing isomorphisms between central simple algebras. We design a statistical zero knowledge protocol which relies on the hardness of computing isomorphisms between orders in division algebras which generalizes a protocol by Hartung and Schnorr, which relies on the hardness of integral equivalence of quadratic forms.<\/jats:p>","DOI":"10.1007\/s00200-021-00529-0","type":"journal-article","created":{"date-parts":[[2021,10,19]],"date-time":"2021-10-19T19:39:26Z","timestamp":1634672366000},"page":"913-930","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["An identification system based on the explicit isomorphism problem"],"prefix":"10.1007","volume":"34","author":[{"given":"S\u00e1ndor Z.","family":"Kiss","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"P\u00e9ter","family":"Kutas","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2021,10,19]]},"reference":[{"issue":"3-4","key":"529_CR1","doi-asserted-by":"publisher","first-page":"235","DOI":"10.1006\/jsco.1996.0125","volume":"24","author":"W Bosma","year":"1997","unstructured":"Bosma, W., Cannon, J., Playoust, C.: The Magma algebra system I: The user language. J. Symb. Comput. 24(3\u20134), 235\u2013265 (1997)","journal-title":"J. Symb. Comput."},{"key":"529_CR2","doi-asserted-by":"publisher","first-page":"177","DOI":"10.1016\/S0022-4049(97)00010-8","volume":"117\u2013118","author":"AM Cohen","year":"1997","unstructured":"Cohen, A.M., Ivanyos, G., Wales, D.B.: Finding the radical of an algebra of linear transformations. J. Pure Appl. Algebra 117\u2013118, 177\u2013193 (1997)","journal-title":"J. Pure Appl. Algebra"},{"key":"529_CR3","doi-asserted-by":"crossref","unstructured":"Cremona, J.E., Fisher, T.A., O\u2019Neil, C., Simon, D., Stoll, M.: Explicit n-descent on elliptic curves I. Algebra. Journal f\u00fcr die reine und angewandte Mathematik 615, 121\u2013155 (2008)","DOI":"10.1515\/CRELLE.2008.012"},{"key":"529_CR4","doi-asserted-by":"crossref","unstructured":"Cremona, J.E., Fisher, T.A., O\u2019Neil, C., Simon, D., Stoll, M.: Explicit $$n$$-descent on elliptic curves II. Geometry. Journal f\u00fcr die reine und angewandte Mathematik 632, 63\u201384 (2009)","DOI":"10.1515\/CRELLE.2009.050"},{"key":"529_CR5","doi-asserted-by":"publisher","first-page":"895","DOI":"10.1090\/S0025-5718-2014-02858-5","volume":"84","author":"JE Cremona","year":"2015","unstructured":"Cremona, J.E., Fisher, T.A., O\u2019Neil, C., Simon, D., Stoll, M.: Explicit $$n$$-descent on elliptic curves III. Algorithms. Math. Comput. 84, 895\u2013922 (2015)","journal-title":"Math. Comput."},{"key":"529_CR6","doi-asserted-by":"crossref","unstructured":"Delfs, H., Knebl, H.: Introduction to Cryptography. 3rd ed., Springer (2015)","DOI":"10.1007\/978-3-662-47974-2"},{"key":"529_CR7","first-page":"207","volume":"1","author":"WM Eberly","year":"1991","unstructured":"Eberly, W.M.: Decompositions of algebras over $${\\mathbb{R}}$$ and $${\\mathbb{C}}$$. Comput. Complex. 1, 207\u2013230 (1991)","journal-title":"Comput. Complex."},{"key":"529_CR8","doi-asserted-by":"crossref","unstructured":"Friedl, K., R\u00f3nyai, L.: Polynomial time solutions of some problems in computational algebra. In Proceedings of the 17th Annual ACM Symposium on Theory of Computing, Providence, Rhode Island, pp. 153\u2013162 (1985)","DOI":"10.1145\/22145.22162"},{"key":"529_CR9","doi-asserted-by":"crossref","unstructured":"Goldreich, O.: Foundations of cryptography I: Basic tools. Cambridge University Press (2001)","DOI":"10.1017\/CBO9780511546891"},{"key":"529_CR10","doi-asserted-by":"publisher","first-page":"690","DOI":"10.1145\/116825.116852","volume":"38","author":"O Goldreich","year":"1991","unstructured":"Goldreich, O., Micali, S., Wigderson, A.: Proofs that yield nothing but their validity or all languages in NP have zero-knowledge proof systems. J. ACM 38, 690\u2013728 (1991)","journal-title":"J. ACM"},{"key":"529_CR11","doi-asserted-by":"crossref","unstructured":"Goldreich, O., Sahai, A., Vadhan, S.: Honest-verifier statistical zero-knowledge equals general statistical zero-knowledge. In: STOC \u201998: Proceedings of the Thirtieth Annual ACM Symposium on Theory of Computing, pp .399\u2013408 (1998)","DOI":"10.1145\/276698.276852"},{"key":"529_CR12","doi-asserted-by":"publisher","first-page":"186","DOI":"10.1137\/0218012","volume":"18","author":"S Goldwasser","year":"1989","unstructured":"Goldwasser, S., Micali, S., Rackoff, C.: The knowledge complexity of interactive proof systems. SIAM J. Comput. 18, 186\u2013208 (1989)","journal-title":"SIAM J. Comput."},{"key":"529_CR13","doi-asserted-by":"publisher","first-page":"2702","DOI":"10.1109\/TIT.2016.2538264","volume":"62","author":"J G\u00f3mez-Torrecillas","year":"2016","unstructured":"G\u00f3mez-Torrecillas, J., Lobillo, F.J., Navarro, G.: A new perspective of cyclicity in convolutional codes. IEEE Trans. Inf. Theory 62, 2702\u20132706 (2016)","journal-title":"IEEE Trans. Inf. Theory"},{"key":"529_CR14","doi-asserted-by":"publisher","first-page":"514","DOI":"10.1016\/j.jalgebra.2005.06.022","volume":"303","author":"WA de Graaf","year":"2006","unstructured":"de Graaf, W.A., Harrison, M., P\u00edlnikova, J., Schicho, J.: A Lie algebra method for rational parametrization of Severi-Brauer surfaces. J. Algebra 303, 514\u2013529 (2006)","journal-title":"J. Algebra"},{"key":"529_CR15","doi-asserted-by":"publisher","first-page":"327","DOI":"10.1515\/JMC.2008.015","volume":"2","author":"RJ Hartung","year":"2008","unstructured":"Hartung, R.J., Schnorr, C.P.: Identification and signatures based on NP-hard problems of indefinite quadratic forms. J. Math. Cryptol. 2, 327\u2013341 (2008)","journal-title":"J. Math. Cryptol."},{"key":"529_CR16","doi-asserted-by":"crossref","unstructured":"Havas, G., Majewski, B.S., Matthews, K.R.: Extended GCD and Hermite normal form algorithms via lattice basis reduction. Exp. Math. 7(2), 125\u2013136 (1998). Addenda and errata: Extended GCD and Hermite normal form algorithms via lattice basis reduction, Exp. Math. 8(2), 205 (1999)","DOI":"10.1080\/10586458.1998.10504362"},{"key":"529_CR17","doi-asserted-by":"crossref","unstructured":"Hub\u00e1cek, P., Rosen, A., Vald, M.: An efficiency-preserving transformation from honest-verifier statistical zero-knowledge to statistical zero-knowledge. In: Nielsen, J., Rijmen, V. (eds) Advances in Cryptology\u2013EUROCRYPT 2018. Lecture Notes in Computer Science, vol 10822. Springer, Cham (2018)","DOI":"10.1007\/978-3-319-78372-7_3"},{"key":"529_CR18","unstructured":"Ivanyos, G.: Algorithms for algebras over global field; Ph. D. thesis, Hungarian Academy of Sciences (1996)"},{"key":"529_CR19","doi-asserted-by":"publisher","first-page":"381","DOI":"10.1007\/s10208-017-9343-2","volume":"18","author":"G Ivanyos","year":"2018","unstructured":"Ivanyos, G., Kutas, P., R\u00f3nyai, L.: Computing explicit isomorphisms with full matrix algebras over $$\\mathbb{F}_q(x)$$. Found. Comput. Math. 18, 381\u2013397 (2018)","journal-title":"Found. Comput. Math."},{"key":"529_CR20","doi-asserted-by":"publisher","first-page":"211","DOI":"10.1016\/j.jalgebra.2012.01.008","volume":"354","author":"G Ivanyos","year":"2012","unstructured":"Ivanyos, G., R\u00f3nyai, L., Schicho, J.: Splitting full matrix algebras over algebraic number fields. J. Algebra 354, 211\u2013223 (2012)","journal-title":"J. Algebra"},{"key":"529_CR21","unstructured":"Ivanyos, G., R\u00f3nyai, L., Sz\u00e1nt\u00f3, \u00c1: Decomposition of algebras over $$\\mathbb{F} _q(x_1,... ,x_m)$$. Appl. Algebra Eng. Commun. Comput. 5, 71\u201390 (1994)"},{"key":"529_CR22","doi-asserted-by":"crossref","unstructured":"Kutas, P.: Splitting quaternion algebras over quadratic number fields. Journal of Symbolic Computation 94, 173-182 (2019)","DOI":"10.1016\/j.jsc.2018.08.002"},{"key":"529_CR23","doi-asserted-by":"crossref","unstructured":"Pierce, R.S.: Associative Algebras. Springer-Verlag (1982)","DOI":"10.1007\/978-1-4757-0163-0"},{"key":"529_CR24","doi-asserted-by":"publisher","first-page":"579","DOI":"10.1016\/j.jsc.2007.01.001","volume":"42","author":"J P\u00edlnikov\u00e1","year":"2007","unstructured":"P\u00edlnikov\u00e1, J.: Trivializing a central simple algebra of degree 4 over the rational numbers. J. Symb. Comput. 42, 579\u2013586 (2007)","journal-title":"J. Symb. Comput."},{"key":"529_CR25","unstructured":"Reiner, I.: Maximal Orders. Academic Press (1975)"},{"key":"529_CR26","doi-asserted-by":"crossref","unstructured":"R\u00f3nyai, L.: Simple algebras are difficult. In: Proceedings of the 19th Annual ACM Symposium on the Theory of Computing, New York, pp. 398\u2013408 (1987)","DOI":"10.1145\/28395.28438"},{"key":"529_CR27","doi-asserted-by":"publisher","first-page":"355","DOI":"10.1016\/S0747-7171(08)80017-X","volume":"9","author":"L R\u00f3nyai","year":"1990","unstructured":"R\u00f3nyai, L.: Computing the structure of finite algebras. J. Symb. Comput. 9, 355\u2013373 (1990)","journal-title":"J. Symb. Comput."}],"container-title":["Applicable Algebra in Engineering, Communication and Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00200-021-00529-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00200-021-00529-0\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00200-021-00529-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,10,10]],"date-time":"2023-10-10T16:04:15Z","timestamp":1696953855000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00200-021-00529-0"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,10,19]]},"references-count":27,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2023,11]]}},"alternative-id":["529"],"URL":"https:\/\/doi.org\/10.1007\/s00200-021-00529-0","relation":{},"ISSN":["0938-1279","1432-0622"],"issn-type":[{"type":"print","value":"0938-1279"},{"type":"electronic","value":"1432-0622"}],"subject":[],"published":{"date-parts":[[2021,10,19]]},"assertion":[{"value":"19 November 2019","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"28 June 2021","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"16 September 2021","order":3,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"19 October 2021","order":4,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}