Primitives and Schemes for Non-atomic Information Authentication
Goce Jakimoski
Stevens Institute of Technology
Monday, September 25, 2:00PM
Babbio Center, Room 110
Stevens Institute of Technology
Abstract
Information authentication is one of the basic information security
goals, and it addresses the issues of source corroboration and
improper or unauthorized modification of data. More specific, data
integrity is the property that the data has not been changed in an
unauthorized manner since its creation, transmission or storage. Data
origin authentication, or message authentication, is the property
whereby a party can be corroborated as a source of the data.
Usually, message authentication is achieved by appending an
authentication tag or a digital signature to the message. The
authentication tag (resp., digital signature) is computed in such a
way so that only an entity that is in possession of the secret key can
produce it, and it is used by the verifier to determine the
authenticity of the message. During this procedure, the message is
considered to be an atomic object in the following sense. The verifier
needs the complete message in order to check its validity. Presented
with the authentication tag (resp., digital signature) and an
incomplete message, the verifier cannot determine whether the
presented incomplete message is authentic or not. We consider a more
general authentication model, where the verifier is able to check the
validity of incomplete messages. In particular, we analyze the cases
of erasure-tolerant information authentication and stream
authentication.
Our model of erasure-tolerant information authentication assumes that
a limited number of the message ``letters'' can be lost during the
transmission. Nevertheless, the verifier should still be able to
check the authenticity of the received incomplete message. We provide
answers to several fundamental questions in this model (e.g., lower
bounds on the deception probability, distance properties, optimal
constructions, etc.), and we propose some constructions of
erasure-tolerant authentication codes.
Streams of data are bit sequences of a finite, but a priori unknown
length that a sender sends to one or more recipients, and they occur
naturally when on-line processing is required. In this case, the
receiver should be able to verify the authenticity of a prefix of the
stream, that is, the part of the stream that has been received so
far. We provide efficient and proven secure schemes for both unicast
and multicast stream authentication.