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 the Composability of Statistically Secure Bit Commitments.

Rafael Dowsley, Jeroen van de Graaf, Jörn Müller‐Quade, Anderson C. A. Nascimento

Published Jan 1, 2008• 2 citations
OpenAlex

Abstract

We show that for bit commitment schemes based on two-party stateless primitives, the stand-alone statistical security implies the statistical universally composable security. I.e. all such schemes are secure with an unlimited adversary, an unlimited simulator and an unlimited environment machine in the universal composability framework. Especially, these protocols can be used in arbitrary statistically secure applications without lowering the security.

Related papers

On the Composability of Statistically Secure Bit Commitments

Rafael Dowsley, Jeroen van de Graaf, Jörn Müller‐Quade +1 more

We show that for bit commitment schemes based on two-party stateless primitives, the stand-alone statistical security implies the statistical universally composable security. I.e., all such schemes are secure with an unlimited adversary, an unlimited simulator and an unlimited environment machine in the universal composability framework. Especially, these protocols can be used in arbitrary statistically secure applications without lowering the security.

網際網路技術學刊•May 1, 2013•14 citations

On the Composability of Statistically Secure Random Oblivious Transfer

Rafael Dowsley, Jörn Müller‐Quade, Anderson C. A. Nascimento

We show that random oblivious transfer protocols that are statistically secure according to a definition based on a list of information-theoretical properties are also statistically universally composable. That is, they are simulatable secure with an unlimited adversary, an unlimited simulator, and an unlimited environment machine. Our result implies that several previous oblivious transfer protocols in the literature that were proven secure under weaker, non-composable definitions of security can actually be used in arbitrary statistically secure applications without lowering the security.

arXiv:1808.10145•Entropy•Jan 16, 2020•3 citations

Long-term Security and Universal Composability.

Jörn Müller‐Quade, Dominique Unruh

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

•Jan 1, 2006•0 citations

Statistical Secrecy and Multi-Bit Commitments

Ivan Damgård, Torben Pryds Pedersen, Birgit Pfitzmann

We present and compare definitions of the notion of "statistically hiding" protocols, and we propose a novel statistically hiding commitment scheme. Informally, a protocol statistically hides a secret if a computationally unlimited adversary who conducts the protocol with the owner of the secret learns almost nothing about it. One definition is based on the L1-norm distance between probability distributions, the other on information theory. We prove that the two definitions are essentially equivalent. For completeness, we also show that statistical counterparts of definitions of computational secrecy are essentially equivalent to our main definitions. Commitment schemes are an important cryptologic primitive. Their purpose is to commit one party to a certain value, while hiding this value from the other party until some later time. We present a statistically hiding commitment scheme allowing commitment to many bits. The commitment and reveal protocols of this scheme are constant round, and the size of a commitment is independent of the number of bits committed to. This also holds for the total communication complexity, except of course for the bits needed to send the secret when it is revealed. The proof of the hiding property exploits the equivalence of the two definitions. Index terms -- Cryptology, Shannon theory, unconditional security, statistically hiding, multi-bit commitment, similarity of ensembles of distributions, zero-knowledge, protocols.

BRICS Report Series•Jun 15, 1996•13 citations

On minimal assumptions to obtain a universally composable quantum bit commitment

Mariano Lemus, Preeti Yadav, Paulo Mateus +2 more

It is well known, due to the no-go theorems, that perfectly secure bit commitment is impossible. For that reason, there exist many proposals for bit commitment protocols that are secure under certain assumptions (such as the existence of a trusted party, computational hardness, or noisy memories). In this paper, we investigate the minimal assumptions required to obtain a secure bit commitment protocol. We show that it is possible to construct a bit commitment scheme with two parties Alice and Bob as long as there is a third party that is willing to broadcast either entangled qubits for the parties or to produce classical strings that are xor-correlated. We also show that the bit commitment scheme proposed is universally composable.

International Conference on Transparent Optical Networks•Jul 1, 2019•3 citations

Statistical secrecy and multibit commitments

Ivan Damgård, Torben Pryds Pedersen, B. Pfitzmann

We present and compare definitions of "statistically hiding" protocols, and we propose a novel statistically hiding commitment scheme. Informally, a protocol statistically hides a secret if a computationally unlimited adversary who conducts the protocol with the owner of the secret learns almost nothing about it. One definition is based on the L/sub 1/-norm distance between probability distributions, the other on information theory. We prove that the two definitions are essentially equivalent. We also show that statistical counterparts of definitions of computational secrecy are essentially equivalent to our main definitions. Commitment schemes are an important cryptologic primitive. Their purpose is to commit one party to a certain value, while hiding this value from the other party until some later time. We present a statistically hiding commitment scheme allowing commitment to many bits. The commitment and reveal protocols of this scheme are constant-round, and the size of a commitment is independent of the number of bits committed to. This also holds for the total communication complexity, except of course for the bits needed to send the secret when it is revealed. The proof of the hiding property exploits the equivalence of the two definitions.

IEEE Transactions on Information Theory•May 1, 1998•67 citations
We show that for bit commitment schemes based on two-party stateless primitives, the stand-alone statistical security implies the statistical universally composable security. I.e. all such schemes are secure with an unlimited adversary, an unlimited simulator and an unlimited environment machine in the universal composability framework. Especially, these protocols can be used in arbitrary statistically secure applications without lowering the security.
We show that random oblivious transfer protocols that are statistically secure according to a definition based on a list of information-theoretical properties are also statistically universally composable. That is, they are simulatable secure with an unlimited adversary, an unlimited simulator, and an unlimited environment machine. Our result implies that several previous oblivious transfer protocols in the literature that were proven secure under weaker, non-composable definitions of security can actually be used in arbitrary statistically secure applications without lowering the security.
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
We present and compare definitions of the notion of "statistically hiding" protocols, and we propose a novel statistically hiding commitment scheme. Informally, a protocol statistically hides a secret if a computationally unlimited adversary who conducts the protocol with the owner of the secret learns almost nothing about it. One definition is based on the L1-norm distance between probability distributions, the other on information theory. We prove that the two definitions are essentially equivalent. For completeness, we also show that statistical counterparts of definitions of computational secrecy are essentially equivalent to our main definitions. Commitment schemes are an important cryptologic primitive. Their purpose is to commit one party to a certain value, while hiding this value from the other party until some later time. We present a statistically hiding commitment scheme allowing commitment to many bits. The commitment and reveal protocols of this scheme are constant round, and the size of a commitment is independent of the number of bits committed to. This also holds for the total communication complexity, except of course for the bits needed to send the secret when it is revealed. The proof of the hiding property exploits the equivalence of the two definitions. Index terms -- Cryptology, Shannon theory, unconditional security, statistically hiding, multi-bit commitment, similarity of ensembles of distributions, zero-knowledge, protocols.
It is well known, due to the no-go theorems, that perfectly secure bit commitment is impossible. For that reason, there exist many proposals for bit commitment protocols that are secure under certain assumptions (such as the existence of a trusted party, computational hardness, or noisy memories). In this paper, we investigate the minimal assumptions required to obtain a secure bit commitment protocol. We show that it is possible to construct a bit commitment scheme with two parties Alice and Bob as long as there is a third party that is willing to broadcast either entangled qubits for the parties or to produce classical strings that are xor-correlated. We also show that the bit commitment scheme proposed is universally composable.
We present and compare definitions of "statistically hiding" protocols, and we propose a novel statistically hiding commitment scheme. Informally, a protocol statistically hides a secret if a computationally unlimited adversary who conducts the protocol with the owner of the secret learns almost nothing about it. One definition is based on the L/sub 1/-norm distance between probability distributions, the other on information theory. We prove that the two definitions are essentially equivalent. We also show that statistical counterparts of definitions of computational secrecy are essentially equivalent to our main definitions. Commitment schemes are an important cryptologic primitive. Their purpose is to commit one party to a certain value, while hiding this value from the other party until some later time. We present a statistically hiding commitment scheme allowing commitment to many bits. The commitment and reveal protocols of this scheme are constant-round, and the size of a commitment is independent of the number of bits committed to. This also holds for the total communication complexity, except of course for the bits needed to send the secret when it is revealed. The proof of the hiding property exploits the equivalence of the two definitions.