I've been looking at cryptographic protocols that give unconditional security -- I'm interested in some of the possibilities that go beyond what a simple one-time-pad can achieve -- and I'm having difficulty in finding published papers on the subject. Applied Cryptography only describes the classical one-time-pad, noting "a one-time-pad provides no authenticity", and doesn't go any further.
I've found a description of a construction of a MAC giving unconditional integrity: if we have a message M where 0<=M<p (p prime), and a key K=(a,b) where 0<=a,b<p, then we can calculate a MAC m_K(M) = a + bM (mod p). That source suggested sending (M, m_K(M)) as a message which a man in the middle cannot successfully fake (because he can't generate the MAC); it suggested that to get secrecy as well one should have another key k, 0<=k<p, and send (M+k mod p, m_K(M)), which is a one-time-pad encrypted message plus MAC. However, that MAC system misses the possibility that, if we add the constraint b!=0, the message M can be recovered from m_K(M) by the recipient (who knows K). So it's actually possible to have unconditional secrecy and integrity with the key only twice as long as the message, transmitting only m_K(M) = a + bM (mod p), if one can detect a fake message by it being nonsensical. (Any modification to the transmitted m_K(M) will cause the decryption process to generate garbage over which the attacker has no influence, which seems a reasonable definition of unconditional integrity. One can make the chance of a successful spoof arbitrarily small by making the message space arbitrarily sparse -- e.g., require that the message be a multiple of 2^42 -- and so this is more flexible in the level of integrity it can provide than the message-plus-MAC scheme is.) I've not been able to find any paper that describes the use of this algorithm to give unconditional secrecy and integrity at once. Nor have I found any paper describing doing this (as MAC or as secrecy-plus-integrity) in GF(2^n), which makes it convenient to operate on bit strings. This seems so stunningly useful that I'm surprised it's not mentioned in AC. Can anyone point me at references that I'm missing? -zefram --------------------------------------------------------------------- The Cryptography Mailing List Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]
