## Ron Rothblum

## Abstract of Master Thesis (Weizmann Inst., 2010)

### On Homomorphic Encryption and Enhanced Trapdoor Permutations

In this thesis we study two remotely related cryptographic primitives:
homomorphic encryption and enhanced trapdoor permutations.

Our main result regarding homomorphic encryption shows that any
private-key encryption scheme that is weakly homomorphic with respect
to addition modulo 2, can be transformed into a public-key encryption
scheme. The homomorphic feature referred to is a minimalistic one;
that is, the length of a homomorphically generated encryption should
be independent of the number of ciphertexts from which it was
created. Our resulting public-key scheme is homomorphic in the
following sense. If i+1 repeated applications of homomorphic
operations can be applied to the private-key scheme, then i repeated
applications can be applied to the public-key scheme.

In an independent part of the thesis, we study (enhanced) trapdoor
permutations (TDPs). We note that in many setting and applications
trapdoor permutations behave unexpectedly. In particular, a TDP may
become easy to invert when the inverter is given auxiliary information
about the element to be inverted (e.g., the random coins that sampled
the element). Enhanced TDPs were defined in order to address the
latter special case, but there are settings in which they apparently
do not suffice (as demonstrated by the introduction of doubly-enhanced
TDPs). We study the hardness of inverting TDP in natural settings,
which reflect the security concerns that arise in various applications
of TDPs to the construction of complex primitives (e.g., Oblivious
Transfer and NIZK). For each such setting, we define a corresponding
variant of the notion of an enhanced TDP such that this variant is
hard to invert in that setting. This yields a taxonomy of variants,
which lie between enhanced TDPs and doubly-enhanced TDPs. We explore
this taxonomy and its relation to various applications.

*Submitted to the Feinberg Graduate School
of the Weizmann Institute of Science, September 2010.*

Available:
the
thesis (in PDF file).

Back to Oded Goldreich's homepage.