Technical Report CS0698

TR#:CS0698
Class:CS
Title: A CONSTRUCTION OF A CIPHER FROM A SINGLE PSEUDORANDOM PERMUTATION
Authors: S. Even and Y. Mansour
PDF - RevisedCS0698.revised.pdf
Abstract: Shannon defined a random cipher as a collection of randomly chosen permutations, one for each value of the key. We suggest a scheme for a block cipher which uses only one randomly chosen permutation, $F$. The key, consisting of two blocks, $K_1$ and $K_2$, is used in the following way: The message block is XORed with $K_1$ before applying $F$, and the outcome is XORed with $K_2$ to produce the cryptogram block. This removes the need to store, or generate a multitude of permutations. Although the resulting cipher is not random, we claim that it is secure. First, it is shown that if $F$ is chosen randomly then, with high probability the scheme is secure against any polynomial-time algorithmic attack. Next, it is shown that if $F$ is chosen pseudorandomly, the system remains secure against oracle-type attacks. The scheme may lead to a system more efficient than systems such as the DES and its siblings, since the designer has to worry about one thing only: How to implement one pseudorandomly chosen permutation. This may be easier than getting one for each key.
CopyrightThe above paper is copyright by the Technion, Author(s), or others. Please contact the author(s) for more information

Remark: Any link to this technical report should be to this page (http://www.cs.technion.ac.il/users/wwwb/cgi-bin/tr-info.cgi/1991/CS/CS0698), rather than to the URL of the PDF files directly. The latter URLs may change without notice.

To the list of the CS technical reports of 1991
To the main CS technical reports page

Computer science department, Technion
admin