Algorithms based on ∗-algebras, and their applications to isomorphism of polynomials with one secret, group isomorphism, and polynomial identity testing

Ivanyos, G; Qiao, Y

Algorithms based on ∗-algebras, and their applications to isomorphism of polynomials with one secret, group isomorphism, and polynomial identity testing

Ivanyos, G Qiao, Y

Permalink

Publication Type:: Conference Proceeding
Citation:: Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms, 2018, pp. 2357 - 2376
Issue Date:: 2018-01-01

Open Access

Copyright Clearance Process

Recently Added
In Progress
Open Access

This item is open access.

Adobe PDF

Download Accepted Manuscript versionAdobe PDF (459.75 kB)

View on publisher's site

View statistics

Full metadata record

Field	Value	Language
dc.contributor.author	Ivanyos, G	en_US
dc.contributor.author	Qiao, Y https://orcid.org/0000-0003-4334-1449	en_US
dc.date.issued	2018-01-01	en_US
dc.identifier.citation	Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms, 2018, pp. 2357 - 2376	en_US
dc.identifier.isbn	9781611975031	en_US
dc.identifier.uri	http://hdl.handle.net/10453/130877
dc.description.abstract	© Copyright 2018 by SIAM. We consider two basic algorithmic problems concerning tuples of (skew-)symmetric matrices. The first problem asks to decide, given two tuples of (skew-)symmetric matrices (B1; : : : ;Bm) and (C1; : : : ;Cm), whether there exists an invertible matrix A such that for every i 2 f1; : : : ;mg, AtBiA = Ci. We show that this problem can be solved in randomized polynomial time over finite fields of odd size, the reals, and the complex numbers. The second problem asks to decide, given a tuple of square matrices (B1; : : : ;Bm), whether there exist invertible matrices A and D, such that for every i 2 f1; : : : ;mg, ABiD is (skew-)symmetric. We show that this problem can be solved in deterministic polynomial time over fields of characteristic not 2. For both problems we exploit the structure of the underlying α-algebras (algebras with an involutive antiautomorphism), and utilize results and methods from the module isomorphism problem. Applications of our results range from multivariate cryptography, group isomorphism, to polynomial identity testing. Specifically, these results imply efficient algorithms for the following problems. (1) Test isomorphism of quadratic forms with one secret over a finite field of odd size. This problem belongs to a family of problems that serves as the security basis of certain authentication schemes proposed by Patarin (Eurocrypt 1996). (2) Test isomorphism of p-groups of class 2 and exponent p (p odd) with order p' in time polynomial in the group order, when the commutator subgroup is of order pO( p '). (3) Deterministically reveal two families of singularity witnesses caused by the skew-symmetric structure. This represents a natural next step for the polynomial identity testing problem, in the direction set up by the recent resolution of the non-commutative rank problem (Garg-Gurvits-Oliveira-Wigderson, FOCS 2016; Ivanyos-Qiao-Subrahmanyam, ITCS 2017).	en_US
dc.relation	http://purl.org/au-research/grants/arc/DE150100720
dc.relation.ispartof	Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms	en_US
dc.relation.isbasedon	10.1137/1.9781611975031.152	en_US
dc.title	Algorithms based on ∗-algebras, and their applications to isomorphism of polynomials with one secret, group isomorphism, and polynomial identity testing	en_US
dc.type	Conference Proceeding
utslib.for	0802 Computation Theory and Mathematics	en_US
pubs.embargo.period	Not known	en_US
pubs.organisational-group	/University of Technology Sydney
pubs.organisational-group	/University of Technology Sydney/Faculty of Engineering and Information Technology
pubs.organisational-group	/University of Technology Sydney/Faculty of Engineering and Information Technology/School of Computer Science
pubs.organisational-group	/University of Technology Sydney/Strength - QSI - Centre for Quantum Software and Information
utslib.copyright.status	open_access
pubs.publication-status	Published	en_US

Abstract:

© Copyright 2018 by SIAM. We consider two basic algorithmic problems concerning tuples of (skew-)symmetric matrices. The first problem asks to decide, given two tuples of (skew-)symmetric matrices (B1; : : : ;Bm) and (C1; : : : ;Cm), whether there exists an invertible matrix A such that for every i 2 f1; : : : ;mg, AtBiA = Ci. We show that this problem can be solved in randomized polynomial time over finite fields of odd size, the reals, and the complex numbers. The second problem asks to decide, given a tuple of square matrices (B1; : : : ;Bm), whether there exist invertible matrices A and D, such that for every i 2 f1; : : : ;mg, ABiD is (skew-)symmetric. We show that this problem can be solved in deterministic polynomial time over fields of characteristic not 2. For both problems we exploit the structure of the underlying α-algebras (algebras with an involutive antiautomorphism), and utilize results and methods from the module isomorphism problem. Applications of our results range from multivariate cryptography, group isomorphism, to polynomial identity testing. Specifically, these results imply efficient algorithms for the following problems. (1) Test isomorphism of quadratic forms with one secret over a finite field of odd size. This problem belongs to a family of problems that serves as the security basis of certain authentication schemes proposed by Patarin (Eurocrypt 1996). (2) Test isomorphism of p-groups of class 2 and exponent p (p odd) with order p' in time polynomial in the group order, when the commutator subgroup is of order pO( p '). (3) Deterministically reveal two families of singularity witnesses caused by the skew-symmetric structure. This represents a natural next step for the polynomial identity testing problem, in the direction set up by the recent resolution of the non-commutative rank problem (Garg-Gurvits-Oliveira-Wigderson, FOCS 2016; Ivanyos-Qiao-Subrahmanyam, ITCS 2017).

Please use this identifier to cite or link to this item:

http://hdl.handle.net/10453/130877