Re: Who's familiar with random oracle model?
From: Thomas Pornin (pornin_at_nerim.net)
Date: 10/27/04
- Next message: Skybuck Flying: "Re: Data Compression Before or After Encryption ?"
- Previous message: Tom St Denis: "Re: Who's familiar with random oracle model?"
- In reply to: sqc_zz: "Who's familiar with random oracle model?"
- Next in thread: Anton Stiglic: "Re: Who's familiar with random oracle model?"
- Messages sorted by: [ date ] [ thread ] [ subject ] [ author ] [ attachment ]
Date: Wed, 27 Oct 2004 14:26:22 +0000 (UTC)
According to sqc_zz <sqc_zz@hotmail-dot-com.no-spam.invalid>:
> I'm learning about it. And may we have a communication? :D
Disclaimer: I am not an expert on the random oracle model. What I
describe in this message is a rough scheme of what I understood
about that model, while talking with people who are such experts.
The "random oracle model" is a framework you may use to prove some
properties on cryptographic algorithms. You use the random oracle
model if you suppose that you have access to a "random oracle". A
"random oracle" is an entity which takes some data as input and
produces some output, with the following characteristics:
-- The output values are contained within a finite space which is
known a priori (e.g., all 256-bit values).
-- When an input is sent to the oracle:
** if the exact same input was sent previously to the oracle, it
returns the exact same answer;
** otherwise, it selects randomly and uniformly an output value in
the output space, and returns it.
A practical random oracle is a hash function, with some conditions
(e.g., all inputs must have the same length).
If you define a protocol which uses a random oracle (i.e., which uses
a hash function in such a way that it may be considered as a random
oracle), then you can establish some security proofs, which are relative
to the number of invocations to the oracle (for instance, you prove that
breaking the system requires to send at least 2^128 distinct requests to
the oracle).
Such a proof is usually deemed "heuristic" because there is no guarantee
that any given hash function, used in any specified way, is actually
a random oracle. There is no proof that a random oracle exists at all
(for that matter, there is no proof that there is such a thing as a hash
function anyway -- usual hash functions such as SHA-1 are just "good
candidates" or "not so bad simulations"). And the proof tends to have
some part of randomness, which means that you will not prove that the
attacker needs "at least 2^N oracle invocations" but something along the
lines of "the attacker needs X oracle invocations where the average
value of X is higher than 2^N".
In that sense, using the random oracle model implies that the proof
is somewhat weaker that a proof which uses a more conventional model.
Nevertheless, the random oracle model is a powerful tool, and a proof in
the random oracle model is much better than no proof at all.
--Thomas Pornin
- Next message: Skybuck Flying: "Re: Data Compression Before or After Encryption ?"
- Previous message: Tom St Denis: "Re: Who's familiar with random oracle model?"
- In reply to: sqc_zz: "Who's familiar with random oracle model?"
- Next in thread: Anton Stiglic: "Re: Who's familiar with random oracle model?"
- Messages sorted by: [ date ] [ thread ] [ subject ] [ author ] [ attachment ]
Relevant Pages
|
