0
$\begingroup$

I'm trying to read through a paper on ring signatures - "How to Leak a Secret" by Rivest, Shamir, Tauman (link: https://link.springer.com/content/pdf/10.1007%2F3-540-45682-1_32.pdf )

In section 3.2 it is said

We assume the existence of a publicly defined symmetric encryption algorithm $E$ such that for any key $k$ of length $l$, the function $E_k$ is a permutation over b-bit strings. Here we use the random (permutation) oracle model which assumes that all the parties have access to an oracle that provides truly random answers to new queries of the form $E_k(x)$ and $E^{−1} _k (y)$, provided only that they are consistent with previous answers and with the requirement that $E_k$ be a permutation

What exactly does this mean? Is $ E_k $ available to (and only to) parties who know the secret key $k$ and does it give random answers to new queries in the same sense as a random oracle, except it's bijective and there's also the inverse oracle? And is this assumption equivalent to the random oracle model? That is, can we construct $E$ given access to a random oracle?

Improve this question
$\endgroup$
2
  • $\begingroup$ It sounds like me like the oracle is available to anybody, and the queries include a value for $k$. I.e., the adversaries don't know the secret key, but they can query for the encryption/decryption of any value under any key of their choice. $\endgroup$
    – Luis Casillas
    Apr 30, 2018 at 23:54
  • $\begingroup$ This is known as the "ideal cipher model" $\endgroup$
    – Mikero
    May 1, 2018 at 5:39

1 Answer 1

Reset to default
1
$\begingroup$

From the middle of p. 561:

Algorithm $A$ accepts the public keys $P_1, P_2, \dots, P_r$ (but not any of the corresponding secret keys) and is given oracle access to $h$, $E$, $E^{-1}$, and to a ring signing oracle. It can work adaptively, querying the oracles at arguments that may depend on previous answers. Eventually, it must produce a valid ring signature on a new message that was not presented to the signing oracle, with a non-negligible probability (over the random answers of the oracles and its own random tape).

Specifically, $A$ is allowed to query $E$ and $E^{-1}$ at any key and any message, with the keys obtained from the oracle for $h$ as stated a little below.

(It doesn't matter that $A$ is allowed to know the bits of the key because presumably the choice of permutation is independent uniform random for each distinct key, so there's no meaningful structure to be had out of the bits of the key.)

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.