deterministic — Blog — Ismael S.-M.

While I was writing my NSERC Proposal for grad school, I came across the field of combinatorial design theory (CDT). Specifically, I came across it's application of Block Design in CDT to deterministic key pre-distribution schemes (KPS) in wireless sensor network. In other words, cryptographic networks with very small computer nodes with little storage where you don't know they're configuration to each other beforehand. Although I am choosing to pursue network optimization for my grad studies, I find this field of CDT quite interesting, especially in the way it can be turned into a cryptography problem. I want to break down the basics of Block Design, and how this can be viewed in cryptography.

In Block Design, we work with a set system (I, B), where I is a set of v elements, and B is a collection of subsets of the elements in I. The elements in I are called points and the subsets in B are called blocks. As an example, if I has 100 numbered points, and each block in B has 20 elements, then you could have one blocks (1,2,3,4,...,20), and a second block (1,3,4,5,...,21). In other words, these blocks could have overlapping. For any element x in I, we say the degree r of x is the number of blocks in which x appears. If all x in I have the same degree r, then (I, B) is called regular. The rank k of (I,B) is the largest sized block in B. If all blocks are the same size k, we say (I,B) is uniform.

Let's put all the above information together. A regular, uniform set system with |I| = v and |B| = b is known as a (v, b, r, k)-design. In such designs, it must be the case that bk = vr. Note, that b is the number of blocks in B whereas k is the number of points in each block. Taking it one step further, a (v, b, r, k)-design where every t points appears in precisely λ blocks is known as a t-(v, b, r, k, λ)-design. Since r and b can be derived from the other variables, we usually just call it a t-(v, k, λ)-design

How does this all relate to cryptography?! First, note that we're talking about a KPS system for sensor node - tiny computers with limited storage space. We want to assign a set of keys to each node such that two nodes that are within talking range that have the same key can securely communicate: this is the basis of cryptography. Going back to Block Design, we can call I the set of total possible keys we have to distribute, and B the collection of sensor nodes. v would be size of I, or the total number of possible keys, k would be the maximum number of keys any sensor node could have, and t and λ would represent a cluster of t keys showing up in λ sensor nodes.

It turns out that by turning this problem in cryptography into a CDT problem, we can make a lot of headway into finding a deterministic way of solving the KPS problems while balancing all the trade-offs such a network faces. Up until this was researched, probabilistic KPS was the main research done in this field, which essentially came down to randomly assigning keys to each sensor node in hopes two with the same key would fall near each other. With the deterministic approach, we take the guess work out of it and get a more stable solution to this problem.

Reference

K. M. Martin, On the Applicability of Combinatorial Designs to Key Predistribution for Wireless
Sensor Networks, In: Chee Y.M., Li C., Ling S., Wang H., Xing C. (eds) Coding and Cryptology.
IWCC 2009. Lecture Notes in Computer Science, vol 5557. Springer, Berlin, Heidelberg (2009).