Long-term security ensures that a protocol remains secure even in the future, when the adversarial computational power could, potentially, become unlimited. The notion of universal composability preserves the security of a cryptographic protocol when it is used in combination with any other protocols, in possibly complex systems. The area of long-term universally composable secure protocols has been developed mostly by Müller-Quade and Unruh. Their research conducted so far has shown the existence of secure long-term UC commitments under general cryptographic assumptions, thus without having an emphasis on the efficiency of the protocols designed. Building on their work and using very efficient zero-knowledge proofs of knowledge from [CL02], this thesis presents a new long-term universally composable secure commitment protocol that is both efficient and plausible to use in practice.
Long-term security ensures that a protocol remains secure even in the future, when the adversarial computational power could, potentially, become unlimited. The notion of universal composability preserves the security of a cryptographic protocol when it is used in combination with any other protocols, in possibly complex systems. The area of long-term universally composable secure protocols has been developed mostly by Müller-Quade and Unruh. Their research conducted so far has shown the existence of secure long-term UC commitments under general cryptographic assumptions, thus without having an emphasis on the efficiency of the protocols designed. Building on their work and using very efficient zero-knowledge proofs of knowledge from [CL02], this thesis presents a new long-term universally composable secure commitment protocol that is both efficient and plausible to use in practice.
Algorithmic progress and future technological advances threaten today’s cryptographic protocols. This may allow adversaries to break a protocol retrospectively by breaking the underlying complexity assumptions long after the execution of the protocol. Longterm secure protocols, protocols that after the end of the execution do not reveal any information to a then possibly unlimited adversary, could meet this threat. On the other hand, in many applications, it is necessary that a protocol is secure not only when executed alone, but within arbitrary contexts. The established notion of universal composability (UC) captures this requirement. This is the first paper to study protocols which are simultaneously long-term secure and universally composable. We show that the usual set-up assumptions used for UC protocols (e.g., a common reference string) are not sufficient to achieve long-term secure and composable protocols for commitments or zero-knowledge protocols. We give practical alternatives (e.g., signature cards) to these usual setupassumptions and show that these enable the implementation of the important primitives
Universal composability (or UC security) provides very strong security guarantees for protocols that run in complex real-world environments. In particular, security is guaranteed to hold when the protocol is run concurrently many times with other secure and possibly insecure protocols. Commitment schemes are a basic building block in many cryptographic constructions, and as such universally composable commitments are of great importance in constructing UC-secure protocols. In this paper, we construct highly efficient UC-secure commitments from the standard DDH assumption, in the common reference string model. Our commitment stage is non-interactive, has a common reference string with O(1) group elements, and has complexity of O(1) exponentiations for committing to a group element (to be more exact, the effective cost is that of 23 1 exponentiations overall, for both the commit and decommit stages). We present 3 a construction that is secure in the presence of static adversaries, and a construction that is secure in the presence of adaptive adversaries with erasures, where the latter construction has an effective additional cost of just 5 1 3 exponentiations. 1
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.
Abstract Everlasting security models the setting where hardness assumptions hold during the execution of a protocol but may get broken in the future. Due to the strength of this adversarial model, achieving any meaningful security guarantees for composable protocols is impossible without relying on hardware assumptions (Müller-Quade and Unruh, JoC’10). For this reason, a rich line of research has tried to leverage physical assumptions to construct well-known everlasting cryptographic primitives, such as commitment schemes. The only known everlastingly UC secure commitment scheme, due to Müller-Quade and Unruh (JoC’10), assumes honestly generated hardware tokens. The authors leave the possibility of constructing everlastingly UC secure commitments from malicious hardware tokens as an open problem. Goyal et al. (Crypto’10) constructs unconditionally UC-secure commitments and secure computation from malicious hardware tokens, with the caveat that the honest tokens must encapsulate other tokens. This extra restriction rules out interesting classes of hardware tokens, such as physically uncloneable functions (PUFs). In this work, we present the first construction of an everlastingly UC-secure commitment scheme in the fully malicious token modelwithout requiringhonest token encapsulation. Our scheme assumes the existence of PUFs and is secure in the common reference string model. We also show that our results are tight by giving an impossibility proof for everlasting UC-securecomputationfrom non-erasable tokens (such as PUFs), even with trusted setup.
Abstract. Zero-knowledge proofs of knowledge (ZK-PoK) for discrete logarithms and related problems are indispensable for practical cryptographic protocols. At Eurocrypt 2009, Camenisch, Kiayias, and Yung provided a specification language (the CKY-language) for such protocols, which allows one to modularly design and analyze cryptographic protocols: protocol designers just need to specify the statement they want to prove in zero-knowledge and are ensured that an efficient proof protocol exists and indeed proves the specified statement, provided that the specification was in the CKY-language. However, as specifications in the CKY-language are realized by so-called Σ-protocols, the resulting protocols only satisfy the classical notion of zero-knowledge proofs of knowledge, which not retained if they are composed with themselves or with other protocols, e.g., when used as building blocks for higher-level applications. This problem can be tackled by moving to the Universal Composability (UC) framework, which guarantees retention of security when composing protocols and, in particular, when using them as building blocks in arbitrary contexts. While there exists generic transformations from Σ-protocols to protocols that are secure under this stronger security notion, these transformation are often not efficient enough for the design of practical protocols. In this paper we are aiming for practically efficient ZK-PoK in the UC-framework by introducing
We propose a modification to the framework of Universally Composable (UC) security [3]. Our new notion, involves comparing the protocol executions with an ideal execution involving ideal functionalities (just as in UC-security), but allowing the environment and adversary access to some super-polynomial computational power. We argue the meaningfulness of the new notion, which in particular subsumes many of the traditional notions of security. We generalize the Universal Composition theorem of [3] to the new setting. Then under new computational assumptions, we realize secure multi-party computation (for static adversaries) without a common reference string or any other set-up assumptions, in the new framework. This is known to be impossible under the UC framework. 1