Chapter 9 - Communication and Cryptography

In the 20th century, theoretical computer science primarily centered on sequential computation models. However, the advent of global networking has shifted the paradigm, presenting new challenges related to communication, cooperation, and security in distributed systems. Understanding computing in this networked world is a central task for modern computer science.

This chapter delves into two critical aspects of networked computing: communication complexity and cryptography. While communication complexity studies the minimal resources (e.g., bits exchanged) required for distributed tasks, cryptography focuses on enabling secure communication in the presence of adversaries. Cryptography, in particular, relies heavily on the concepts of complexity theory, algorithmics, and randomization that we explored in previous chapters. It offers counterintuitive solutions that allow for secure interactions even over insecure channels. (For instance, how can two parties agree on a secret key without ever meeting, or how can you prove you know something without revealing what it is?)

We will begin by examining classical cryptosystems and their inherent weaknesses, which led to the revolutionary idea of public-key cryptography. We will then explore the widely used RSA cryptosystem in detail, understanding its mathematical foundations and security assumptions. Following this, we will discuss digital signatures and authentication protocols, which are crucial for verifying identity and message integrity. The chapter will also introduce interactive proof systems and zero-knowledge proofs, powerful tools for verifying knowledge without revealing it. Finally, we will touch upon the design of efficient communication networks, exemplified by Beneš networks.

9.1 Aims

By the end of this chapter, you will be able to:

• Understand Cryptosystem Fundamentals: Grasp the basic components and requirements of a cryptosystem, including plaintext, ciphertext, and keys.
• Differentiate Symmetric and Asymmetric Cryptography: Understand the key distribution problem in classical (symmetric) systems and how public-key (asymmetric) cryptography solves it.
• Comprehend One-Way Functions: Learn the properties of one-way functions and their role as the foundation of public-key cryptography.
• Master RSA Encryption: Understand the key generation, encryption, and decryption processes of the RSA algorithm, along with its mathematical proof of correctness.
• Design Digital Signatures: Learn how public-key cryptography enables secure digital signatures and authentication.
• Explore Interactive Proofs: Understand the concept of interactive and zero-knowledge proof systems and their applications.
• Analyze Communication Networks: Gain insight into the design principles and optimality of communication networks like Beneš networks.

---

9.2 Classical Cryptosystems

Cryptology is the study of secret communication. It comprises cryptography (the design of secure systems) and cryptanalysis (the art of breaking them). Here, we focus on cryptography.

The basic scenario involves a sender who wants to send a secret plaintext message to a receiver. To prevent an unauthorized eavesdropper from reading the message, it is sent in an encrypted form, called ciphertext. The encryption and decryption processes are governed by a key.

Definition 9.1 (Cryptosystem)

A cryptosystem is a triple $(\mathcal{M},\mathcal{A},\mathcal{S})$, where:

• $\mathcal{M}$ is the set of all possible plaintexts.
• $\mathcal{A}$ is the set of all possible ciphertexts.
• $\mathcal{S}$ is the set of all possible keys. Each key $\alpha \in \mathcal{S}$ defines an injective encryption function $E_{\alpha }:\mathcal{M}\to \mathcal{A}$ and its inverse decryption function $D_{\alpha }=E_{\alpha }^{-1}:\mathcal{A}\to \mathcal{M}$.

Requirements for a Cryptosystem:

1. $E_{\alpha }$ and $D_{\alpha }$ must be efficiently computable.
2. Without knowing $\alpha$, it must be computationally infeasible to compute the plaintext $x$ from a given ciphertext $E_{\alpha }(x)$.

The Caesar Cipher

The simplest cryptosystem is the Caesar cipher. For a plaintext over the Latin alphabet, each letter is replaced by a letter shifted $k$ positions forward (cyclically). The key $k\in \{0,\dots ,25\}$.

Caesar Cipher

Plaintext: KRYPTOGRAPHIEISTFASZINIEREND Key: $k=3$ Ciphertext: NUBSWRJUDSKLHLVWIDVCLQLHUHQG

Weakness: This system is easily broken by trying all 26 possible keys (brute-force attack) or by using frequency analysis of letters in the language. (With so few keys, a modern computer can crack it in milliseconds.)

The Key Distribution Problem

Classical cryptosystems are symmetric: the same key is used for both encryption and decryption (or one can be easily derived from the other). This means the sender and receiver must share a common secret key. The fundamental problem is: How do Alice and Bob securely agree on this shared secret key over an insecure channel? (If they can’t meet in person to exchange the key, any communication channel they use could be eavesdropped upon, compromising the key before it’s even used.) This is the key distribution problem, and it remained a major hurdle for centuries.

---

9.3 Public-Key Cryptosystems and RSA

The revolutionary idea of public-key cryptography (also known as asymmetric cryptography) emerged in the 1970s, solving the key distribution problem. It relies on one-way functions.

Definition 9.1 (One-Way Function)

A function $f:{\Sigma }^{\ast }\to {\Gamma }^{\ast }$ is a one-way function if it satisfies the following properties: (Think of it like breaking a glass: easy to do, but practically impossible to reassemble perfectly.)

1. Efficiently Computable: $f$ can be computed in polynomial time.
2. Hard to Invert: For any randomized polynomial-time algorithm $A$, the probability that $A$ can compute $x$ from $f(x)$ is negligibly small.
3. Trapdoor: There exists secret information (a “trapdoor”) that makes $f^{-1}$ efficiently computable.

Candidates for One-Way Functions:

• Integer Factorization: Multiplication of two large primes is easy; factoring their product is believed to be hard. (There is no known polynomial-time algorithm for factoring large numbers on classical computers, making it a suitable candidate for a one-way function.)
• Discrete Logarithm: Exponentiation modulo a prime is easy; finding the exponent (discrete logarithm) is believed to be hard.

The RSA Cryptosystem

The RSA cryptosystem, named after Rivest, Shamir, and Adleman, is the most widely used public-key cryptosystem. Its security relies on the presumed difficulty of factoring large numbers.

Key Generation (by Receiver Bob):

1. Choose two large random prime numbers, $p$ and $q$ (e.g., each hundreds of bits long).
2. Compute $n=p\cdot q$. This $n$ is part of the public key.
3. Compute Euler’s totient function $\varphi (n)=(p-1)(q-1)$.
4. Choose an integer $e$ (the public exponent) such that $1<e<\varphi (n)$ and $\text{gcd}(e,\varphi (n))=1$.
5. Compute the integer $d$ (the private exponent) such that $e\cdot d\equiv 1(\mathrm{mod}\varphi (n))$. This $d$ is the trapdoor.

• Public Key: $(e,n)$ (published for anyone to use for encryption).
• Private Key: $d$ (kept secret by Bob; $p,q,\varphi (n)$ are also kept secret).

Encryption (by Sender Alice): To encrypt a plaintext message $w$ (represented as an integer $0\le w<n$): $c=E_{e,n}(w)=w^e(\mathrm{mod}n)$

Decryption (by Receiver Bob): To decrypt a ciphertext $c$: $w=D_{d,n}(c)=c^d(\mathrm{mod}n)$

Both exponentiation operations ($w^e(\mathrm{mod}n)$ and $c^d(\mathrm{mod}n)$) can be computed efficiently using the repeated squaring method (as seen in Chapter 8). (This method reduces the number of multiplications from $O(e)$ to $O(\log e)$, which is critical for large exponents.)

Correctness of RSA

The correctness of RSA relies on Euler’s Theorem, a generalization of Fermat’s Little Theorem.

Theorem 9.1 (Euler's Theorem)

Let $w$ and $n$ be two positive integers with $\text{gcd}(w,n)=1$. Then $w^{\varphi (n)}\equiv 1(\mathrm{mod}n)$.

Theorem 9.2 (Correctness of RSA)

Let p, q, n, e, d be determined as in RSA. Then for all integers w such that $0\le w<n$: $D_{d,n}(E_{e,n}(w))=(w^e{)}^d(\mathrm{mod}n)=w$

Proof of RSA Correctness

From the key generation, $e\cdot d\equiv 1(\mathrm{mod}\varphi (n))$, which means $e\cdot d=j\cdot \varphi (n)+1$ for some integer $j\ge 0$. We need to show $w^{j\cdot \varphi (n)+1}\equiv w(\mathrm{mod}n)$.

Case 1: $\text{gcd}(w,n)=1$. By Euler’s Theorem, $w^{\varphi (n)}\equiv 1(\mathrm{mod}n)$. So $w^{ed}=w^{j\cdot \varphi (n)+1}=(w^{\varphi (n)}{)}^j\cdot w\equiv 1^j\cdot w\equiv w(\mathrm{mod}n)$.

Case 2: $\text{gcd}(w,n)\ne 1$. This means $w$ is a multiple of $p$ or $q$ (or both). Without loss of generality, assume $p$ divides $w$. Since $q$ is prime and $w<n=pq$, $q$ cannot divide $w$ (unless $w=0$).

• Since $p$ divides $w$, $w\equiv 0(\mathrm{mod}p)$. Thus $w^{ed}\equiv 0(\mathrm{mod}p)$.
• Since $q$ does not divide $w$, $\text{gcd}(w,q)=1$. By Fermat’s Little Theorem, $w^{q-1}\equiv 1(\mathrm{mod}q)$. Since $\varphi (n)=(p-1)(q-1)$, $w^{\varphi (n)}=w^{(p-1)(q-1)}=(w^{q-1}{)}^{p-1}\equiv 1^{p-1}\equiv 1(\mathrm{mod}q)$. So $w^{ed}=w^{j\cdot \varphi (n)+1}=(w^{\varphi (n)}{)}^j\cdot w\equiv 1^j\cdot w\equiv w(\mathrm{mod}q)$. We have $w^{ed}\equiv w(\mathrm{mod}p)$ (since both are 0 mod p) and $w^{ed}\equiv w(\mathrm{mod}q)$. By the Chinese Remainder Theorem, this implies $w^{ed}\equiv w(\mathrm{mod}pq)$, i.e., $w^{ed}\equiv w(\mathrm{mod}n)$.

The case $w=0$ is trivial: $0^{ed}\equiv 0(\mathrm{mod}n)$.

Security: The security of RSA relies on the computational difficulty of factoring $n$ into $p$ and $q$. If an adversary can factor $n$, they can compute $\varphi (n)$ and then $d$, thus breaking the encryption.

---

9.4 Digital Signatures

Digital signatures provide authenticity and integrity for electronic documents, analogous to handwritten signatures.

Requirements for Digital Signatures:

1. Authenticity: The receiver must be convinced that the signature is from the sender.
2. Non-repudiation: The sender cannot later deny having signed the document.
3. Integrity: The document has not been altered since it was signed.
4. Unforgeability: No one else can forge the sender’s signature.

Protocol for Digital Signatures (using RSA)

Alice wants to sign a document $w$ for Bob. Alice has her own RSA key pair: public key $(e_A,n_A)$ and private key $d_A$. Bob knows Alice’s public key.

1. Alice computes a hash $H(w)$ of the document $w$. (A hash function produces a fixed-size “fingerprint” of the document. Even a tiny change to the document results in a completely different hash, making it a reliable integrity check.)
2. Alice “signs” the hash: $\sigma =(H(w){)}^{d_A}(\mathrm{mod}{n}_A)$.
3. Alice sends $(w,\sigma )$ to Bob.

Verification (by Bob):

1. Bob computes $H(w)$ from the received document.
2. Bob “decrypts” the signature: $H^{\prime }(w)={\sigma }^{e_A}(\mathrm{mod}{n}_A)$.
3. Bob checks if $H(w)=H^{\prime }(w)$. If they match, the signature is valid.

Why it works:

• Only Alice knows $d_A$, so only she could have produced $\sigma$ such that ${\sigma }^{e_A}\equiv H(w)(\mathrm{mod}{n}_A)$. This ensures authenticity and non-repudiation. (Even Bob, the receiver, cannot forge Alice’s signature because he only knows her public key $e_A$, not her private key $d_A$.)
• Any alteration to $w$ would result in a different $H(w)$, which would not match $H^{\prime }(w)$, ensuring integrity.

---

9.5 Interactive Proof Systems and Zero-Knowledge Proofs

In Chapter 6, we learned that problems in NP have polynomial-time verifiers. This means a “yes” answer to an NP problem can be accompanied by a short, efficiently checkable proof. Interactive proof systems generalize this idea, allowing a prover (P) to convince a verifier (V) of a statement’s truth through a series of interactions, possibly involving randomness.

Definition 9.2 (Interactive Proof System)

A language $L$ has an interactive proof system if there exists a randomized polynomial-time verifier $V$ such that for all $x\in {\Sigma }^{\ast }$: (Imagine a powerful “prover” trying to convince a computationally limited “verifier” of a mathematical truth.)

1. Completeness: If $x\in L$, there exists a prover $P$ such that $V$ accepts $x$ with probability greater than $2/3$ after interacting with $P$. (The specific constants $2/3$ and $1/3$ are arbitrary; any constants strictly greater than $1/2$ and strictly less than $1/2$ respectively would work, as the probabilities can be amplified by repetition.)
2. Soundness: If $x\notin L$, then for any prover $P^{\prime }$, $V$ accepts $x$ with probability less than $1/3$ after interacting with $P^{\prime }$.

The probabilities $2/3$ and $1/3$ are arbitrary constants; they can be amplified arbitrarily close to 1 and 0 by repeating the interaction.

Example: Graph Non-Isomorphism

The Graph Isomorphism problem (GI) asks if two graphs $G_1,G_2$ are structurally identical. It is in NP. Its complement, Graph Non-Isomorphism (NONISO), asks if $G_1,G_2$ are not isomorphic. It is not known if NONISO is in NP. However, NONISO has an interactive proof system.

Interactive Proof for NONISO

Input: $(G_1,G_2)$

1. Verifier V: a. Randomly chooses $i\in \{1,2\}$ and a random permutation $\pi$ of the vertices. b. Computes $H=\pi (G_i)$ (a randomly relabeled version of $G_i$). c. Sends $H$ to Prover P.
2. Prover P: a. Receives $H$. P (with unlimited computational power) determines if $H$ is isomorphic to $G_1$ or $G_2$. b. Sends $j\in \{1,2\}$ back to V, indicating which original graph $H$ is isomorphic to.
3. Verifier V: a. Checks if $j=i$. If so, V accepts. Otherwise, V rejects.

Why it works:

• Completeness (if $G_1,G_2$ are non-isomorphic): An honest P knows which graph $H$ came from and always sends $j=i$. V always accepts.
• Soundness (if $G_1,G_2$ are isomorphic): If $G_1,G_2$ are isomorphic, then $H$ is isomorphic to both $G_1$ and $G_2$. P cannot distinguish whether $H$ came from $G_1$ or $G_2$. P must guess $i$. P’s guess is correct with probability $1/2$. By repeating the protocol $k$ times, the probability of a dishonest P fooling V drops to $(1/2{)}^k$.

IP = PSPACE

A remarkable result by Shamir (1990) shows the immense power of interactive proofs:

Theorem 9.3 (Shamir's Theorem)

The class of languages with interactive proof systems (IP) is equal to PSPACE. $\text{IP}=\text{PSPACE}$ This means that even problems requiring polynomial space (which can be exponentially larger than polynomial time) can have their proofs verified efficiently through interaction and randomness.

Zero-Knowledge Proof Systems

A zero-knowledge proof (ZKP) is an interactive proof system with an additional, crucial property: the verifier learns nothing from the interaction beyond the fact that the statement is true. The verifier cannot use the interaction to convince a third party, nor does it gain any information about the secret itself. (Imagine proving to someone that you know a secret password without actually telling them the password.)

Zero-Knowledge Proof for Graph Isomorphism

Input: $G_1,G_2$. Prover P wants to convince Verifier V that $G_1\cong G_2$ without revealing the isomorphism.

1. Prover P: a. Randomly chooses a permutation $\pi$ and computes $H=\pi (G_1)$. b. “Commits” to $H$ (e.g., by encrypting it or using a cryptographic hash) and sends the commitment to V.
2. Verifier V: a. Randomly chooses $j\in \{1,2\}$. b. Sends $j$ to P (this is the “challenge”).
3. Prover P: a. “Opens” the commitment to $H$. b. If $j=1$, P sends $\pi$ (the permutation that maps $G_1$ to $H$). c. If $j=2$, P sends $\sigma$ (the permutation that maps $G_2$ to $H$, where $\sigma =\pi \circ \text{iso}(G_1,G_2)$).
4. Verifier V: a. Checks if $H=\pi (G_1)$ (if $j=1$) or $H=\sigma (G_2)$ (if $j=2$).

If $G_1\cong G_2$, P can always answer correctly. If $G_1\ncong G_2$, P cannot produce a valid $H$ that is isomorphic to both $G_1$ and $G_2$. The zero-knowledge property comes from the fact that V only sees a random isomorphic copy $H$ and a random permutation, which V could have generated itself.

ZKP systems have significant practical applications in authentication (proving identity without revealing a password), anonymous credentials, and secure multi-party computation.

---

9.6 Design of a Communication Network

Designing efficient communication networks is a complex task, balancing cost, performance, and scalability. We consider the problem of building an $n$-permutation network. (This is a network designed to efficiently route messages between $n$ senders and $n$ receivers, where any sender can connect to any receiver, and all connections can happen simultaneously without interference.)

Problem: Connect $n$ “x-participants” ($x_0,\dots ,x_{n-1}$) to $n$ “y-participants” ($y_0,\dots ,y_{n-1}$) such that any permutation of connections (i.e., $x_j$ wants to talk to $y_{i_j}$ for all $j$) can be realized simultaneously with edge-disjoint paths.

A simple solution is a complete bipartite graph, connecting every $x_j$ to every $y_k$. This requires $n^2$ edges, which is too costly and complex for large $n$. We need networks with a constant maximum degree for each node.

We measure the cost of a permutation network by the number of switching nodes (nodes that are not participants) and the length of the longest path.

Theorem 9.4

Every n-permutation network must have at least $\Omega (n\log n)$ switching nodes.

Proof of Lower Bound for Permutation Networks

Let $m$ be the number of switching nodes. Each switching node can be in one of a constant number of states (e.g., 2 states for a simple switch). The participant nodes also have states. The total number of possible state assignments in the network must be at least $n!$ (the number of permutations). If each of the $m$ switching nodes has 2 states, and each of the $2n$ participant nodes has 2 states, then $2^m\cdot 2^{2n}\ge n!$. Taking ${\log }_2$ of both sides: $m+2n\ge {\log }_2(n!)$. Using Stirling’s approximation for ${\log }_2(n!)\approx n{\log }_{2}n-n{\log }_{2}e$: $m\ge n{\log }_{2}n-n{\log }_{2}e-2n\in \Omega (n\log n)$.

Beneš Networks

Beneš networks are a class of asymptotically optimal permutation networks. An $r$-dimensional Beneš network, ${\text{Benes}}_r$, can realize any $2^r$-permutation.

The construction is recursive: ${\text{Benes}}_r$ is built from two ${\text{Benes}}_{r-1}$ networks and two “layers” of $2^r$ switches.

Theorem 9.5

For each $r\in {\mathbb{N}}^{+}$, ${\text{Benes}}_r$ is a $2^r$-permutation network.

Proof of Beneš Network Permutation Property

The proof is by induction on $r$. It shows that for any permutation, paths can be routed through the network such that they are edge-disjoint. The recursive structure allows for a divide-and-conquer routing strategy.

A ${\text{Benes}}_r$ network for $n=2^r$ participants has $(2r-1)2^r$ switching nodes. This is $O(n\log n)$ switching nodes, matching the lower bound. (This means you can’t build a permutation network with significantly fewer switching nodes, making Beneš networks theoretically as efficient as possible in terms of hardware.) The length of the longest path is $2r-1$, which is $O(\log n)$. Beneš networks are highly modular and regular, making them practical for construction.

---

Summary

• Cryptography enables secure communication over insecure channels, relying heavily on complexity theory and randomization.
• Classical (symmetric) cryptosystems suffer from the key distribution problem, as sender and receiver must share a secret key.
• Public-key (asymmetric) cryptosystems solve this by using one-way functions with trapdoors, allowing public encryption keys and private decryption keys.
• RSA is a prominent public-key cryptosystem whose security is based on the difficulty of integer factorization. Its correctness is proven using Euler’s Theorem.
• Digital signatures use public-key cryptography to provide authenticity, non-repudiation, and integrity for electronic documents.
• Interactive proof systems allow a prover to convince a verifier of a statement’s truth through interaction, even for problems in PSPACE.
• Zero-knowledge proof systems are interactive proofs where the verifier learns nothing beyond the truth of the statement.
• Communication networks like Beneš networks provide asymptotically optimal solutions for realizing any permutation of connections between participants, with $O(n\log n)$ switching nodes and $O(\log n)$ path length.

---

Previous Chapter: Chapter 8 - Randomization Next Up: Chapter 10 - Grammars and Chomsky Hierarchy

Exercises

Exercise 9.1 (Caesar Cipher Decryption)

Decrypt the ciphertext NUBSWRJUDSKLHLVWIDVCLQLHUHQG if you know it was encrypted with a Caesar cipher and the plaintext is in English.

Solution

By trying all 25 possible shifts (or using frequency analysis, where ‘U’ is the most frequent letter in the ciphertext, likely corresponding to ‘E’ in English), we find that a shift of 3 positions backward (or 23 forward) decrypts the message. Plaintext: KRYPTOGRAPHIEISTFASZINIEREND

Exercise 9.2 (RSA Key Generation and Usage)

Bob chooses $p=5$ and $q=11$.

1. Calculate $n$ and $\varphi (n)$.

2. Choose a suitable public exponent $e$.

3. Calculate the private exponent $d$.

4. Encrypt the message $w=8$.

5. Decrypt the resulting ciphertext.

Solution

1. $n=p\cdot q=5\cdot 11=55$. $\varphi (n)=(p-1)(q-1)=(5-1)(11-1)=4\cdot 10=40$.
2. Choose $e$ such that $1<e<40$ and $\text{gcd}(e,40)=1$. Let’s pick $e=3$.
3. Calculate $d$ such that $e\cdot d\equiv 1(\mathrm{mod}40)$. $3d\equiv 1(\mathrm{mod}40)$. We can use the Extended Euclidean Algorithm or test values. $3\cdot 27=81\equiv 1(\mathrm{mod}40)$. So $d=27$.
4. Public key: $(3,55)$. Private key: $27$. Encrypt $w=8$: $c=w^e(\mathrm{mod}n)=8^3(\mathrm{mod}55)=512(\mathrm{mod}55)$. $512=9\cdot 55+17$, so $c=17$.
5. Decrypt $c=17$: $w^{\prime }=c^d(\mathrm{mod}n)=17^{27}(\mathrm{mod}55)$. This is a bit tedious by hand, but using repeated squaring: $17^{27}(\mathrm{mod}55)=8$. The original message $w=8$ is recovered.

Exercise 9.3 (Digital Signature Authentication)

Design a communication protocol for digital signatures that fulfills the following requirements:

6. Bob must be convinced of Alice’s authenticity.

7. Alice should be protected from Bob forging her signature.

8. No third party eavesdropping on the communication may learn the content of the signed document.

Solution

Alice has RSA keys $(e_A,n_A)$ (public) and $d_A$ (private). Bob has RSA keys $(e_B,n_B)$ (public) and $d_B$ (private).

1. Alice computes $H(w)$ (hash of document $w$).
2. Alice signs $H(w)$: $\sigma =(H(w){)}^{d_A}(\mathrm{mod}{n}_A)$.
3. Alice encrypts $w$ and $\sigma$ with Bob’s public key: $C_w=w^{e_B}(\mathrm{mod}{n}_B)$ and $C_{\sigma }={\sigma }^{e_B}(\mathrm{mod}{n}_B)$.
4. Alice sends $(C_w,C_{\sigma })$ to Bob.

Verification (by Bob):

1. Bob decrypts $C_w$ and $C_{\sigma }$: $w^{\prime }=(C_w{)}^{d_B}(\mathrm{mod}{n}_B)$ and ${\sigma }^{\prime }=(C_{\sigma }{)}^{d_B}(\mathrm{mod}{n}_B)$.

2. Bob computes $H(w^{\prime })$.

3. Bob verifies Alice’s signature: $H^{\prime \prime }(w^{\prime })=({\sigma }^{\prime }{)}^{e_A}(\mathrm{mod}{n}_A)$.

4. Bob checks if $H(w^{\prime })=H^{\prime \prime }(w^{\prime })$. If they match, the signature is valid and the message is authentic.

• Authenticity/Non-repudiation: Only Alice could have created $\sigma$.
• Protection from Bob: Bob cannot forge Alice’s signature for another document $u$ because he doesn’t know $d_A$.
• Confidentiality: Only Bob can decrypt $C_w$ and $C_{\sigma }$ using his private key $d_B$.

Exercise 9.4 (Beneš Network Properties)

For an $r$-dimensional Beneš network ${\text{Benes}}_r$ (which handles $n=2^r$ participants):

9. How many switching nodes does it have?

10. What is the length of the longest path between an x-participant and a y-participant?

Solution

1. A ${\text{Benes}}_r$ network has $2r-1$ stages of switches, and each stage has $n/2=2^{r-1}$ switching nodes. So, the total number of switching nodes is $(2r-1)\cdot 2^{r-1}$. For $n$ participants, this is $({\log }_{2}n)\cdot n-n/2$, which is $O(n\log n)$.
2. The length of the longest path (number of switching nodes traversed) is $2r-1$. For $n$ participants, $r={\log }_{2}n$, so the path length is $2{\log }_{2}n-1$, which is $O(\log n)$.