Improved topology assumptions for threshold cryptography in mobile ad hoc networks

ABSTRACT

Mobile Ad Hoc Networks (MANET), due to their lack of physical infrastructures or centralized authorities, pose a number of security challenges to a protocol designer. In particular, several typical application scenarios demand the design of protocols that cannot base their security on the existence of trusted parties or setup information, but rather need to leverage uniquely on assumptions limiting the corrupting power of the adversaries. This naturally defines security design and analysis paradigms similar to those of the Threshold Cryptography area, where it is typically assumed that an adversary can corrupt up to a limited amount of entities or resources. Therefore a secure realization of primitives from Threshold Cryptography in MANET promises to be applicable to several MANET protocols.Recently, in [10], we started the analysis of Threshold Cryptography solutions over MANET, by focusing on the problem of extending to these networks known efficient threshold signature schemes for wired networks. In particular, we noted a major design difficulty due to the lack of full network connectivity that significantly constrained the network topology assumptions under which a MANET threshold signature scheme can be proved secure. In this paper we continue our investigation and present a new MANET threshold signature scheme that is secure under significantly improved topology assumptions. Surprisingly, we break through an apparent barrier due to well-known results from the Distributed Computing area.

REFERENCES

• 1: D. Beaver and S. Haber, Cryptographic Protocols Provably Secure Against Dynamic Adversaries, in Proc. of Eurocrypt 1992.
• 2: Christian Bettstetter , Giovanni Resta , Paolo Santi, The Node Distribution of the Random Waypoint Mobility Model for Wireless Ad Hoc Networks, IEEE Transactions on Mobile Computing, v.2 n.3, p.257-269, March 2003 [doi>10.1109/TMC.2003.1233531]
• 3: R. B. Bobba, L. Eschenauer, V. Gligor, and W. Arbaugh, Bootstrapping Security Associations for Routing in MANETs, in Institute for Systems Research, ISR Technical Report 2002--44, May 2002
• 4: Dan Boneh , Matthew K. Franklin, Efficient Generation of Shared RSA Keys (Extended Abstract), Proceedings of the 17th Annual International Cryptology Conference on Advances in Cryptology, p.425-439, August 17-21, 1997
• 5: Dan Boneh , Ben Lynn , Hovav Shacham, Short Signatures from the Weil Pairing, Proceedings of the 7th International Conference on the Theory and Application of Cryptology and Information Security: Advances in Cryptology, p.514-532, December 09-13, 2001
• 6: Yvo G. Desmedt , Yair Frankel, Threshold cryptosystems, Proceedings on Advances in cryptology, p.307-315, July 1989, Santa Barbara, California, United States
• 7: Y. Desmedt, Threshold Cryptography, in European Transaction of Telecommunications, vol. 5, n, 4, 1994.
• 8: Giovanni Di Crescenzo, Security of erasable memories against adaptive adversaries, Proceedings of the 2005 ACM workshop on Storage security and survivability, November 11-11, 2005, Fairfax, VA, USA [doi>10.1145/1103780.1103798]
• 9: G. Di Crescenzo, N. Ferguson, R. Impagliazzo and M. Jakobsson, How to Forget a Secret, in Proc. of STACS 2000.
• 10: G. Di Crescenzo, R. Ge and G. Arce, Threshold Cryptography over Mobile Ad Hoc Networks, in Proc. of SCN 2004.
• 11: P. Feldman, A Practical Scheme for Non-Interactive Verifiable Secret Sharing, in Proc. of FOCS 87.
• 12: R. Gennaro, S. Jarecki, H. Krawczyk and T. Rabin, Revisiting the Distributed Key Generation for Discrete Log Based Cryptosystems, in Proc. of RSA security conf. 03.
• 13: Amir Herzberg , Stanislaw Jarecki , Hugo Krawczyk , Moti Yung, Proactive Secret Sharing Or: How to Cope With Perpetual Leakage, Proceedings of the 15th Annual International Cryptology Conference on Advances in Cryptology, p.339-352, August 27-31, 1995
• 14: Aram Khalili , Jonathan Katz , William A. Arbaugh, Toward Secure Key Distribution in Truly Ad-Hoc Networks, Proceedings of the 2003 Symposium on Applications and the Internet Workshops (SAINT'03 Workshops), p.342, January 27-31, 2003
• 15: G. Montenegro and C. Castelluccia, Statistically Unique and Cryptographically Verifiable (SUCV) Identifier and Addresses, in Proc. of NDSS 2002.
• 16: James Newsome , Elaine Shi , Dawn Song , Adrian Perrig, The sybil attack in sensor networks: analysis & defenses, Proceedings of the third international symposium on Information processing in sensor networks, April 26-27, 2004, Berkeley, California, USA [doi>10.1145/984622.984660]
• 17: Greg O'Shea , Michael Roe, Child-proof authentication for MIPv6 (CAM), ACM SIGCOMM Computer Communication Review, v.31 n.2, April 2001 [doi>10.1145/505666.505668]
• 18: A Threshold Cryptosystem without a Trusted Party, in Proc. of Eurocrypt 91.
• 19: Round Optimal Distributed Key Generation of Threshold Cryptosystem based on Discrete Logarithm Problem, in Proc. of ACNS 2003.
• 20: L. Zhou and Z. J. Haas. Securing Ad Hoc Networks, in IEEE Network Magazine, vol. 13, no.6, 1999.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY

Additional Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Graph algorithms; Network problems
  G.4 MATHEMATICAL SOFTWARE
      Subjects: Algorithm design and analysis

  J. Computer Applications
  J.7 COMPUTERS IN OTHER SYSTEMS
      Subjects: Military

General Terms:
Algorithms, Security, Theory

Keywords:
distributed cryptography, mobile ad hoc networks, threshold cryptography, threshold signatures