Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

In the security proof of Brent Waters's paper Efficient Identity-Based Encryption Without Random Oracles, he uses a novel “artificial abort” step on page 6.

At this point the simulator is still unable to use the output from the adversary. An adversary’s probability of success could be correlated with the probability that the simulator needs to abort. This stems from the fact that two different sets of $q$ private key queries may cause the simulator to abort with different probabilities.

What is the purpose of this step? Also, I am confused by the first sentence above. What goes wrong if I just use the output from the adversary without this artificial abort step?

share|improve this question
add comment

1 Answer 1

up vote 1 down vote accepted

The problem that arises in the security proof is that the adversary who may win the real game with some probability may however cause the simulation to nearly always abort (by issuing a private key query that requires the simulation to abort) and the probability of an abort may be different for different sets of private key queries.

So, the problem is that the reduction may not be able to use the adversary as the simulation may arbitrarily fail (the success probability of the reduction is conditioned on the adversary not causing an abort) and thus the proof does not go trough. The problem is not to "just use the output", the problem is that you would not be able to get the security proof done without any additional measures.

Now, if the upper and lower bound on the probability that the adversary causes an abort are closely related, the adversary can be used in the reduction as you know that the simulation will always abort with the same probability and then the proof goes through. Note that this introduces a loss in the tightness of the reduction.

Waters therefore cleverly introduced artificial aborts, which basically means that the reduction at the end of a successful simulation (one that did not abort) estimates the probability of abort for hypothetical simulations with the adversary for the same set of private key queries. The reduction then artificially aborts with some probability related to the probability computed before. This is quite counter intuitive as the reduction after a successful run aborts, but this allows to prove the closeness of lower and upper bound on the probability of abort and makes the reduction work and the proof go trough.

There is a paper from EUROCRYPT 2009 which shows how to eliminate the requirement of artificial aborts and thus complicated security proofs for the Waters scheme.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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