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.

Linkable ring signatures on elliptic curves over finite fields

The algorithms for signing a message and verifying a linkable ring signature on elliptic curves, are very similar to their equivalents from the original paper [3] which operate with the Discrete Logarithm Problem (DLP). In fact, I will not take credit for anything other than transcribing the original algorithms to operate on elliptic curves, and some of the language in the following specification is directly taken from the paper:

Let q denote a large prime number, E denote an elliptic curve, P denote a base point on the elliptic curve E with order q. Let H1 : {0,1}* ↦ Zq and H2 : {0,1}* ↦ Zq be some statistically independent cryptographic hash functions, For i = 1, ⋯, n, each user i has a distinct public key Yi and a private key xi such that Yi=xiP. Let L={Y1, ⋯, Yn} be the list of n public keys. LetMapToPoint(x, E) be a function that injectively maps an integer x to a point on the curve E, such as the MapToGrouph' algorithm from [4].

Signing

Given message m ∈ {0,1}*, signer has private and public keys xπ and Yπ

  1. Compute H=MapToPoint(H2( L ), E) and Y*=xπ ⋅ H
  2. Pick u ∈ R Zq, and compute

     c_{\pi+1}=\mathbf{H_1}(L, Y^*, m, uP, uH)

  3. For i = π+1, ⋯, n, 1, ⋯, π-1, pick siR Zq

     c_{i+1}=\mathbf{H_1}(L, Y^*, m, s_iP+c_iY_i, s_iH+c_iY^*)

  4. Compute sπ = u - xπ cπ mod q

The signature is σL( m ) = (c1, s1, ⋯, sn, Y*).

The Y* is the signer's unique tag for this exact ring. If he is to sign another message with the exact same ring, the tag will be the same and thus one can link two signatures simply by comparing the tags.

However, if the rings aren't exactly the same, even if the keys in the ring are just in a different order, the tag will also be different and thus unusable for linking any two signatures.

UPDATE: Originally I calculated H = H2( L ) ⋅ P, but, as reddit user bitwiseshiftleft noted in this thread, that would make it possible for anyone to test if the tag Y*=xπ ⋅ H belongs to a certain public key in the list.

Verifying

The signature σL( m ) = (c1, s1, ⋯, sn, Y*) on a message m and a list of public keys L is verified as follows.

  1. Compute H=MapToPoint(H2( L ), E), and for i = 1, ⋯, n, compute the following:

     Z_i'=s_iP+c_iY_i \\ Z_i''=s_iH+c_iY^* \\ c_{i+1}=\mathbf{H_1}(L,Y^*,m,Z_i',Z_i''), \mathrm{if} i \neq n

  2. Check whether c1 = H1( L, Y*, m, Z'n, Z''n ). If yes, accept. Otherwise, reject.

Python implementation

The implementation of linkable ring signatures over elliptic curves (ec_lsag_test.py), which can be found at the bottom of this post, signs and verifies a message with a linkable ring signature using from 2 to 10,000 public keys as the ring. It also measures the time spent signing and verifying the message, as well as the estimated size of the signature. The results of these measurements are shown in the next section.

UPDATE: The implementation now makes use of my Py-EC Python elliptic curve library, which is a nice pythonic wrapper for the OpenSSL elliptic curve functions.

The previous implementation was directly using the OpenSSL wrapper used in PyBitmessage, which is a further extension of the PyElliptic wrapper for OpenSSL. The previous implementation can still be found in this gist: https://gist.github.com/jesperborgstrup/10633874.

Test results

These tests were performed on my Lenovo Thinkpad E420s. The raw test result data can be found in the gist in the very bottom of this post.

I compare the amount of members (public keys) in the signature to the size of the signature, as well as the time taken to sign and verify. Each measurement was done 10 times in a row and the average over these 10 times is used.

The two following figures show how the size and time is linear in the amount of keys in a signature:

ring_signature_size
ring_signature_time

Linear regression of the above datasets gives us the time and size as linear functions of the amount of members in the ring (the units are seconds and bytes, respectively):

 \mathrm{time}(n)=0.00542900+0.03047425 \\ \mathrm{size}(n)=96.00n+64.95 \\

Note that while the time spent of course is specific to my test computer and will vary, the size is the same for everybody.

The next plots are the time and size per key, which show that the size of the signature goes smoothly towards 96 bytes per key as the key count increases. The time plot is a little bit more unstable, but shows that it consistently took between 5 and 7.5 ms to sign and verify per key.

ring_signature_size_per_key
ring_signature_time_per_key

Conclusion

I have provided a working implementation of linkable ring signatures over elliptic curves in Python, which has a quite okay performance; a ring signature with 100 members takes around three quarters of a second to sign and verify, while it takes roughly 70 seconds to sign and verify a signature with 10,000 members.

While 70 seconds to sign and verify a signature with 10,000 members is a bit much for anyone to perform on their personal computer, the implementation is merely a proof-of-concept and as such is not optimized for performance, so it is likely that the runtime could be improved further.

Also, if one wanted to design an e-voting scheme or the like using linkable ring signatures, it is worth noting that rings with more than, say, 1,000 members could be broken down into deterministically defined subrings. These subrings just have to be big enough for anyone to be anonymous in them.

It is my hope that linkable ring signatures will be a basic functionality in applications such as Bitmessage, allowing for the features described in the previous section What are linkable ring signatures useful for: Whistleblowing, e-voting, and more that I cannot even imagine.

References

[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}
}
[4] D. Boneh, B. Lynn, and H. Shacham, "Short ſignatures from the weil pairing," 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. 514-532.
[Bibtex]
@inproceedings{Boneh:2001:SSW,
author = {Boneh, Dan and Lynn, Ben and Shacham, Hovav},
title = {Short Signatures from the Weil Pairing},
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 = {514--532},
numpages = {19},
url = {http://dl.acm.org/citation.cfm?id=647097.717005},
acmid = {717005},
publisher = {Springer-Verlag},
address = {London, UK, UK},
}

Appendix - Implementation code

Note: The implementation requires Py-EC to work. The earlier implementation which doesn't have this requirement can be found here: https://gist.github.com/jesperborgstrup/10633874.

About the author

Jesper Borgstrup Jesper is a Masters student of computer science at the University of Copenhagen.

Leave a Reply

Your email address will not be published. Required fields are marked *

* Copy This Password *

* Type Or Paste Password Here *

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>