Giesbrecht's algorithm, the HFE cryptosystem and Ore's p^s-polynomials

zbMATH Open1018.12011arXiv1611.04479MaRDI QIDQ4550787FDOQ4550787

Authors: Robert S. Coulter, George Havas, Marie Henderson 

Publication date: 10 February 2003

Abstract: We report on a recent implementation of Giesbrecht's algorithm for factoring polynomials in a skew-polynomial ring. We also discuss the equivalence between factoring polynomials in a skew-polynomial ring and decomposing $p^s$-polynomials over a finite field, and how Giesbrecht's algorithm is outlined in some detail by Ore in the 1930's. We end with some observations on the security of the Hidden Field Equation (HFE) cryptosystem, where $p$-polynomials play a central role.

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

Recommendations

• Advances in Cryptology - CRYPTO 2003
• Publication:4941844
• Public Key Cryptography - PKC 2005
• The degree of regularity of HFE systems
• scientific article; zbMATH DE number 1617932

zbMATH Keywords

factoring polynomialsskew-polynomial ringhidden field equation cryptosystemimplementation of Giesbrecht's algorithm

Mathematics Subject Classification ID

Cryptography (94A60) Group rings (16S34)

Cited In (3)

• Why you cannot even hope to use Ore algebras in cryptography
• Algebraic Condition for Decomposition of Large-Scale Linear Dynamic Systems
• An isomorphism test for modules over a non-commutative PID. Applications to similarity of Ore polynomials.

This page was built for publication: Giesbrecht's algorithm, the HFE cryptosystem and Ore's $p^s$-polynomials

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4550787)