New and improved zero-knowledge argument systems for code-based cryptography

Abstract

Since a large amount of research devotes to improvements in quantum algorithms, current cryptographic constructions and primitives are at the threat of being broken once powerful quantum machines become real. Post-quantum cryptography appears to demonstrate cryptographic constructions and primitives believed to be secure against the attacks of such quantum machines. To this end, NIST proposed Post-Quantum Cryptography Standardization process to solicit, evaluate, and standardize quantum-resistant cryptographic algorithms. At the current stage of this process, many cryptographic algorithms in various assumptions against quantum-quantum computing advanced to the third-round submission. These quantum-resistant assumptions include code-based, lattice-based, multivariate and hash-based assumptions. Among these assumptions, code-based cryptography does not seem to get much attraction from the community of cryptographic research as many privacy-preserving systems are still missing or have not been improved much in terms of efficiency and diversity of functionalities.

In the field of code-based cryptography, we improve and refine code-based cryptographic constructions through the following contributions:

1. We refine the Stern-like framework for constructing zero-knowledge arguments in terms of efficiency by refining the components used in the execution of Stern's protocol including using functions with necessary properties in place of a permutation and compressing the random masks.

2. We improve range arguments by considering broader ranges of numbers. The numbers considered in our context are signed and fractional ones. Handling with these numbers is quite non-trivial since we need to resolve the issues of overflows and sign bits. We finally achieve a zero-knowledge argument of knowledge for comparing two committed signed fractional numbers which then leads to the constructions of range arguments.

3. We propose a new zero-knowledge argument for evaluating on committed symmetric Boolean functions. Although we considered a restricted class of functions, it has sufficiently large cardinality and has various potential applications since many popular functions can be represented under this class such as threshold, parity and sorting functions.

4. We construct repudiable-and-claimable ring signature and fully dynamic group signature schemes. Those schemes are previous code-based constructions of ring signatures and group signatures with new functionalities attached. Our schemes have signature's size logarithmic in the cardinality of the respective ring or group.

5. We introduce a new definition of fully dynamic attribute-based signatures. We realize it by constructing a code-based fully dynamic attribute-based signature scheme in the random oracle model by assuming the hardness of code-based problems, and soundness and zero-knowledge properties of the underlying zero-knowledge arguments of knowledge. To construct such a signature scheme, we devise a new technique for handling NAND gates in a Boolean circuit with a relatively small cost of witness representations.