Zero Knowledge Identity Proofs

Dimitrios.Petropoulos at Dimitrios.Petropoulos at
Tue Jun 26 05:45:17 EDT 2001

Interestingly enough, I don't think this is the case because the objective is to prevent Alice from acting on  Dave's challenges. The confusion may also have arisen because of my use of terms. In this email I'll use 'signing' to mean creation of proof of origin (and classic digital signature algorithms like RSA will suffice). When an entity is trying to prove their identity I'll refer to it as 'acting on' or 'transforming' a challenge. I'll try to clarify:

Alice does not need to 'sign' any challenge since she is the 'prover', i.e. the entity that needs to prove the truthfulness and genuineness of her identity to Bob, who is the 'verifier' and therefore the entity producing the challenges. In the course of proving her identity to Bob using a zero knowledge proof of identity, Alice will accept a number of challenges from Bob (the number of which Bob has to decide depending on his perception of risk; each iteration reduces the likelihood of successful impersonation by half), perform some transformations and return the result to Bob who will verify the transformations.

In this scheme, Alice can fall victim to Bob and Carol working together to defraud both Alice and Dave (the Mafia Fraud example), whereby Carol masquerades as Alice to Dave and relays Dave's challenges -through Bob- to Alice, who will perform the transformations believing she is proving her identity to Bob (when in fact she is proving it to Dave).

Digital signatures (e.g. RSA) on the challenge vectors (along with sensible additional information like prover & verifier identities, timestamps/nonces, etc. to prevent other attacks on the message semantics) would prevent the Mafia Fraud attack since -in this example- Alice would only perform the protocol run if the challenge vector is signed by Bob, whereas Dave will send challenge vectors carrying his signature to Carol (which can no longer relay them to Alice).

I cannot see why Alice would have to transform both the challenge and the signature on it (this, incidentally, would mean that you cannot use signatures with message recovery). Apologies if there's something in Marc's email that I have misunderstood; grateful if I could have it pointed out to me.

Dimitrios Petropoulos

> I'm not hep to the identification scheme literature, but I'll just a note
> that in Dimitrios's scheme, Alice can't just sign the challenge, but must
> also include Dave's signature in her signature.  That is, Alice must sign all
> of {S_dave(challenge), challenge}, not just the challenge by itself.  And
> Dave has to verify that both the challenge and his signature were signed by
> Alice.  Otherwise, Bob could just masquerade Dave's challenge.
>         Marc
> Dimitrios.Petropoulos at wrote:
> >
> > I think this is a case for additional protective mechanisms to extend the
> > protocol semantics (there is nothing in the protocol prohibiting the
> > verifier to perform a verification on behalf of a third party, which is
> > the vulnerability exploited in the Mafia Fraud attack). This
> > 'challenge-relay' can easily be defeated if the verifier (in the Mafia
> > Fraud case that's Bob and Dave) is required to digitally sign their
> > challenges. If challenges are signed then Alice will only proceed with
> > the rest of the protocol run if the challenge indeed comes from Bob;
> > Carol can still pass Dave's challenges to Bob but Alice will refuse to
> > perform the protocol run having noticed that the challenges do not come
> > from Bob. The optimised versions of the Feige-Fiat-Shamir and Guillou-
> > Quisquater protocols make signing easier since they employ a vector of
> > challenges to perform multiple accreditations- in order to avoid
> > multiple messages.
> >
> > Regards,
> > Dimitrios Petropoulos
> ---------------------------------------------------------------------
> The Cryptography Mailing List
> Unsubscribe by sending "unsubscribe cryptography" to
> majordomo at

        Visit our Internet site at

Any views expressed in this message are those of  the  individual
sender,  except  where  the sender specifically states them to be
the views of Reuters Ltd.

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

More information about the cryptography mailing list