HFE and BDDs: A Practical Attempt at Cryptanalysis

摘要: HFE (Hidden Field Equations) is a public key cryptosystem using univariate polynomials over finite fields. It was proposed by J. Patarin in 1996. Well chosen parameters during the construction produce system of quadratic multivariate \({\mathbb{F}_2}\) as key. An enclosed trapdoor used to decrypt messages. We propose ciphertext-only attack which mainly consists satisfying boolean formula. Our algorithm based on BDDs (Binary Decision Diagrams), introduced Bryant 1986, allow represent and manipulate, possibly efficiently, functions. This paper devoted some experimental results we obtained while trying solve Patarin’s challenge. approach not successful, nevertheless it provided interesting information about security cryptosystem.