Forward-Secure Linkable Ring Signatures from Bilinear Maps

Xavier Boyen; Thomas Haines

doi:10.3390/cryptography2040035

journal article Open Access Nov 08, 2018

Forward-Secure Linkable Ring Signatures from Bilinear Maps

Xavier Boyen Thomas Haines

Cryptography Vol. 2 No. 4 pp. 35 · MDPI AG

View at Publisher Save 10.3390/cryptography2040035

Abstract

We present the first linkable ring signature scheme with both unconditional anonymity and forward-secure key update: a powerful tool which has direct applications in elegantly addressing a number of simultaneous constraints in remote electronic voting. We propose a comprehensive security model, and construct a scheme based on the hardness of finding discrete logarithms, and (for forward security) inverting bilinear or multilinear maps of moderate degree to match the time granularity of forward security. We prove efficient security reductions—which, of independent interest, apply to, and are much tighter than, linkable ring signatures without forward security, thereby vastly improving the provable security of these legacy schemes. If efficient multilinear maps should ever admit a secure realisation, our contribution would elegantly address a number of problems heretofore unsolved in the important application of (multi-election) practical Internet voting. Even if multilinear maps are never obtained, our minimal two-epoch construction instantiated from bilinear maps can be combinatorially boosted to synthesise a polynomial time granularity, which would be sufficient for Internet voting and more.

Topics

No keywords indexed for this article. Browse by subject →

References

27

[1]

Liu "Linkable ring signature with unconditional anonymity" IEEE Trans. Knowl. Data Eng. (2014) 10.1109/tkde.2013.17

[2]

Fujisaki, E., and Suzuki, K. (2007, January 16–20). Traceable ring signature. Proceedings of the 10th International Conference on Practice and Theory in Public-Key Cryptography, Beijing, China.

[3]

Boyen, X., and Haines, T. (2018). Forward-Secure Linkable Ring Signatures. Australasian Conference on Information Security and Privacy, Springer. 10.1007/978-3-319-93638-3_15

[4]

Garg, S., Gentry, C., and Halevi, S. (20132, January 26–30). Candidate multilinear maps from ideal lattices. Proceedings of the 32nd Annual International Conference on the Theory and Applications of Cryptographic Techniques, Athens, Greece.

[5]

Langlois, A., Stehlé, D., and Steinfeld, R. (2014, January 11–15). GGHlite: More efficient multilinear maps from ideal lattices. Proceedings of the 33rd Annual International Conference on the Theory and Applications of Cryptographic Techniques, Copenhagen, Denmark. 10.1007/978-3-642-55220-5_14

[6]

Liu, J.K., Wei, V.K., and Wong, D.S. (2004). Linkable spontaneous anonymous group signature for ad hoc groups. Information Security and Privacy, Springer. 10.1007/978-3-540-27800-9_28

[7]

Pointcheval "Security proofs for signature schemes" Eurocrypt (1996)

[8]

Pedersen, T.P. (1991, January 11–15). Non-interactive and information-theoretic secure verifiable secret sharing. Proceedings of the Annual International Cryptology Conference (CRYPTO ’91), Santa Barbara, CA, USA.

[9]

Davies "Group signatures" Lecture Notes in Computer Science (1991) 10.1007/3-540-46416-6_22

[10]

Rivest, R.L., Shamir, A., and Tauman, Y. (2001, January 9–13). How to leak a secret. Proceedings of the 7th International Conference on the Theory and Application of Cryptology and Information Security, Gold Coast, Australia. 10.1007/3-540-45682-1_32

[11]

Boneh "Applications of multilinear forms to cryptography" Contemp. Math. (2003) 10.1090/conm/324/05731

[12]

Boneh "Immunizing multilinear maps against zeroizing attacks" IACR Cryptol. ePrint Arch. (2014)

[13]

Cheon, J.H., Han, K., Lee, C., Ryu, H., and Stehlé, D. (2015, January 26–30). Cryptanalysis of the multilinear map over the integers. Proceedings of the Annual International Conference on the Theory and Applications of Cryptographic Techniques, Sofia, Bulgaria. 10.1007/978-3-662-46800-5_1

[14]

Coron, J.S., Lepoint, T., and Tibouchi, M. (2013). Practical multilinear maps over the integers. Advances in Cryptology—CRYPTO, Springer. 10.1007/978-3-642-40041-4_26

[15]

Gentry, C., Gorbunov, S., and Halevi, S. (2015). Graph-induced multilinear maps from lattices. Theory of Cryptography, Springer. 10.1007/978-3-662-46497-7_20

[16]

Adida, B. (August, January 28). Helios: Web-based open-audit voting. Proceedings of the USENIX Security, San Jose, CA, USA.

[17]

Demirel, D., Van De Graaf, J., and Araújo, R. (2012, January 6–7). Improving helios with everlasting privacy towards the public. Proceedings of the eVOTE/Trustworthy Elections (USENIX), Bellevue, WA, USA.

[18]

Tsoukalas "From helios to zeus" USENIX J. Elect. Technol. Syst. (2013)

[19]

Adida, B. (2010). Helios v3 Verification Specs, Helios Voting. Technical Report.

[20]

Zhandry "Adaptively secure broadcast encryption with small system parameters" IACR Cryptol. ePrint Arch. (2014)

[21]

Hu, Y., and Jia, H. (2016, January 8–12). Cryptanalysis of GGH map. Proceedings of the 35th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Vienna, Austria. 10.1007/978-3-662-49890-3_21

[22]

Albrecht, M.R., Bai, S., and Ducas, L. (2016, January 14–18). A subfield lattice attack on overstretched NTRU assumptions. Proceedings of the 36th Annual International Cryptology Conference, Santa Barbara, CA, USA. 10.1007/978-3-662-53018-4_6

[23]

Cheon "An algorithm for NTRU problems and cryptanalysis of the GGH multilinear map without a low level encoding of zero" LMS J. Comput. Math. (2016) 10.1112/s1461157016000371

[24]

Cramer, R., Ducas, L., Peikert, C., and Regev, O. (2016, January 8–12). Recovering short generators of principal ideals in cyclotomic rings. Proceedings of the Annual International Conference on the Theory and Applications of Cryptographic Techniques, Vienna, Austria. 10.1007/978-3-662-49896-5_20

[25]

Miles, E., Sahai, A., and Zhandry, M. (2016, January 14–18). Annihilation attacks for multilinear maps: Cryptanalysis of indistinguishability obfuscation over GGH13. Proceedings of the 36th Annual International Cryptology Conference, Santa Barbara, CA, USA. 10.1007/978-3-662-53008-5_22

[26]

Paneth "On the equivalence of obfuscation and multilinear maps" IACR Cryptol. ePrint Arch. (2015)

[27]

Barak "On the (im)possibility of obfuscating programs" J. ACM (2012) 10.1145/2160158.2160159

Metrics

8

Citations

27

References

Details

Published: Nov 08, 2018
Vol/Issue: 2(4)
Pages: 35
License: View

Authors

X

Xavier Boyen

Queensland University of Technology, Brisbane 4000, Australia

T

Thomas Haines

Polyas GmbH, 10179 Berlin, Germany

Funding

Australian Research Council Award: FT140101145

Cite This Article

Xavier Boyen, Thomas Haines (2018). Forward-Secure Linkable Ring Signatures from Bilinear Maps. Cryptography, 2(4), 35. https://doi.org/10.3390/cryptography2040035

Forward-Secure Linkable Ring Signatures from Bilinear Maps

You May Also Like