×

Pseudorandomness of Camellia-like scheme. (English) Zbl 1190.94032

Summary: M. Luby and C. Rackoff [SIAM J. Comput. 17, 373–386 (1988; Zbl 0644.94018)] idealized DES by replacing each round function with one large random function. In this paper, the author idealizes Camellia [K. Aoki et al., Lect. Notes Comput. Sci. 2012, 39–56 (2001; Zbl 1037.94540)] (a 128-bit block cipher) by replacing each S-box with one small random function, which is named Camellia-like scheme. It is then proved that five-round Camellia-like scheme is pseudorandom and eight-round Camellia-like scheme is super-pseudorandom for adaptive adversaries. Further the paper considers more efficient construction of Camellia-like scheme, and discusses how to construct pseudorandom Camellia-like scheme from less random functions.

MSC:

94A60 Cryptography

Software:

Camellia
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Luby M, Rackoff C. How to construct pseudorandom permutations from pseudorandom functions. SIAM Journal on Computing, 1988, 17(2): 373–386. (A preliminary version including other results appeared in Proceedings of the 18th ACM Symposium on Theory of Computing, 1986, pp.356–363). · Zbl 0644.94018
[2] Schnorr C P. On the construction of random number generators and random function generators. In Advances in Cryptology–Eurocrypt’88, LNCS 330, Springer-Verlag, Davos, Switzerland, May 1988, pp.225–232. · Zbl 0663.65004
[3] Rueppel R A. On the security of Schnorr’s pseudorandom generator. In Advances in Cryptology–Eurocrypt’89, LNCS 434, Springer-Verlag, Houthalen, Belgium, April 1989, pp.423–428.
[4] Zheng Y, Matsumoto T, Imai H. Impossibility and optimality results on constructing pseudorandom permutations. In Advances in Cryptology-Eurocrypt’89, LNCS 434, Springer-Verlag, Houthalen, Belgium, April 1989, pp.412–422. · Zbl 0733.65004
[5] Zheng Y, Matsumoto T, Imai H. On the construction of block ciphers provably secure and not relying on any unproved hypotheses. In Advances in Cryptology–Crypto’89, LNCS 435, Springer-Verlag, New York, USA, Aug. 1989, pp.461–480. · Zbl 0722.94020
[6] Pieprzyk J. How to construct pseudorandom permutations from single pseudorandom functions. In Advances in Cryptology–Eurocrypt’90, LNCS 473, Springer-Verlag, Aarhus, Denmark, May 1990, pp.140–150. · Zbl 0779.65005
[7] Patarin J. New results on pseudorandom permutation generators based on the DES Scheme. In Advances in Cryptology–Crypto’91, LNCS 547, Springer-Verlag, Brighton, UK, April 1991, pp.72–77. · Zbl 0925.94085
[8] Sadeghiyan B, Pieprzyk J. On the necessary and sufficient conditions for the construction of super pseudorandom permutations. In Advances in Cryptology–Asiacrypt’91, LNCS 739, Springer-Verlag, Sydney, Australia, Dec. 1991, pp.117–123. · Zbl 0808.94025
[9] Pieprzyk J, Sadeghiyan B. Optimal Perfect Randomizers. In Advances in Cryptology–Asiacrypt’91, LNCS 739, Springer-Verlag, Sydney, Australia, Dec. 1991, pp.225–236. · Zbl 0808.94026
[10] Maurer U M. A simplified and generalized treatment of Luby-Rackoff pseudorandom permutation generators. In Advances in Cryptology–Eurocrypt’92, LNCS 658, Springer-Verlag, Balatonfüred, Hungary, May 1992, pp.239–255. · Zbl 0797.65002
[11] Patarin J. How to construct pseudorandom permutations from a single pseudorandom function. In Advances in Cryptology–Eurocrypt’92, LNCS 658, Springer-Verlag, Balatonfüred, Hungary, May 1992, pp.256–266. · Zbl 0801.65006
[12] Even S, Mansour Y. A construction of a cipher from a single pseudorandom permutation. In Advances in Cryptology–Asiacrypt’91, LNCS 739, Springer-Verlag, Sydney, Australia, Dec. 1991, pp.181–193. · Zbl 1053.94552
[13] Lucks S. Faster Luby-Rackoff ciphers. In Fast Software Encryption–FSE’96, LNCS 1039, Springer-Verlag, Haifa, Israel, Jan. 1996, pp.189–203. · Zbl 1373.94923
[14] Patel S, Ramzan Z, Sundaram G. Towards making Luby-Rackoff ciphers optimal and practical. In Fast Software Encryption–FSE’99, LNCS 1636, Springer-Verlag, Rome, Italy, Mar. 1999, pp.171–185. · Zbl 0942.94023
[15] Naor M, Reingold O. On the construction of pseudorandom permutations Luby-Rackoff revisited. Journal of Cryptology, 1999, 12(1): 29–66. · Zbl 0936.94010 · doi:10.1007/PL00003817
[16] Naor M, Reingold O. From unpredictability to indistinguishability: A simple construction of pseudo-random functions from MACs. In Advances in Cryptology–Crypto’98, LNCS 1462, Springer-Verlag, Santa Barbara, CA, USA, Aug. 1998, pp.267–282. · Zbl 0931.94047
[17] Vaudenay S. Provable security for block ciphers by decorrelation. In Proc. Symposium on Theoretical Aspects of Computer Science’98, LNCS 1373, Springer-Verlag, Paris, France, Mar. 1998, pp.249–275. · Zbl 0921.94012
[18] Iwata T, Kurosawa K. On the pseudorandomness of the AES finalists–RC6 and Serpent. In Fast Software Encryption–FSE 2000, LNCS 1978, Springer-Verlag, New York, USA, April 2000, pp.231–243. · Zbl 0994.68630
[19] Iwata T, Yoshino T, Yuasa T, Kurosawa K. Round security and super-pseudorandomness of MISTY type structure. In Fast Software Encryption–FSE 2001, LNCS 2355, Springer-Verlag, Yokohama, Japan, April 2001, pp.233–247. · Zbl 1073.68632
[20] Ramzan Z, Reyzin L. On the round security of symmetric-key cryptographic primitives. In Advances in Cryptology–Crypto 2000, LNCS 1880, Springer-Verlag, Santa Barbara, CA, USA, Aug. 2000, pp.376–393. · Zbl 0995.94534
[21] Gilbert H, Minier M. New results on the pseudorandomness of some block cipher constructions. In Fast Software Encryption–FSE 2001, LNCS 2355, Springer-Verlag, Yokohama, Japan, April 2001, pp.248–266. · Zbl 1073.68628
[22] Moriai S, Vaudenay S. On the pseudorandomness of top-level schemes of block ciphers. In Advances in Cryptology–Asiacrypt 2000, LNCS 1876, Berlin: Springer-Verlag, Kyoto, Japan, Dec. 2000, pp.289–302. · Zbl 0966.94013
[23] Aoki K, Ichikawa T, Kanda M et al. Specification of Camellia–A 128-bit block cipher. In Selected Areas in Cryptography–SAC 2000, LNCS 2012, Springer-Verlag, Waterloo, Ontario, Canada, August 2000, pp.183–191.
[24] http://www.cryptonessie.org
[25] Wenling Wu, Dengguo Feng, Hua Chen. Collision attack and pseudorandomness of reduced-round Camellia. In Selected Areas in Cryptography–SAC 2004, LNCS 3357, Berlin: Springer-Verlag, Waterloo, Ontario, Canada, August 2004, pp.256–270. · Zbl 1117.94339
[26] Vaudenay S. On provable security of conventional cryptography. In Information Security and Cryptography–ICISC’99, LNCS 1787, Berlin: Springer-Verlag, Seoul, Korea, Dec. 1999, pp.1–16. · Zbl 1032.94528
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.