OSEC

Neohapsis is currently accepting applications for employment. For more information, please visit our website www.neohapsis.com or email hr@neohapsis.com
Crypto Archives: Re: Lucre fixed?

Re: Lucre fixed?

Subject: Re: Lucre fixed?
From: Ben Laurie (benalgroup.co.uk)
Date: Sun Dec 05 1999 - 07:21:00 CST

lcs Mixmaster Remailer wrote:
>
> A few comments on http://anoncvs.aldigital.co.uk/lucre/theory2.pdf:
>
> We have p as a strong prime with (p-1)/2 also a strong prime. It seems
> unnecessary at this point to choose g as a generator of the subgroup of
> order (p-1)/2. This adds considerable complexity, you constantly have
> to check that elements are in that subgroup, which involves a costly
> exponentiation, and possibly a generate-check-retry cycle. Also the
> bank has to do an extra exponentiation to verify subgroup membership
> at deposit time.

Ian Goldberg pointed out to me that the cute way to fix this is to
define oneway'(x) to be g^oneway(x).

> Better to let g generate the whole group. Yes, this leaks the low
> order bit of k, but k has to be odd anyway so that it has an inverse.
> So choose odd k. You're not giving up anything significant in doing that.
> k doesn't need to be all that big, just big enough to prevent square
> root attacks - 160 to 256 bits is plenty.

Yeah, this is another way to "fix" the problems, but it is less
mathematically appealing (at least to me) and its nice to keep the maths
working for large subgroups. I'll certainly note this approach, though.

> The way you are calculating your oneway function, it embeds x. So your
> coin can actually just be z. The mint calculates z^(1/k) to recover
> y, pulls x out of the left bits, and verifies that y = oneway(x).

Yeah - the form of the coin got to be the way it was when k wasn't
necessarily invertible.

> The first defense [note spelling] variant doesn't work, because the
> bank can guess whether the user is going to demand r or t. If it
> guesses right, it can respond correctly even though it didn't raise
> y*g^b to the k power. To use this one, the bank needs to replicate it
> enough times to reduce the chance of cheating to a safe level; 10 times
> gives one chance in a thousand of cheating, which may be good enough.
> The bank chooses 10 different r values and sends the Q, A for each one.
> Then the user demands r/t ten times: r, r, t, r, t, r, r, t, t, t.
> The bank gives the appropriate response for each of the 10 instances.

The general idea was that a cheating bank wouldn't cheat just once, so
they'd get caught in the end - but I'll certainly note that repeated
rounds might be needed for greater confidence (I didn't note it before
because I thought it rather obvious).

> Actually the Variation 2 proof can be seen as a generalization of the
> Variation 1, allowing you to do it in just one guess, but there isn't
> time to go into the details of that here.

Eh? Ah, hmm - perhaps I see - the bits of the challenge are effectively
a serious of choices between r and t, kind of. Right?

> You should trust the non-interactive variant, it is widely used in
> discrete log signatures, Schnorr being one of the simplest examples.
> Of course if you want you can do it interactively, since the user is
> talking to the bank already anyway.

Guess I'll have to bang my head against it for a while before I'm
convinced.

> The formula in 5.2 for the random seed bit size, n, uses log base g of p.
> It appears to need to use log base 2 of p, since you are counting bits.

Oops, yes.

Thanks for the comments.

Cheers,

Ben. 

--
SECURE HOSTING AT THE BUNKER! http://www.thebunker.net/hosting.htm

http://www.apache-ssl.org/ben.html

"My grandfather once told me that there are two kinds of people: those
who work and those who take the credit. He told me to try to be in the
first group; there was less competition there."
     - Indira Gandhi

This archive was generated by hypermail 2b27 : Sun Dec 05 1999 - 09:49:40 CST