TY - CONF T1 - Attacking cryptographic schemes based on "perturbation polynomials" T2 - Proceedings of the 16th ACM conference on Computer and communications security Y1 - 2009 A1 - Albrecht,Martin A1 - Gentry,Craig A1 - Halevi,Shai A1 - Katz, Jonathan KW - pairwise key establishment KW - random perturbation polynomial KW - sensor network security AB - 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 polynomialbased 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). Our results cast doubt on the viability of using "perturbation polynomials" for designing secure cryptographic schemes. JA - Proceedings of the 16th ACM conference on Computer and communications security T3 - CCS '09 PB - ACM CY - New York, NY, USA SN - 978-1-60558-894-0 UR - http://doi.acm.org/10.1145/1653662.1653664 M3 - 10.1145/1653662.1653664 ER -