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

International Conference on Ubiquitous Information Management and Communication (IMCOM)

On unconditionally binding code-based commitment schemes

Kirill Morozov, Partha Sarathi Roy, Kouichi Sakurai

Published Jan 5, 2017• 7 citations
Publisher

Abstract

In this work, we construct a dual version of statistically binding commitment scheme by Jain et al. (Asiacrypt 2012) with shorter commitment size under hardness of syndrome decoding. Then, we point out that perfectly binding variants of the above schemes follow directly from the Randomized McEliece and Niederreiter public key encryption schemes, assuming indistinguishability of permuted Goppa codes, as well as hardness of the exact learning parity with noise (xLPN) problem (for the McEliece scheme) and hardness of syndrome decoding (for the Niederreiter scheme). Our key observation here is that perfect binding (as opposed to statistical binding) requires exact knowledge of minimal distance of the underlying code. Finally, we provide security evaluation of our proposals, and compare their performance with that of existing schemes.

DOI
10.1145/3022227.3022327

Related papers

A Provably Secure Group Signature Scheme from Code-Based Assumptions.

Martianus Frederic Ezerman, Hyung Tae Lee, San Ling +2 more

Abstract. We solve an open question in code-based cryptography by introducing the first provably secure group signature scheme from code-based assumptions. Specifically, the scheme satisfies the CPA-anonymity and traceability requirements in the random oracle model, assuming the hardness of the McEliece problem, the Learning Parity with Noise prob-lem, and a variant of the Syndrome Decoding problem. Our construction produces smaller key and signature sizes than the existing post-quantum group signature schemes from lattices, as long as the cardinality of the underlying group does not exceed the population of the Netherlands ( ≈ 224 users). The feasibility of the scheme is supported by implementa-tion results. Additionally, the techniques introduced in this work might be of independent interest: a new verifiable encryption protocol for the randomized McEliece encryption and a new approach to design formal security reductions from the Syndrome Decoding problem.

•Jan 1, 2015•0 citations

Oblivious Transfer Based on the McEliece Assumptions

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

We implement one-out-of-two bit oblivious transfer (OT) based on the assumptions used in the McEliece cryptosystem: the hardness of decoding random binary linear codes, and the difficulty of distinguishing a permuted generating matrix of Goppa codes from a random matrix. To our knowledge this is the first OT reduction to these problems only. We present two different constructions for oblivious transfer, one based on cut-and-chose arguments and another one which is based on a novel generalization of Bennett-Rudich commitments which may be of independent interest. Finally, we also present a variant of our protocol which is based on the Niederreiter cryptosystem.

IEICE Transactions on Fundamentals of Electronics Communications and Computer Sciences•Jan 1, 2012•7 citations

Oblivious Transfer Based on the McEliece Assumptions

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

We implement one-out-of-two bit oblivious transfer (OT) based on the assumptions used in the McEliece cryptosystem: the hardness of decoding random binary linear codes, and the difficulty of distinguishing a permuted generating matrix of Goppa codes from a random matrix. To our knowledge this is the first OT reduction to these problems only. We present two different constructions for oblivious transfer, one based on cut-and-choose arguments and another one which is based on a novel generalization of Bennett-Rudich commitments which may be of independent interest. Finally, we also present a variant of our protocol which is based on the Niederreiter cryptosystem.

•Aug 10, 2008•0 citations

A post-quantum UC-commitment scheme in the global random oracle model from code-based assumptions

Pedro Costa Branco

In this work, we propose a post-quantum UC-commitment scheme in the Global Random Oracle Model, where only one non-programmable random oracle is available. The security of our proposal is based on two well-established post-quantum hardness assumptions from coding theory: The Syndrome Decoding and the Goppa Distinguisher. We prove that our proposal is perfectly hiding and computationally binding.

Advances in Mathematics of Communications•Nov 25, 2019•2 citations

Zero-Knowledge Protocols for Code-Based Public-Key Encryption

Rong Lin Hu, Kirill Morozov, Tsuyoshi Takagi

Code-based public-key encryption schemes (PKE) are the candidates for post-quantum cryptography, since they are believed to resist the attacks using quantum algorithms. The most famous such schemes are the McEliece encryption and the Niederreiter encryption. In this paper, we present the zero-knowledge (ZK) proof systems for proving statements about data encrypted using these schemes. Specifically, we present a proof of plaintext knowledge for both PKE's, and also a verifiable McEliece PKE. The main ingredients of our constructions are the ZK identification schemes by Stern from Crypto'93 and by Jain, Krenn, Pietrzak, and Tentes from Asiacrypt'12.

IEICE Transactions on Fundamentals of Electronics Communications and Computer Sciences•Jan 1, 2015•4 citations

An Unconditionally Hiding and Long-Term Binding Post-Quantum Commitment Scheme

Daniel Cabarcas, Denise Demirel, Florian Göpfert +2 more

Abstract. Commitment schemes are among cryptography’s most im-portant building blocks. Besides their basic properties, hidingness and bindingness, for many applications it is important that the schemes ap-plied support proofs of knowledge. However, all existing solutions which have been proven to provide these protocols are only computationally hiding or are not resistant against quantum adversaries. This is not suitable for long-lived systems, such as long-term archives, where com-mitments have to provide security also in the long run. Thus, in this work we present a new post-quantum unconditionally hiding commit-ment scheme that supports (statistical) zero-knowledge protocols and allows to refreshes the binding property over time. The bindingness of our construction relies on the approximate shortest vector problem, a lattice problem which is conjectured to be hard for polynomial approxi-mation factors, even for a quantum adversary. Furthermore, we provide a protocol that allows the committer to prolong the bindingness prop-erty of a given commitment while showing in zero-knowledge fashion that the value committed to did not change. In addition, our construc-tion yields two more interesting features: one is the ability to “convert” a Pedersen commitment into a lattice-based one, and the other one is the construction of a hybrid approach whose bindingness relies on the discrete logarithm and approximate shortest vector problems.

•Jun 1, 2015•6 citations
In this work, we construct a dual version of statistically binding commitment scheme by Jain et al. (Asiacrypt 2012) with shorter commitment size under hardness of syndrome decoding. Then, we point out that perfectly binding variants of the above schemes follow directly from the Randomized McEliece and Niederreiter public key encryption schemes, assuming indistinguishability of permuted Goppa codes, as well as hardness of the exact learning parity with noise (xLPN) problem (for the McEliece scheme) and hardness of syndrome decoding (for the Niederreiter scheme). Our key observation here is that perfect binding (as opposed to statistical binding) requires exact knowledge of minimal distance of the underlying code. Finally, we provide security evaluation of our proposals, and compare their performance with that of existing schemes.
Abstract. We solve an open question in code-based cryptography by introducing the first provably secure group signature scheme from code-based assumptions. Specifically, the scheme satisfies the CPA-anonymity and traceability requirements in the random oracle model, assuming the hardness of the McEliece problem, the Learning Parity with Noise prob-lem, and a variant of the Syndrome Decoding problem. Our construction produces smaller key and signature sizes than the existing post-quantum group signature schemes from lattices, as long as the cardinality of the underlying group does not exceed the population of the Netherlands ( ≈ 224 users). The feasibility of the scheme is supported by implementa-tion results. Additionally, the techniques introduced in this work might be of independent interest: a new verifiable encryption protocol for the randomized McEliece encryption and a new approach to design formal security reductions from the Syndrome Decoding problem.
We implement one-out-of-two bit oblivious transfer (OT) based on the assumptions used in the McEliece cryptosystem: the hardness of decoding random binary linear codes, and the difficulty of distinguishing a permuted generating matrix of Goppa codes from a random matrix. To our knowledge this is the first OT reduction to these problems only. We present two different constructions for oblivious transfer, one based on cut-and-chose arguments and another one which is based on a novel generalization of Bennett-Rudich commitments which may be of independent interest. Finally, we also present a variant of our protocol which is based on the Niederreiter cryptosystem.
We implement one-out-of-two bit oblivious transfer (OT) based on the assumptions used in the McEliece cryptosystem: the hardness of decoding random binary linear codes, and the difficulty of distinguishing a permuted generating matrix of Goppa codes from a random matrix. To our knowledge this is the first OT reduction to these problems only. We present two different constructions for oblivious transfer, one based on cut-and-choose arguments and another one which is based on a novel generalization of Bennett-Rudich commitments which may be of independent interest. Finally, we also present a variant of our protocol which is based on the Niederreiter cryptosystem.
Code-based public-key encryption schemes (PKE) are the candidates for post-quantum cryptography, since they are believed to resist the attacks using quantum algorithms. The most famous such schemes are the McEliece encryption and the Niederreiter encryption. In this paper, we present the zero-knowledge (ZK) proof systems for proving statements about data encrypted using these schemes. Specifically, we present a proof of plaintext knowledge for both PKE's, and also a verifiable McEliece PKE. The main ingredients of our constructions are the ZK identification schemes by Stern from Crypto'93 and by Jain, Krenn, Pietrzak, and Tentes from Asiacrypt'12.
Abstract. Commitment schemes are among cryptography’s most im-portant building blocks. Besides their basic properties, hidingness and bindingness, for many applications it is important that the schemes ap-plied support proofs of knowledge. However, all existing solutions which have been proven to provide these protocols are only computationally hiding or are not resistant against quantum adversaries. This is not suitable for long-lived systems, such as long-term archives, where com-mitments have to provide security also in the long run. Thus, in this work we present a new post-quantum unconditionally hiding commit-ment scheme that supports (statistical) zero-knowledge protocols and allows to refreshes the binding property over time. The bindingness of our construction relies on the approximate shortest vector problem, a lattice problem which is conjectured to be hard for polynomial approxi-mation factors, even for a quantum adversary. Furthermore, we provide a protocol that allows the committer to prolong the bindingness prop-erty of a given commitment while showing in zero-knowledge fashion that the value committed to did not change. In addition, our construc-tion yields two more interesting features: one is the ability to “convert” a Pedersen commitment into a lattice-based one, and the other one is the construction of a hybrid approach whose bindingness relies on the discrete logarithm and approximate shortest vector problems.