Recently, in the research field of cryptography, owing to complications on evolutions of newprotocols security proofs of these protocols have become challenging and difficult tasks. Thisdissertation focuses on simplifications of security proofs for cryptographic protocols with twoapproaches.One is constructing protocols which satisfy universally composable security. The universalcomposition (UC) framework provides strong and robust secure composability, i.e., the securityof a component protocol (primitive) which is UC secure in a stand-alone manner will alwaysbe preserved even when it is executed concurrently with other unbounded number of UC secureprimitives in an adversarial controlled manner. In this dissertation, we propose a ring signaturescheme which is an anonymous signature scheme and prove that the scheme satisfies universallycomposable security. By using our protocol we are able to ease the burden of security proofsfor an anonymous message authentication protocol which is constructed by composing with ringsignature.The other is automated or mechanizing security proofs based on formal methods by investigatingthe symbolic proof method. Though a framework in order to make mechanizing securityproofs for protocols based on computationally hardness assumptions was proposed in the previousstudy, there exists a problem that application methods for important protocols are unknownfor lack of case studies. In this dissertation, we propose applications to some important protocols(digital signature and key exchange) and show that mechanizing security proofs are possible.These two approaches enable to reduce costs of security proofs for new protocols respectively.
Recently, in the research field of cryptography, owing to complications on evolutions of newprotocols security proofs of these protocols have become challenging and difficult tasks. Thisdissertation focuses on simplifications of security proofs for cryptographic protocols with twoapproaches.One is constructing protocols which satisfy universally composable security. The universalcomposition (UC) framework provides strong and robust secure composability, i.e., the securityof a component protocol (primitive) which is UC secure in a stand-alone manner will alwaysbe preserved even when it is executed concurrently with other unbounded number of UC secureprimitives in an adversarial controlled manner. In this dissertation, we propose a ring signaturescheme which is an anonymous signature scheme and prove that the scheme satisfies universallycomposable security. By using our protocol we are able to ease the burden of security proofsfor an anonymous message authentication protocol which is constructed by composing with ringsignature.The other is automated or mechanizing security proofs based on formal methods by investigatingthe symbolic proof method. Though a framework in order to make mechanizing securityproofs for protocols based on computationally hardness assumptions was proposed in the previousstudy, there exists a problem that application methods for important protocols are unknownfor lack of case studies. In this dissertation, we propose applications to some important protocols(digital signature and key exchange) and show that mechanizing security proofs are possible.These two approaches enable to reduce costs of security proofs for new protocols respectively.
The Universal Composability (UC) framework provides provable security guaranties for harsh application environment, where we want to construct protocols which keep security guarantees even when they are concurrently composed with arbitrary number of arbitrary (even hostile) protocols.This is a very strong guarantee.The UC-framework inherently supports the modular design, which allows secure composition of arbitrary number of UC-secure components with an arbitrary protocol.In contrast, traditional analysis and design is a stand alone analysis where security of a single instance is considered, i.e. an instance which is not in potential interaction with any concurrent instances.Furthermore, a typical traditional analysis is informal, i.e. without a formal proof.In spite of these facts, beyond the task of key-exchange this technology have not really took the attention of the community of applied cryptography.From practitioner's point of view the UC-world may seem more or less an academic interest of theoretical cryptographers.Accordingly we take a pragmatic approach, where we concentrate on meaningful compromises between the assumed adversarial strength, ideality wishes and realization complexity while keeping provable security guarantees within the UC-framework.We believe that even modest but provable goals (especially, if tunable to application scenarios) are interesting if a wider penetration of the UC-technology is desired into the daily-practice of protocol applications.
We propose a novel paradigm for defining security of cryptographic protocols, called universally composable security. The salient property of universally composable definitions of security is that they guarantee security even when a secure protocol is composed of an arbitrary set of protocols, or more generally when the protocol is used as a component of an arbitrary system. This is an essential property for maintaining security of cryptographic protocols in complex and unpredictable environments such as the Internet. In particular, universally composable definitions guarantee security even when an unbounded number of protocol instances are executed concurrently in an adversarially controlled manner, they guarantee non-malleability with respect to arbitrary protocols, and more. We show how to formulate universally composable definitions of security for practically any cryptographic task. Furthermore, we demonstrate that practically any such definition can be realized using known techniques, as long as only a minority of the participants are corrupted. We then proceed to formulate universally composable definitions of a wide array of cryptographic tasks, including authenticated and secure communication, key-exchange, public-key encryption, signature, commitment, oblivious transfer, zero knowledge and more. We also make initial steps towards studying the realizability of the proposed definitions in various settings.
The universally composable symbolic analysis (UCSA) framework layers Dolev-Yao style symbolic analysis on top of the universally composable (UC) secure framework to construct computationally sound proofs of cryptographic protocol security. The original proposal of the UCSA framework by Canetti and Herzog (2004) focused on protocols that only use public key encryption to achieve 2-party mutual authentication or key exchange. This thesis expands the framework to include protocols that use digital signatures as well. In the process of expanding the framework, we identify a flaw in the framework’s use of UC ideal functionality Fpke. We also identify issues that arise when combining Fpke with the current formulation of ideal signature functionality Fsig. Motivated by these discoveries, we redefine the Fpke and Fsig functionalities appropriately. Thesis Supervisor: Ronald L. Rivest Title: Viterbi Professor of Computer Science Thesis Supervisor: Ran Canetti Title: Visiting Scientist
Recently some efforts were made towards capturing the security requirements from digital signature schemes as an ideal functionality within a composable security framework. This modeling of digital signatures potentially has some significant analytical advantages (such as enabling component-wise analysis of complex systems that use signature schemes, as well as symbolic and automatable analysis of such systems). However, it turns out that formulating ideal functionalities that capture the properties expected from signature schemes in a way that is both sound and enjoys the above advantages is not a trivial task. This work has several contributions. We first correct some flaws in the definition of the ideal signature functionality of Canetti, 2001, and subsequent formulations. Next we provide a minimal formalization of “ideal certification authorities ” and show how authenticated communication can be obtained using ideal signatures and an ideal certification authority. This is done while guaranteeing full modularity (i.e., each component is analyzed as stand-alone), and in an unconditional and errorless way. This opens the door to symbolic and automated analysis of protocols for these tasks, in a way that is both modular and cryptographically sound.
Recently some efforts were made towards capturing the security requirements from digital signature schemes as an ideal functionality within a composable security framework. This modeling of digital signatures potentially has some significant analytical advantages (such as enabling component-wise analysis of complex systems that use signature schemes, as well as symbolic and automatable analysis of such systems). However, it turns out that formulating ideal functionalities that capture the properties expected from signature schemes in a way that is both sound and enjoys the above advantages is not a trivial task. This work has several contributions. We first correct some flaws in the definition of the ideal signature functionality of Canetti, 2001, and subsequent formulations. Next we provide a minimal formalization of "ideal certification authorities" and show how authenticated communication can be obtained using ideal signatures and an ideal certification authority. This is done while guaranteeing full modularity (i.e., each component is analyzed as stand-alone), and in an unconditional and errorless way. This opens the door to symbolic and automated analysis of protocols for these tasks, in a way that is both modular and cryptographically sound.
In this paper, we present a simpler and more restricted variant of the universally composable security (UC) framework that is suitable for “standard ” two-party and multiparty computation tasks. Many of the complications of the UC framework exist in order to enable more general tasks than classic secure computation. This generality may be a barrier to entry for those who are used to the stand-alone model of secure computation and wish to work with universally composable security but are overwhelmed by the differences. The variant presented here (called simplified universally composable security, or just SUC) is closer to the definition of security for multiparty computation in the stand-alone setting. The main difference is that a protocol in the SUC framework runs with a fixed set of parties who know each other’s identities ahead of time, and machines cannot be added dynamically to the execution. As a result, the definitions of polynomial time and protocol composition are much simpler. In addition, the SUC framework has authenticated channels built in, as is standard in previous definitions of security, and all communication is done via the adversary in order to enable arbitrary scheduling of messages. Due to these differences, not all cryptographic tasks can be expressed in the SUC framework.