Category Archives: Cryptography

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}
}