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 Access

Information-Theoretically Secure String Commitments Based on Packet Reordering Channels

Vinícius de Morais Alves, Rafael Dowsley, Rafael T. de Sousa, Anderson C. A. Nascimento

Published Jan 1, 2021• 0 citations
Publisher

Abstract

Realizing fundamental cryptographic primitives with unconditional security is a central topic in information-theoretic cryptography. These primitives can be realized based on physical assumptions, such as the existence of noisy channels, an upper bound on the storage capacity, or the laws of quantum mechanics. Palmieri and Pereira [1] demonstrated that delays in communication channels can be used as a reasonable and effective assumption to obtain an unconditionally secure oblivious transfer protocol against honest-but-curious adversaries. While any oblivious transfer protocol secure against malicious adversaries can be used to implement commitment, the reduction does not work if the oblivious transfer protocol is only secure against honest-but-curious adversaries. Thus, the question of obtaining a secure commitment protocol based on channel delays is still open. In this paper, we provide a concrete protocol for implementing string commitments based on packet reordering – a consequence of channel delays in packet networks.

DOI
10.1109/access.2021.3118959

Related papers

String commitment from unstructured noise

Jiawei Wu, Masahito Hayashi, Marco Tomamichel

Noisy channels are a foundational resource for constructing cryptographic primitives such as string commitment and oblivious transfer. The noisy channel model has been extended to unfair noisy channels, where adversaries can influence the parameters of a memoryless channel. In this work, we introduce the unstructured noisy channel model as a generalization of the unfair noisy channel model to allow the adversary to manipulate the channel arbitrarily subject to certain entropic constraints. We present a string commitment protocol with established security and derive its achievable commitment rate, demonstrating the feasibility of commitment against this stronger class of adversaries. Furthermore, we show that the entropic constraints in the unstructured noisy channel model can be derived from physical assumptions such as noisy quantum storage. Our work thus connects two distinct approaches to commitment, i.e., the noisy channel and physical limitations.

arXiv:2501.00281•Dec 31, 2024•1 citation

Unconditional secure cooperation on real-world networks : the case of oblivious transfer

Paolo Palmieri

Historically, cryptography was created and used to deliver messages between people in such a way that only the intended receiver would be able to read them. The two persons communicating trusted each other, but not the rest of the world - for instance, not the message bearer. But what happens if we assume instead that even the receiver of a message may not be trusted by the sender, while both still have an interest in communicating? This problem is addressed by secure multi-party computation, that studies communication and shared computation between mutually distrusting parties. In a world where most of the communication happens over the Internet, and where an ever-increasing amount of computation is outsourced, for example to the cloud, multi-party computation is a subject of crucial importance. However, unconditionally secure multi-party protocols have never found practical application: the lack of realistic noisy channel models, that are required to achieve security against computationally unbounded adversaries, prevents implementation over real-world, standard communication protocols.\n\nIn this thesis, we study the properties and characteristics of noisy channels, and we introduce new models based on real-world error sources that have never been studied in this context, such as delays. On the contrary, previous works mostly focused on theoretical noisy channels that have little in common with the reality of network communication. We show that the models we propose are suitable for multi-party computation by building on each of them a protocol for oblivious transfer, a fundamental cryptographic primitive that implies any secure computation. Thanks to the realism of our noisy channels, we are able to provide the first working implementation of unconditionally secure oblivious transfer over both wired and wireless networks and different Internet protocols, which we test thoroughly in an extensive set of experiments. Our constructions are not only more realistic, but also more flexible, as they allow larger ranges of error probabilities. This will eventually open the way for the widespread use of unconditionally secure multi-party computation.

•Jan 1, 2013•0 citations

Quantum Key Distribution and String Oblivious Transfer in Noisy Channels

Dominic R ayers

We prove the unconditional security of a quantum key distribution (QKD) protocol on a noisy channel against the most general attack allowed by quantum physics. We use the fact that in a previous paper we have reduced the proof of the unconditionally security of this QKD protocol to a proof that a corresponding Quantum String Oblivious Transfer (String-QOT) protocol would be unconditionally secure against Bob if implemented on top of an unconditionally secure bit commitment schcmc. We prove a lemma that extends a security proof given by Yao for a (one bit) QOT protocol to this String-QOT protocol. This result and the reduction mentioned above implies the unconditional security of our QKD protocol despite our previous proof that unconditionally secure bit commitment schemes are impossible.

•Jan 1, 2002•17 citations

On Commitment over General Compound Channels

Anuj Kumar Yadav, Manideep Mamindlapally, Pranav Joshi +1 more

As computation and communication become increasingly ubiquitous, data security remains a key consideration. Hence, cryptographic primitives lie at the heart of several modern digital technologies. In this work, we study one such important cryptographic primitive called commitment. Here two parties, say Alice and Bob, aim to realize a protocol with the following functionality: Alice seeks to share or commit to a bit string securely with Bob with the requirement that the string is hidden from Bob until she chooses to reveal it to him. Bob wants to ensure that the protocol binds Alice to her original choice of bit string by allowing him to successfully detect when she cheats at the time of revealing her string. This seemingly elementary cryptographic functionality is extremely powerful and finds wide use in technologies like blockchains, digital contracts, cryptocurrencies, etc.. More generally, commitment has also been widely studied for applications like sealed-bid auctions, distributed coin tossing, etc.. Building on Wyner's classic work on wiretap channels, unconditionally-secure or information-theoretically secure protocols have been realized for a wide variety of problems, including commitment, using noisy channels as a resource. Crucially, however, the security guarantees are intimately tied to the knowledge of the noise statistics; these could be compromised when noise statistics are imprecisely known. In this work, we seek to study information-theoretically secure commitment over a class of unreliable noisy channels called compound channels. In particular, we study commitment over compound discrete memoryless channels (compound-DMCs) where the instantiated channel is known to be a DMC but its realization or channel state is not known exactly and can only be localized to a potential set of possible states. We precisely characterize the optimal throughput or commitment capacity over general compound DMCs. We also study the effect of state-awareness at the two parties, when the parties are honest and when they are malicious, on the commitment capacity of such compound DMCs. Interestingly, we show that committer-side state-awareness can non-trivially increase the commitment throughput over the compound DMC which is not the case when one has only receiver-side state awareness. In particular, we completely characterize the commitment capacity for all state-aware configurations for compound DMCs.

International Conference on Communication Systems & Networks (COMSNETS)•Jan 4, 2022•3 citations

On unconditionally secure oblivious transfer from continuous channels

Motohiko Isaka

In this paper, we consider an information theoretically secure cryptographic primitive known as oblivious transfer based on noisy channels. We present a protocol and two approaches to base the primitive on much wider class of signal sets and continuous channels than the existing results on the Gaussian channel. We also evaluate the associated information theoretic efficiency of the protocol for some cases of interest.

IEEE International Symposium on Information Theory (ISIT)•Jun 1, 2010•4 citations

On the Commitment Capacity of Unfair Noisy Channels

Claude Crépeau, Rafael Dowsley, Anderson C. A. Nascimento

Noisy channels are a valuable resource from a cryptographic point of view. They can be used for exchanging secret-keys as well as realizing other cryptographic primitives such as commitment and oblivious transfer. To be really useful, noisy channels have to be considered in the scenario where a cheating party has some degree of control over the channel characteristics. Damgård et al. (EUROCRYPT 1999) proposed a more realistic model where such level of control is permitted to an adversary, the so called unfair noisy channels, and proved that they can be used to obtain commitment and oblivious transfer protocols. Given that noisy channels are a precious resource for cryptographic purposes, one important question is determining the optimal rate in which they can be used. The commitment capacity has already been determined for the cases of discrete memoryless channels and Gaussian channels. In this work we address the problem of determining the commitment capacity of unfair noisy channels. We compute a single-letter characterization of the commitment capacity of unfair noisy channels. In the case where an adversary has no control over the channel (the fair case) our capacity reduces to the well-known capacity of a discrete memoryless binary symmetric channel.

arXiv:1905.10921•IEEE Transactions on Information Theory•Jan 17, 2020•15 citations
Realizing fundamental cryptographic primitives with unconditional security is a central topic in information-theoretic cryptography. These primitives can be realized based on physical assumptions, such as the existence of noisy channels, an upper bound on the storage capacity, or the laws of quantum mechanics. Palmieri and Pereira [1] demonstrated that delays in communication channels can be used as a reasonable and effective assumption to obtain an unconditionally secure oblivious transfer protocol against honest-but-curious adversaries. While any oblivious transfer protocol secure against malicious adversaries can be used to implement commitment, the reduction does not work if the oblivious transfer protocol is only secure against honest-but-curious adversaries. Thus, the question of obtaining a secure commitment protocol based on channel delays is still open. In this paper, we provide a concrete protocol for implementing string commitments based on packet reordering – a consequence of channel delays in packet networks.
Noisy channels are a foundational resource for constructing cryptographic primitives such as string commitment and oblivious transfer. The noisy channel model has been extended to unfair noisy channels, where adversaries can influence the parameters of a memoryless channel. In this work, we introduce the unstructured noisy channel model as a generalization of the unfair noisy channel model to allow the adversary to manipulate the channel arbitrarily subject to certain entropic constraints. We present a string commitment protocol with established security and derive its achievable commitment rate, demonstrating the feasibility of commitment against this stronger class of adversaries. Furthermore, we show that the entropic constraints in the unstructured noisy channel model can be derived from physical assumptions such as noisy quantum storage. Our work thus connects two distinct approaches to commitment, i.e., the noisy channel and physical limitations.
Historically, cryptography was created and used to deliver messages between people in such a way that only the intended receiver would be able to read them. The two persons communicating trusted each other, but not the rest of the world - for instance, not the message bearer. But what happens if we assume instead that even the receiver of a message may not be trusted by the sender, while both still have an interest in communicating? This problem is addressed by secure multi-party computation, that studies communication and shared computation between mutually distrusting parties. In a world where most of the communication happens over the Internet, and where an ever-increasing amount of computation is outsourced, for example to the cloud, multi-party computation is a subject of crucial importance. However, unconditionally secure multi-party protocols have never found practical application: the lack of realistic noisy channel models, that are required to achieve security against computationally unbounded adversaries, prevents implementation over real-world, standard communication protocols.\n\nIn this thesis, we study the properties and characteristics of noisy channels, and we introduce new models based on real-world error sources that have never been studied in this context, such as delays. On the contrary, previous works mostly focused on theoretical noisy channels that have little in common with the reality of network communication. We show that the models we propose are suitable for multi-party computation by building on each of them a protocol for oblivious transfer, a fundamental cryptographic primitive that implies any secure computation. Thanks to the realism of our noisy channels, we are able to provide the first working implementation of unconditionally secure oblivious transfer over both wired and wireless networks and different Internet protocols, which we test thoroughly in an extensive set of experiments. Our constructions are not only more realistic, but also more flexible, as they allow larger ranges of error probabilities. This will eventually open the way for the widespread use of unconditionally secure multi-party computation.
We prove the unconditional security of a quantum key distribution (QKD) protocol on a noisy channel against the most general attack allowed by quantum physics. We use the fact that in a previous paper we have reduced the proof of the unconditionally security of this QKD protocol to a proof that a corresponding Quantum String Oblivious Transfer (String-QOT) protocol would be unconditionally secure against Bob if implemented on top of an unconditionally secure bit commitment schcmc. We prove a lemma that extends a security proof given by Yao for a (one bit) QOT protocol to this String-QOT protocol. This result and the reduction mentioned above implies the unconditional security of our QKD protocol despite our previous proof that unconditionally secure bit commitment schemes are impossible.
As computation and communication become increasingly ubiquitous, data security remains a key consideration. Hence, cryptographic primitives lie at the heart of several modern digital technologies. In this work, we study one such important cryptographic primitive called commitment. Here two parties, say Alice and Bob, aim to realize a protocol with the following functionality: Alice seeks to share or commit to a bit string securely with Bob with the requirement that the string is hidden from Bob until she chooses to reveal it to him. Bob wants to ensure that the protocol binds Alice to her original choice of bit string by allowing him to successfully detect when she cheats at the time of revealing her string. This seemingly elementary cryptographic functionality is extremely powerful and finds wide use in technologies like blockchains, digital contracts, cryptocurrencies, etc.. More generally, commitment has also been widely studied for applications like sealed-bid auctions, distributed coin tossing, etc.. Building on Wyner's classic work on wiretap channels, unconditionally-secure or information-theoretically secure protocols have been realized for a wide variety of problems, including commitment, using noisy channels as a resource. Crucially, however, the security guarantees are intimately tied to the knowledge of the noise statistics; these could be compromised when noise statistics are imprecisely known. In this work, we seek to study information-theoretically secure commitment over a class of unreliable noisy channels called compound channels. In particular, we study commitment over compound discrete memoryless channels (compound-DMCs) where the instantiated channel is known to be a DMC but its realization or channel state is not known exactly and can only be localized to a potential set of possible states. We precisely characterize the optimal throughput or commitment capacity over general compound DMCs. We also study the effect of state-awareness at the two parties, when the parties are honest and when they are malicious, on the commitment capacity of such compound DMCs. Interestingly, we show that committer-side state-awareness can non-trivially increase the commitment throughput over the compound DMC which is not the case when one has only receiver-side state awareness. In particular, we completely characterize the commitment capacity for all state-aware configurations for compound DMCs.
Noisy channels are a valuable resource from a cryptographic point of view. They can be used for exchanging secret-keys as well as realizing other cryptographic primitives such as commitment and oblivious transfer. To be really useful, noisy channels have to be considered in the scenario where a cheating party has some degree of control over the channel characteristics. Damgård et al. (EUROCRYPT 1999) proposed a more realistic model where such level of control is permitted to an adversary, the so called unfair noisy channels, and proved that they can be used to obtain commitment and oblivious transfer protocols. Given that noisy channels are a precious resource for cryptographic purposes, one important question is determining the optimal rate in which they can be used. The commitment capacity has already been determined for the cases of discrete memoryless channels and Gaussian channels. In this work we address the problem of determining the commitment capacity of unfair noisy channels. We compute a single-letter characterization of the commitment capacity of unfair noisy channels. In the case where an adversary has no control over the channel (the fair case) our capacity reduces to the well-known capacity of a discrete memoryless binary symmetric channel.