International Association for Cryptologic Research

International Association
for Cryptologic Research


Paper: Attacking Cryptographic Schemes Based on "Perturbation Polynomials"

Martin R. Albrecht
Craig Gentry
Shai Halevi
Jonathan Katz
Search ePrint
Search Google
Abstract: We show attacks on several cryptographic schemes that have recently been proposed for achieving various security goals in sensor networks. Roughly speaking, these schemes all use "perturbation polynomials" to add "noise" to polynomial-based systems that offer information-theoretic security, in an attempt to increase the resilience threshold while maintaining efficiency. We show that the heuristic security arguments given for these modified schemes do not hold, and that they can be completely broken once we allow even a slight extension of the parameters beyond those achieved by the underlying information-theoretic schemes. Our attacks apply to the key predistribution scheme of Zhang et al. (MobiHoc~2007), the access-control schemes of Subramanian et al. (PerCom~2007), and the authentication schemes of Zhang et~al. (INFOCOM~2008).
  title={Attacking Cryptographic Schemes Based on "Perturbation Polynomials"},
  booktitle={IACR Eprint archive},
  keywords={cryptographic protocols / cryptanalysis, lattice techniques, key pre-distribution},
  note={ 14301 received 26 Feb 2009},
  author={Martin R. Albrecht and Craig Gentry and Shai Halevi and Jonathan Katz},