Tag Archives: anonymity

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}

Bitmessage address mixing

Riffle shuffle

This post introduces the concept of address mixing in Bitmessage - what it is, why it is useful, and how it could be done.

This post does not contain a complete algorithm nor claim to know the best solution to the problem, but is rather intended to start a debate on the best way to achieve the goals described in the following section:

What is address mixing?

Address mixing is when a group of people who knows the Bitmessage addresses of each other, works together to create a list of alternate addresses owned by the same group of people, but without knowing who owns which address.

In other words, everybody creates a new address and shares it with the others in such a way that no member of the group (or anybody outside of the group) can deduce which of the new addresses belong to a specific person of the group.

The idea is that of a trustless mix network - i.e. one that doesn't require anyone to trust anyone else for the process to work.

For this purpose, we assume that any adversary has knowledge of the people in the group, as well as any CMLs or DMLs used by the group.

Why is address mixing useful?

Address mixing potentially has a lot of use cases, but the most obvious is the case where a group of people wants to anonymously send messages to each other without revealing who is the sender, while still convincing everybody that the sender is a member of the group.

One could easily imagine a scenario where this group of people wants to conduct a completely anonymous survey (or maybe an election) while ensuring that only the responses of group members are regarded as valid.

Messages in Bitmessage only provide pseudonymity; if you know the identity of the person behind the sender address, he or she is not anonymous at all. This is undesirable in certain scenarios where the senders of messages wish to be completely anonymous to the group.

Of course, decentralized mailing lists (DMLs or chans) already provides the functionality of sending anonymous messages to a group (and, in fact, the address mixing schemes proposed here will make use of chans), but receiving a message anonymously in a chan only proves that the sender knows of the chan, and not that the sender is an accepted member of the group of people using the chan.

Continue reading