Implementing a pricing function (Extracting Square Roots)

[Falk Köppe]

Hello @all,

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?

 

[Falk Köppe]

That's not the method you are looking for. This one is for an
approximation of the square root computed in the field of real numbers,
whereas you want to use modular integers which are something entirely
different.

You may want to look at:
   http://en.wikipedia.org/wiki/Modular_exponentiation
for a starter on modular integer. Then, proceed to the "Handbook
of Applied Cryptography": download chapter 2 from:
   http://www.cacr.math.uwaterloo.ca/hac/
and read pages 67 to 70.

Then (and only then ! Mathematics make sense only if you lookup things
in the right order) proceed to:
   http://en.wikipedia.org/wiki/Quadratic_residue
and especially the part titled "Complexity of finding square roots".
You will find that if you choose your prime p to be equal to 3 modulo 4,
then extracting a square root is mostly a matter of a modPow() call.

        --Thomas Pornin

Thank you Thomas for your quick and thoughtful reply.

I started reading your literature and already noticed, that my
approach was way off, because of my false naive assumptions. The sqrt
method got deleted. I started to fix my verify method to check
congruency of modular integers:

private boolean isCongruent( BigInteger a, BigInteger b, BigInteger
n )
{
BigInteger aRemainder = a.remainder(n);
BigInteger bRemainder = b.remainder(n);

return ( aRemainder.compareTo(bRemainder) == 0 );
}

The next enlightenment you provided was an exact term of what I'm
actually looking for: finding a modular square root with a prime
modulus p (a^2 congruent to b mod p). The description of the pricing
function by Cynthia Dwork and Moni Noar does not state further details
on the prime modulus p. So there are three cases:

(1) the prime modulus p is congruent to 3 modulo 4 or
(2) the prime modulus p is 2 or
(3) the prime modulus p is congruent to 1 modulo 4.

You already said that case (1) is simple: a = b.modpow( ( p + 1 ) / 4,
p ).
Probably p must be > 2 because of case (2).
I need an algorithm for case (3).

Now the question is, what algorithm to use to find the modular square
root with a prime modulus p congruent to 1 modulo 4. The Shanks-
Tonelli Algorithm (http://www.math.vt.edu/people/brown/doc/sqrts.pdf
starting on page 91) seems to be a solution. I found a python
implementation of that algorithm (http://eli.thegreenplace.net/
2009/03/07/computing-modular-square-roots-in-python/), which I don't
trust/understand completely. I could not find a java implementation of
the Shanks-Tonelli Algorithm. I can't convice my head just yet that
this algorithm was meant by Cynthia Dwork and Moni Noar in their paper
"Pricing via Processing or Combating Junk Mail" (1993).


I feel like I'm getting closer, but I'm not there yet...
- Are there better/other algorithms for finding a modular square root
with a prime modulus?
- Is there a java implementation of such an algorithm?
- I assume that the pricing function works by me providing prime p and
integer b. Then I ask for integer a with a^2 congruent to b mod p.
Wouldn't it be unfair if the prime modulus p is case (3) for some and
case (1) or case (2) for others? Is b an arbitrary integer number > 0
or are there any requirements on b?


Sorry, it took me about five hours to write this response, so please
excuse any clouded parts. I hope it still makes sense.

 

[Falk Köppe]

Hello Thomas,

I just want to leave a quick note to really thank you for your effort
and endurance. I will step through your suggestions tomorrow.

Greetings
Falk Köppe

 

[Falk Köppe]

Hello Thomas,

sorry, that my answer is late, but I had too much to do the last two
days. First I want to thank you again for your effort to help me to
better understand modular integer arithmetic. Specially your
literature paved the way for my better understanding.

You may want to use mod() instead of remainder(): mod() will return
a more appropriate result for a negative source value. For positive
integers, remainder() and mod() return the same value (but 'mod' is
shorter, thus easier to type than 'remainder').

I changed the function accordingly.

Not necessarily. In the protocols described by Dwork and Naor, the
prime p may be fixed; actually, it should be fixed, once and for all,
and everybody should use that p. You then are free to select a p
which is convenient, i.e. equal to 3 modulo 4.

I decided to go this way and use a prime modulus p congruent to 3 mod
4. This is implemented with the following function, which returns a
random prime with numBits number of bits and the characteristic of
beeing congruent to 3 mod 4. I can't decide yet, if the prime p should
be fixed or not, because I want to regulate the difficulty or time it
takes to find a square root.

private BigInteger findConvenientPrime(int numBits) {
boolean foundConvenientPrime = false;
Random random = new SecureRandom();
BigInteger result = null;

while (!foundConvenientPrime) {
result = BigInteger.probablePrime(numBits, random);

if (isCongruent(result, BigInteger.valueOf(3),
BigInteger.valueOf(4)) {
foundConvenientPrime = true;
}
}

return result;
}

The Dwork-Naor article describes b as being computed with a hash
function on a some data which includes the source message, the sending
date and the destination address. The point is to make it impossible for
the sender to reuse the same b for several messages (the pricing
function makes sense only if the sender must 'pay' the price for each
sent message).

I create a random BigInteger value b, with 0 <= b < p. This would be
my equivalent to the proposed hash function. Because I can't accept
values b that don't have a square root, the following algorithm
increments b by one until a value b is found that has a square root.

// finds the square root of the first integer starting with b
// that has a square root
public BigInteger findSquareRoot(BigInteger b, BigInteger p) {
BigInteger squareRoot = null;

if (p.compareTo(BigInteger.valueOf(2) == 0) {
squareRoot = b;
}
else {
boolean foundSquareRoot = false;

while (!foundSquare) {
squareRoot = b.modpow(p.add(BigInteger.ONE)
.divide(BigInteger.valueOf(4)), p)

if (isCongruent(squareRoot.multiply(squareRoot), b, p) {
foundSquareRoot = true;
} else {
b = b.add(BigInteger.ONE);
}
}
}

return squareRoot;
}

So if someone is unlucky, than she gets a value b that does not have a
square root and needs to try as long as she finds a square root. The
reason I need a square root is, that if I would accept null values,
then I can't be sure she really calculated the challenge, instead of
just returning null. To check, if she said the truth I would have to
calculate the square root myself, which defeats the purpose of the
pricing function. I'm not interested in the actual square root, but in
the fact, that she really calculated it.

I will now try to regulate the number of bits of prime p and the
number of bits of value b to figure out how it effects the time it
takes to find a square root with the given algorithm.

Greetings,
Falk Köppe

 

[Lew]

private BigInteger findConvenientPrime(int numBits) {
    boolean foundConvenientPrime = false;
    Random random = new SecureRandom();
    BigInteger result = null;

    while (!foundConvenientPrime) {
        result = BigInteger.probablePrime(numBits, random);

        if (isCongruent(result, BigInteger.valueOf(3),
BigInteger.valueOf(4)) {
            foundConvenientPrime = true;
        }
    }

    return result;

Alternative idioms
1)
private BigInteger findConvenientPrime(int numBits) {
Random random = new SecureRandom();

BigInteger result;
boolean found;
do {
result = BigInteger.probablePrime( numBits, random );

found = isCongruent( result, BigInteger.valueOf(3),
BigInteger.valueOf(4) );
} while ( ! found );
return result;
}

2)
private BigInteger findConvenientPrime(int numBits) {
Random random = new SecureRandom();

BigInteger result;
for ( boolean found = false; ! found;
found = isCongruent( result, BigInteger.valueOf(3),
BigInteger.valueOf(4) )
) {
result = BigInteger.probablePrime( numBits, random );
}
return result;
}

3)
private BigInteger findConvenientPrime(int numBits) {
Random random = new SecureRandom();

while ( true ) {
final BigInteger result = BigInteger.probablePrime( numBits,
random );

if ( isCongruent( result, BigInteger.valueOf(3),
BigInteger.valueOf(4) ) {
return result;
}
}
}

This code hasn't been compiled, much less tested, so it might contain
typos.

 

[Falk Köppe]

Hello Lew,

thanks for your improvement. I really liked your first implementation
and changed my function accordingly.

1)
 private BigInteger findConvenientPrime(int numBits) {
   Random random = new SecureRandom();

   BigInteger result;
   boolean found;
   do {
     result = BigInteger.probablePrime( numBits, random );

     found = isCongruent( result, BigInteger.valueOf(3),
BigInteger.valueOf(4) );
   } while ( ! found );

   return result;
 }

Greetings,
Falk Köppe

 

[Lew]

thanks for your improvement. I really liked your first implementation
and changed my function accordingly.

Each has something to recommend it. #1 is probably the easiest to read. #2
limits the scope of 'found' to the loop, a good thing since 'found' is the
most temporary of the variables. #3 (which could have used 'for(;' instead
of 'while(true)') eliminates 'found' altogether, limits the scope of 'result'
to the loop, and makes the 'result' variable 'final'.