CS 298-2
Theory Seminar

Shai Halevi
IBM

BTE encryption: construction and applications

We introduce a new cryptographic primitive, binary-tree public-key encryption (BTE), and show applications to CCA-security and forward security.

BTE is a variant of (hierarchical) ID-based encryption (IBE). As opposed to standard IBE, for which all the known constructions are proven in the random oracle model, we show how to construct a secure BTE in the standard model, based on the bilinear-DDH assumption. On the other hand, BTE can be used to implement (hierarchical) IBE, albeit with a somewhat weaker notion of security.

Next we show how to obtain CCA security from any "weak IBE" scheme. Combined with the previous result, this means that we have a new construction of CCA secure encryption in the standard model, based on the bilinear DDH assumption. Differently than all prior CCA-secure schemes, this construction does not use "proof of ciphertext validity", and therefore it is the only known standard-model construction that dose not fit the "CCA security paradigm" exhibited by Sahai and Elkind.

Time permitting, I will also talk about an application to forward-secure encryption. Forward secure encryption provides a way to mitigate key-exposure attacks, by periodically refresh the secret key (without changing the corresponding public key), so that key-exposure does not compromise the secrecy of past ciphertexts. The challenge is to construct forward-secure encryption where efficiency does not degrade linearly with the number of time periods. We show how to use BTE encryption to construct forward-secure encryption scheme, in which all the parameters degrade only logarithmically in the number of time periods.