Cryptology ePrint Archive: Report 2008/078

A Short Proof of the PRP/PRF Switching Lemma

Donghoon Chang and 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}.

Category / Keywords: secret-key cryptography / PRP, PRF, Switching Lemma

Date: received 20 Feb 2008

Contact author: pointchang at gmail com

Available format(s): Postscript (PS) | Compressed Postscript (PS.GZ) | PDF | BibTeX Citation

Version: 20080227:044332 (All versions of this report)

Short URL: ia.cr/2008/078

Discussion forum: Show discussion | Start new discussion