Quote from: adam3us on October 09, 2013, 04:41:24 PM

signed-hashcash variant with an indistinguishable short-cut [...] based on RSA:

setup: c=random, s=salt, i=counter, t=random mod 2^k, a=c^t mod n, m=message
repeat find i such that t =? h( s, i, a, m ) mod 2^k
verify: a == c^t mod n and t = h( s, i, a, m ) mod 2^k
shortcut: s=salt, v=random, i=plausible random, t = h( s, i, a, m ) mod 2^k, c=v^(1/t) mod n

works because knowing p, q you can efficiently compute arbitrary t-th roots.

[...]not blindable/offloadable because the work is in the exposed hash, but RSA has a simpler form of blinding so its a start.

Here's a pair of offloadable blindable functions:

First RSA based

public params:

[EDITED to relabel x as e, as its more like a large RSA public e exponent]

n=pq (primes p & q deleted at setup)
g=shared generator
e=2^(2^w)-1 ie a big, big number
y=g^e mod n (generated cheaply at setup, or computable one-off cost afterwards)

blind:

m=message
b=random blinding factor
r=g^b*m (broacast r to miners)

work:

s=r^e mod n (expensive because e is big and carm(n)=(p-1)(q-1)/2 is unknown)

unblind:

u=y^b (unblinding factor)
m^e = s/u (as s/y^b=r^e/g^{be}=g^{be}*m^e/g^{be})

Not bad other than the trap-door of n that you cant disprove knowledge of without a trusted person at setup. Its also non parallelizable, and deterministic cost, so its not a good distributed mining function. But the cost factor w can be increased fairly arbitrarily without n being bigger than 3072 bits. Presumably can construct a signature out of this somehow.

square root (4.1 from Dwork & Naor) is also blindable:

public:

prime p (of size relating to w)

blind:

m=message
b=random blinding factor
r=b^2*m (broacast r to miners)

work:

s=sqrt(r)

unblind:

m=s/b (as sqrt(r)=sqrt(b^2*m)=b*sqrt(m))

There are signature schemes based on square root (assuming RSA groups) but that could work over prime field, if the scheme doesnt need a trap-door, just use a very large prime so that its a big amount of work to compute the square root. Unfortunately that makes big prime fields as you cant increase the work factor without increasing p. (And using repeated square root wont work much because there are also n-th root algorithms).

Square root doesnt have to be determinstic and the tonelli-shanks square root algorithm even has
some randomness (better for distributed mining) however there are there are slower algorithms which do not and there is a precomputation on Tonelli shanks if you have to find multiple square roots. To make the precomputation too large you have to increase s where p=2^s*q+1 but before it gets to be a useful size another algorithm becomes better Cipolla which has some small randomness but more of the work is deterministic. The verification cost and RAM usage also increases as the prime size increases, and the difference between cost and verification is not as stark, ie it starts to get quite expensive to verify even for interesting work factors.

Adam