Cryptography Reference
In-Depth Information
B.2.2. Constructions
Both message-authentication and signature schemes can be constructed based on the
existence of one-way functions.
B.2.2.1. Message Authentication
Message-authentication schemes can be constructed using pseudorandom functions
[103]: To authenticate the message x with respect to key s , one generates the tag f s ( x ),
where f s is the pseudorandom function associated with s . Verification is done in the
same (analogous) way. However, as noted in [15], extensive use of pseudorandom
functions would seem to be overkill for achieving message authentication, and more
efficient schemes can be obtained based on other cryptographic primitives. We mention
two approaches:
1. fingerprinting the message using a scheme that is secure against forgery provided that
the adversary does not have access to the scheme's outcome (e.g., using Universal
Hashing [49]), and “ hiding ” the result using a non-malleable scheme (e.g., a private-key
encryption or a pseudorandom function). (Non-malleability is not required in certain
cases [209].)
2. hashing the message using a collision-free scheme [58, 59] and authenticating the result
using a MAC that operates on (short) fixed-length strings [15].
B.2.2.2. Signature Schemes
Three central paradigms in the construction of signature schemes are the “refreshing”
of the “effective” signing key, the use of an “authentication tree,” and the “hashing
paradigm.”
The Refreshing Paradigm [125]. To demonstrate this paradigm, suppose we have a
signature scheme that is robust against a “random message attack” (i.e., an attack in
which the adversary obtains signatures only to randomly chosen messages). Further
suppose that we have a one-time signature scheme (i.e., a signature scheme that is secure
against an attack in which the adversary obtains a signature to a single message of its
choice). Then we can obtain a secure signature scheme as follows: When a new message
needs to be signed, we generate a new random signing key for the one-time signature
scheme, use it to sign the message, and sign the corresponding (one-time) verification
key using the fixed signing key of the main signature scheme 7 (which is robust against
a “random message attack”) [71]. We note that one-time signature schemes (as utilized
here) are easy to construct (e.g., [161]).
The Authentication-Tree Paradigm [160, 125]. To demonstrate this paradigm, we
show how to construct a general signature scheme using only a one-time signature
scheme (alas, one where a 2 n -bit string can be signed with respect to an n -bit-long
7 Alternatively, one can generate the one-time key pair and the signature to its verification key ahead of time,
leading to an “off-line/on-line” signature scheme [71].
Search WWH ::




Custom Search