On the semantic security of cellular automata based pseudo-random permutation using results from the Luby-Rackoff construction

• Autorzy: Faraoun K. M.

Identyfikatory

DOI

10.1515/umcsinfo-2015-0004

• Języki publikacji: EN

Abstrakty

EN

This paper proposes a semantically secure construction of pseudo-random permutations using second-order reversible cellular automata. We show that the proposed construction is equivalent to the Luby- Racko model if it is built using non-uniform transition rules, and we prove that the construction is strongly secure if an adequate number of iterations is performed. Moreover, a corresponding symmetric block cipher is constructed and analysed experimentally in comparison with popular ciphers. Obtained results approve robustness and ecacy of the construction, while achieved performances overcome those of some existing block ciphers.

Słowa kluczowe

EN

semantic security; reversible cellular automata; block ciphers; cryptography

• Wydawca: Wydawnictwo UMCS
• Czasopismo: Annales Universitatis Mariae Curie-Skłodowska. Sectio AI, Informatica
• Rocznik: 2015
• Tom: Vol. 15, no. 1
• Strony: 21--31
• Opis fizyczny: Bibliogr. 30 poz., rys., tab.

Twórcy

autor

Faraoun K. M.

• Computer science department, Djilalli Liabbes University Sidi Bel Abbés, Algeria

Bibliografia

• [1] Zheng, Yuliang, Matsumoto, Tsutomu, et Imai, Hideki. On the construction of block ciphers provably secure and not relying on any unproved hypotheses. In : Advances in Cryptology-CRYPTO'89 Proceedings. Springer New York, 1990. p. 461-480.
• [2] Mmaurer, Ueli et Pietrzak, Krzysztof. The security of manyround Luby-Rackoff pseudo-random permutations. In : Advances in Cryptology-EUROCRYPT 2003. Springer Berlin Heidelberg, 2003. p. 544- 561.
• [3] Patarin, Jacques. Security of random Feistel schemes with 5 or more rounds. In : Advances in Cryptology- CRYPTO 2004. Springer Berlin Heidelberg, 2004. p. 106-122.
• [4] Luby, Michael et Rackoff, Charles. How to construct pseudorandom permutations from pseudorandom functions. SIAM Journal on Computing, 1988, vol. 17, no 2, p. 373-386.
• [5] Feistel, Horst. Cryptography and computer privacy. Scientific american, 1973, vol. 228, p. 15-23.
• [6] Wolfram, Stephen. Cryptography with cellular automata. In : Advances in Cryptology-CRYPTO'85 Proceedings. Springer Berlin Heidelberg, 1986. p. 429-432.
• [7] Nandi, S., Kar, B. K., et Pal Chaudhuri, P. Theory and applications of cellular automata in cryptography. Computers, IEEE Transactions on, 1994, vol. 43, no 12, p. 1346-1357.
• [8] Kari, Jarkko. Crypto-systems based on reversible cellular automata. Manuscript, August, 1992.
• [9] Zhang, Chang N. et Li, Hua. Reconfigurable pipelined cellular automata array for cryptography. In : Communications, Circuits and Systems and West Sino Expositions, IEEE 2002 International Conference on. IEEE, 2002. p. 1213-1217.
• [10] Seredyński, Marcin, Pienkosz, Krzysztof, et Bouvry, Pascal. Reversible cellular automata based encryption. In : Network and Parallel Computing. Springer Berlin Heidelberg, 2004. p. 411-418.
• [11] Sen, Subhayan, Shaw, Chandrama, Chowdhuri, Dipanwita Roy, et al.Cellular automata based crypto-system (CAC). In : Information and Communications Security. Springer Berlin Heidelberg, 2002. p. 303-314.
• [12] Ray, Abhishek et Das, Debasis. Encryption algorithm for block ciphers based on programmable cellular automata. In : Information Processing and Management. Springer Berlin Heidelberg, 2010. p. 269-275.
• [13] Tripathy, Somanath et Nandi, Sukumar. LCASE: Lightweight Cellular Automata-based Symmetric-key Encryption. IJ Network Security, 2009, vol. 8, no 3, p. 243-252.
• [14] Kumaravel, A. et Meetei, Oinam Nickson. An application of non-uniform cellular automata for efficient cryptography. In : Information & Communication Technologies (ICT), 2013 IEEE Conference on. IEEE, 2013. p. 1200-1205.
• [15] Anghelescu, Petre. Security of telemedical applications over the internet using programmable cellular automata. International Journal of Intelligent Computing Research, IJICR, 2012, vol. 3, no 1/2, p. 245-251.
• [16] Abdo, A. A., Lian, Shiguo, Ismail, I. A., et al. A cryptosystem based on elementary cellular automata. Communications in Nonlinear Science and Numerical Simulation, 2013, vol. 18, no 1, p. 136-147.
• [17] Sung, Jaechul, Hong, Deukjo, et Hong, Seokhie. Cryptanalysis of an involutional block cipher using cellular automata. Information Processing Letters, 2007, vol. 104, no 5, p. 183-185.
• [18] Liu, Jingmei, Cheng, Xiangguo, et Wang, Xinmei. Cryptanalysis of a cellular automata crypto-system. In : Computational Intelligence and Security. Springer Berlin Heidelberg, 2005. p. 49-54.
• [19] Li, Chengqing et Lo, Kwok-Tung. Cryptanalysis of an image encryption scheme using cellular automata substitution and scan. In : Advances in Multimedia Information Processing-PCM 2010. Springer Berlin Heidelberg, 2010. p. 601-610.
• [20] Szaban, Mirosław et Seredyński, Franciszek. Searching for efficient cellular automata based keys applied in symmetric key cryptography. Annales UMCS Sectio AI Informatica, 2015, vol. 7, p. 49-60.
• [21] Faraoun, Kamel Mohamed. A genetic strategy to design cellular automata based block ciphers. Expert Systems with Applications, 2014, vol. 41, no 17, p. 7958-7967.
• [22] Mohamed, Faraoun Kamel. A parallel block-based encryption schema for digital images using reversible cellular automata. Engineering Science and Technology, an International Journal, 2014, vol. 17, no 2, p. 85-94.
• [23] Faraoun, Kamel Mohamed. Fast encryption of RGB color digital images using a tweakable cellular automaton based schema. Optics & Laser Technology, 2014, vol. 64, p. 145-155.
• [24] Katz, Jonathan et Lindell, Yehuda. Introduction to modern cryptography. CRC Press, 2014.
• [25] Cattaneo, Gianpiero, Dennunzio, Alberto, Formenti, Enrico, et al. Non-uniform cellular automata. In: Language and Automata Theory and Applications. Springer Berlin Heidelberg, 2009. p. 302-313.
• [26] Toffoli, Tommaso et Margolus, Norman H. Invertible cellular automata: A review. Physica D: Nonlinear Phenomena, 1990, vol. 45, no 1, p. 229-253.
• [27] Wolfram, Stephen. A new kind of science. Champaign : Wolfram media, pp. 437-440, 2002.
• [28] Cattaneo, Gianpiero, Dennunzio, Alberto, Formenti, Enrico, et al. Non-uniform cellular automata. In : Language and Automata Theory and Applications. Springer Berlin Heidelberg, 2009. p. 302-313.
• [29] Cattaneo, Gianpiero, Dennunzio, Alberto, Formenti, Enrico, et al. Non-uniform cellular automata. In : Language and Automata Theory and Applications. Springer Berlin Heidelberg, 2009. p. 302-313.
• [30] W.Dai, Crypto++ 5.6.0 Benchmarks. http://www.cryptopp.com/benchmarks.html.