3
$\begingroup$

Definition 1 on Page 7 of “An Efficient System for Non-transferable Anonymous Credentials with Optional Anonymity Revocation” by Camenisch and Lysyanskaya, uses the term “simulator” in defining the security of a cryptographic credential system, which I'm finding a little confusing.

In particular, the sentence says:

CSS is secure if there exists a simulator S (ideal-world adversary [defined above as a probabilistic polynomial time machine]) such that the following holds: […]

What does “simulator” in a cryptographic credential system's definition of security?
Also, what does it mean for a probabilistic machine to be "interactive"?

| improve this question | |
$\endgroup$
3
$\begingroup$

"simulator":

That's a definition of security in a model that is related to but weaker than the universal composability framework (thanks to Yehuda Lindell for making that clear and you can look at the paper in his comment). You could also look up the wiki link and I think there are also several question on this site.

As @Yehuda Lindell mentions in a comment, if you are not familiar with the concept of a "simulator" at all so far it is better to look at definitions of secure (multiparty) computation or the zero-knowledge property of interactive proofs.

"interactive":

Think of two probabilistic polynomial time Turing machines (Turing machine with additional random tape) who have local input and output tapes (as usual), but also additional tapes to write input to the other machine and receive input from it. Both machines after interacting halt with local outputs.

For instance, a machine $A$ may run on local input a secret key and machine $B$ on the respective public key and a message. After interaction $B$ halts with a signature for the message and $A$ with no local output (that would be the signing procedure of a blind signature scheme, which you probably know or are familiar with when studying anonymous credentials).

| improve this answer | |
$\endgroup$
  • $\begingroup$ Actually simulation goes back to earlier stand alone definitions for secure computation. These are easier to understand than universal composability so are a better place to start. $\endgroup$ – Yehuda Lindell Jul 23 '15 at 17:05
  • $\begingroup$ @Yehuda Lindell That's certainly true. But the poster asks for the simulator in context of this security model for anonymous credentials. Thanks you anyway, I will edit it into the question. $\endgroup$ – DrLecter Jul 23 '15 at 17:10
  • $\begingroup$ But that paper doesn't use universal composability... $\endgroup$ – Yehuda Lindell Jul 23 '15 at 18:08
  • $\begingroup$ That's true, but doesnt it come quite close? UC was very fresh back then. But I guess you are the expert :) $\endgroup$ – DrLecter Jul 23 '15 at 18:27
  • $\begingroup$ Actually no. It is much closer to the definition in Canetti 2000 (see eprint.iacr.org/1998/018). This gives security in the "stand-alone model" (where security under sequential composition is guaranteed, but not concurrent). In UC there is an interactive environment which makes a very fundamental difference, both to feasibility and constructions. $\endgroup$ – Yehuda Lindell Jul 23 '15 at 19:01

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.