Zero-Knowledge Proofs: keeping a secret a secret.

Certain situations in our lives require us letting people know we have the authority, or capability to do something, however we don't always want to disclose the details. When you apply for an appartment, how do you let the landlord know you can afford the rent without sharing your salary? When participating in a secret auction, how do the owners announce the winner without revealing any bids? This would be simple if everybody could be perfectly trusted, but when dealing with finances, reputation, and security, all parties want to ensure everything is truthful and fair. In some cases, proving you know a secret is equivalent to proving your identity; for example, if you had a recipe with a secret ingredient that only you knew, proving to others you know the secret ingredient would prove the dish you shared is indeed yours. In these cases, it is crucial that this information does not leak.

A solution to this problem became the basis for Zero-Knowledge Proofs (ZKP), techniques and protocols used in cryptographic proofs of authentication or knowledge without revealing any details. The original definitions of ZKP were based on an interaction between a pair of verifier and prover [1]. In many of these situations, a secret is known that grants a user authentication or verification. If this secret is stolen, others could pose as the original user and gain access to cryptographic systems.

The most essential properties of a zero-knowledge procedure is that an interaction between a verifier and prover can only end with the prover claiming its knowledge of a value x if the prover does in fact know x. The crucial result of this is that a prover who does know the secret cannot trick anybody into thinking otherwise; these two properties are known as completeness and soundness respectively. This is paramount for trustless systems; without the existence of a safeguard, a non-authenticated user could lie about its credentials in the hopes of fool others. The protocol should yield zero-knowledge to the verifier, meaning the verifier learns no new information from its interaction with the prover. Our last property is that of computational efficiency; in any cryptographic system, the time complexity taken for this verification should be quick [1].

Other use cases for ZKP include proving you have enough money for a transaction, proving you are a member of a group without revealing your identity, proving you know the location of a hidden object without revealing the location, and proving you know the solution to a puzzle without sharing it [2].

Example - Discrete Log Problem [3]:

Consider the key value y = g^x \mod p for large prime number $p$, a value often used in public-private key cryptography [4]. In this case, the values of g and p are publicly known, but x is a secret known only to those authenticated in the public-private key cryptographic system. For large values g and p, finding this value x such y = g^x mod p can be very difficult and not possible to do by brute force in a reasonable time.

Suppose user A chose a random value of x, calculated y=g^x mod p, and distributed y to parties with whom A wishes to connect cryptographically. If a new member B arrives and is given y, B wants to verify if y actually came from A as claimed, and thus that there exists encrypted communication with A. How does A prove this fact to B without sharing any more details than is already known, in this case the values g, p and y.

The following protocol repeats T>1 times:

• Step 1: A chooses a random value r in {1,...,p-1} and sends c = y^r to B.
• Step 2: B send back a random binary value b to A.
• Step 3: A will return d = r + bx mod (p-1) to B.
• Step 4: B will verify if g^d mod p = c y^b mod p.

This procedure is executed multiple times because it is possible for A to guess the value of b and fake an answer. If A guesses correctly that b=0, then A would be able to convince B with a random r and the appropriate c; however, if A knows b=1 will be requested, A can compute c' = g^r/y mod p to give to B followed by d=r'. From Step 4, this verification would yield g^r' mod p = c' y mod p = g^r'/y y mod p. By requesting different values of b over several iterations, this ensures A can only pass every test if the value *x is known.

Example - Undeniable Signature [5]:

Similar to the previous example, suppose the public key y=g^x is known however x is known only to A. Using x, A can sign a message m to communicate that the message was approved and sent by A; this signature is z=m^x. The following protocol proves the valid signature of A without revealing x when g, y=g^x, m and z are public:

• Step 1: A chooses a random value r in {1,...,p-1}, B chooses two random values a, b in {1,...,p-1}. Each party does not yet reveal their values.
• Step 2: B sends the value c = m^a g^b to A.
• Step 3: A send the pair {m^a g^b+r, (m^a g^b+r)^x} = {c g^r, c^x g^rx} to B.
• Step 4: B sends values a and b to A to reconstruct Step 2.
• Step 5: Once the reconstruction is successful, A sends value r to B to reconstruct Step 3:
  
  {m^a g^b+r, (m^a g^b+r)^x} ={m^a g^b+r, z^a y^b+r}
  .

Once this last step is verified, B has confirmed that the signature z is valid and came from A without A ever having to share the secret key x.

Zero-Knowledge Range Proofs

Zero-Knowledge Range Proofs(ZKRP) allow for flexibility in the value claimed. For a user A with secret x and a verifier B, a ZKRP suffices to prove to B that the value x is within a certain range of numbers, without ever specifying x. This can be useful with credit checks for an apartment for A to say its salary is enough without stating it. Geographically, A could make a claim about in which country the user resides, without pinpointing a location. Cryptographically, both ZKP and ZKRP have seen prototypes for use in blockchain technologies [2] as well as the fully private cryptocurrency Zcash [6].

ZKP can serve as a powerful tool in modern cryptography to prove without doubt one's authentication, signature, or credibility without the need to divulge any secrets. Privacy and security are of the utmost importance to many users and applications, and ZKP contribute to the verification and concurrent hiding of absolute truths in a trustless system.

References

[1] S. Goldwasser, S. Micali, and C. Rackoff, “The knowledge complexity ofinteractive proof systems,”SIAM Journal on computing, vol. 18, no. 1,pp. 186–208, 1989.

[2] T. Koens, C. Ramaekers, and C. Van Wijk, “Efficient zero-knowledge rangeproofs in ethereum,”ING, blockchain@ ing. com, 2018.

[3] D. Chaum, J.-H. Evertse, and J. Van De Graaf, “An improved protocol fordemonstrating possession of discrete logarithms and some generalizations,”inWorkshop on the Theory and Application of of Cryptographic Techniques,pp. 127–141, Springer, 1987.

[4] W. Diffie and M. Hellman, “New directions in cryptography,”IEEE trans-actions on Information Theory, vol. 22, no. 6, pp. 644–654, 1976.

[5] D. Chaum, “Zero-knowledge undeniable signatures,” inWorkshop on theTheory and Application of of Cryptographic Techniques, pp. 458–464,Springer, 1990.

[6] “Zcash.” http://z.cash. Accessed: 2020-04-19.

Cryptographic Techniques used in Wireless Sensor Networks

Data collection can be done in various forms, and one such way that is becoming increasingly more popular is through the use of Wireless Sensor Networks (WSN). These networks are comprised of various sensor nodes, tiny computers that individually collect data from their environment, and communicate this information with each other. One term often used by tech companies to describe WSNs is Internet of Things, painting the image of various interconnected machines within a region as small as the household or as large as a city. For a more detailed look at WSNs, check out my post here.

Regardless of the size of WSN, security of the collected data is crucial. As a WSN becomes larger, the risk of hacking a single node increases. As such, extensive security measures are applied to WSNs in the form of cryptography, ensuring that the data collected remains encrypted and unreadable until it leaves the system. In this article, I will define the two flavours of cryptography: symmetric and asymmetric. Furthermore, I will explore methods of applying these cryptographic protocols on WSNs given a finite communication radius of sensor nodes. 

Cryptographic Basics

Before diving in to cryptography in WSNs, let's define some key cryptographic terms. Cryptography refers to the study of secure communication in the presence of adversaries - those who may be trying to intercept the transferred information. Specifically, we are concerned with making our information private or unreadable to adversaries but readable to our target - two subsequent methods known as encryption and decryption. Encryption can be seen as the process of turning plaintext - our unchanged message - into ciphertext - an unreadable message - and finally back into plaintext. 

This encryption-decryption process can be done in a number of ways, but we will focus only on the two most common below.

Symmetric Cryptography

Also known as secret-key cryptography, symmetric cryptography uses a single symmetric key for both encryption and decryption. As we see in Figure 1, decrypting the encrypted message will garner us our original message [1]. Mathematically, if we look at the encryption process as a function K on a message t as K(t) and the decryption process on a message t as the inverse of K on t, we get the following properties.

(1) K^-1(K(t)) = t
(2) K(t) = K^-1(t)
(3) K(K(t)) = t

Property (1) is the definition of encryption and decryption such that they "undo" each other. Property (2) and (3) are unique to symmetric cryptography: from (2), the symmetric encryption key is the same as the symmetric decryption key, and thus from (3), a single symmetric encryption key will decrypt itself.

Figure 1: The symmetric encryption process

In WSNs, we have a cryptographic tradeoff we must consider. Using a single key between all sensor nodes will make our WSN vulnerable - hacking a single node will make the whole network defenseless and the data susceptible to attack and retrieval by third parties. On the other hand, having a unique key for every pair of nodes is not possible given the small storage space of nodes - a network with n nodes would require each node to hold n-1 unique keys, and the whole network would need (n-1)n/2 keys. 

Keeping this in mind, we install as many keys on a single node as is reasonable given storage space, number of total network keys, number of neighbouring nodes, and how much data is to be collected for a given time frame. One such method of key-distribution using combinatorial design theory is found here.

Two nodes within a network that are within communication range will use a symmetric key K which is the product of all keys these two nodes have in common. More clearly, if node i and node j are neighbours, and out of n total network keys they share m keys, such that m < n, then the symmetric key i and j use is as follows:

K = K¹_{i, j} x K²_{i, j} x ... x K^m_{i, j},
where each K^k_{i, j} is the k^th key in common between nodes i and j; k = 1,...,m

Asymmetric Cryptography

Also known as public-key cryptography, asymmetric cryptography uses two separate keys for each of the encryption and decryption processes. For the encryption process, the sender uses a public key that is available to all senders in the system; for the decryption process, the receiver uses a private key that is only available to the receiver [1]. In Figure 2, we see the asymmetric key process.

Figure 2: The asymmetric encryption process

In order to obtain two keys - a private-key that decrypts the encryption of the public-key - they are created together. These are known as public-private key pairs. Our keys that we obtain must follow a set of properties.

(1)D(E(t)) = t
(2) E(D(t)) ≠ t

Note, by (2) we see that D(t) ≠ E^-1(t) since a public-key cannot decrypt a private-key.

As we see in Figure 3, this key pair is created in the destination device; the private-key remains with the destination device, whereas the public-key is made available to all source devices. One example of this process is GitHub [4], where to use SSH Authentication users will create a key pair on their device and upload the public-key GitHub. This allows users to securely push or pull code from their GitHub repositories. 

Figure 3: The creation and distribution of private-public key pairs [3].

In a WSN, a node would create a key pair, store the private-key locally and send out the public-key to neighbouring nodes. Once again, keeping in mind the tradeoff of storage vs. vulnerability, we may choose to create several key-pairs and send out multiple public-keys to different nodes.

Secure Node Hopping

Depending on the topology of your network, you may require multiple hops to reach your sink node [5] - a transfer of data between two devices, moving towards a target. An overview of different network topologies is available in my post here.  Suppose you have a path of nodes such as in Figure 4 where we need to transfer data from node p to node s - usually our sink node. One method to do this would be to fully encrypt and decrypt the data between every hop; this method requires each neighbouring pair of nodes to have a key-pair E and D. Here, we are not concerned with whether E and D are symmetric or asymetric. This may not be a scalable option. 

Figure 4: Hops with a key-pair between each pair of neighbouring nodes.

Another method is to take advantage of the fact that sink nodes normally have larger storage based on their function of sending data out of the system. In this case, we can have a single key-pair between p and our sink s such that our node p can send data to neighbouring nodes without the other nodes decrypting our data until we reach s. This keeps our data secure through each hop while not requiring our nodes to hold too many keys. This process is shown in Figure 5.

Figure 5: Hops with the sink storing multiple decryption keys.

Conclusion

Organizations implementing WSNs for data collection take appropriate measures to ensure the data collected is not compromised, accessed, or stolen. Apart from physical security, cryptography is a natural step in data integrity and security. Understanding the different cryptographic protocols used in WSNs and their implementations helps organizations choose the best protocols and key distributions for their networks.

References

[1] Stallings, William Cryptography and Network Security - Principles and Practice, 4th ed., Prentice Hall, 2005, Chapter 2.1, 8.1

[2] 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).

[3] Gustavo S. Quirino, Admilson R. L. Ribeiro and Edward David Moreno (September 6th 2012). Asymmetric Encryption in Wireless Sensor Networks, Wireless Sensor Networks Mohammad A. Matin, IntechOpen, DOI: 10.5772/48464. Available from: https://www.intechopen.com/books/wireless-sensor-networks-technology-and-protocols/asymmetric-encryption-in-wireless-sensor-networks, Chapter 3.1.2

[4] GitHub 2018, accessed 1 September 2018 , <https://help.github.com/articles/connecting-to-github-with-ssh/>

[5] Elias Yaacoub and Adnan Abu-Dayya (September 6th 2012). Multihop Routing for Energy Efficiency in Wireless Sensor Networks, Wireless Sensor Networks Mohammad A. Matin, IntechOpen, DOI: 10.5772/39221. Available from: https://www.intechopen.com/books/wireless-sensor-networks-technology-and-protocols/multihop-routing-for-energy-efficiency-in-wireless-sensor-networks

Basics of Wireless Sensor Networks

Many companies and organizations rely heavily on data. Whether you're predicting growth of a company's revenue, or estimating how much inventory to order based on historic sales, data is essential to the management of all companies. As technology advances, the ability to collect outside data becomes easier via many computerized methods. One methods uses sensor nodes, tiny computers that collect data from their environment. The collection of sensor nodes that communicate together are known as a Wireless Sensor Network (WSN).

Sensor Nodes

Each sensor node is built with a sensor interface, a power source, storage, a microprocessor, and an antenna. Referring to Figure 1, we have a sensor chip which picks up various data from the environment, a power source which could be battery or solar powered, a radio transceiver with an antenna to communicate with other nodes, and a microprocessor to tie everything together [5]. 

Figure 1: Architecture of a sensor node. [5]

Three components that are constantly being improved are the range of radio frequency, the lifetime of the power supply, and the size of the storage. Particularly with the size of the storage, we want a sensor node that is as small as possible while holding as much data as possible prior to transmission.

The small size of storage also gives rise to other problems in the cryptographic communication of nodes, as they hold a smaller number of keys. For more information, refer to my post on cryptographic pre-distribution in WSNs.

Sensors can pick up different types of data based on their type and configuration. Passive, omnidirection sensors require no trigger aside from the  force acting upon it, and have no sense of direction - a wheel sensor on the road that tracks speed and traffic level fall into this category. Passive, narrow-beamed sensors send signal in a single direction and collect data based on objects that pass through this beam - store security sensors at the door fall into this category. Finally, active sensors are sensors which actively survey their environment - this can take the form of radio or sonar signals [6].

Figure 2: When nodes pick up data, they "hop" towards the sink. [4]

Sink, Gateway and Network Topology

In a WSN, the data collected from each node is forwarded to a sink, either directly or through multiple hops. This sink can then use the data locally, or it can transmit the data to various sources via a gateway [1]. In the following figures and examples, the sink node may or may not have a gateway attached.

 

Bus or In-Line Topology

A traditional bus topology in a wired network has all devices connected to a running wire that extends the whole network. In a WSN [2], one can think of the equivalent to an in-line topology, where each node can communicate to adjacent nodes only. For any node not adjacent to the sink node, several hops are necessary for the data to travel from the node to the sink. Note, this topology is a special case of a tree topology in which every node has at most one child.

Figure 3: An in-line topology of 5 sensor nodes and one sink, with each node only having adjacent nodes in its radius of communication.

Tree Topology

With the sink node at its root, a network in a tree topology has every node connected with at most one parent node and 0 or more child nodes. We can say the level of a node in such a network is the number of link separating itself and the root (sink). From this definition, we can clearly see that the sink node has a level of 0.

Figure 4: A tree topology, could branch out to many leaf nodes or as few as one.

Star and Snowflake Topology

Similar to a wired star topology, there is a central device to which all other nodes connect; in this case it is the sink node. Although the sink may communicate to every node, each node may only communicate with the sink. A snowflake topology is an extension of the star topology, where each node connected directly to the source may branch out to further nodes. Similar to the in-line topology, these nodes would hop up the snowflake to the center sink node.

Figure 5: Five sensor nodes arranged in a star topology with a sink at the center.

Figure 6: An extension of Figure 2 with four extra nodes branching out of the core star, creating a snowflake topology.

Mesh Topology

The benefit of a WSN is that a node doesn't need to rely on any cables to connect nodes; rather, it can communicate with any node that's within it's radius of communication. Simply, a mesh topology is any architecture that contains a cycles. One can also think of mesh topologies as being void of any dictated structure present in the topologies above. One major benefit of networks in mesh topologies is that losing one node due to computer failure or hacking does not disrupt the rest of the network. Furthermore, if a set of nodes in the middle slow down due to data traffic or maintenance, then alternate routes from the further nodes to the sink can be found.

Figure 7: A mesh topology, the most likely network structure given a wireless network's radius of communication.

Random and Arbitrary Networks

When dealing with wired networks, it is necessary to plan the network architecture in advance. Nodes are assembled, the architecture is planned, and the network with cables are deployed. The nature of wireless networks gives the user more freedom during the deployment process. No longer are we restricted by whether a cable pathway is feasible. This allows us to deploy networks with a large quantity of nodes. With these large scale networks, we deal with both random and arbitrary networks.

In a random network, nodes are randomly and uniformly distributed over a geographical area [3]. This uniform design allows us to collect data over approximately even intervals, and can be ideal for groups interested in full data coverage. The size of these networks are usually assumed to be large so that analysis of the network and its properties become well-define.

In arbitrary networks, we cannot guarantee the uniform distribution of the nodes. The are networks in which the deployment of the nodes may be ad hoc in nature. [3] For example, a company may be interested in deploying nodes over a forest, but only have access to a small number of nodes; these nodes are normally deployed by hand or with the use of a plane or helicopter to drop nodes over the most important areas. Similarly, a network may be required along a port in the water; in these cases, a boat may drop nodes at random, and the current may deposit the nodes off target. There are many examples where it may not be possible to guarantee or even attempt uniformity.

In all cases, multiple sinks are possible and may be useful as the number of nodes becomes large.

Figure 8: An example of a random grid network, where n nodes are deployed randomly and uniformly over a unit square region, further broken down

Figure 9: An example of an arbitrary network, where the nodes are spread throughout the forest to detect forest fires.

Wireless Sensor Networks benefit from being able to communicate with any node in it's RF radius, lending these networks to a variety of well connected architectures. Although the small storage of these sensors does create limiting issues in data collection and cryptography, advancements in technology are increasing the radius of communication and allowing more memory to fit into smaller sized storage. 

With the prevalence of data science and machine learning in today's market, WSNs will become more popular as a cheap and efficient means of precise data collection.

References

[1] Buratti C., Conti A., Dardari D., Verdone R., An Overview on Wireless Sensor Networks Technology and Evolution Sensors,ISSN 1424-8220, August 2009

[2] Acharjya P. P., Santra S. A study and analysis on Computer Network Topology for Data Communication, International Journal of Emerging Technology and Advanced Engineering, Volume 3, Issue 1, January 2013

[3] El Emary, Ibrahiem M. M., Ramakrishnan, S., Wireless Sensor Networks: From Theory to Application, Boca Raton, Fla. : CRC Press, c2014 (Norwood, Mass. : Books24x7.com, Chapter 1.2, 1.3

[4] Chiara Buratti 1,* , Andrea Conti 2, Davide Dardari 1 and Roberto Verdone, An overview of Wireless Sensor Network Technology and Evolution, Sensor 2009, 9(9), 6869-6896

[5] Cao X., Hu F. Wireless Sensor Networks: Principles and Practice, Auerbach Publications Chapter 2

[6] https://en.wikipedia.org/wiki/Sensor_node#Sensors

The Elo rating: How it's used from NBA to League of Legends

Originally created for chess by Arpad Elo, the Elo rating system has become the standard rating system in many two team/player games from sports (NBA, NFL), competitive table games (Scrabble), and many video games (League of Legends, CounterStrike). 

Intuitively, a higher Elo rating represents a higher skilled player or team. If Team A and Team B play each other and r(A) > r(B) (r(X) being the Elo rating of team X), then Team A is expected to score more points. If r(A) = r(B), then both teams are expected to score the same number of points. 

In sports, the Elo rating of two teams stand as a good representation of who will win. FiveThirtyEight.com has a good breakdown of Elo in NBA and NFL. In video games, Elo drives the matchmaking process so that two teams with similar Elo scores - which means similarly skilled teams - are matched.

Once a game is concluded, each team's Elo score is updated by a factor relative to the other team's score. In other words, if a stronger team wins against a weaker team, then the stronger team's Elo would rise a small amount, and the weaker team would decrease the same amount. If the underdog wins, then their Elo would increase a larger amount, and the favoured team's score would decrease by the same larger amount. This was the reason for the creation of Elo: before Elo, a chess player who would beat many lower skilled players would have a higher ranking than a player who would have a small win rate against highly skilled players. The Elo rating system fixes this.

Formula

For Team X against Team Y, we let the Elo rating of each be r(X) and r(Y). Ultimately, after the game between these team concludes, we are going to have the following update for team X:

R(X) = 10^r(X)/400

E(X) = R(X) / (R(X) + R(Y))

r'(X) = r(X) + K*(S(X) - E(X))

r(X) is the pre-game Elo rating and r'(X) is the updated Elo rating. E(X) is the expected number of points scored, from 0 to 1. S(X) is the actual result of the game, with S(X) = 1 if Team X wins, S(X) = 0 if Team X loses, and S(X) = 0.5 if it's a tie. K is a constant term, set by the respective league, and determines how significant the change in a team's updated Elo. If K is too small, a team's Elo would take a very long time to increase. On the flip side, if K is too large then a team's Elo would vary greatly. In the below example. we'll be using K = 32.

You can think of 1 as being the total points scored between both teams, so E(X) + E(Y) = 1. In the below NBA example, if E(X) = 0.62 and we say the total points scored is 82, then this breaks down to 51-31 for Team X vs Team Y. In other words, Team X scores 62% of the total points scored.

Example

Let's look at an example from the NBA. Say we have Team A, considered a strong team, with an Elo rating of 2000. Team B is considered an average team with an Elo rating of 1600. We can write this as r(A) = 2000 and r(B) = 1600. 

R(A) = 10^2000/400 = 100,000

R(B) = 10^1600/400 = 10,000

E(A) = 100,000/110,000 = 0.91

E(B) = 10,000/110,000 = 0.09

We look at the three posibilities: Team A wins, Team A loses, and Team A and B tie.

Team A wins

S(A) = 1 and S(B) = 0. The Elo ratings are updated as follows:

r'(A) = 2000 + 32(1 - 0.91) = 2000 + 32(0.09) = 2003

r'(B) = 1600 + 32(0 - 0.09) = 1600 - 32(0.09) = 1597

The favoured team won, and the Elo's were updated slightly accordingly.

Team A and B tie

S(A) = S(B) = 0.5. The Elo ratings are updated as follows:

r'(A) = 2000 + 32(0.5 - 0.91) = 2000 - 32(0.41) = 1987

r'(B) = 1600 + 32(0.5 - 0.09) = 1600 + 32(0.41) = 1613

In this case, Team A was favoured to win by a large margin. As a result, when the teams tie, Team A's Elo decreases by an amount larger than the previous update. Similarly, Team B, as the underdog, tied with a stronger team so their Elo increased.

Team A loses

S(A) = 0 and S(B) = 1. The Elo ratings are updated as follows:

r'(A) = 2000 + 32(0 - 0.91) = 2000 - 32(0.91) = 1971

r'(B) = 1600 + 32(1 - 0.09) = 1600 + 32(0.91) = 1629

Once again, Team A was favoured to win by a large margin, but this time they lost. Team B's Elo increased significantly compared to the amount it increased when it tied with Team A.

Combinatorial design theory and how it applies to cryptography

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).