Cryptography Reference
In-Depth Information
may be secure if the message is “randomized” before RSA (or the other
schemes) is applied.
6.2
Constructions
Secure
message authentication schemes
can be constructed using
pseudorandom functions (68). Specifically, the key-generation algo-
rithm consists of selecting a seed
s
n
∈{
0
,
1
}
for such a function,
n
, and the (only valid) tag of message
x
with
respect to the key
s
is
f
s
(
x
). As in the case of our private-key encryp-
tion scheme, the proof of security of the current message authentication
scheme consists of two steps:
}
∗
→{
denoted
f
s
:
{
0
,
1
0
,
1
}
(1) Prove that an idealized version of the scheme, in which one
uses a uniformly selected function
F
:
n
,rather
than the pseudorandom function
f
s
, is secure (i.e., unforge-
able).
(2) Conclude that the real scheme (as presented above) is secure
(because, otherwise one could distinguish a pseudorandom
function from a truly random one).
}
∗
→{
{
0
,
1
0
,
1
}
Note that the aforementioned message authentication scheme makes
an “extensive use of pseudorandom functions” (i.e., the pseudorandom
function is applied directly to the message, which requires a general-
ized notion of pseudorandom functions (cf. Section 3.3)). More ecient
schemes may be obtained either based on a more restricted use of a
pseudorandom function (cf., e.g., (17)) or based on other cryptographic
primitives (cf., e.g., (93)).
Constructing secure
signature schemes
seems more dicult than
constructing message authentication schemes. Nevertheless, secure sig-
nature schemes can be constructed based on any one-way function.
Furthermore:
Theorem 6.2.
((103; 114), see (67, Sec. 6.4)):
The following three
conditions are equivalent.
