A Security Analysis of Uniformly-Layered Rainbow - Post-Quantum Cryptography

Cryptography Reference

In-Depth Information

12. Kipnis, A., Patarin, J., Goubin, L.: Unbalanced Oil and Vinegar Sschemes. In:

Stern, J. (ed.) EUROCRYPT 1999. LNCS, vol. 1592, pp. 206-222. Springer,

Heidelberg (1999)

13. Kipnis, A., Shamir, A.: Cryptanalysis of the Oil & Vinegar Signature Scheme.

In: Krawczyk, H. (ed.) CRYPTO 1998. LNCS, vol. 1462, pp. 257-266. Springer,

Heidelberg (1998)

14. Ong, H., Schnorr, C.P., Shamir, A.: An ecient signature scheme based on

quadratic equations. In: Proc. 16th ACM Symp. Theory Comp., pp. 208-216 (1984)

15. Patarin, J.: Cryptanalysis of the Matsumoto and Imai Public Key Scheme of Euro-

crypt 1988. In: Coppersmith, D. (ed.) CRYPTO 1995. LNCS, vol. 963, pp. 248-261.

Springer, Heidelberg (1995)

16. Petzoldt, A., Bulygin, S., Buchmann, J.: Selecting Parameters for the Rainbow

Signature Scheme. In: Sendrier, N. (ed.) PQCrypto 2010. LNCS, vol. 6061, pp.

218-240. Springer, Heidelberg (2010)

17. Petzoldt, A., Bulygin, S., Buchmann, J.: CyclicRainbow - A Multivariate Signa-

ture Scheme with a Partially cyclic Public Key. In: Gong, G., Gupta, K.C. (eds.)

INDOCRYPT 2010. LNCS, vol. 6498, pp. 33-48. Springer, Heidelberg (2010)

18. Pollard, J.M., Schnorr, C.P.: An ecient solution of the congruence x 2 +

ky 2 ≡

(mod n). IEEE Trans. Inf. Theory IT-33, 702-709 (1987)

19. Rai, T.S.: Infinite Grobner bases and Noncommutative Polly Cracker Cryptosys-

tems. PhD Thesis, Virginia Polytechnique Institute and State Univ. (2004)

20. Satoh, T., Araki, K.: On construction of signature scheme over a certain noncom-

mutative ring. IEICE Trans. Fundamentals E80-A, 702-709 (1997)

21. Shamir, A.: Ecient Signature Schemes Based on Birational Permutations. In:

Stinson, D.R. (ed.) CRYPTO 1993. LNCS, vol. 773, pp. 1-12. Springer, Heidelberg

(1994)

22. Uchiyama, S., Ogura, N.: Cryptanalysis of the Birational Permutation Signa-

ture Scheme over a Non-commutative Ring. JSIAM Lett.ers 2, 85-88 (2010),

http://eprint.iacr.org/2009/245

23. Yang, B.-Y., Chen, J.-M.: Building Secure Tame-Like Multivariate Public-Key

Cryptosystems: The New TTS. In: Boyd, C., Gonzalez Nieto, J.M. (eds.) ACISP

2005. LNCS, vol. 3574, pp. 518-531. Springer, Heidelberg (2005)

Extension of HS Scheme

To construct HS scheme, we need the condition of a non-commutative ring R

that the realization in matrix algebra of R is closed by a transpose operation.

Hashimoto et al. gave an following example of non-commutative rings satisfying

the above condition except for quaternion algebras and matrix algebras [10] .

Lemma 1 ([10]). Let G be a finite group with an embedding ψ : G

( m, L ) .

If ψ ( G ) is closed by transpose operation, then so is the group algebra R = L [ G ](

→ M

→

( m, L )) .

However, it is dicult to find such G and ψ in general. In this appendix, we

consider that the above condition is loosened. First, we introduce a ring with

involution.