Cryptography Reference
In-Depth Information
when the image of the projection is a subspace over an intermediate extension
field of
F
q
. Clearly, in the case
d
=1,
d
+
θ<
2
,and
|
n
−
3
θ
|
>
1,
πk
is a
hyperplane, and thus
S
G
=
F
q
, which is optimal.
7Con lu on
Multivariate public key cryptography has several desirable traits as a potential
candidate for post-quantum security. Unfortunately, a standard metric by which
we can judge the security of a multivariate scheme has yet to be determined.
One consequence of this current status of the field is the similar cryptanalyses
of several promising ideas.
We offer the size of the space of linear maps,
S
G
, illustrating the initial dif-
ferential symmetries of the core map,
f
, as a benchmark for the judgement
of differential security in modern multivariate public key cryptosystems. As evi-
dence of the feasibility and utility of this method as a measurement of differential
security, we measure these spaces for several key players in the evolution of the
recent big-field schemes. In the cases of schemes which have been broken, we
find that these spaces are large, at least as large as the size of the big field. In
the cases of currently considered secure variants, such as the projected SFLASH
scheme, pSFLASH, we find that we can make this space as small as possible.
References
1. Shor, P.W.: Polynomial-time algorithms for prime factorization and discrete loga-
rithms on a quantum computer. SIAM J. Sci. Stat. Comp. 26, 1484 (1997)
2. Chen, A.I.-T., Chen, M.-S., Chen, T.-R., Cheng, C.-M., Ding, J., Kuo, E.L.-H.,
Lee, F.Y.-S., Yang, B.-Y.: SSE Implementation of Multivariate PKCs on Modern
X86 CPUs. In: Clavier, C., Gaj, K. (eds.) CHES 2009. LNCS, vol. 5747, pp. 33-48.
Springer, Heidelberg (2009)
3. Chen, A.I.-T., Chen, C.-H.O., Chen, M.-S., Cheng, C.-M., Yang, B.-Y.: Practical-
Sized Instances of Multivariate PKCs: Rainbow, TTS, and
IC-Derivatives. In:
Buchmann, J., Ding, J. (eds.) PQCrypto 2008. LNCS, vol. 5299, pp. 95-108.
Springer, Heidelberg (2008)
4. Yang, B.-Y., Cheng, C.-M., Chen, B.-R., Chen, J.-M.: Implementing Minimized
Multivariate PKC on Low-Resource Embedded Systems. In: Clark, J.A., Paige,
R.F., Polack, F.A.C., Brooke, P.J. (eds.) SPC 2006. LNCS, vol. 3934, pp. 73-88.
Springer, Heidelberg (2006)
5. Clough, C., Baena, J., Ding, J., Yang, B.-Y., Chen, M.-s.: Square, a New Multi-
variate Encryption Scheme. In: Fischlin, M. (ed.) CT-RSA 2009. LNCS, vol. 5473,
pp. 252-264. Springer, Heidelberg (2009)
6. Baena, J., Clough, C., Ding, J.: Square-Vinegar Signature Scheme. In: Buch-
mann, J., Ding, J. (eds.) PQCrypto 2008. LNCS, vol. 5299, pp. 17-30. Springer,
Heidelberg (2008)
7. 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)
