POSH: A generalized CAPTCHA with security applications
Waseem Daher, Ran Canetti
CCS 2008
Let g be a primitive root modulo a prime p. It is proved that the triples (gx, gy, gxy), x, y = 1, ..., p-1, are uniformly distributed modulo p in the sense of H. Weyl. This result is based on the following upper bound for double exponential sums. Let ε > 0 be fixed. Then Σp-1x,y-1 exp (2πiagx+bgy+cgxy/p) = O(p31/16+ε) uniformly for any integers a, b, c with gcd(a, b, c, p) = 1. Incomplete sums are estimated as well. The question is motivated by the assumption, often made in cryptography, that the triples (gx, gy, gxy) cannot be distinguished from totally random triples in feasible computation time. The results imply that this is in any case true for a constant fraction of the most significant bits, and for a constant fraction of the least significant bits.
Waseem Daher, Ran Canetti
CCS 2008
Adrian Perrig, Ran Canetti, et al.
Proceedings of the IEEE Computer Society Symposium on Research in Security and Privacy
Ran Canetti, Ivan Damgård, et al.
Journal of Cryptology
William Aiello, Steven M. Bellovin, et al.
ACM TISSEC