I have been studying several ABE schemes and I understand the security assumptions and the several types of security models used for the security game between the Challenger and the Adversary.

What still confuses me is the security proof which involves an additional entity "The Simulator" which is usually done at the end of the different papers.

My question is what is the concept behind that security proof? What is the aim and what are the rules that guide the process as I need to understand that to apply it to the scheme I am working on.

N/B - If the question needs any additional details I would be glad to provide them or edit if it needs any changes. Also I have not stated any exact papers as its a general concept that applies to all the schemes I have read about and I am not sure yet if there is any difference in how it is done except for the fact that the different schemes are based on different security assumptions.

  • $\begingroup$ I can probably help you with understanding why simulators are used in cryptographic proofs, but I've never studied ABE and could probably not help with particular proofs about ABE. So is your question related to ABE in particular, or is it just that you saw simulators being used in proofs related to ABE and would like to understand the underlying ideas? Simulators are used in any simulation-based cryptographic proof, which are used in countless primitives and protocols, and not only ABE. $\endgroup$ – Geoffroy Couteau May 11 '16 at 22:32
  • $\begingroup$ Yehuda Lindell wrote an excellent tutorial on the topic, see ePrint 2016/046. $\endgroup$ – user94293 May 12 '16 at 0:08
  • $\begingroup$ @GeoffroyCouteau Reading about ABE was the first time I ran into security proofs using simulators so while my question arose from the ABE papers I have read, I think any information you could provide about simulators in general for cryptographic proofs will help me understand their application in ABE. $\endgroup$ – chisky May 12 '16 at 12:36

Given your answer to my comment, I'll try to give you an intuition about why simulators are used in cryptographic proofs (but as already mentioned, I cannot help much for the particular case of ABE).

Disclaimer: this will be a very (very) informal explanation

Imagin two players, Alice and Bob, performing some cryptographic protocol. Alice has an input $a$, Bob has an input $b$, and both players would like to reveal securely $f(a,b)$ to Alice, for some public function $f$, without revealing anything more. Now, let's say you wish to prove that the protocol is secure for Bob, namely, that Alice cannot learn anything about $b$ by interacting with Bob, except, obviously, for $f(a,b)$. How to show that? Here is the trick: we replace Bob by another entity, which has the two following features:

  • From the viewpoint of Alice, the behavior of this entity is exactly the same as Bob's behavior. In other words, Alice's view when interacting with Bob is indistinguishable from her view when interacting with this entity. We say that this entity simulates Bob, hence we call it a simulator.

  • The entity does not know Bob's input at all. We assume that it does only know the output $f(a,b)$ of the protocol.

Now you can already see how the proof goes: when Alice interacts with Bob, from her viewpoint, she could be interacting with the simulator, because she wouldn't be able to see the difference. But this simulator does not even know $b$, it does only know $f(a,b)$. Therefore, Alice cannot learn anything more than $f(a,b)$ from Bob, because if she could, she would be able to tell that she does not play with the simulator (who only knows $f(a,b)$), which she cannot do, according to our first feature.

So, in general, the proof will consist in describing such a simulator, and then showing step by step that its behavior cannot be distinguished from Bob's behavior.

Let us look at a toy example. As you are talking about ABE, which are already quite complex primitive, I assume that you might have already heard of simpler (but still far from trivial) primitives, such as additively homomorphic encryption. But in short, an additively homomorphic encryption scheme $E$ allows you to compute sum and external products inside ciphertexts: from $x,y,E(a),E(b)$, one can compute $E(ax+by)$. Moreover, we say that it is semantically secure, informally, if given $E(x), a, b$, where $x \in \{a,b\}$, no player (without the secret key) can tell whether $x=a$ or $x=b$. Consider the following protocol:

  • Alice's input: $x,y$.

  • Bob's input: $a,b$.

  • Output: Bob learns $ax+by$, Alice learns nothing.

  • Protocol: Bob sends $E(a),E(b)$, where $E$ is an additively homomorphic encryption scheme for which he knows the secret key. Alice homomorphically compute $E(ax+by)$ and sends this ciphertext back; Bob decrypts it to get $ax+by$.

Let us now show that this protocol is secure for Bob, by showing that Alice learns nothing. We replace Bob by the following simulator: the simulator knows absolutely nothing, pick two random values $a',b'$ and send $E(a'),E(b')$ instead of $E(a),E(b)$ (and does nothing afterward). From the viewpoint of Alice, this is indistinguishable from Bob's behavior, because of the semantic security of the scheme. As this simulator does not even know $a,b$, this shows that Alice cannot learn anything from the protocol.

In this particular, oversimplified case, there are probably more straightforward ways to argue the security. But in more general cases, simulators quickly become unavoidable. Let me try to explain why:

If you want to perform some task securely with a protocol, you can list all the security requirements that you want for this task, and try to prove that your protocol satisfies these requirements. But what if there are requirements that you forgot? Things you did not think of? To avoid this, there is a better solution: describe the task that you want to perform as an ideal functionality For example, for the previous toy example, this could be the following description:

  • Alice and Bob communicate with the functionality via perfectly secure authenticated channels.
  • When receiving $(a,b)$ from Bob and $(x,y)$ from Alice, the functionality computes $ax+by$ and sends it to Bob (again, via a secure channel)
  • The functionality ignores any input which does not have the correct form.

Now, take your protocol, and consider an adversary against this protocol. To show that this protocol is as secure as the ideal functionality that you defined, you will proceed as follows: the adversary will interact with a simulator, which will play the role of an interface between this adversary and the ideal functionality. In other words, the adversary plays the real protocol, but not with an honest player: he plays it with a simulator. This simulator does not know the inputs of the honest players, but can interact with the ideal functionality, playing the role of the adversary. In a way, here is what happen: the simulator tricks the adversary into thinking that he plays the real protocol (by behaving in a way which is indistinguishable from that of honest players), while the adversary is in fact playing against the ideal functionality: the simulator interacts on his behavior with the functionality, and plays the protocol using only the answers he got from this functionality.

If you can exhibit such a simulator, then you have shown the security of your protocol, because whatever the adversary does in the real protocol, he could be interacting with a simulator which does only interface it with the functionality, hence can only learn things that he could have learned by directly playing against the ideal functionality. Recall that this functionality is our definition of a secure protocol for the task we have in mind, so by definition, what an adversary can learn by playing with it is at most what we agree to let him know.

In practice, this require some care in the design of the ideal functionality (using session IDs to avoid attacks in which the adversary plays several versions of the protocol and try to learn things by mixing inputs and outputs, etc). This does also not guarantee that your protocol will remain secure if composed with other protocol (this require a stronger model).

I hope this gave you an intuition. If now you want more practical knowledge on how to do cryptographic proofs using simulation, I agree with user94293 that the recent tutorial of professor Lindell on this topic should be an excellent starting point (I have to admit I have not read it yet, but it seems safe to assume that it'll be a good tutorial, given its author).

If you have any question, please don't hesitate. If anyone wants to point out parts of my explanations that are prohibitively informal and should be removed/rewritten, I accept it too :)

  • $\begingroup$ Thanks for the explanation. Currently reading the tutorial that user94293 recommended and trying to understand as its a new concept to me. Will ask any questions that may arise from that and hopefully will have a better idea of how it is used in ABE. $\endgroup$ – chisky May 13 '16 at 13:21
  • $\begingroup$ Why is the goal to send Alice $f(a,b)$ in the example, and not something simpler like just $b$? $\endgroup$ – caveman Jun 11 '16 at 18:59
  • $\begingroup$ It depends of the context. Think for example that $a$ and $b$ could be Alice's and Bob's fortunes, and f could be the greater than functionality. Alice could be willing to know which one of Bob and her is the richest, while Bob would agree to let her know that but would not want to reveal is fortune. Numerous problems with such requirements arise in concrete situations with players who want to perform computation (e.g., statistical analysis) on some data which must remain hidden (e.g. because it could be private information on individuals). $\endgroup$ – Geoffroy Couteau Jun 11 '16 at 20:34
  • $\begingroup$ @GeoffroyCouteau still struggling with the tutorial by professor lindell. I understand the concept of the security proofs and what the aim is. How do I bridge the gap between the general idea and how it is applied in the concept of ABE or even IBE? $\endgroup$ – chisky Jun 14 '16 at 14:39
  • $\begingroup$ As I already said, I never worked on IBE nor ABE. However, I wrote several simulation based proofs, so if there is a particular proof that you've not managed to understand yet, or a statement you are trying to prove, you can send it to me and I'll see if I can help. $\endgroup$ – Geoffroy Couteau Jun 14 '16 at 15:15

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.