[tahoe-dev] Terminology niggling [Was: Storing a small file leads to a weird read capability]

[Jack Lloyd]

On Wed, Apr 07, 2010 at 11:57:06AM -0700, Brian Warner wrote:

> The confidentiality of a CHK file can be evaluated by assuming the
> attacker gets the ciphertext (but not the filecap), and access to some
> sort of confirmation mechanism (known as an "oracle" in the
> cryptographic literature). If they're trying to guess your login
> password, then the oracle is to try to use the password to actually log
> in. If the encrypted file contains a secure hash of the plaintext (or
> any error-checking mechanism at all), then the oracle is to try to
> decrypt the file and then check to see if the error-checking codes look
> ok. (in this case the oracle is not perfect: sometimes it will give you
> false positives. I think this is known as a "random oracle", which gives
> you some probability of saying "yes" that is influenced by the accuracy
> of your guess).

I don't think 'random oracle' is the right terminology for
this. Usually (at least in the crypto-theory lit), this means an
oracle which behaves like a random function. For instance a random
oracle might map arbitrary bit strings onto a 256 bit output string:

  f : {0,1}^* -> {0,1}^256

Each time you invoke the oracle, it checks to see if has previously
been invoked with the same input in the past. If so, it outputs
whatever it output before. Otherwise it generates a uniform random 256
bit string and outputs it (and saves it for future reference). In the
'random oracle design methodology', one creates constructions that are
provably secure assuming use of a random oracle, and then substitute a
cryptographic hash function where the random oracle had been assumed.
(So the proofs don't apply directly, but if you assume the hash is
secure than you perhaps have some additional confidence that the
design is not flawed in construction. There are subtleties though, for
instance IIRC a few years ago someone proved that a particular
(carefully chosen) construction was secure if instantiated with a
random oracle but insecure if instantiated with any fixed hash
function.

I think the term for a general oracle function that is not always
correct is a 'probabilistic oracle'.

-Jack