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

arXiv:0811.3589 · IEEE Transactions on Information Theory

Bit Commitment From Nonsignaling Correlations

Severin Winkler, Jürg Wullschleger, Stefan Wolf

Published Feb 18, 2011• 3 citations
arXivHTMLPDF

Abstract

Central cryptographic functionalities such as encryption, authentication, or secure two-party computation cannot be realized in an information-theoretically secure way from scratch. This serves as a motivation to study what (possibly weak) primitives they can be based on. We consider as such starting points general two-party input-output systems that do not allow for message transmission and show that they can be used for realizing unconditionally secure bit commitment as soon as they are nontrivial, i.e., cannot be securely realized from distributed randomness only.

DOI
10.1109/tit.2011.2104471

Related papers

Bit Commitment from Non-Local Correlations

Severin Winkler, Stefan Wolf, Juerg Wullschleger

Central cryptographic functionalities such as encryption, authentication, or secure two-party computation cannot be realized in an information-theoretically secure way from scratch. This serves as a motivation to study what (possibly weak) primitives they can be based on. We consider as such starting points general two-party input-output systems that do not allow for message transmission, and show that they can be used for realizing unconditionally secure bit commitment as soon as they are non-trivial, i.e., cannot be realized from distributed randomness only. In particular, our result implies that any twoqubit state without hidden-variable model has an input-output behavior allowing for unconditional bit commitment.

•Nov 21, 2008•1 citation

New Monotones and Lower Bounds in Unconditional Two-Party Computation

Stefan Wolf, Jürg Wullschleger

Since oblivious transfer, a primitive of paramount importance in secure two- and multiparty computation, cannot be realized in an unconditionally secure way for both parties from scratch, reductions to weak information-theoretic primitives as well as between different variants of the functionality are of great interest. In this context, various monotones-quantities that cannot be increased by any protocol-are introduced and then used to derive lower bounds on the possibility and efficiency of such reductions.

IEEE Transactions on Information Theory•May 29, 2008•34 citations

Bit commitment from weak non-locality

Stefan Wolf, Jürg Wullschleger

So-called non-local boxes, which have been introduced as an idealizationndifferent respects - of the behavior of entangled quantum states, have been known to allow for unconditional bit commitment between the two involved parties. We show that, actually, any possible non-local correlation which produces random bits on both sides can be used to implement bit commitment, and that this holds even when the parties are allowed to delay their inputs to the box. Since a particular example is the behavior of an EPR pair, this resource allows for implementing unconditionally secure bit commitment as long as the parties cannot entangle their Qbits with any other system

IEEE Information Theory Workshop (ITW)•Dec 10, 2005•3 citations

Bit Commitment from Weak Non-Locality

Stefan Wolf, Juerg Wullschleger

So-called non-local boxes, which have been introduced as an idealization-in different respects-of the behavior of entangled quantum states, have been known to allow for unconditional bit commitment between the two involved parties. We show that, actually, any possible non-local correlation which produces random bits on both sides can be used to implement bit commitment, and that this holds even when the parties are allowed to delay their inputs to the box. Since a particular example is the behavior of an EPR pair, this resource allows for implementing unconditionally secure bit commitment as long as the parties cannot entangle their Qbits with any other system.

arXiv:quant-ph/0508233•Aug 31, 2005•1 citation

Cryptography without one-way functions

Dima Yu. Grigoriev, Vladimir Shpilrain

We show that some problems in cryptography can be solved without using one-way functions. The latter are usually regarded as a central concept of cryptography, but the very existence of one-way functions depends on difficult conjectures in complexity theory, most notably on the notorious “P ̸ = NP ” conjecture. This is why cryptographic primitives that do not employ one-way functions are often called “unconditionally secure”. In this paper, we suggest protocols for secure computation of the sum, product, and some other functions of two or more elements of an arbitrary constructible ring, without using any one-way functions. A new input that we offer here is that, in contrast with other proposals, we conceal “intermediate results ” of a computation. For example, when we compute the sum of k numbers, only the final result is known to (one of) the parties; partial sums are not known to anybody. Other applications of our method include voting/rating over insecure channels and a rather elegant and efficient solution of the “two millionaires problem”. While it is fairly obvious that a secure (bit) commitment between two parties is

•Jan 1, 2011•0 citations

An elementary completeness proof for secure two-party computation primitives

Ye Wang, Prakash Ishwar, Shantanu D. Rane

In the secure two-party computation problem, two parties wish to compute a (possibly randomized) function of their inputs via an interactive protocol, while ensuring that neither party learns more than what can be inferred from only their own input and output. For semi-honest parties and information-theoretic security guarantees, it is well-known that, if only noise-less communication is available, only a limited set of functions can be securely computed; however, if interaction is also allowed over general communication primitives (multi-input/output channels), there are “complete” primitives that enable any function to be securely computed. The general set of complete primitives was characterized recently by Maji, Prabhakaran, and Rosulek leveraging an earlier specialized characterization by Kilian. Our contribution in this paper is a simple, self-contained, alternative derivation using elementary information-theoretic tools.

arXiv:1402.4360•IEEE Information Theory Workshop (ITW)•Nov 1, 2014•0 citations
Central cryptographic functionalities such as encryption, authentication, or secure two-party computation cannot be realized in an information-theoretically secure way from scratch. This serves as a motivation to study what (possibly weak) primitives they can be based on. We consider as such starting points general two-party input-output systems that do not allow for message transmission and show that they can be used for realizing unconditionally secure bit commitment as soon as they are nontrivial, i.e., cannot be securely realized from distributed randomness only.
Central cryptographic functionalities such as encryption, authentication, or secure two-party computation cannot be realized in an information-theoretically secure way from scratch. This serves as a motivation to study what (possibly weak) primitives they can be based on. We consider as such starting points general two-party input-output systems that do not allow for message transmission, and show that they can be used for realizing unconditionally secure bit commitment as soon as they are non-trivial, i.e., cannot be realized from distributed randomness only. In particular, our result implies that any twoqubit state without hidden-variable model has an input-output behavior allowing for unconditional bit commitment.
Since oblivious transfer, a primitive of paramount importance in secure two- and multiparty computation, cannot be realized in an unconditionally secure way for both parties from scratch, reductions to weak information-theoretic primitives as well as between different variants of the functionality are of great interest. In this context, various monotones-quantities that cannot be increased by any protocol-are introduced and then used to derive lower bounds on the possibility and efficiency of such reductions.
So-called non-local boxes, which have been introduced as an idealizationndifferent respects - of the behavior of entangled quantum states, have been known to allow for unconditional bit commitment between the two involved parties. We show that, actually, any possible non-local correlation which produces random bits on both sides can be used to implement bit commitment, and that this holds even when the parties are allowed to delay their inputs to the box. Since a particular example is the behavior of an EPR pair, this resource allows for implementing unconditionally secure bit commitment as long as the parties cannot entangle their Qbits with any other system
So-called non-local boxes, which have been introduced as an idealization-in different respects-of the behavior of entangled quantum states, have been known to allow for unconditional bit commitment between the two involved parties. We show that, actually, any possible non-local correlation which produces random bits on both sides can be used to implement bit commitment, and that this holds even when the parties are allowed to delay their inputs to the box. Since a particular example is the behavior of an EPR pair, this resource allows for implementing unconditionally secure bit commitment as long as the parties cannot entangle their Qbits with any other system.
We show that some problems in cryptography can be solved without using one-way functions. The latter are usually regarded as a central concept of cryptography, but the very existence of one-way functions depends on difficult conjectures in complexity theory, most notably on the notorious “P ̸ = NP ” conjecture. This is why cryptographic primitives that do not employ one-way functions are often called “unconditionally secure”. In this paper, we suggest protocols for secure computation of the sum, product, and some other functions of two or more elements of an arbitrary constructible ring, without using any one-way functions. A new input that we offer here is that, in contrast with other proposals, we conceal “intermediate results ” of a computation. For example, when we compute the sum of k numbers, only the final result is known to (one of) the parties; partial sums are not known to anybody. Other applications of our method include voting/rating over insecure channels and a rather elegant and efficient solution of the “two millionaires problem”. While it is fairly obvious that a secure (bit) commitment between two parties is
In the secure two-party computation problem, two parties wish to compute a (possibly randomized) function of their inputs via an interactive protocol, while ensuring that neither party learns more than what can be inferred from only their own input and output. For semi-honest parties and information-theoretic security guarantees, it is well-known that, if only noise-less communication is available, only a limited set of functions can be securely computed; however, if interaction is also allowed over general communication primitives (multi-input/output channels), there are “complete” primitives that enable any function to be securely computed. The general set of complete primitives was characterized recently by Maji, Prabhakaran, and Rosulek leveraging an earlier specialized characterization by Kilian. Our contribution in this paper is a simple, self-contained, alternative derivation using elementary information-theoretic tools.