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.