UCLA

Cryptography is an active field of theoretical research. It is also a place where many unproven,

but time-tested practical ideas exist. This work exposits a few strands that connect

these two sides of the Cryptographic coin.

The two main results presented are,

1. The first traitor tracing scheme based on prime order bilinear groups. While prime

order bilinear groups are practical, existing schemes for traitor tracing were based

on the more structurally rich, but much less practical composite order bilinear groups.

Our work brings the rich structure of composite order bilinear groups and the efficiency

of prime order groups together.

2. A formal model for CAPTCHAs which captures the intuition that any automaton

must request human help to solve CAPTCHA problems. We use this model to obtain

positive results in the eld of concurrent security. This is the first result that brings

CAPTCHA, a widely adopted practical security tool, into main stream cryptography

to achieve tasks that are known to be theoretically impossible in the plain model.