Abstract: 
Part I: Theory Provable security is an important goal in the design of publickey 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, reductionbased 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 publickey encryption scheme from a key encapsulation mechanism (KEM), a onetime message authentication code (onetime MAC), and a pseudorandom bit string generator. A reductionbased security proof shows that DHAES achieves security against (adaptive) chosenciphertext attacks if these underlying primitives are secure. (Such chosenciphertext attacks are the most general attack scenario for publickey encryption.) A specific application for publickey 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 publickey 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 lengthpreserving mixes, but it is not secure against active attacks. This thesis presents a new construction for practical lengthpreserving mixes, which uses the cryptographic primitives described for DHAES. The conventional definition of security against chosen ciphertext attacks for publickey encryption schemes is not applicable to lengthpreserving mixes, so appropriate security definitions are introduced; it is shown that the mix construction achieves provable security. Part II: Practice Most instantiations of publickey cryptography involve computing powers (exponentiation) or computing power products ("multiexponentiation") in some commutative semigroup with neutral element. This thesis describes the sliding window technique for arbitrary commutative semigroups with neutral element and its signeddigit 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 multiexponentiation; 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, sidechannel 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 2wary lefttoright method employing special representations of scalars, and a 2wary righttoleft method with a special randomized initialization stage. 
Alternative Abstract: 
Alternative Abstract  Language 

Part I: Theory Provable security is an important goal in the design of publickey 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, reductionbased 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 publickey encryption scheme from a key encapsulation mechanism (KEM), a onetime message authentication code (onetime MAC), and a pseudorandom bit string generator. A reductionbased security proof shows that DHAES achieves security against (adaptive) chosenciphertext attacks if these underlying primitives are secure. (Such chosenciphertext attacks are the most general attack scenario for publickey encryption.) A specific application for publickey 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 publickey 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 lengthpreserving mixes, but it is not secure against active attacks. This thesis presents a new construction for practical lengthpreserving mixes, which uses the cryptographic primitives described for DHAES. The conventional definition of security against chosen ciphertext attacks for publickey encryption schemes is not applicable to lengthpreserving mixes, so appropriate security definitions are introduced; it is shown that the mix construction achieves provable security. Part II: Practice Most instantiations of publickey cryptography involve computing powers (exponentiation) or computing power products ("multiexponentiation") in some commutative semigroup with neutral element. This thesis describes the sliding window technique for arbitrary commutative semigroups with neutral element and its signeddigit 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 multiexponentiation; 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, sidechannel 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 2wary lefttoright method employing special representations of scalars, and a 2wary righttoleft method with a special randomized initialization stage.  English 
