Cryptographic Reductions: Classification and Applications to Ideal Models

Provable security refers to the ability to give rigorous mathematical proofs towards the security of a cryptographic construction; in some sense one of the best possible security guarantees one can attain. These proofs are most often given through so-called reductions to a simpler construction or to some well-studied number-theoretic assumption. This thesis deals with two aspects of such reductions. First, since a reduction may be difficult to obtain, many reductions for widely-used signature and encryption schemes are conducted in a model that idealizes some underlying building block of the scheme, for example by replacing a hash function with a truly random function. With these reductions in idealized models, it is difficult to compare requirements of cryptographic schemes because the idealization introduces all desired properties simultaneously and it is inexplicit which ones are used and to what extent. This complicates practical considerations when choosing from multiple candidate constructions for the same task. We develop a novel mechanism to relate schemes proven in idealized models. In this thesis, we present a reductionist paradigm that allows meaningful comparisons of constructions in idealized models with respect to the idealized part. Some of the idealized constructions considered here are the well-known compression-function constructions from blockciphers by Preneel, Govaerts, and Vandewalle (PGV; CRYPTO, 1993), and the twin ElGamal encryption scheme by Cash, Kiltz, and Shoup (Journal of Cryptology, 2009). Our main results show that the random oracle of the twin ElGamal encryption scheme reduces to the random oracle of the regular ElGamal encryption scheme, the PGV constructions fall into two groups, and the so-called double-block-length constructions reduce to one of the PGV constructions with respect to their ideal cipher. We can thus conclude that the PGV constructions are essentially equivalent within their respective groups and that double-block-length constructions are strictly superior, not only because of their increased key length. Similarly, the regular ElGamal scheme can be replaced by the twin ElGamal scheme (keeping in mind the reduction's tightness), even though the proofs are in an idealized model. These latter results greatly help designers and implementers of practical cryptographic constructions to select the better of two (or more) seemingly equivalent options. Ideal-model reducibility as a comparison tool is applicable to any two constructions whose proof is in an idealized model. The second aspect of reductions we study in this thesis relates to the absence of reductions. Sometimes, insurmountable obstacles in finding a reduction result in a proof that reductions of some kind cannot exists at all. In that case, it is particularly important to carefully understand what the non-existent reductions look like---since, perhaps, a slightly different reduction is feasible. We develop means that allow us to better understand existing reductions in the literature. This thesis presents a new framework, akin to the one by Reingold, Trevisan, and Vadhan (TCC, 2004), for classifying reductions in a more fine-grained and more systematic way. The new framework clarifies the role of efficiency of adversaries and primitives within reductions, covers meta-reduction separations, and provides new insights on the power of relativizing reductions. Consequently, a classification within the new framework clearly points out avenues to circumvent existing impossibility results and enables an assessment of their strength. The generality of the framework permits classification of a large body of existing reductions, but it is easily extensible to include further properties