Improving efficiency of cryptographic constructions
Leonid Reyzin, Nenad Dedić · 2009
Generic cryptographic techniques can be used out-of-the-box to provide secure solutions to many problems. However, it is possible to obtain more efficient solutions if they are tailored to specific problems. This thesis considers two specific problems and shows efficiency improvements or simplifications over existing solutions. (1) Improving efficiency of pseudorandom generators (PRG). It is shown how to exploit certain natural properties of one-way (OW) functions to construct efficient PRGs and PRG families. Considered efficiency measures are computation time and seed size. In particular it is shown how so-called regular OWFs yield PRGs with short seed. It is further shown how to use OWFs with certain reducibility properties to obtain fast PRGs. (2) Communication-efficient private database queries. The Server holds a large database X of N elements; the User poses a query q and wishes to find out f( q, X) for some public function f. Security mandates that the User learn only f(q, X), and the Server only the bit-size of f(q, X). Communication is at a premium here, i.e. it must depend only mildly on the database size N. The thesis shows efficient solutions to the Element-rank problem, where the database entries are integers and f counts how many of them are smaller than q. The focus is in particular on securing against a malicious User at a very small efficiency cost: a constant factor overhead with a simple implementation, as compared to previously known complex generic techniques with a poly-logarithmic overhead.