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.

Py-EC: Easy and efficient elliptic curves for Python

In Python, dealing directly with the OpenSSL library (through PyElliptic) easily becomes a hassle with the use of C pointers and string buffers.

To make things easier, I decided to make a wrapper for PyElliptic to make the manipulation of elliptic curves and points more Pythonic. The result is called Py-EC, is available on GitHub, and licensed under the MIT license (except for the part from PyElliptic, which is licensed under GPLv3).

Especially point addition and multiplication is way easier, as you can see in the examples on GitHub.

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.

letter-seal

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.
[Bibtex]
@inproceedings{Rivest:2001:HLS,
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.
[Bibtex]
@inproceedings{Chaum:1991:GS,
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=10.1.1.86.7757&rep=rep1&type=pdf},
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.
[Bibtex]
@INPROCEEDINGS{Liu:2004:LSAG,
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

Bitmessage centralized and decentralized mailing lists


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

Bitmessage

During my research for my upcoming master's thesis, I couldn't find any good description of the mailing list functionality in Bitmessage, so I decided to look into it myself and write about my findings .

In Bitmessage, two types of mailing lists exist; centralized and decentralized mailing lists. This article first describes the two types of mailing lists and then summarizes their key differences.

Continue reading

Bitmessage protocol dissector for Wireshark

During my research of the Bitmessage protocol, I decided that it would be useful to be able to dissect the network packages to and from the Bitmessage client in Wireshark.

Apparently, no one had created a Wireshark dissector for Bitmessage before, so I did just that in Lua and am sharing the result publicly on GitHub.

It can currently recognize the the version, verack, addr, inv, and getdata message types as well as the getpubkey, pubkey, msg, and broadcast object types.

Continue reading

Bitcoin and related concepts


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

Bitcoin-160

This post contains my notes in my attempt to describe the ecosystem surrounding Bitcoin and cryptocurrency in general as well as some other concepts that I have researched for my thesis in Computer Science.

The reader is assumed to have a basic understanding of how Bitcoin works.

If you are interested, the referenced papers are collected in BibTeX format here.

Continue reading

Partia for Android - Free social board gaming app

Over the last many months, I have been working on my social board gaming app for Android.

I am proud to announce: Partia for Android

Partia is a fun place to play your favourite games against your friends.

Partia is a free multi-game app that allows you to play a variety of classic turn-based games against your friends.

Games:

  • Reversi (Othello)
  • Backgammon
  • Battleships
  • More coming soon!

Link Partía on to Android Market: Partia on Android Market

Restart Python program if source has been modified

One of the nice features of developing a project with Django's development server, is the server's ability to restart/reload the project if its source has been modified.

I wanted to accomplish the same thing for an arbitrary Python program, and thus wrote a script, SourceChangeMonitor, to monitor a Python program for changes in the source code, and restart it when a change is detected.

Download: SourceChangeMonitor.py, a Python source code monitor

Continue reading