On the Optimal Key Size of the Even-Mansour Cipher in the Random Function Oracle Model

국문 초록 (Abstract)

본 논문은 Even-Mansour 암호에 대해 안전성 약화 없이 키 사이즈를 줄이는 방법에 대해 다룬다. Even과 Mansour는 랜덤 순열 모델에서 랜덤 순열 P와 두 개의 키를 이용하여 평문 M을 암호화하는 기법(C = k₂? P(M ? k₁))을 제안하였다. ASIACRYPT 2004에서 Gentry와 Ramzen은 4 라운드의 Feistel 구조를 이용하여 Even-Mansour 모델의 랜덤 순열을 랜덤 함수로 대치한 새로운 모델을 제안하고 안전성을 증명하였다. 본 논문에서는 Gentry-Ramzen 모델에 필요한 키사이를 반으로 줄이는 방법을 살펴보고 제안한 방법에 대한 안전성을 랜덤 함수 모델에서 증명한다.

다국어 초록 (Multilingual Abstract)

We describe the problem of reducing the key material in the Even-Mansour cipher without security degradation. Even and Mansour proposed a block cipher based on XORing secret key material just prior to and after applying random oracle permutation P such that C = k₂? P(M ? k₁). Recently, Gentry and Ramzan showed that this scheme in the random permutation oracle can be replaced by the four-round Feistel network construction in the random function oracle and also proved that their scheme is super-pseudorandom. In this paper we reduce the key size from 2n to n, which is the optimal key size of Even-Mansour cipher in the random function oracle model and also give almost the same level of security.

목차 (Table of Contents)

• 요약
• ABSTRACT
• Ⅰ. Introduction
• Ⅱ. Notations and Standard Definitions
• Ⅲ. Gentry-Ramzan’s Generic Model vs. Ours
• Ⅳ. Proof of the Main Results
• Ⅴ. Conclusion
• 참고문헌(References)
• 〈著者紹介〉

참고문헌 (Reference)

1 "The Security of Cipher Block Chaining Advances in Cryptology - CRYPTO’94" Springer-Verlag 341-839 358, 1994.

2 "On the Round Security of Symmetric-Key Cryptographic Primitives" 1880 : 376-393, 2000

3 "On the Construction of Pseudorandom Permutations : Luby-Rackoff Revisited," 12 : 29-66, 1999.

4 "Noncryptographic Primitive for Pseudorandom Permutation" 2365 : 149-163, 2004

5 "New Results of Pseudorandom Permutation Generators based on the DES Scheme Advances in Cryptology - CRYPTO’91" Springer-Verlag 301-576 312, 1991.

6 "Luby-Rackoff Ciphers : Why XOR is not Exclusive" 2595 : 271-290, 2002

7 "How to Re-use Round Function in Super-Pseudorandom Permutation" 224-235, 2004

8 "How to Construct Pseudorandom and Super Pseudorandom Permutations from One Single Pseudorandom Function Advances in Cryptology - EUROCRYPT’92" Springer-Verlag 256-658 266, 1992.

9 "How to Construct Pseudorandom Permutations from Pseudorandom Functions" 17 : 373-386, 1988.

10 "Eliminating Random Permutation Oracles in the Even-Mansour Cipher" 32-47, 2004.

11 "A Paradigm for Designing Efficient Protocols First ACM Conference on Computer and Communications Security" 62-73, 1993.

12 "A Construction of a Cipher from a Single Pseudorandom Permutation Journal of Cryptology 1997. Earlier version in ASIACRYPT’91" Springer-Verlag 10 : 151 210-162 739 224, 1991.