  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 $(B_1, \dots, B_m)$ and $(C_1, \dots, C_m)$,
whether there exists an invertible matrix $A$ such that for every $i\in\{1,
\dots, m\}$, $A^tB_iA=C_i$. We show that this problem can be solved in
randomized polynomial time over finite fields of odd size, the real field, and
the complex field. The second problem asks to decide, given a tuple of square
matrices $(B_1, \dots, B_m)$, whether there exist invertible matrices $A$ and
$D$, such that for every $i\in\{1, \dots, m\}$, $AB_iD$ 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, 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 (Eurocrypto 1996). (2) Test
isomorphism of $p$-groups of class 2 and exponent $p$ ($p$ odd) with order
$p^k$ in time polynomial in the group order, when the commutator subgroup is of
order $p^{O(\sqrt{k})}$. (3) Deterministically reveal two families of
singularity witnesses caused by the skew-symmetric structure, which represents
a natural next step for the polynomial identity testing problem following the
direction set up by the recent resolution of the non-commutative rank problem
(Garg et al., FOCS 2016; Ivanyos et al., ITCS 2017).
