F

#### Falk Köppe

I have a problem implementing a pricing function (Extracting Square

Roots). The following explanation of the pricing function Extracting

Square Roots is by Cynthia Dwork and Moni Noar from their paper

"Pricing via Processing or Combating Junk Mail" (1993).

"The simplest implementation of our idea is to base the difficulty of

sending on the difficulty (but not infeasibility) of extracting square

roots modulo a prime p. Again, there is no known shortcut for this

function.

- Index:A prime p of length depending on the difference parameter; a

reasonable length would be 1024 bits.

- Definition of fp: The domain of fp is Zp. fp(x) = sqrt(x) mod p.

- Verification: Given x, y, check that y.pow(2) == x mod p.

The checking step requires only one multiplication. In contrast, no

method of extracting square roots mod p is known that requires fewer

than about log p multiplications. Thus, the larger we take the length

of p, the larger the difference between the time needed to evaluate fp

and the time needed for verification."

My wrong approach with a smaller test prime number looks like this:

public void extract() {

int primeLength = 4;

BigInteger prime = BigInteger.probablePrime( primeLength, new

SecureRandom() );

BigInteger x = BigInteger.ZERO;

BigInteger y = BigInteger.ZERO;

do {

x = x.add( BigInteger.ONE );

y = sqrt( x ).mod( prime );

} while( ! verify( x, y, prime ) );

System.out.println( x );

System.out.println( y );

System.out.println( prime );

}

private boolean verify( BigInteger x, BigInteger y, BigInteger prime )

{

return ( y.pow( 2 ).compareTo( x.mod( prime ) ) == 0 );

}

// source: faruk akgul /blog - Java's Missing Algorithm: Biginteger

Sqrt

private BigInteger sqrt( BigInteger n ) {

BigInteger a = BigInteger.ONE;

BigInteger b = new BigInteger( n.shiftRight( 5 ).add( new

BigInteger( "8" ) ).toString() );

while ( b.compareTo( a ) >= 0 ) {

BigInteger mid = new BigInteger( a.add( b ).shiftRight

( 1 ).toString() );

if ( mid.multiply( mid ).compareTo( n ) > 0 ) {

b = mid.subtract( BigInteger.ONE);

} else {

a = mid.add( BigInteger.ONE );

}

}

return a.subtract( BigInteger.ONE );

}

I don't get the concept of the pricing function at all. My head hurts.

I would really appreciate some help on how to implement the explained

function or answers on one of the following questions:

- What exactly is the domain of Zp? Are those all integer numbers from

0 to p, because everything mod p is either smaller or equal to p? That

would make y definitely a BigInteger.

- What am I exactly looking for? Am I right to increase x by one each

time the verification returned false?

- Should y be a large number given, or is it calculated in the loop

the way I implemented it?

- Do we even talk about BigIntegers only, or should x be a decimal

because of the sqrt method?

- My implementation can't be right, because, for example, it always

returns y=1 and x=1, which is verified, but probably not the point of

the pricing function.

Gosh...it's supposed to be the simplest implemenation, and I'm not

even able to get that right...where is the hole I can bury myself?