Provably secure group signature schemes from code-based assumptions
We solve an open question in code-based cryptography by introducing two provably secure group signature schemes from code-based assumptions. Our basic scheme satisfies the \textsf{CPA}-anonymity and traceability requirements in the random oracle model, assuming the hardness of the McEliece problem,...
| Main Authors: | , , , , |
|---|---|
| Other Authors: | |
| Format: | Journal Article |
| Language: | English |
| Published: |
2020
|
| Subjects: | |
| Online Access: | https://hdl.handle.net/10356/143454 |
| _version_ | 1826112565332148224 |
|---|---|
| author | Ezerman, Martianus Frederic Lee, Hyung Tae Ling, San Nguyen, Khoa Wang, Huaxiong |
| author2 | School of Physical and Mathematical Sciences |
| author_facet | School of Physical and Mathematical Sciences Ezerman, Martianus Frederic Lee, Hyung Tae Ling, San Nguyen, Khoa Wang, Huaxiong |
| author_sort | Ezerman, Martianus Frederic |
| collection | NTU |
| description | We solve an open question in code-based cryptography by introducing two provably secure group signature schemes from code-based assumptions. Our basic scheme satisfies the \textsf{CPA}-anonymity and traceability requirements in the random oracle model, assuming the hardness of the McEliece problem, the Learning Parity with Noise problem, and a variant of the Syndrome Decoding problem. The construction produces smaller key and signature sizes than the previous group signature schemes from lattices, as long as the cardinality of the underlying group does not exceed $2^{24}$, which is roughly comparable to the current population of the Netherlands.
We develop the basic scheme further to achieve the strongest anonymity notion, \ie, \textsf{CCA}-anonymity, with a small overhead in terms of efficiency.
The feasibility of two proposed schemes is supported by implementation results.
Our two schemes are the first in their respective classes of provably secure groups signature schemes. Additionally, the techniques introduced in this work might be of independent interest. These are a new verifiable encryption protocol for the randomized McEliece encryption and a novel approach to design formal security reductions from the Syndrome Decoding problem. |
| first_indexed | 2024-10-01T03:09:09Z |
| format | Journal Article |
| id | ntu-10356/143454 |
| institution | Nanyang Technological University |
| language | English |
| last_indexed | 2024-10-01T03:09:09Z |
| publishDate | 2020 |
| record_format | dspace |
| spelling | ntu-10356/1434542023-02-28T19:55:29Z Provably secure group signature schemes from code-based assumptions Ezerman, Martianus Frederic Lee, Hyung Tae Ling, San Nguyen, Khoa Wang, Huaxiong School of Physical and Mathematical Sciences Science::Mathematics::Applied mathematics::Information theory Science::Mathematics::Discrete mathematics::Cryptography Code-based Group Signature Zero-knowledge Protocol We solve an open question in code-based cryptography by introducing two provably secure group signature schemes from code-based assumptions. Our basic scheme satisfies the \textsf{CPA}-anonymity and traceability requirements in the random oracle model, assuming the hardness of the McEliece problem, the Learning Parity with Noise problem, and a variant of the Syndrome Decoding problem. The construction produces smaller key and signature sizes than the previous group signature schemes from lattices, as long as the cardinality of the underlying group does not exceed $2^{24}$, which is roughly comparable to the current population of the Netherlands. We develop the basic scheme further to achieve the strongest anonymity notion, \ie, \textsf{CCA}-anonymity, with a small overhead in terms of efficiency. The feasibility of two proposed schemes is supported by implementation results. Our two schemes are the first in their respective classes of provably secure groups signature schemes. Additionally, the techniques introduced in this work might be of independent interest. These are a new verifiable encryption protocol for the randomized McEliece encryption and a novel approach to design formal security reductions from the Syndrome Decoding problem. Accepted version 2020-09-02T06:29:41Z 2020-09-02T06:29:41Z 2020 Journal Article Ezerman, M. F., Lee, H. T., Ling, S., Nguyen, K., & Wang, H. (2020). Provably secure group signature schemes from code-based assumptions. IEEE Transactions on Information Theory, 66(9), 5754-5773. doi:10.1109/TIT.2020.2976073 0018-9448 https://hdl.handle.net/10356/143454 10.1109/TIT.2020.2976073 9 66 5754 5773 en IEEE Transactions on Information Theory © 2020 IEEE. Personal use of this material is permitted. Permission from IEEE must be obtained for all other uses, in any current or future media, including reprinting/republishing this material for advertising or promotional purposes, creating new collective works, for resale or redistribution to servers or lists, or reuse of any copyrighted component of this work in other works. The published version is available at: https://doi.org/10.1109/TIT.2020.2976073 application/pdf |
| spellingShingle | Science::Mathematics::Applied mathematics::Information theory Science::Mathematics::Discrete mathematics::Cryptography Code-based Group Signature Zero-knowledge Protocol Ezerman, Martianus Frederic Lee, Hyung Tae Ling, San Nguyen, Khoa Wang, Huaxiong Provably secure group signature schemes from code-based assumptions |
| title | Provably secure group signature schemes from code-based assumptions |
| title_full | Provably secure group signature schemes from code-based assumptions |
| title_fullStr | Provably secure group signature schemes from code-based assumptions |
| title_full_unstemmed | Provably secure group signature schemes from code-based assumptions |
| title_short | Provably secure group signature schemes from code-based assumptions |
| title_sort | provably secure group signature schemes from code based assumptions |
| topic | Science::Mathematics::Applied mathematics::Information theory Science::Mathematics::Discrete mathematics::Cryptography Code-based Group Signature Zero-knowledge Protocol |
| url | https://hdl.handle.net/10356/143454 |
| work_keys_str_mv | AT ezermanmartianusfrederic provablysecuregroupsignatureschemesfromcodebasedassumptions AT leehyungtae provablysecuregroupsignatureschemesfromcodebasedassumptions AT lingsan provablysecuregroupsignatureschemesfromcodebasedassumptions AT nguyenkhoa provablysecuregroupsignatureschemesfromcodebasedassumptions AT wanghuaxiong provablysecuregroupsignatureschemesfromcodebasedassumptions |