TU Darmstadt / ULB / tuprints

Public-Key Cryptography

Möller, Bodo :
Public-Key Cryptography.
[Online-Edition]
TU Darmstadt
[Ph.D. Thesis], (2003)

[img]
Preview
PDF
pkc-tp.pdf
Available under Simple publication rights for ULB.

Download (587Kb) | Preview
Item Type: Ph.D. Thesis
Title: Public-Key Cryptography
Language: English
Abstract:

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.

Alternative Abstract:
Alternative AbstractLanguage
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.English
Uncontrolled Keywords: Kryptographie
Alternative keywords:
Alternative keywordsLanguage
KryptographieGerman
cryptographyEnglish
Classification DDC: 000 Allgemeines, Informatik, Informationswissenschaft > 004 Informatik
Divisions: Fachbereich Informatik
Date Deposited: 17 Oct 2008 09:21
Last Modified: 07 Dec 2012 11:49
Official URL: http://elib.tu-darmstadt.de/diss/000372
URN: urn:nbn:de:tuda-tuprints-3722
License: Simple publication rights for ULB
Referees: Buchmann, Prof. Dr. Johannes and Paar, Prof. Dr. Christof
Advisors: Buchmann, Prof. Dr. Johannes
Refereed: 16 September 2003
URI: http://tuprints.ulb.tu-darmstadt.de/id/eprint/372
Export:

Actions (login required)

View Item View Item