Public-Key Cryptography

Part I: Theory Provable security is an important goal in the design of public-key cryptosystems. For most security properties, it is computational security that has to be considered: an attack scenario describes how adversaries interact with the cryptosystem, trying to attack it; the system can be called secure if adversaries with reasonably bounded computational means have negligible prospects of success. The lack of computational problems that are guaranteed to be hard in an appropriate sense means that there is little hope for absolute proofs of computational security. Instead, reduction-based security proofs have to be used: the computational security of a complex cryptographic scheme is related to the security of simpler underlying cryptographic primitives (under appropriate notions of security). The idea is to show that if the complex scheme is not secure, then this is because one of the primitives is not secure. Security can be described quantitatively as "concrete security", measured depending on the power given to adversaries. The DHAES construction (due to Abdalla, Bellare, and Rogaway) allows building a public-key encryption scheme from a key encapsulation mechanism (KEM), a one-time message authentication code (one-time MAC), and a pseudo-random bit string generator. A reduction-based security proof shows that DHAES achieves security against (adaptive) chosen-ciphertext attacks if these underlying primitives are secure. (Such chosen-ciphertext attacks are the most general attack scenario for public-key encryption.) A specific application for public-key cryptography is considered, namely Chaum's mix chain concept for untraceable electronic mail via cryptographic remailers: to obtain anonymity without requiring trust in a single authority, messages are recursively public-key encrypted to multiple intermediates (mixes), each of which forwards the message after removing one layer of encryption. To conceal as much information as possible when using variable (source routed) chains, all messages passed to mixes should be of the same length; thus, message length should not decrease when a mix transforms an input message into the corresponding output message directed at the next mix in the chain. Chaum described an implementation for such length-preserving mixes, but it is not secure against active attacks. This thesis presents a new construction for practical length-preserving mixes, which uses the cryptographic primitives described for DHAES. The conventional definition of security against chosen ciphertext attacks for public-key encryption schemes is not applicable to length-preserving mixes, so appropriate security definitions are introduced; it is shown that the mix construction achieves provable security. Part II: Practice Most instantiations of public-key cryptography involve computing powers (exponentiation) or computing power products ("multi-exponentiation") in some commutative semigroup with neutral element. This thesis describes the sliding window technique for arbitrary commutative semigroups with neutral element and its signed-digit variant ("window NAF") for groups where inversion is fast (e.g. point groups of elliptic curves and class groups of imaginary quadratic number fields), and then presents new techniques. Fractional windows, a generalization of the previously known window methods, can be useful for devices with limited storage. Interleaved exponentiation is a simple strategy for multi-exponentiation; the comparison with previous simultaneous exponentiation methods shows that it often provides better efficiency. Window NAF splitting is a method for fast exponentiation with precomputation for a fixed base in groups where inversion is fast. For the case of elliptic curves, side-channel attacks are discussed, i.e. attacks where adversaries use power consumption measurements or similar observations to derive information on secret values. Two methods are shown that are designed to limit potential information leakage available to adversaries: a 2w-ary left-to-right method employing special representations of scalars, and a 2w-ary right-to-left method with a special randomized initialization stage