Graph-theoretic design and analysis of key predistribution schemes

Alon, Noga, Milman, Vitali D.: $$\lambda _i$$ λ i , Isoperimetric inequalities for graphs, and superconcentrators. Journal of Combinatorial Theory, Series B 38(1), 73–88 (1985)

Alon N., Spencer J.H.: The Probabilistic Method. Wiley, Hoboken (2000).

Bailey R.A., Cameron P.J.: Combinatorics of optimal designs. Surv. Comb. 365, 19–73 (2009).

Bailey R.A., Cameron P.J.: Using graphs to find the best block designs. Preprint. http://uk.arxiv.org/abs/1111.3768 (2011).

Bapat R.B., Dey A.: Optimal block designs with minimal number of observations. Stat. Probab. Lett. 11(5), 399–402 (1991).

Blackburn S.R., Gerke S.: Connectivity of the uniform random intersection graph. Discret. Math. 309(16), 5130–5140 (2009).

Bollobás B.: Combinatorics: Set Systems, Hypergraphs, Families of Vectors, and Combinatorial Probability. Cambridge University Press, Cambridge (1986).

Buser P.A.: A note on the isoperimetric constant. Ann. Sci. l’Éc. Norm. Supér. 15(2), 213–230 (1982).

Cakiroglu S.A.: An upper bound on the algebraic connectivity of regular graphs. Preprint. http://arxiv.org/abs/1503.01758 (2014).

Cameron P.J.: Combinatorics: Topics, Techniques, Algorithms. Cambridge University Press, Cambridge (1994).

Cameron P.J.: Permutation Groups. Cambridge University Press, Cambridge (1999).

Cameron P.J.: Random strongly regular graphs. Electron. Notes Discret. Math. 10, 54–63 (2001). http://maths.qmul.ac.uk/pjc/preprints/randsrg.pdf .

Cameron P.J.: Strongly regular graphs. Preprint. http://designtheory.org/library/preprints/srg.pdf (2001).

Cameron P.J., van Lint J.H.: Graph Theory, Coding Theory and Block Designs. London Mathematical Society Lecture Note Series. Cambridge University Press, Cambridge (1975).

Çamtepe S.A., Yener B.: Combinatorial design of key distribution mechanisms for wireless sensor networks. In: Computer Security—ESORICS 2004. Lecture Notes in Computer Science, vol. 3193, pp. 293–308. Springer, Heidelberg (2004).

Çamtepe S.A., Yener B.: Key distribution mechanisms for wireless sensor networks: a survey. Rensselaer Polytechnic Institute, Computer Science Department, Technical Report TR-05-07 (2005).

Çamtepe S.A., Yener B., Yung M.: Expander graph based key distribution mechanisms in wireless sensor networks. In: IEEE International Conference on Communications, ICC 06, pp. 2262–2267 (2006).

Chan H., Perrig A., Song D.: Random key predistribution schemes for sensor networks. In: SP ’03, Proceedings of the 2003 IEEE Symposium on Security and Privacy. IEEE Computer Society, pp. 197–213. IEEE Computer Society Press, Los Alamitos (2003).

Cheeger J.: A lower bound for the smallest eigen value of the Laplacian. Probl. Anal. 625, 195–199 (1970).

Chen W.-K.: Applied Graph Theory: Graphs and Electrical Networks. North-Holland, Amsterdam (1976).

Chen C.-Y., Chao H.-C.: A survey of key distribution in wireless sensor networks. Secur. Commun. Netw. 7(12), 2495–2508 (2011).

Cheng C.-S., Bailey R.A.: Optimality of some two-associate-class partially balanced incomplete-block designs. Ann. Stat. 19(3), 1667–1671 (1991).

Chung F.R.K.: Spectral graph theory. In: CBMS Conference on Recent Advances in Spectral Graph Theory. American Mathematical Society, Providence (1997).

Colbourn C.J., Dinitz J.H.: Handbook of Combinatorial Designs. CRC Press, Boca Raton (2010).

Davidoff G., Sarnak P., Valette A.: Elementary Number Theory, Group Theory and Ramanujan Graphs. London Mathematical Society Student Texts, vol. 55. Cambridge University Press, Cambridge (2003).

Desmedt Y., Duif N., van Tilborg H., Wang H.: Bounds and constructions for key distribution schemes. Adv. Math. Commun. 3(3), 273–293 (2009).

Di Pietro R., Mancini L.V., Mei A., Panconesi A., Radhakrishnan J.: Redoubtable sensor networks. ACM Trans. Inf. Syst. Secur. (TISSEC) 11(3), 1–22 (2008).

Dodziuk J.: Difference equations, isoperimetric inequality and transience of certain random walks. Trans. Am. Math. Soc. 284(2), 787–794 (1984).

Dodziuk J., Kendall W.S.: Combinatorial Laplacians and isoperimetric inequality: from local times to global geometry. Control Phys. 150, 68–74 (1986).

Dolev D., Dwork C., Waarts O., Yung M.: Perfectly secure message transmission. J. ACM 40(1), 17–47 (1993).

Erdös P., Rényi A.: On the evolution of random graphs. In: Publication of the Mathematical Institute of the Hungarian Academy of Sciences, pp. 17–61 (1960).

Eschenauer L., Gligor V.D.: A key-management scheme for distributed sensor networks. In: Proceedings of the 9th ACM Conference on Computer and Communications Security—CCS ’02, pp. 41–47. ACM, New York (2002).

Friedman J.: Some graphs with small second eigenvalue. Combinatorica 15(1), 31–42 (1995).

Friedman J., Wigderson A.: On the second eigenvalue of hypergraphs. Combinatorica 15(1), 43–65 (1995).

Harary F: Graph Theory. Addison-Wesley, Reading (1969).

Hoory S., Linial N., Wigderson A.: Expander graphs and their applications. Bull. Am. Math. Soc. 43(4), 439–562 (2006).

Kendall M., Martin K.M.: On the role of expander graphs in key predistribution schemes for wireless sensor networks. In: Research in Cryptology. Lecture Notes in Computer Science, vol. 7242, pp. 62–82. Springer, Heidelberg (2012).

Kendall M., Kendall E., Kendall W.S.A.: A generalised formula for calculating the resilience of random key predistribution schemes. ICAR Cryptol. 2012, 426 (2012). http://eprint.iacr.org/2012/426 .

Kendall M., Martin K.M., Ng S.L., Paterson M.B., Stinson D.R.: Broadcast-enhanced key predistribution schemes. ACM Trans. Sens. Netw. 11(1), 6:1–6:33 (2014).

Kleinberg J., Rubinfeld R.: Short paths in expander graphs. IEEE Annu. Symp. Found. Comput. Sci. 37, 86–95 (1996).

Lanphier D., Miller C., Rosenhouse J., Russell A.: Expansion properties of Levi graphs. ARS Comb. 80(3), 1–7 (2006).

Lee J., Stinson D.R.: A combinatorial approach to key predistribution for distributed sensor networks. In: IEEE Wireless Communications and Networking Conference, pp. 1200–1205. IEEE, New Orleans (2005).

Lee J., Stinson D.R.: Deterministic key predistribution schemes for distributed sensor networks. In: Selected Areas in Cryptography. Lecture Notes in Computer Science, vol. 3357, pp. 294–307. Springer, Heidelberg (2005).

Lee J., Stinson D.R.: Common intersection designs. J. Comb. Des. 14(4), 251–269 (2006).

Levi F.W.: Finite Geometrical Systems: Six Public Lectures Delivered in February, 1940, at the University of Calcutta. The University of Calcutta (1942).

Nilli A.: On the second eigenvalue of a graph. Discret. Math. 91(2), 207–210 (1991).

Paterson M.B., Stinson D.R.: A unified approach to combinatorial key predistribution schemes for sensor networks. Des. Codes Cryptogr. 71, 433–457 (2014).

Purdy E.: Locally expanding hypergraphs and the unique games conjecture. PhD Thesis, University of Chicago (2008).

Shafiei H., Mehdizadeh A., Khonsari A., Ould-Khaoua M.: A combinatorial approach for key-distribution in wireless sensor networks. In: IEEE Global Telecommunications Conference, pp. 1–5. IEEE, Houston (2008).

van Lint J.H., Schrijver A.: Construction of strongly regular graphs, two-weight codes and partial geometries by finite fields. Combinatorica 1(1), 63–73 (1981).

Wallis W.D.: Combinatorial Designs. Pure and Applied Mathematics. Marcel Dekker, New York (1988).

Xiao Y., Rayi V.K., Sun B., Du X., Hu F., Galloway M.: A survey of key management schemes in wireless sensor networks. Comput. Commun. 30(11–12), 2314–2341 (2007).

Yağan O., Makowski A.M.: On the existence of triangles in random key graphs with a note on their small-world property. Preprint. http://andrew.cmu.edu/user/oyagan/Journals/IT_Triangle.pdf (2013).