How to Build Pseudorandom Functions from Public Random Permutations
| Autor: | Yu Long Chen, Eran Lambooij, Bart Mennink |
|---|---|
| Rok vydání: | 2019 |
| Předmět: |
Discrete mathematics
Pseudorandom number generator business.industry Computer science Cryptography 0102 computer and information sciences 02 engineering and technology State (functional analysis) Function (mathematics) Encryption 01 natural sciences Pseudorandom function family Permutation 010201 computation theory & mathematics 0202 electrical engineering electronic engineering information engineering 020201 artificial intelligence & image processing business Block cipher |
| Zdroj: | Advances in Cryptology – CRYPTO 2019 ISBN: 9783030269470 CRYPTO (1) |
| DOI: | 10.1007/978-3-030-26948-7_10 |
| Popis: | Pseudorandom functions are traditionally built upon block ciphers, but with the trend of permutation based cryptography, it is a natural question to investigate the design of pseudorandom functions from random permutations. We present a generic study of how to build beyond birthday bound secure pseudorandom functions from public random permutations. We first show that a pseudorandom function based on a single permutation call cannot be secure beyond the \(2^{n/2}\) birthday bound, where n is the state size of the function. We next consider the Sum of Even-Mansour (SoEM) construction, that instantiates the sum of permutations with the Even-Mansour construction. We prove that SoEM achieves tight \(2n{/}3\)-bit security if it is constructed from two independent permutations and two randomly drawn keys. We also demonstrate a birthday bound attack if either the permutations or the keys are identical. Finally, we present the Sum of Key Alternating Ciphers (SoKAC) construction, a translation of Encrypted Davies-Meyer Dual to a public permutation based setting, and show that SoKAC achieves tight \(2n{/}3\)-bit security even when a single key is used. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|