Tag Archives: ring signatures

Master's thesis: Private, trustless and decentralized message consensus and voting schemes

I recently (December 19th, 2014) defended my master's thesis in Computer Science. For anyone interested, you can read the report here: Private, trustless and decentralized message consensus and voting schemes

The abstract is as follows:

This thesis proposes a protocol to conduct anonymous, trustless, decentralized elections over the internet. Only registered voters can vote, multiple votes from the same voter are easily detected and discarded, and it is infeasible to determine the identity behind a given vote with a better probability than random guessing.

The voting protocol builds on top of a decentralized deadline consensus protocol which can form a consensus about which messages have been sent before a specific deadline. This consensus protocol can also be used to suit other purposes such as contests, auctions and applications in a decentralized manner.

The protocols use the Bitmessage protocol for communication. Bitcoin, blockchain-technology and Invertible Bloom Lookup Tables are used for defining deadlines and timestamping of messages. Linkable Ring Signatures provide a signature scheme suitable for signing votes.

A proof-of-concept client has been developed and implemented, where one can create and run elections with a basic ballot format.

Linkable Ring Signatures over Elliptic curves

Warning: Invalid argument supplied for foreach() in /var/www/html/wp-content/plugins/papercite/lib/BibTex_osbib.php on line 185

Warning: Invalid argument supplied for foreach() in /var/www/html/wp-content/plugins/papercite/lib/BibTex_osbib.php on line 185

This post explains the concepts of ring signatures and linkable ring signatures, a possible application for these primitives, a translation of the linkable ring signature scheme to work with elliptic curves over finite fields, a Python implementation of the elliptic curve ring signature scheme, and some test results to show the efficiency of this implementation.


Introduction to linkable ring signatures

Ring signatures [1] are a type of digital signature which allow a message to be signed by a single entity in a group, or a ring, proving that the message is indeed signed by someone in the ring without providing any information that could identify the actual signer amongst the ring members.

Furthermore, ring signatures (as opposed to group signatures [2]) are spontaneous, meaning that no setup phase, no central group manager, and no group secret is needed. In fact, all the other members of the ring need not even know that they are part of a ring.

A ring signature's size is, due to the spontaneous property, linear in the amount of members in the ring. Likewise, the time required to sign and verify a ring signature is also linear in the amount of members.

Linkable ring signatures [3] are like plain ring signatures, but with an additional property: It is possible to link two signatures to the same signer, without disclosing the identity of that signer.

What are linkable ring signatures useful for?

Plain ring signatures are useful for e.g. whistleblowing, as hinted by the title How to leak a secret of the original ring signature paper [1], and section 2.2 of that paper gives a good, straightforward motivation for using ring signatures for whistleblowing.

Linkable ring signatures can also be used for whistleblowing, in the case where a journalist may not believe a single whistleblower, but would want several, distinct members of a ring to sign the same information in order for it to be considered trustworthy.

Another very promising use-case for linkable ring signatures is in e-voting, where the ring is the list of registered voters, and the linkable ring signature ensures that only registered voters' votes are considered valid while also ensuring that double-voting easily can be identified and the double-voter's votes discarded1.

As it is put very nicely by the authors of How to leak a secret: “Group signatures are useful when the members want to cooperate, while ring signatures are useful when the members do not want to cooperate.” [1]

1 Linkable ring signatures actually eliminate the need for address mixing in Bitmessage, a concept which I introduced a little over a month ago, since they allow for both anonymity and authenticity within a specified group of people.

Continue reading

[1] R. L. Rivest, A. Shamir, and Y. Tauman, "How to leak a ſecret," in Proceedings of the 7th ınternational conference on the theory and application of cryptology and ınformation ſecurity: advances in cryptology, London, UK, UK, 2001, pp. 552-565.
author = {Rivest, Ronald L. and Shamir, Adi and Tauman, Yael},
title = {How to Leak a Secret},
booktitle = {Proceedings of the 7th International Conference on the Theory and Application of Cryptology and Information Security: Advances in Cryptology},
series = {ASIACRYPT '01},
year = {2001},
isbn = {3-540-42987-5},
pages = {552--565},
numpages = {14},
acmid = {717015},
publisher = {Springer-Verlag},
address = {London, UK, UK},
[2] D. Chaum and E. Van Heyst, "Group ſignatures," in Proceedings of the 10th annual ınternational conference on theory and application of cryptographic techniques, Berlin, Heidelberg, 1991, pp. 257-265.
author = {Chaum, David and Van Heyst, Eug\`{e}ne},
title = {Group Signatures},
booktitle = {Proceedings of the 10th Annual International Conference on Theory and Application of Cryptographic Techniques},
series = {EUROCRYPT'91},
year = {1991},
isbn = {3-540-54620-0},
location = {Brighton, UK},
pages = {257--265},
numpages = {9},
url = {http://citeseerx.ist.psu.edu/viewdoc/download?doi=},
urldate = {2014-03-11},
acmid = {1754897},
publisher = {Springer-Verlag},
address = {Berlin, Heidelberg},
[3] J. K. Liu, V. K. Wei, and D. S. Wong, "Linkable ſpontaneous anonymous group ſignature for ad hoc groups," in In acıſp’04, volume 3108 of lncſ, 2004, pp. 325-335.
author = {Joseph K. Liu and Victor K. Wei and Duncan S. Wong},
title = {Linkable Spontaneous Anonymous Group Signature for Ad Hoc Groups},
booktitle = {In ACISP’04, volume 3108 of LNCS},
year = {2004},
pages = {325--335},
publisher = {Springer-Verlag}