Skip to main content
U.S. flag

An official website of the United States government

Official websites use .gov
A .gov website belongs to an official government organization in the United States.

Secure .gov websites use HTTPS
A lock ( ) or https:// means you’ve safely connected to the .gov website. Share sensitive information only on official, secure websites.

Practical Cryptanalysis of k-ary C*

Published

Author(s)

Daniel C. 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 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 CryptoChallenge 11 by constructing and solving linear systems of moderate size in a few minutes.
Citation
Cryptology ePrint Archive
Volume
2019

Keywords

Multivariate Cryptography, k-ary C*, differential attack

Citation

Smith-Tone, D. (2019), Practical Cryptanalysis of k-ary C*, Cryptology ePrint Archive, [online], https://tsapps.nist.gov/publication/get_pdf.cfm?pub_id=928519, https://eprint.iacr.org/2019/841 (Accessed December 13, 2024)

Issues

If you have any questions about this publication or are having problems accessing it, please contact reflib@nist.gov.

Created July 18, 2019, Updated July 29, 2019