Cryptography Reference
In-Depth Information
Table 3.
Summary of the complexity of the attacks given in this paper. In both cases,
we measure the number of computations over the corresponding field with
q
being
the size of the ground field,
n
an intermediate extension degree, and
the embedding
degree.
Algorithm
Attack
Complexity
over
(
n
+
)
q
+1
(2
n
+
)
3
Double-Layer Square
Key Recovery
F
q
n
+
+
p
2
3
Square+
Key Recovery
F
q
n
+
to the equivalent of “multi-HFE” [6] does not seem to be a good idea. It was
already established that this variant actually leads to a
weaker
version of the
original odd-HFE. Similarly, we can conclude that Square- is broken, as is MIA-.
Both variations were suggested in [8], the first as “bivariate Square", the other
as Square-. On the other hand, a secure version of Square will most certainly
give rise to a secure version of MIA.
In particular, Square has exactly the same big advantage over odd-HFE that
MIA/C
∗
has over HFE:
Speed
. When it comes to signing/decrypting, both will
outperform the more secure variants by orders of magnitudes. Hence, it seems
to be too early to call the overall game “Square” being over but it seems a fair
guess that some further modifications will be tried. If they will stand the test of
time is a different question altogether.
Acknowledgments.
We want to thank Gottfried Herold (Bochum) for fruitful
discussions and helpful remarks. Furthermore we thank the reviewers for helpful
comments.
The authors were supported by the German Science Foundation (DFG) through
an Emmy Noether grant where the second author is principal investigator. All
authors were in part supported by the European Commission through the IST
Programme under contract
ICT-2007-216676 Ecrypt II
.
References
[1] Akkar, M.-L., Courtois, N.T., Duteuil, R., Goubin, L.: A Fast and Secure Im-
plementation of Sflash. In: Desmedt, Y.G. (ed.) PKC 2003. LNCS, vol. 2567, pp.
267-278. Springer, Heidelberg (2002)
[2] Bettale, L., Faugère, J.-C., Perret, L.: Cryptanalysis of Multivariate and Odd-
Characteristic HFE Variants. In: Catalano, D., Fazio, N., Gennaro, R., Nicolosi,
A. (eds.) PKC 2011. LNCS, vol. 6571, pp. 441-458. Springer, Heidelberg (2011)
[3] Billet, O., Gilbert, H.: Cryptanalysis of Rainbow. In: De Prisco, R., Yung, M.
(eds.) SCN 2006. LNCS, vol. 4116, pp. 336-347. Springer, Heidelberg (2006)
[4] Billet, O., Macario-Rat, G.: Cryptanalysis of the Square Cryptosystems. In:
Matsui, M. (ed.) ASIACRYPT 2009. LNCS, vol. 5912, pp. 451-468. Springer,
Heidelberg (2009)
[5] Buss, J.F., Frandsen, G.S., Shallit, J.O.: The computational complexity of some
problems of linear algebra. Research Series RS-96-33, BRICS, Department of Com-
puter Science, University of Aarhus, pages 39 (September 1996),
http://www.brics.dk/RS/96/33/
