research-article

Pairing-Based Onion Routing with Improved Forward Secrecy

Authors:

Greg M. Zaverucha,

Ian GoldbergAuthors Info & Claims

ACM Transactions on Information and System Security (TISSEC), Volume 13, Issue 4

Article No.: 29, Pages 1 - 32

https://doi.org/10.1145/1880022.1880023

Published: 01 December 2010 Publication History

Abstract

This article presents new protocols for onion routing anonymity networks. We define a provably secure privacy-preserving key agreement scheme in an identity-based infrastructure setting, and use it to design new onion routing circuit constructions. These constructions, based on a user’s selection, offer immediate or eventual forward secrecy at each node in a circuit and require significantly less computation and communication than the telescoping mechanism used by the Tor project. Further, the use of an identity-based infrastructure also leads to a reduction in the required amount of authenticated directory information. Therefore, our constructions provide practical ways to allow onion routing anonymity networks to scale gracefully.

References

[1]

Blake, I., Seroussi, G., and Smart, N. P., Eds. 2005. Advances in Elliptic Curve Cryptography. London Mathematical Society Lecture Note Series, No. 317, Cambridge University Press, Cambridge, UK. 183--252.

Digital Library

[2]

Boneh, D. and Franklin, M. 2001. Identity-based encryption from the weil pairing. In Proceedings of the International Cryptology Conference, Advances in Cryptology (CRYPTO’01). Lecture Notes in Computer Science, vol. 2139, Springer, 213--229.

Digital Library

[3]

Camenisch, J. and Lysyanskaya, A. 2005. A formal treatment of onion routing. In Proceedings of the International Cryptology Conference, Advances in Cryptology (CRYPTO’05). Lecture Notes in Computer Science, vol. 3621, Springer, 169--187.

Digital Library

[4]

Canetti, R. 2001. Universally composable security: A new paradigm for cryptographic protocols. In Proceedings of the 42nd IEEE Symposium on Foundations of Computer Science (FOCS’01). IEEE Computer Society, 136--145.

Digital Library

[5]

Canetti, R., Halevi, S., and Katz, J. 2007. A forward-secure public-key encryption scheme. J. Cryptol. 20, 3, 265--294.

Digital Library

[6]

Chaum, D. 1981. Untraceable electronic mail, return addresses, and digital pseudonyms. Comm. ACM 4, 2, 84--88.

Digital Library

[7]

Chien, H. and Lin, R. 2006. Identity-based key agreement protocol for mobile ad-hoc networks using bilinear pairing. In Proceedings of the IEEE International Conference on Sensor Networks, Ubiquitous, and Trustworthy Computing (SUTC’06). IEEE Computer Society, 520--529.

Digital Library

[8]

Coron, J.-S. 2000. On the exact security of full domain hash. In Proceedings of the International Cryptology Conference, Advances in Cryptology (CRYPTO’00). Lecture Notes in Computer Science, vol. 1880, Springer, 229--235.

Digital Library

[9]

Dai, W. 1998. PipeNet 1.1. http://www.weidai.com/pipenet.txt.

[10]

Dingledine, R. and Mathewson, N. 2008. Tor protocol specification. https://www.torproject.org/svn/trunk/doc/spec/tor-spec.txt.

[11]

Dingledine, R., Mathewson, N., and Syverson, P. 2004. Tor: The second-generation onion router. In Proceedings of the 13th USENIX Security Symposium. USENIX, 303--320.

Digital Library

[12]

Dupont, R. and Enge, A. 2006. Provably secure non-interactive key distribution based on pairings. Discr. Appl. Math. 154, 2, 270--276.

Digital Library

[13]

Freedman, M. J. and Morris, R. 2002. Tarzan: A peer-to-peer anonymizing network layer. In Proceedings of the 9th ACM Conference on Computer and Communications Security (CCS’02). ACM, 193--206.

Digital Library

[14]

Goldberg, I. 2006. On the security of the tor authentication protocol. In Proceedings of the 6th Workshop on Privacy Enhancing Technologies (PET’06). Lecture Notes in Computer Science, vol. 4258, Springer, 316--331.

Digital Library

[15]

Goldschlag, D., Reed, M., and Syverson, P. 1996. Hiding routing information. In Proceedings of the 1st Internationa Workshop on Information Hiding. Lecture Notes in Computer Science, vol. 1174, Springer, 137--150.

Digital Library

[16]

Huang, D. 2007. Pseudonym-based cryptography for anonymous communications in mobile ad hoc networks. Int. J. Secur. Netw. 2, 3-4, 272--283.

Digital Library

[17]

Kate, A. and Goldberg, I. 2007. A distributed private-key generator for identity-based cryptography. Tech. rep. CACR 2007-33, Centre for Applied Cryptographic Research. http://www.cacr.math.uwaterloo.ca/techreports/2007/cacr2007-33.pdf.

[18]

Kate, A., Zaverucha, G. M., and Goldberg, I. 2007a. Pairing-based onion routing. In Proceedings of the 7th Privacy Enhancing Technologies Symposium (PETS’07). Lecture Notes in Computer Science, vol. 4776, Springer, 95--112.

Digital Library

[19]

Kate, A., Zaverucha, G. M., and Hengartner, U. 2007b. Anonymity and security in delay tolerant networks. In Proceedings of the 3rd International Conference on Security and Privacy in Communication Networks (SecureComm’07). IEEE Computer Society, 504--513.

[20]

Khalili, A., Katz, J., and Arbaugh, W. 2003. Toward secure key distribution in truly ad-hoc networks. In Proceedings of the IEEE Workshop on Security and Assurance in Ad-Hoc Networks. IEEE Computer Society, 342--346.

Digital Library

[21]

Koblitz, N. and Menezes, A. 2005. Pairing-based cryptography at high security levels. In Proceedings of the 10th IMA International Conference on Cryptography and Coding. Lecture Notes in Computer Science, vol. 3796, Springer, 13--36.

Digital Library

[22]

Lynn, B. 2008. PBC library---The pairing-based cryptography library. http://crypto.stanford.edu/pbc/.

[23]

Mauw, S., Verschuren, J., and de Vink, E. 2004. A formalization of anonymity and onion routing. In Proceedings of the 9th European Symposium on Research Computer Security (ESORICS’04). Lecture Notes in Computer Science, vol. 3193, Springer, 109--124.

[24]

Menezes, A., Okamoto, T., and Vanstone, S. 1991. Reducing elliptic curve logarithms to logarithms in a finite field. In Proceedings of the 23rd Annual ACM Symposium on Theory of Computing (STOC’91). ACM, 80--89.

Digital Library

[25]

Menezes, A., Oorschot, P. V., and Vanstone, S. 1997. Handbook of Applied Cryptography 1st Ed. CRC Press, Boca Raton, FL.

Digital Library

[26]

Möller, B. 2003. Provably secure public-key encryption for length-preserving chaumian mixes. In Proceedings of the Cryptographers’ Track at the RSA Conference (CT-RSA’03). Lecture Notes in Computer Science, vol. 2612, Springer, 244--262.

Digital Library

[27]

Okamoto, E. and Okamoto, T. 2005. Cryptosystems based on elliptic curve pairing. In Proceedings of the Conference on Modeling Decisions for Artificial Intelligence (MDAI’05). Lecture Notes in Computer Science, vol. 3558, Springer, 13--23.

Digital Library

[28]

Øverlier, L. and Syverson, P. 2007. Improving efficiency and simplicity of tor circuit establishment and hidden services. In Proceedings of the 7th Privacy Enhancing Technologies Symposium (PETS’07). Lecture Notes in Computer Science, vol. 4776, Springer, 134--152.

Digital Library

[29]

Rahman, S., Inomata, A., Okamoto, T., Mambo, M., and Okamoto, E. 2006. Anonymous secure communication in wireless mobile ad-hoc networks. In Proceedings of the 1st International Conference on Ubiquitous Convergence Technology (ICUCT’06). Lecture Notes in Computer Science, vol. 4412, Springer, 140--149.

Digital Library

[30]

Reed, M., Syverson, P., and Goldschlag, D. 1998. Anonymous connections and onion routing. IEEE J. Select. Areas Comm. 16, 4, 482--494.

Digital Library

[31]

Rennhard, M. and Plattner, B. 2002. Introducing MorphMix: Peer-to-peer based anonymous internet usage with collusion detection. In Proceedings of the Workshop on Privacy in the Electronic Society (WPES’02). ACM, 91--102.

Digital Library

[32]

Sakai, R., Ohgishi, K., and Kasahara, M. 2000. Cryptosystems based on pairing. In Proceedings of the Symposium on Cryptography and Information Security (SCIS’00).

[33]

Seth, A. and Keshav, S. 2005. Practical security for disconnected nodes. In Proceedings of the IEEE ICNP Workshop on Secure Network Protocols (NPSec’05). IEEE Computer Society, 31--36.

Digital Library

[34]

Shamir, A. 1979. How to share a secret. Comm. ACM 22, 11, 612--613.

Digital Library

[35]

Syverson, P., Tsudik, G., Reed, M., and Landwehr, C. 2000. Towards an analysis of onion routing security. In Proceedings of the Designing Privacy Enhancing Technologies: Workshop on Design Issues in Anonymity and Unobservability. Lecture Notes in Computer Science, vol. 2009, Springer, 96--114.

Digital Library

[36]

Tor Project. 2008. Tor: Anonymity online. https://www.torproject.org/.

[37]

Verheul, E. 2001. Evidence that XTR is more secure than supersingular elliptic curve cryptosystems. In Proceedings of the International Cryptology Conference, Advances in Cryptology (Eurocrypt’01). Lecture Notes in Computer Science, vol. 2045, Springer, 195--210.

Digital Library

Cited By

Pierre SMejri M(2024)DIDOR: A Decentralized Identifier Based Onion Routing ProtocolSafe, Secure, Ethical, Responsible Technologies and Emerging Applications10.1007/978-3-031-56396-6_5(71-85)Online publication date: 18-Apr-2024
https://doi.org/10.1007/978-3-031-56396-6_5
Kuhn CHofheinz DRupp AStrufe T(2021)Onion Routing with RepliesAdvances in Cryptology – ASIACRYPT 202110.1007/978-3-030-92075-3_20(573-604)Online publication date: 1-Dec-2021
https://doi.org/10.1007/978-3-030-92075-3_20
Lauer SGellert KMerget RHandirk TSchwenk J(2020)T0RTT: Non-Interactive Immediate Forward-Secret Single-Pass Circuit ConstructionProceedings on Privacy Enhancing Technologies10.2478/popets-2020-00302020:2(336-357)Online publication date: 8-May-2020
https://doi.org/10.2478/popets-2020-0030
Show More Cited By

Index Terms

Pairing-Based Onion Routing with Improved Forward Secrecy

Recommendations

Certificateless onion routing
CCS '09: Proceedings of the 16th ACM conference on Computer and communications security

Onion routing protocols allow users to establish anonymous channels to preserve their privacy over a public network. Several protocols implementing this primitive have been proposed in recent years, and TOR, a real-life implementation, provides an onion ...
Fully non-interactive onion routing with forward secrecy

Onion routing is a privacy-enabling protocol that allows users to establish anonymous channels over a public network. In such a protocol, parties send their messages through $$n$$ anonymizing servers (called a circuit ) using several layers of encryption. ...
A certificateless approach to onion routing

Onion routing protocols allow users to establish anonymous channels to preserve their privacy over a public network. Several protocols implementing this primitive have been proposed in recent years, and The onion routing network (Tor), a real-life ...

Comments

Information & Contributors

Information

Published In

cover image ACM Transactions on Information and System Security

ACM Transactions on Information and System Security Volume 13, Issue 4

December 2010

412 pages

ISSN:1094-9224

EISSN:1557-7406

DOI:10.1145/1880022

Issue’s Table of Contents

Copyright © 2010 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 December 2010

Accepted: 01 February 2009

Revised: 01 February 2009

Received: 01 February 2008

Published in TISSEC Volume 13, Issue 4

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article
Research
Refereed

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

21
Total Citations
View Citations
830
Total Downloads

Downloads (Last 12 months)18
Downloads (Last 6 weeks)1

Reflects downloads up to 14 Sep 2024

Other Metrics

View Author Metrics

Citations

Cited By

Pierre SMejri M(2024)DIDOR: A Decentralized Identifier Based Onion Routing ProtocolSafe, Secure, Ethical, Responsible Technologies and Emerging Applications10.1007/978-3-031-56396-6_5(71-85)Online publication date: 18-Apr-2024
https://doi.org/10.1007/978-3-031-56396-6_5
Kuhn CHofheinz DRupp AStrufe T(2021)Onion Routing with RepliesAdvances in Cryptology – ASIACRYPT 202110.1007/978-3-030-92075-3_20(573-604)Online publication date: 1-Dec-2021
https://doi.org/10.1007/978-3-030-92075-3_20
Lauer SGellert KMerget RHandirk TSchwenk J(2020)T0RTT: Non-Interactive Immediate Forward-Secret Single-Pass Circuit ConstructionProceedings on Privacy Enhancing Technologies10.2478/popets-2020-00302020:2(336-357)Online publication date: 8-May-2020
https://doi.org/10.2478/popets-2020-0030
Zuo ZChang CZhang YHe RQin XYung K(2020)P4Label: packet forwarding control mechanism based on P4 for software-defined networkingJournal of Ambient Intelligence and Humanized Computing10.1007/s12652-020-01719-3Online publication date: 29-Jan-2020
https://doi.org/10.1007/s12652-020-01719-3
Sengupta JRuj SBit SHansdah RKrishnaswamy DVaidya N(2019)End to end secure anonymous communication for secure directed diffusion in IoTProceedings of the 20th International Conference on Distributed Computing and Networking10.1145/3288599.3295577(445-450)Online publication date: 4-Jan-2019
https://dl.acm.org/doi/10.1145/3288599.3295577
Catalano DFiore DGennaro R(2017)A certificateless approach to onion routingInternational Journal of Information Security10.1007/s10207-016-0337-x16:3(327-343)Online publication date: 1-Jun-2017
https://dl.acm.org/doi/10.1007/s10207-016-0337-x
Chaum DDas DJavani FKate AKrasnova ADe Ruiter JSherman A(2017)cMix: Mixing with Minimal Real-Time Asymmetric Cryptographic OperationsApplied Cryptography and Network Security10.1007/978-3-319-61204-1_28(557-578)Online publication date: 26-Jun-2017
https://doi.org/10.1007/978-3-319-61204-1_28
Xiong HQin ZVasilakos A(2016)ReferencesIntroduction to Certificateless Cryptography10.1201/9781315372693-13(273-305)Online publication date: 13-Oct-2016
https://doi.org/10.1201/9781315372693-13
Ghosh SKate A(2016)Post-Quantum Forward-Secure Onion RoutingApplied Cryptography and Network Security10.1007/978-3-319-28166-7_13(263-286)Online publication date: 9-Jan-2016
https://doi.org/10.1007/978-3-319-28166-7_13
Zhu H(2015)A provable privacy-protection system for multi-server environmentNonlinear Dynamics10.1007/s11071-015-2198-782:1-2(835-849)Online publication date: 16-Jun-2015
https://doi.org/10.1007/s11071-015-2198-7
Show More Cited By

View Options

Get Access

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Article

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Issue’s Table of Contents