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

On Universal Composable Security of Time-Stamping Protocols

Toshihiko Matsuo, Shin’ichiro Matsuo

Published Jan 1, 2005• 7 citations
OpenAlex

Abstract

Abstract. Time-stamping protocols, which assure that a document was existed at a certain time, are applied to some useful and practical applications such as electronic patent applications and so on. There are two major time-stamping protocols, the simple protocol and the linking protocol. In the former, a time-stamp authority issues a time-stamp token that is the digital signature of the concatenated value of a hashed message and the present time. In the latter, the time-stamp authority issues a time-stamp token that is the hash value of the concatenated value of a hashed message and the previous hash value. Although security requirements and analysis for above time-stamping protocols has been discussed, there are no strict cryptographic security notions for them. In this paper, we reconsider the security requirements for timestamping protocols and define security notions for them, in a universally composable security sense, which was proposed by Canetti. We also show that these notions can be achieved using combinations of a secure key exchange protocol, a secure symmetric encryption scheme, and a secure digital signature scheme.

Related papers

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 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.

IEEE Computer Security Foundations Workshop (CSFW)•Nov 12, 2004•90 citations

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 security: a new paradigm for cryptographic protocols

Ran Canetti

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.

Annual Symposium on Foundations of Computer Science•Jan 1, 2001•3,416 citations

Simplifications of security proofs for cryptographic protocols

一樹 米山

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.

•Jan 1, 2008•0 citations

Quantum-Secure Timestamp for the Integrity of Classical Signatures in Quantum Transition

Kyu-Hyun Kang, Nam-Su Jho, Taek-Young Youn

As the development of quantum computers becomes a reality, concerns about the security of classical cryptography are growing. In the case of signature schemes, integrity must be guaranteed for a sufficient period of time after their generation. However, during the transition to the post-quantum era, it is difficult to guarantee the integrity of signatures previously generated using classical cryptography. In this paper, we design a quantum-secure timestamp that is secure even in the quantum era, utilizing a Time Stamping Authority, even for general users who cannot use post-quantum signatures, and we propose a transformation technique to enhance the security of classical signatures. Also, we focus on the security of classical signatures and the generation of hybrid signatures in the specific context of the transition between classical and post-quantum environments by defining the transition point based on quantum resistance. Finally, we analyze the security and performance of our timestamp scheme and demonstrate that it can guarantee the integrity of signed messages both now and in the post-quantum era.

IEEE Access•Jan 1, 2026•0 citations
Abstract. Time-stamping protocols, which assure that a document was existed at a certain time, are applied to some useful and practical applications such as electronic patent applications and so on. There are two major time-stamping protocols, the simple protocol and the linking protocol. In the former, a time-stamp authority issues a time-stamp token that is the digital signature of the concatenated value of a hashed message and the present time. In the latter, the time-stamp authority issues a time-stamp token that is the hash value of the concatenated value of a hashed message and the previous hash value. Although security requirements and analysis for above time-stamping protocols has been discussed, there are no strict cryptographic security notions for them. In this paper, we reconsider the security requirements for timestamping protocols and define security notions for them, in a universally composable security sense, which was proposed by Canetti. We also show that these notions can be achieved using combinations of a secure key exchange protocol, a secure symmetric encryption scheme, and a secure digital signature scheme.
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.
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.
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.
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.
As the development of quantum computers becomes a reality, concerns about the security of classical cryptography are growing. In the case of signature schemes, integrity must be guaranteed for a sufficient period of time after their generation. However, during the transition to the post-quantum era, it is difficult to guarantee the integrity of signatures previously generated using classical cryptography. In this paper, we design a quantum-secure timestamp that is secure even in the quantum era, utilizing a Time Stamping Authority, even for general users who cannot use post-quantum signatures, and we propose a transformation technique to enhance the security of classical signatures. Also, we focus on the security of classical signatures and the generation of hybrid signatures in the specific context of the transition between classical and post-quantum environments by defining the transition point based on quantum resistance. Finally, we analyze the security and performance of our timestamp scheme and demonstrate that it can guarantee the integrity of signed messages both now and in the post-quantum era.