Code-based cryptography : new privacy-preserving constructions

• Main Author: Zeng, Neng
• Other Authors: Wang Huaxiong
• Format: Thesis-Doctor of Philosophy
• Language: English
• Published: Nanyang Technological University 2020
• Subjects: Science::Mathematics
• Online Access: https://hdl.handle.net/10356/142777
• Institution: Nanyang Technological University

Code-based cryptography is one of the promising candidates of post-quantum cryptography. It has a long history, dated back to the seminal work by McEliece in 1978, but did suffer from a relatively slow development. Recently, it has witnessed resurgence in building theoretical or practical constructions such as identity-based encryptions, public key encryptions and so on. However, its subfield of privacy preserving constructions is not fully developed. On one hand, many primitives still need to improve, e.g., accumulators, ring signatures, e-cash systems and so on. On the other hand, many important building blocks are still missing, such as proofs of knowledge of a hash preimage/image and set membership proofs. Observing the underdevelopment of code-based cryptography, we are aiming to introduce several privacy-preserving constructions to help enrich the diversity and advance the state-of-affairs of this field. Specifically, we put forth five main contributions: (1) We design a code-based commitment scheme which is statistically hiding and computationally binding with companion proofs of a valid opening using zero knowledge argument. A good feature is that it can be easily composed with other cryptographic primitives and relations. (2) We construct the first logarithmic code-based Merkle-tree accumulator and zero knowledge proofs for set membership which have numerous privacy-preserving applications in ring signature, group signatures, e-cash and so on. An accumulator is able to compute a short accumulated value by hashing a set of elements and generate a short witness for each element to show that it belonging to the set. An honest prover who possesses a valid element-witness pair can convince a verifier in a zero knowledge manner that a specific input element is included in the hashed set. Our accumulator can be utilized in membership proofs, the prover follows and develops Stern’s zero knowledge arguments to demonstrate that he knows a hidden hash chain from the element to the accumulated root value without revealing any information of it. (3) We present the first logarithmic-size code-based ring signatures. All constructions prior to ours suffered from linear signature size. Generally speaking, it is non-trivial to design logarithmic size ring signatures since a powerful supporting technique is needed. We design such scheme based on our first logarithmic-size code-based accumulator. (4) We construct the first group signatures with logarithmic signature size in code-based assumptions. Our scheme follows the framework of group signature in static model (Bellare et al. - EUROCRYPT 2003) and has shorter signature compared to the lattice constructions and the previous code-based proposals. Furthermore, it achieves CCA2-anonymity. (5) We obtain the first code-based verifier-local revocation group signature with backward unlinkability. In 2004, Boneh and Shacham first formalized the concept of Verifier-Local Revocation (VLR) group signatures, in which the up-to-date revocation information only sent to verifiers who can use it to check if a signer has been revoked. Backward unlinkability is a desirable functionality which allows to retain the anonymity of the past signatures of revoked users. This property was put forth by Song in 2001. All existing VLR group signatures with backward unlinkability are based on number-theoretic assumptions that subject to quantum attacks. Our scheme achieves BU-anonymity and traceability by assuming the hardness of the DLPN problem and 2-RNSD problem. Furthermore, we propose the first decentralized e-cash system which relies on code-based assumptions that are conjectured to be quantum resistant and no such scheme appeared in code-based cryptography.