Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

IEEE Computer Security Foundations Workshop (CSFW)

Universally composable signature, certification, and authentication

Ran Canetti

Published Nov 12, 2004• 90 citations
Publisher

Abstract

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.

DOI
10.1109/csfw.2004.1310743

Related papers

Universally composable signature, certification, and authentication

Ran Canetti

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.

•Jun 28, 2004•168 citations

Universally Composable Signatures, Certification and Authentication

Ran Canetti

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. ∗An extended abstract of this work appears in the proceedings of the 17th Computer Security Foundations Workshop (CSFW). This is a slightly corrected version. The first version of this paper, which dates November 18 2003, contained by mistake the date November 16, 2004 on its title page. †IBM T.J. Watson Research Center. Email: canetti@watson.ibm.com.

•Jan 1, 2003•41 citations

Universally Composable Authentication and Key-exchange with Global PKI

Ran Canetti, Daniel Shahaf, Margarita Vald

Message authentication and key exchange are two of the most basic tasks of cryptography. Solutions based on public-key infrastructure (PKI) are prevalent. Still, the state of the art in composable security analysis of PKI-based authentication and key exchange is somewhat unsatisfactory. Specifically, existing treatments either (a) make the unrealistic assumption that the PKI is accessible only within the confines of the protocol itself, thus failing to capture real-world PKI-based authentication, or (b) impose oftenunnecessary requirements—such as strong on-line non-transferability—on candidate protocols, thus ruling out natural candidates. We give a modular and universally composable analytical framework for PKI-based message authentication and key exchange protocols. This framework guarantees security even when the PKI is pre-existing and globally available, without being unnecessarily restrictive. Specifically, we model PKI as a global set-up functionality within the Global UC security model [Canetti et al., TCC 2007] and relax the ideal authentication and key exchange functionalities accordingly. We then demonstrate the security of basic signature-based authentication and key exchange protocols. Our modeling makes minimal security assumptions on the PKI in use; in particular, “knowledge of the secret key” is not needed.

•Jan 1, 2014•2 citations

Composable Authentication with Global PKI.

Ran Canetti, Daniel Shahaf, Margarita Vald

Message authentication is one of the most basic tasks of cryptography, and authentication based on public-key infrastructure (PKI) is one of the most prevalent methods for message and entity authentication. Still, the state of the art in composable security analysis of PKI-based authentication is somewhat unsatisfactory. Specifically, existing treatments either (a) make the unrealistic assumption that the PKI is accessible only within the confines of the authentication protocol itself, thus failing to capture real-world PKI-based authentication, or (b) impose often-unnecessary requirements—such as strong on-line non-transferability—on candidate protocols, thus ruling out natural candidates. We give a modular and composable analytical framework for PKI-based message authentication protocols. This framework guarantees security even when the PKI is pre-existing and globally available, without being unnecessarily restrictive. Specifically, we model PKI as a global set-up functionality within the Global UC security model [Canetti et al., TCC 2007] and relax the ideal authentication functionality accordingly. We then demonstrate the security of a simple signature-based authentication protocol. Our modeling makes minimal security assumptions on the PKI in use; in particular, “knowledge of the secret

•Jan 1, 2014•1 citation

On symbolic analysis of cryptographic protocols

Akshay Patil

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

•Jan 1, 2005•13 citations

Sound and Fine-grain Specification of Ideal Functionalities

Juan A. Garay, Aggelos Kiayias, Hong-Sheng Zhou

Nowadays it is widely accepted to formulate the security of a protocol carrying out a given task via the "trusted-party paradigm," where the protocol execution is compared with an ideal process where the outputs are computed by a trusted party that sees all the inputs. A protocol is said to securely carry out a given task if running the protocol with a realistic adversary amounts to "emulating" the ideal process with the appropriate trusted party. In the Universal Composability (UC) framework the program run by the trusted party is called an ideal functionality. While this simulation-based security formulation provides strong security guarantees, its usefulness is contingent on the properties and correct specification of the ideal functionality, which, as demonstrated in recent years by the coexistence of complex, multiple functionalities for the same task as well as by their "unstable" nature, does not seem to be an easy task. In this paper we address this problem, by introducing a general methodology for the sound specification of ideal functionalities. First, we introduce the class of canonical ideal functionalities for a cryptographic task, which unifies the syntactic specification of a large class of cryptographic tasks under the same basic template functionality. Furthermore, this representation enables the isolation of the individual properties of a cryptographic task as separate members of the corresponding class. By endowing the class of canonical functionalities with an algebraic structure we are able to combine basic functionalities to a single final canonical functionality for a given task. Effectively, this puts forth a bottom-up approach for the specification of ideal functionalities: first one defines a set of basic constituent functionalities for the task at hand, and then combines them into a single ideal functionality taking advantage of the algebraic structure. In our framework, the constituent functionalities of a task can be derived either directly or, following a translation strategy we introduce, from existing game-based definitions; such definitions have in many cases captured desired individual properties of cryptographic tasks, albeit in less adversarial settings than universal composition. Our translation methodology entails a sequence of steps that derive a corresponding canonical functionality given a game-based definition. In this way, we obtain a well-defined mapping of game-based security properties to their corresponding UC counterparts. Finally, we demonstrate the power of our approach by applying our methodology to a variety of basic cryptographic tasks, including commitments, digital signatures, zero-knowledge proofs, and oblivious transfer. While in some cases our derived canonical functionalities are equivalent to existing formulations, thus attesting to the validity of our approach, in others they differ, enabling us to "debug" previous definitions and pinpoint their shortcomings.

•Jan 1, 2009•0 citations
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.
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. ∗An extended abstract of this work appears in the proceedings of the 17th Computer Security Foundations Workshop (CSFW). This is a slightly corrected version. The first version of this paper, which dates November 18 2003, contained by mistake the date November 16, 2004 on its title page. †IBM T.J. Watson Research Center. Email: canetti@watson.ibm.com.
Message authentication and key exchange are two of the most basic tasks of cryptography. Solutions based on public-key infrastructure (PKI) are prevalent. Still, the state of the art in composable security analysis of PKI-based authentication and key exchange is somewhat unsatisfactory. Specifically, existing treatments either (a) make the unrealistic assumption that the PKI is accessible only within the confines of the protocol itself, thus failing to capture real-world PKI-based authentication, or (b) impose oftenunnecessary requirements—such as strong on-line non-transferability—on candidate protocols, thus ruling out natural candidates. We give a modular and universally composable analytical framework for PKI-based message authentication and key exchange protocols. This framework guarantees security even when the PKI is pre-existing and globally available, without being unnecessarily restrictive. Specifically, we model PKI as a global set-up functionality within the Global UC security model [Canetti et al., TCC 2007] and relax the ideal authentication and key exchange functionalities accordingly. We then demonstrate the security of basic signature-based authentication and key exchange protocols. Our modeling makes minimal security assumptions on the PKI in use; in particular, “knowledge of the secret key” is not needed.
Message authentication is one of the most basic tasks of cryptography, and authentication based on public-key infrastructure (PKI) is one of the most prevalent methods for message and entity authentication. Still, the state of the art in composable security analysis of PKI-based authentication is somewhat unsatisfactory. Specifically, existing treatments either (a) make the unrealistic assumption that the PKI is accessible only within the confines of the authentication protocol itself, thus failing to capture real-world PKI-based authentication, or (b) impose often-unnecessary requirements—such as strong on-line non-transferability—on candidate protocols, thus ruling out natural candidates. We give a modular and composable analytical framework for PKI-based message authentication protocols. This framework guarantees security even when the PKI is pre-existing and globally available, without being unnecessarily restrictive. Specifically, we model PKI as a global set-up functionality within the Global UC security model [Canetti et al., TCC 2007] and relax the ideal authentication functionality accordingly. We then demonstrate the security of a simple signature-based authentication protocol. Our modeling makes minimal security assumptions on the PKI in use; in particular, “knowledge of the secret
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
Nowadays it is widely accepted to formulate the security of a protocol carrying out a given task via the "trusted-party paradigm," where the protocol execution is compared with an ideal process where the outputs are computed by a trusted party that sees all the inputs. A protocol is said to securely carry out a given task if running the protocol with a realistic adversary amounts to "emulating" the ideal process with the appropriate trusted party. In the Universal Composability (UC) framework the program run by the trusted party is called an ideal functionality. While this simulation-based security formulation provides strong security guarantees, its usefulness is contingent on the properties and correct specification of the ideal functionality, which, as demonstrated in recent years by the coexistence of complex, multiple functionalities for the same task as well as by their "unstable" nature, does not seem to be an easy task. In this paper we address this problem, by introducing a general methodology for the sound specification of ideal functionalities. First, we introduce the class of canonical ideal functionalities for a cryptographic task, which unifies the syntactic specification of a large class of cryptographic tasks under the same basic template functionality. Furthermore, this representation enables the isolation of the individual properties of a cryptographic task as separate members of the corresponding class. By endowing the class of canonical functionalities with an algebraic structure we are able to combine basic functionalities to a single final canonical functionality for a given task. Effectively, this puts forth a bottom-up approach for the specification of ideal functionalities: first one defines a set of basic constituent functionalities for the task at hand, and then combines them into a single ideal functionality taking advantage of the algebraic structure. In our framework, the constituent functionalities of a task can be derived either directly or, following a translation strategy we introduce, from existing game-based definitions; such definitions have in many cases captured desired individual properties of cryptographic tasks, albeit in less adversarial settings than universal composition. Our translation methodology entails a sequence of steps that derive a corresponding canonical functionality given a game-based definition. In this way, we obtain a well-defined mapping of game-based security properties to their corresponding UC counterparts. Finally, we demonstrate the power of our approach by applying our methodology to a variety of basic cryptographic tasks, including commitments, digital signatures, zero-knowledge proofs, and oblivious transfer. While in some cases our derived canonical functionalities are equivalent to existing formulations, thus attesting to the validity of our approach, in others they differ, enabling us to "debug" previous definitions and pinpoint their shortcomings.