theory: unconditional security

[Zefram]

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 majordomo at wasabisystems.com