Information Security and Cryptography Research Group

Non-Expanding, Key-Minimal, Robustly-Perfect, Linear and Bilinear Ciphers

James L. Massey, Ueli Maurer, and Muzhong Wang

Advances in Cryptology — EUROCRYPT '87, Lecture Notes in Computer Science, Springer-Verlag, vol. 304, pp. 237–247, Apr 1987.

The purposes of this paper are: (1) to give appropriate definitions of robustly-perfect ciphers, linear ciphers and bilinear ciphers; (2) to give two general constructions of robustly-perfect bilinear block ciphers that do not expand the plaintext and that have the smallest possible amount of secret key; (3) to give some isolated examples of robustly-perfect linear stream ciphers that use less key than had been earlier conjectured to be necessary; and (4) to suggest some possible useful applications for robustly-perfect linear and bilinear ciphers.

Section 2 introduces the notion of a robustly-perfect block cipher and shows the connection of such ciphers to Latin squares. Linear and bilinear block ciphers are defined in Sections 3 and 4, respectively. Two general constructions of non-expanding, key-minimal robustly-perfect bilinear ciphers are also given in Section 4, and some as-yet-unanswered questions about such ciphers are raised. Section 5 gives a tentative general definition of a linear stream cipher, and exhibits some counterexamples to a conjecture by Massey and Rueppel on the amount of key required in such ciphers. Finally, Section 6 suggests some possible practical applications for robustly-perfect linear and bilinear ciphers and points out some further open questions about such ciphers.

BibTeX Citation

@inproceedings{MaMaWa87,
    author       = {James L. Massey and Ueli Maurer and Muzhong Wang},
    title        = {Non-Expanding, Key-Minimal, Robustly-Perfect, Linear and Bilinear Ciphers},
    booktitle    = {Advances in Cryptology --- EUROCRYPT~'87},
    pages        = 237--247,
    series       = {Lecture Notes in Computer Science},
    volume       = 304,
    year         = 1987,
    month        = 4,
    publisher    = {Springer-Verlag},
}

Files and Links