A New Efficient Threshold Ring Signature Scheme Based on Coding Theory
- 20 June 2011
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Information Theory
- Vol. 57 (7), 4833-4842
- https://doi.org/10.1109/tit.2011.2145950
Abstract
Ring signatures were introduced by Rivest, Shamir, and Tauman in 2001. These signatures allow a signer to anonymously authenticate a message on behalf of a group of his choice. This concept was then extended by Bresson, Stern, and Szydlo into t-out-of-N (threshold) ring signatures in 2002. We propose in this article a generalization of Stern's code-based identification (and signature) scheme to design a practical t -out-of- N threshold ring signature scheme. The size of the resulting signatures is in O(N) and does not depend on t , contrary to most of the existing protocols. Our scheme is existentially unforgeable under a chosen message attack in the random oracle model assuming the hardness of the minimum distance problem, is unconditionally source hiding, has a very short public key and has an overall complexity in O(N). This protocol is the first efficient code-based ring signature scheme and the first code-based threshold ring signature scheme. Moreover it has a better complexity than number-theory based schemes which have a complexity in O(Nt). This paper is an extended version of a paper published in the conference PQCrypto 2008, with complete proofs and definitions.Keywords
This publication has 26 references indexed in Scilit:
- Efficient Ring Signatures Without Random OraclesPublished by Springer Science and Business Media LLC ,2007
- Separable Linkable Threshold Ring SignaturesLecture Notes in Computer Science, 2004
- Deniable Ring AuthenticationLecture Notes in Computer Science, 2002
- How to Leak a SecretLecture Notes in Computer Science, 2001
- How to Achieve a McEliece-Based Digital Signature SchemeLecture Notes in Computer Science, 2001
- A new algorithm for finding minimum-weight words in a linear code: application to McEliece's cryptosystem and to narrow-sense BCH codes of length 511IEEE Transactions on Information Theory, 1998
- A new paradigm for public key identificationIEEE Transactions on Information Theory, 1996
- A new identification scheme based on syndrome decodingLecture Notes in Computer Science, 1994
- How to share a secretCommunications of the ACM, 1979
- Limit distribution of the minimum distance of random linear codesIEEE Transactions on Information Theory, 1967