Information Security and Cryptography Research Group

Idealizations of Practical Cryptographic Building Blocks

Christian Badertscher

PhD Thesis, ETH Zurich, 2018.

Security definitions are at the core of cryptographic research. Their importance stems from the fact that they enable security proofs of protocols in a mathematically rigorous way. More specifically, one has to develop formal models and security notions such that the derived security guarantees of a protocol are sound and convincing. Most existing security definitions are property-based or game-based, which means that a protocol is secure if it fulfills a postulated set of requirements. While this approach seems fine at first sight, it has several drawbacks. The reason is that such properties are formulated with respect to an attacker with a defined set of capabilities. However, if a protocol is used in an application where an attacker has more influence than previously assumed, all proven guarantees turn out to be void.

A much better approach is to define security as a construction and in particular to specify what ideal system or module a cryptographic protocol achieves in any possible context. Turned around, any application can be assured that running the protocol is as if the ideal system was available in the first place. For example, a protocol for secure communication could be expected to emulate an ideal secure channel, i.e., a system that allows to transmit a message from a sender to a receiver and no one except for the intended recipient should learn the contents of the message. A security proof consists of showing that a protocol, based on certain assumptions, is indeed indistinguishable from the ideal system. Such proofs are typically quite involved and more complex than property-based proofs.

In this thesis, we follow the above methodology to study practically relevant cryptographic problems for which it is important to have clean security statements that hold in any possible context. This thesis contributes to the following areas:

In the realm of secure communication, we formulate which ideal systems are achieved by protocols that are based on symmetric primitives. We further show the limits of such protocols by showing that no protocol can perfectly emulate a secure channel only based on a shared secret key and insecure communication. We further extend our study to communication protocols that are based on public-key primitives.

In the realm of secure outsourced storage, we develop a novel framework to reason about the achieved security of data-outsourcing schemes. We show which ideal systems are desired and possible to achieve. We hereby observe that existing definitions are often weaker than what would be needed by applications and we show how to improve existing protocols to achieve a higher level of security.

In the context of digital signature schemes, we present a novel way to capture their security following the above methodology and prove that this novel view is equivalent to the standard game-based definition.

Finally, in the context of blockchain protocols, we show which ideal functionality is achieved by the Bitcoin blockchain. Since numerous emerging applications rely on the security provisions of blockchain protocols, identifying the ideal module which any such application can rely on is of great practical importance.

BibTeX Citation

@phdthesis{Badi18,
    author       = {Christian Badertscher},
    title        = {Idealizations of Practical Cryptographic Building Blocks},
    year         = {2018},
    school       = {ETH Zurich},
}

Files and Links