Paper 2019/841

Practical Cryptanalysis of k-ary C*

Daniel Smith-Tone


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 first-fall degree is a good approximation of the solving degree, an assumption that the paper notes requires ``greater justification and clarification." 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.

Available format(s)
Public-key cryptography
Publication info
Preprint. MINOR revision.
Multivariate Cryptographyk-ary C*big fielddifferential attack
Contact author(s)
daniel smith @ nist gov
2019-07-19: received
Short URL
Creative Commons Attribution


      author = {Daniel Smith-Tone},
      title = {Practical Cryptanalysis of k-ary C*},
      howpublished = {Cryptology ePrint Archive, Paper 2019/841},
      year = {2019},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.