Weak Pseudorandomness and Unpredictability
Johan Sjödin
To base the security of practical cryptographic schemes on weakened assumptions (which are hence more likely to hold) and to improve their efficiency are general research goals in cryptography. In this thesis we continue this quest. We focus on the most traditional problems in cryptography, namely that of assuring privacy and authenticity of data in the symmetric setting (where both the sender and the receiver share a secret key).
We study the Feistel-network which is a popular structure underlying many block-ciphers – e.g. DES – where the cipher is constructed from many simpler rounds, each defined by some function. In particular, we investigate the security of the Feistel-network against chosen-plaintext-attack (CPA) distinguishers when the only security guarantee we have for the round functions is that they are secure against non-adaptive chosen-plaintext attacks (nCPA). Thus the round functions have a strictly weaker security guarantee than what we would like to achieve for the whole construction. We show that in the information-theoretic setting, four rounds with nCPA-secure functions are enough and necessary to get a CPA-secure permutation. We also prove that this result unfortunately does not translate into the more practically relevant pseudorandom setting.
Further, we focus on weak pseudorandom functions (WPRFs), defined similarly to pseudorandom functions (PRFs) but where the distinguisher only gets to see the outputs on random inputs (and not on inputs of its choice). We propose a chosen-ciphertext-attack secure encryption scheme, based on any WPRF, that is superior to all previous proposed schemes given in the literature (in terms of key-material and applications of the WPRF). This is achieved by an efficient strengthening of any WPRF to a PRF and by a range-extension method for WPRFs that is optimal within a large and natural class of range extensions (especially all known today).
We also introduce a general paradigm for domain extension of message authentication codes and an essentially optimal extension for practical use.
BibTeX Citation
@phdthesis{Sjo07,
author = {Johan Sjödin},
title = {Weak Pseudorandomness and Unpredictability},
editor = {Ueli Maurer},
booktitle = {ETH Series in Information Security and Cryptography},
volume = 8,
year = 2007,
institution = {D-INFK},
note = {ETH Series in Information Security and Cryptography, vol. 8, Hartung-Gorre Verlag, ISBN 3-86628-088-2},
school = {{ETH Zurich}},
publisher = {Hartung-Gorre Verlag},
}