Zero Knowledge Identity Proofs

Marc Branchaud marcnarc at
Tue Jun 26 19:00:26 EDT 2001

Well, I can't be sure that I'm not misunderstanding something either.  For
the most part, I agree with Dimitrios that challenges with proof of origin
are part of the solution to Mafia Fraud attacks.  My main point is that I
don't think simply signing the challenge is enough.

Let me try to restate things symbolically.  Nominally, in the naive case,
Dave would present Alice with a challenge, X, and Alice would transform &
return the challenge: X'.  This, as we know, is vulnerable to the Mafia

What I believe Dimitrios is proposing is for Dave to present both the
challenge and a signature on the challenge: {X, S_dave(X)}.  Then, Alice
would verify that the signature corresponds to the person she thinks she's
talking to, and if so she can return the transformed challenge X'.

I'm essentially contending that Dave needs to verify that Alice did indeed
see the challenge & signature he presented.  Consider Mafia Fraud against the
above scenario.  Dave presents {X, S_dave(X)} to Carol, who forwards it to
Bob.  Now, Bob can re-sign the challenge himself, and present {X, S_bob(X)}
to Alice.  Alice will happily verify that the challenge comes from Bob, and
return X' to Bob, who then passes it to Carol & then on to Dave.   The fraud
is successful, because Dave can't tell that Alice saw Bob's signature on the
challenge and not his own.

So the X' that Alice computes must be a function f(X, S_dave(X)) on both the
challenge and the signature.  (If, in the naive case, X'=S_alice(X), then to
truly prevent the fraud we need X'=S_alice(X,S_dave(X)).)  Now the fraud
fails because Alice would compute X'=f(X, S_bob(X)), and so Dave (not Alice)
would detect the fraud.

So it's not enough for Dave to simply sign the challenge & for Alice to
verify that signature.  Alice must prove to Dave that she saw his signature
and not somebody else's.

BTW, without giving it any thought, I believe this scheme is safe against
replay attacks (because Dave generates a new challenge every time).  Does
anybody have any thoughts about that?


The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to majordomo at

More information about the cryptography mailing list