Chaum's credentials (technical question)

-----BEGIN PGP SIGNED MESSAGE-----

In response to the recent discussions about identity, pseudonyms,
"is-a-person" credentials, etc., I've been studying Chaum's paper from
Auscrypt 90, "Showing Credentials without Identification; Transferring
Signatures between Unconditionally Unlinkable Pseudonyms."  This is quite
a dense and rather cryptic paper which requires careful reading.  It
doesn't help that the references got left off when the paper was printed.
There are also quite a few obvious misprints in some of the printed
formulas.

I am trying to understand one particular passage, on page 258.  Chaum
uses the idea of a credential as an RSA signature on a pseudonym, where
the pseudonym is a number Px.  The RSA modulus has, in this case, two
exponents e1 and e2 which mean different things.  (Say, e1 means "good
credit risk" and e2 means "good driving record".)  The corresponding
private exponents are d1 and d2.  If a person has these two credentials
that means that he has the two numbers Px^d1 and Px^d2, from the
credentialling organization.  These RSA signatures prove that he actually
has the characteristics described in the credential.

Now, I am having a problem with Chaum's math.  This is a little technical
but I know we have some people on the list who know some number theory.
Here is what Chaum says:

   "Suppose an organization X were to require that you have each of two
   credentials, say both that with public exponents e1 and e2.  You could
   send X separatley Px^d1 and Px^d2.  It is also possible for you to use
   the two credentials to form the single credential Px^(d1*d2), which
   will be called their AND....  To create the AND, you: set g to the
   multiplicative inverse of d1 modulo d2; set h to the remainder after
   dividing g*d1-1 by d2; and computing
   (Px^d1)^g * (Px^d2)^(-h) = Px^(d1*d2)."

It would be really nice if this AND credential could be created like this,
because it might be applicable to digital cash.  Instead of having to go
through the complicated spending transaction for each piece of cash, you
might be able to combine all the pieces of cash into one, and just spend
that.  It would be more compact.

But Chaum's math doesn't work.  First of all, he says "you" should set g
to the inverse of d1 modulo d2.  But this seems to presume knowledge of
d1 and d2.  Yet "you" don't know these things; these are the secret
exponents of the signing agency.  So is Chaum actually talking here about
something the signing agency does?  It didn't sound that way from the
context.

If the signing agency wants to compute Px^(d1*d2), given Px^d1 and Px^d2,
it can do so easily enough; simply take Px^d1 to the d2 power.  You don't
need to go through this rigamarole with g and h.  So that interpretation
doesn't make much sense either.

The other possibility I thought of is that he meant that the signing
agency would make g and h, as he defined them, public.  With g and h
then users could combine their credentials as he said.  But even that
doesn't work; his whole formula doesn't make sense.  g is the inverse
of d1 mod d2; this means that g*d1 = 1 mod d2, or in other words
g*d1 - 1 = k*d2 for some k.  That's the definition of the multiplicative
inverse.  Okay, but then he says h is the remainder when g*d1-1 is divided
by d2.  But look: g*d1-1 is a MULTIPLE of g2!  The remainder will always
be zero.  So that doesn't make any sense either.

So I thought, perhaps he really meant that h should be the quotient
rather than the remainder; it would be "k" in the equation I just wrote.
Then we'd have g*d1 - 1 = h*d2, which is somewhat encouraging because
it resembles his formula.  But his formula is (Px^d1)^g * (Px^d2)^(-h),
which is Px^(g*d1 - h*d2).  Rearranging the equation two lines above,
we see that g*d1 - h*d2 = 1.  So we end up with just Px, not Px^(d1*d2).
So this isn't right, either.

In fact, the notion that you can calculate Px^(d1*d2) from Px^d1 and
Px^d2 is pretty questionable, since the impossibility of doing this is
the basis of Diffie-Hellman key exchange!

In short, I haven't found any interpretation of Chaum's math that makes
sense.  Can anyone shed any light on this?  Was this just a mistake in
a paper which was, after all, just intended for conference proceedings,
not a refereed journal?  Thanks -

Hal

-----BEGIN PGP SIGNATURE-----
Version: 2.3a

iQCVAgUBLNLlRKgTA69YIUw3AQEmegP9HzQt1vMwuLvVVr2e3LNrL5lPh9jg/cb4
rQkTvh+XVCKlqsI7TJ2pCeAwLygxPMlcw4/3sAeV9K1hWqk0B+bSFU8qWQSmka5+
2OpJIXt2C+N/qVMKiFzAKMmQf680iVUxdj/TvfV6kZ6hPA5eqHdnHWy45QKEck3B
VMNwKRPz2Mo=
=TLs8
-----END PGP SIGNATURE-----

Hal Finney writes about a paper of Chaum's, and near the end asks:

>In short, I haven't found any interpretation of Chaum's math that makes
>sense.  Can anyone shed any light on this?  

I think you're correct, Hal.  From everything I can tell, Chaum's
confused product and greatest common divisor.

First, though, there's a basic fact about the arithmetic of integers
which everyone who wants to learn more algebra should know.  Z is the
set of integers.

    For every m,n in Z, there is a,b in Z such that a*m + b*n = gcd(m,n).

One calculates the gcd by means of the Euclidean algorithm, and the
coefficients a and b by an extension of that algorithm.  Lots of basic
algorithm books contain descriptions.

From an abstract point of view, this is a simple consequence that Z is
a principal ideal domain.  The ideal (m,n) is composed of the linear
span of m and n.  Since this ideal is principal, by definition there
is a c such that (m,n) = (c).  Clearly c is in the linear span of m
and n, hence coefficients exist.

Note that reducing mod n gives a*m = gcd(m,n) (mod n).  If m and n are
relatively prime (means gcd = 1), the a is m inverse mod n.  Likewise
b is n inverse mod m.  This is a standard algorithm for calculating
modular inverses.

Here's the relevant passage, again:

>   "Suppose an organization X were to require that you have each of two
>   credentials, say both that with public exponents e1 and e2.  You could
>   send X separatley Px^d1 and Px^d2.  It is also possible for you to use
>   the two credentials to form the single credential Px^(d1*d2), which
>   will be called their AND....  To create the AND, you: set g to the
>   multiplicative inverse of d1 modulo d2; set h to the remainder after
>   dividing g*d1-1 by d2; and computing
>   (Px^d1)^g * (Px^d2)^(-h) = Px^(d1*d2)."

I believe that Hal is correct when he points out that h is not a
remainder (which would be zero, as he points out) but the quotient.  I
originally misread this as quotient because I recognized the context.

First, the multiplicative inverse of d1 (mod d2) exists only if the
two are relatively prime.  Hal did not quote the whole article, so I
don't know if this criterion is stated elsewhere.  Let us assume the
d's have this property, since the d's can be so chosen.

The calculation of d1 (mod d2) is exactly the calculation of the
coefficients in the extended Euclidean algorithm above.  Consider a*d1
+ b*d2 = 1.  Reducing mod d2, we have a*d1 = 1 (mod d2).  That means
that a is d1^(-1) (mod d2).  Likewise (a*d1 - 1) / d2 = -b.  Chaum's
description exactly fits the gcd context.

>The other possibility I thought of is that he meant that the signing
>agency would make g and h, as he defined them, public.  

That's my interpretation as well.  After the calculation, as Hal
observes, you just end up with Px, not Px^(d1*d2).  That's totally
useless, since you already knew Px.

It is certainly possible to create coefficients for combining
credentials such that you end up with a product in the exponent.  For
example, the pairs <d2,0> and <0,d1> both work nicely, with the bad
side effect that you've given away a private key.  Let's try blinding
them.

Suppose you have coefficients a and b such that a*d1+b*d2=0; the pair
<d2,-d1> works here.  Then every such pair of product-combining
coefficients can be represented as <d2,0> + r*<a,b>.  Since the
exponents are mod phi(N), we can suppose that the pair <d2+r*a,r*b>
doesn't _directly_ reveal the private keys.  But it's unclear to me
that this pair of coefficients doesn't reveal d1 and d2.  One doesn't
know phi(N), but one may not need to.

Eric