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

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...

Full description

Saved in:
Bibliographic Details
Main Author: Tang, Khai Hanh
Other Authors: Ling San
Format: Thesis-Doctor of Philosophy
Language:English
Published: Nanyang Technological University 2022
Subjects:
Online Access:https://hdl.handle.net/10356/160385
Tags: Add Tag
No Tags, Be the first to tag this record!
Institution: Nanyang Technological University
Language: English
id sg-ntu-dr.10356-160385
record_format dspace
spelling sg-ntu-dr.10356-1603852023-02-28T23:43:20Z New and improved zero-knowledge argument systems for code-based cryptography Tang, Khai Hanh Ling San Wang Huaxiong School of Physical and Mathematical Sciences Nguyen Ta Toan Khoa HXWang@ntu.edu.sg, lingsan@ntu.edu.sg, khoa@uow.edu.au Science::Mathematics 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. Doctor of Philosophy 2022-07-21T00:43:14Z 2022-07-21T00:43:14Z 2022 Thesis-Doctor of Philosophy Tang, K. H. (2022). New and improved zero-knowledge argument systems for code-based cryptography. Doctoral thesis, Nanyang Technological University, Singapore. https://hdl.handle.net/10356/160385 https://hdl.handle.net/10356/160385 10.32657/10356/160385 en MOE2016-T2-2-014(S) This work is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License (CC BY-NC 4.0). application/pdf Nanyang Technological University
institution Nanyang Technological University
building NTU Library
continent Asia
country Singapore
Singapore
content_provider NTU Library
collection DR-NTU
language English
topic Science::Mathematics
spellingShingle Science::Mathematics
Tang, Khai Hanh
New and improved zero-knowledge argument systems for code-based cryptography
description 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.
author2 Ling San
author_facet Ling San
Tang, Khai Hanh
format Thesis-Doctor of Philosophy
author Tang, Khai Hanh
author_sort Tang, Khai Hanh
title New and improved zero-knowledge argument systems for code-based cryptography
title_short New and improved zero-knowledge argument systems for code-based cryptography
title_full New and improved zero-knowledge argument systems for code-based cryptography
title_fullStr New and improved zero-knowledge argument systems for code-based cryptography
title_full_unstemmed New and improved zero-knowledge argument systems for code-based cryptography
title_sort new and improved zero-knowledge argument systems for code-based cryptography
publisher Nanyang Technological University
publishDate 2022
url https://hdl.handle.net/10356/160385
_version_ 1759855216359899136