Cryptology ePrint Archive: Report 2019/841

Practical Cryptanalysis of k-ary C*

Daniel Smith-Tone

Abstract: Recently, an article by Felke appeared in Cryptography and Communications discussing the security of biquadratic C* and a further generalization, k-ary C*. The article derives lower bounds for the complexity of an algebraic attack, directly inverting the public key, under an assumption that the fi rst-fall degree is a good approximation of the solving degree, an assumption that the paper notes requires ``greater justi fication and clari fication."

In this work, we provide a practical attack breaking all k-ary C* schemes. The attack is based on differential techniques and requires nothing but the ability to evaluate the public key and solve linear systems. In particular, the attack breaks the parameters provided in CryptoChallenge11 by constructing and solving linear systems of moderate size in a few minutes.

Category / Keywords: public-key cryptography / Multivariate Cryptography, k-ary C*, big field, differential attack

Date: received 18 Jul 2019

Contact author: daniel smith at nist gov

Available format(s): PDF | BibTeX Citation

Version: 20190719:134824 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]