A Short Proof of the PRP/PRF Switching Lemma

Donghoon Chang; Mridul Nandi

Paper 2008/078 Original: eprint.iacr.org/2008/078 ↗

A Short Proof of the PRP/PRF Switching Lemma

Donghoon Chang

Mridul Nandi

Abstract

In Eurocrypt 2006, Bellare and Rogaway \cite{BeRo06} gave a proof of the PRP/PRF switching Lemma using their game-based proof technique. In the appendix of the same paper, they also gave an proof without games. In this paper, we give another proof of the switching lemma, which is simple and mathematically-clear and easy to uderstand. Our proof is based on \textit{the strong interpolation theorem}.

Metadata

Available format(s): PDF
Category: Secret-key cryptography
Publication info: Preprint.
History: 2008-02-27: last updated; 2008-02-27: published
Short URL: https://ia.cr/2008/078
License: https://creativecommons.org/licenses/by/4.0/

BibTeX

@misc{cryptoeprint:2008/078,
      author = {Donghoon Chang and Mridul Nandi},
      title = {A Short Proof of the PRP/PRF Switching Lemma},
      howpublished = {Cryptology {ePrint} Archive, Paper 2008/078},
      year = {2008},
      url = {https://eprint.iacr.org/2008/078}
}