Algorithms Based on *-Algebras, and Their Applications to Isomorphism of Polynomials with One Secret, Group Isomorphism, and Polynomial Identity Testing

DOI10.1137/18M1165682zbMath1422.68116arXiv1708.03495OpenAlexW2942921829MaRDI QIDQ4634059

Gábor Ivanyos, Youming Qiao

Publication date: 7 May 2019

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1708.03495

zbMATH Keywords

multivariate cryptographypolynomial identity testinginvolutive algebragroup isomorphism problemmodule isomorphism

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Symbolic computation and algebraic computation (68W30) Cryptography (94A60)

Related Items

Derandomization and absolute reconstruction for sums of powers of linear forms, On the Complexity of Isomorphism Problems for Tensors, Groups, and Polynomials I: Tensor Isomorphism-Completeness, Tensor isomorphism by conjugacy of Lie algebras, Practical post-quantum signature schemes from isomorphism problems of trilinear forms, General linear group action on tensors: a candidate for post-quantum cryptography, Group-theoretic generalisations of vertex and edge connectivities, Improved Algorithms for Alternating Matrix Space Isometry: From Theory to Practice, From Independent Sets and Vertex Colorings to Isotropic Spaces and Isotropic Decompositions: Another Bridge between Graphs and Alternating Matrix Spaces, Testing isomorphism of graded algebras

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Optimal algorithms of Gram-Schmidt type
• Splitting full matrix algebras over algebraic number fields.
• A fast isomorphism test for groups whose Lie algebra has genus 2
• Decompositions of algebras over \(\mathbb{R}\) and \(\mathbb{C}\)
• Decomposition of algebras over finite fields and number fields
• Invariant Wedderburn factors
• Testing isomorphism of modules.
• Decomposing \(p\)-groups via Jordan algebras.
• Vector spaces of matrices of low rank
• Forms over real algebras and the multisignature of a manifold
• Finding maximal orders in semisimple algebras over \(\mathbb{Q}\)
• Finding the radical of an algebra of linear transformations
• Computing Levi decompositions in Lie algebras
• HMFEv -- an efficient multivariate signature scheme
• Computing Cartan subalgebras of Lie algebras
• Efficient decomposition of associative algebras over finite fields
• Polynomial-time algorithms for quadratic isomorphism of polynomials: the regular case
• Algorithmic properties of maximal orders in simple algebras over \(\mathbb{Q}\)
• Non-commutative Edmonds' problem and matrix semi-invariants
• Characterizing Valiant's algebraic complexity classes
• Jordan and associative rings with nilpotent and invertible elements
• Computing the structure of finite algebras
• New Insight into the Isomorphism of Polynomial Problem IP1S and Its Use in Cryptography
• Hidden Fields Equations (HFE) and Isomorphisms of Polynomials (IP): Two New Families of Asymmetric Algorithms
• Isomorphism in expanding families of indistinguishable groups
• Arithmetic Circuits: A survey of recent results and open questions
• Practical Cryptanalysis of the Identification Scheme Based on the Isomorphism of Polynomial with One Secret Problem
• Finding central decompositions of p-groups
• Fast randomized algorithms for the structure of matrix algebras over finite fields (extended abstract)
• CONSTRUCTING THE GROUP PRESERVING A SYSTEM OF FORMS
• Polynomial Equivalence Problems: Algorithmic and Theoretical Aspects
• The Finite Simple Groups
• Progress on Polynomial Identity Testing - II
• Singular spaces of matrices and their application in combinatorics
• A Deterministic Method for Computing Splitting Elements in Simple Algebras over Q
• Constructive Non-Commutative Rank Computation Is in Deterministic Polynomial Time.
• Graph-Theoretic Algorithms for the “Isomorphism of Polynomials” Problem
• Deterministic equation solving over finite fields
• Algorithms for Group Isomorphism via Group Extensions and Cohomology
• A Fast Cryptanalysis of the Isomorphism of Polynomials with One Secret Problem
• Computing isometry groups of Hermitian maps
• Deterministic Polynomial Time Algorithms for Matrix Completion Problems
• On the n^{log n} isomorphism technique (A Preliminary Report)
• INVOLUTIONS AND ANTI-AUTOMORPHISMS OF ALGEBRAS
• The Classification of Real Division Algebras
• Groups with Abelian Central Quotient Group
• Derandomizing polynomial identity tests means proving circuit lower bounds