1
$\begingroup$

I am learning the simulation-based security proofs in MPC, and have read the great tutorial "How to simulate it" by Prof. Lindell.

Here's my understanding about why we need to "extract adversary's input" in writing simulation proofs against malicious adversaries (please correct if I am wrong): For a malicious adversary, it is not guaranteed to follow the protocol, so "a simulator is able to extract A's input" means "as long as the protocol does not abort, we could be sure that A must be inputting something valid (i.e. following the protocol) ". So the "extracting input" step is crucial for writing proofs against malicious adversary. If we can extract A's input, everything left are just the same as the semihonest proofs.

The example of changing semihonest OT into malicious OT with ZKP meets my above understandings, because ZKP could prove the prover's correct behaviors, and could extract the prover's input. However, when reading other proofs, I found it hard to understand why could random oracles extract inputs as well.

E.g. Proof of Theorem 1 in [1] says "SIMs builds two tables T1 = (x, φ) and T2 = ((h, t), ψ) to answer the hash queries to H1 and H2 respectively". How could SIMs know the inputs to H1 and H2? If SIMs could do that, does it mean we can extract inputs simply by asking the parties to hash their inputs, and any semihonest-secure protocols become malicious-secure ones by simply introducing an extra hash-input step (which is obviously not true) ?

I know there must be some basic mistakes in my understandings, and would be very grateful if someone could point it out. Thanks.

[1] Jarecki S, Liu X. Fast secure computation of set intersection.

$\endgroup$
0
$\begingroup$

This is exactly what makes the random oracle model an idealized model. If $H$ is a hash function in the standard model, an adversary can run $H$ "in its head", and this will be inscrutable to a simulator. But in the random oracle model, the only way to evaluate the hash function $H$ is through a well-defined oracle interface. The simulator gets to play the role of this interface! -- just like it is allowed to play the role of the honest parties.

If SIMs could do that, does it mean we can extract inputs simply by asking the parties to hash their inputs, and any semihonest-secure protocols become malicious-secure ones by simply introducing an extra hash-input step (which is obviously not true) ?

If the protocol instructs parties to hash some information, and that adversary does it, then, yes, the simulator (in the random oracle model) will be able to observe that call to the hash. But an adversary can just not call the hash function at all (and just send junk messages in the protocol), or hash the "wrong" value instead, or hash a billion "decoy" values. The simulator will need to do something sensible in all of these cases!

In your hypothetical example, the protocol would need to contain some method for the other participants to "check" that the hash was called. I'm not sure what this would look like in your scenario. But it would have to give the simulator some advantage: after seeing how the adversary acted in the rest of the protocol, along with seeing the list of all random-oracle queries made by the adversary, hopefully the simulator can deduce which query was the "real" one.

I think you will find that the examples in "How to Simulate It" will have this property. You can't just ask an adversary to query $H$ on their private input, but then do nothing with the result. They have to interact with $H$ in a way that gives the simulator an advantage, when the simulator is allowed to observe all queries to $H$ and also observe the rest of the protocol messages too. I'm sure you will see that in "How to Simulate It", the simulator will "cross-reference" these tables $T_1$ and $T_2$ with protocol messages sent by the adversary, in order to extract.

$\endgroup$
1
  • $\begingroup$ Thanks ! See if I get it right : SIM could "extract A's input" means the protocol is able to force A to behave honestly during the full protocol. Since A behave honestly, it must has a valid input. So once we extract it, the rest of proof is just the same with the semihonest version. $\endgroup$
    – vince.h
    Apr 28 at 11:34

Your Answer

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

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