I am working on the simulation-based proof, where Random Oracle (RO) is used to extract malicious parties' input. In particular, the RO considered in the proof has a small range (whose size is independent of any security parameter and is a constant). Such a small range can result in a non-negligible collision rate.

The proof can be simplified as follows. The malicious $P_1$ has access to RO and queries RO with its (maliciously-chosen) input $x$. Now, the simulator wants to extract $x$ by observing the RO queries that $P_1$ has made. However, given that (probabilistic polynomial-time) $P_1$ can query RO for polynomially many times before the simulator's extraction, there may be several distinct inputs corresponding to the same RO response due to collision. That is, the list of RO queries is long and each possible response may have several pre-images in this list. How can the simulator successfully extract the exact $x$ in this case? Is it reasonable to conclude that RO can be used to extract inputs only if it has a negligible collision rate?


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.