Non-Expanding, Key-Minimal, Robustly-Perfect, Linear and Bilinear Ciphers
James L. Massey and Ueli Maurer and Muzhong Wang
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.