CS 758: Cryptography and Network Security

These notes follow the Spring 2016 course taught by Douglas R. Stinson at the David R. Cheriton School of Computer Science, University of Waterloo. The course extends basic cryptography into the multiuser and network context, covering cryptographic protocols, identification, key management, multicast security, and zero-knowledge proofs.

---

Module 1: Course Information and Introduction

Goals and Prerequisites

Basic cryptography is concerned with secure communication between two parties; this course is interested in cryptographic protocols in a multiuser or network context. The mathematical prerequisites include basic complexity theory, elementary number theory, algebra (finite groups, finite fields, linear algebra), probability theory, and combinatorics. This is not a pure mathematics course, but it carries significant mathematical content.

The course outline progresses through a review of cryptographic primitives and their applications to information security, followed by techniques for entity authentication including passwords, challenge-response, and identification schemes such as Fiat–Shamir and Guillou–Quisquater, and general techniques for zero-knowledge proofs for NP-complete languages. The second half covers protocols for key establishment, transport, agreement, and maintenance — including Kerberos, Diffie–Hellman key agreement, STS, forward secrecy, and unconditionally secure schemes such as the Blom scheme — followed by cryptography in multi-user settings: secret sharing, broadcast encryption, conference key distribution, and copyright protection.

---

Module 2: Goals of Cryptography and Cryptographic Tools

The Goals of Cryptography

Cryptographic systems serve multiple security objectives that can be classified as follows. Confidentiality (or secrecy) means that data cannot be understood by an unauthorized party. Data integrity means that data cannot be modified by an unauthorized party. Data origin authentication is achieved when it can be verified that data was transmitted by a particular source. Entity authentication (or identification) refers to the verification of the identity of a person, computer, or other device.

Beyond these primary goals, non-repudiation occurs when it is impossible for someone to deny having transmitted a message that they did in fact transmit. Access control refers to the restriction of electronic or physical access to authorized parties. Anonymity refers to the anonymous transmission of data so that the origin cannot be determined.

Cryptographic Tools (Primitives)

Encryption schemes are used to achieve confidentiality. Signature schemes are used to “sign” data; a signature helps to ensure data integrity and data origin authentication, and it can also provide non-repudiation. Message authentication codes (MACs) provide data integrity. Cryptographic hash functions shrink a long string into a short, random-looking string; they are used to provide unpredictable redundancy in data and are also used for key derivation.

Key agreement protocols establish a common secret key known to two or more specified parties; this key is subsequently used for another cryptographic purpose such as symmetric-key encryption or message authentication. Identification schemes provide entity authentication. Pseudorandom number generators expand a small, truly random seed into a long string of bits that cannot be distinguished from random bits; they are used in many cryptographic contexts, including key generation.

The following table summarizes which cryptographic tools can operate with public/private key pairs, secret keys, or no keys:

Scheme	Public/private key	Secret key	No key
Encryption scheme	✓	✓
Signature scheme	✓	✓
MAC		✓
Hash function			✓
Key agreement scheme	✓		✓
Identification scheme	✓		✓

Secure Socket Layer

The SSL protocol illustrates how these tools combine in practice. The client identifies itself as Alice; the server responds as Bob, Inc., sending its public key together with a CA signature \(\text{sig}_{\text{CA}}(\mathbf{PK})\). The client verifies the public key, generates a master secret MS, and encrypts it as \(y = e_{\mathbf{PK}}(\text{MS})\). The server decrypts to recover MS, and both parties derive two session keys via \(K_1, K_2 = h(\text{MS})\).

Cryptosystem Definition

A cryptosystem is a five-tuple \((\mathcal{P}, \mathcal{C}, \mathcal{K}, \mathcal{E}, \mathcal{D})\), where:

1. \(\mathcal{P}\) is a finite set of possible plaintexts
2. \(\mathcal{C}\) is a finite set of possible ciphertexts
3. \(\mathcal{K}\), the keyspace, is a finite set of possible keys
4. For each \(K \in \mathcal{K}\), there is an encryption rule \(e_K \in \mathcal{E}\) and a corresponding decryption rule \(d_K \in \mathcal{D}\) such that \(d_K(e_K(x)) = x\) for every plaintext \(x \in \mathcal{P}\).

In a secret-key cryptosystem, the key \(K\) is known to both Alice and Bob. In a public-key cryptosystem, the encryption key \(e_K\) is public but the decryption key is known only to the receiver.

The Advanced Encryption Standard (AES)

AES has a block length of 128 bits and supports key lengths of 128, 192, and 256 bits. The number of rounds \(\text{Nr}\) equals 10 for 128-bit keys, 12 for 192-bit keys, and 14 for 256-bit keys.

The algorithm operates as follows. Given a plaintext \(x\), the State is initialized to \(x\) and the AddRoundKey operation XORs the RoundKey with State. For each of the first \(\text{Nr} - 1\) rounds, AES performs a substitution called SubBytes using an S-box, a permutation ShiftRows, an operation MixColumns, and then AddRoundKey. The final round performs SubBytes, ShiftRows, and AddRoundKey. The ciphertext \(y\) is the resulting State.

SubBytes operates in the finite field \(\mathbb{F}_{2^8} = \mathbb{Z}_2[x]/(x^8 + x^4 + x^3 + x + 1)\), mapping each byte through a field inversion followed by an affine transformation over \(\mathbb{Z}_2\). ShiftRows cyclically shifts row \(i\) of the State by \(i\) positions. MixColumns treats each column as a polynomial over \(\mathbb{F}_{2^8}\) and multiplies by a fixed polynomial modulo \(x^4 + 1\).

Modes of Operation

In ECB (electronic code book) mode, each plaintext block \(x_i\) is independently encrypted with the same key \(K\). This naive mode is deterministic and leaks structure.

\[y_i = e_K(y_{i-1} \oplus x_i), \quad i \geq 1.\]

The RSA Public-Key Cryptosystem

\[\mathcal{K} = \{(n, p, q, a, b) : ab \equiv 1 \pmod{\phi(n)}\}.\]

For key \(K = (n, p, q, a, b)\), encryption is \(e_K(x) = x^b \bmod n\) and decryption is \(d_K(y) = y^a \bmod n\). The values \(n\) and \(b\) form the public key; \(p, q\) and \(a\) form the private key.

Example. Suppose \(p = 101\), \(q = 113\), so \(n = 11413\) and \(\phi(n) = 11200\). With public exponent \(b = 3533\), the private exponent is \(a = 3533^{-1} \bmod 11200 = 6597\). To encrypt plaintext \(x = 9726\): \(y = 9726^{3533} \bmod 11413 = 5761\). Bob recovers \(x = 5761^{6597} \bmod 11413 = 9726\).

The Rabin Cryptosystem

Let \(n = pq\). The encryption function is \(e_K(x) = x^2 \bmod n\), and decryption requires computing \(\sqrt{y} \bmod n\). The public key is \(n\); the private key is the factorization \((p, q)\). Note that there are four square roots of any valid ciphertext \(y\) modulo \(n\), so the legitimate message must be identified by redundancy.

Signature Schemes

A signature scheme is a five-tuple \((\mathcal{P}, \mathcal{A}, \mathcal{K}, \mathcal{S}, \mathcal{V})\). The signing algorithm \(\text{sig}_K : \mathcal{P} \to \mathcal{A}\) and verification algorithm \(\text{ver}_K : \mathcal{P} \times \mathcal{A} \to \{\text{true}, \text{false}\}\) satisfy \(\text{ver}_K(x, y) = \text{true}\) if and only if \(y = \text{sig}_K(x)\).

Using hash functions with signatures. Rather than signing the full message \(x\), Alice computes \(z = h(x)\) and signs the digest: \(y = \text{sig}_K(z)\). Bob verifies by recomputing \(z = h(x)\) and checking \(\text{ver}_K(z, y)\). This is far more efficient than signing long messages directly.

RSA Signature Scheme. Using the same setup as RSA encryption, the signing operation is \(\text{sig}_K(x) = x^a \bmod n\) and verification is \(\text{ver}_K(x, y) = \text{true} \Leftrightarrow x \equiv y^b \pmod{n}\).

Digital Signature Standard (DSS)

Let \(p\) be a 1024-bit prime and \(q\) a 160-bit prime dividing \(p - 1\). Let \(\alpha \in \mathbb{Z}_p^*\) have order \(q\). The private key is \(a\) where \(0 \leq a \leq q-1\), and the public key includes \(\beta = \alpha^a \bmod p\).

\[\gamma = (\alpha^k \bmod p) \bmod q, \qquad \delta = (\text{SHA-1}(x) + a\gamma) k^{-1} \bmod q.\]

Verification checks \((\alpha^{e_1} \beta^{e_2} \bmod p) \bmod q = \gamma\), where \(e_1 = \text{SHA-1}(x) \cdot \delta^{-1} \bmod q\) and \(e_2 = \gamma \delta^{-1} \bmod q\).

Hash Functions and Families

A hash family is a four-tuple \((\mathcal{X}, \mathcal{Y}, \mathcal{K}, \mathcal{H})\) where \(\mathcal{X}\) is a (possibly infinite) set of messages, \(\mathcal{Y}\) is a finite set of digests, and each keyed hash function \(h_K : \mathcal{X} \to \mathcal{Y}\). An unkeyed hash function has a single key.

\[z_0 \leftarrow \text{IV}, \quad z_i \leftarrow \text{compress}(z_{i-1} \| y_i), \quad h(x) = g(z_r).\]

SHA-1 is an iterated hash function producing a 160-bit digest. It pads the input to a multiple of 512 bits, splits into 16-word blocks, then processes through 80 rounds using bitwise operations (AND, OR, XOR, NOT), addition modulo \(2^{32}\), and circular shifts. The round functions \(f_t\) vary across four groups of 20 rounds.

CBC-MACs

\[y_0 \leftarrow 0^t, \quad y_i \leftarrow e_K(y_{i-1} \oplus x_i), \quad \text{CBC-MAC}_K(x) = y_n.\]

Comparison: Public-Key vs. Secret-Key Cryptography

Secret-key cryptographic protocols are typically 100 to 1000 times faster than corresponding public-key protocols. Public-key protocols are described by simple mathematical functions whose security rests on intractability assumptions (factoring, discrete log), while secret-key systems rely on complex compositions of simple substitutions and permutations.

Public keys can be distributed freely through directories or certificates, but require authentication via a public-key infrastructure. The authenticity of secret keys is guaranteed by the protocol used to generate or distribute them.

---

Module 3: Mathematical Background

Modular Arithmetic

For integers \(a, b\) and positive integer \(m\), we write \(a \equiv b \pmod{m}\) if \(m \mid (b - a)\). The notation \(a \bmod m\) (without parentheses) denotes the non-negative remainder when \(a\) is divided by \(m\). The set \(\mathbb{Z}_n = \{0, 1, \ldots, n-1\}\) equipped with addition and multiplication modulo \(n\) forms the ring of integers modulo \(n\).

Finite Abelian Groups

A finite abelian group is a pair \(G = (X, \star)\) satisfying closure, commutativity, associativity, the existence of an identity element, and the existence of inverses. The order of the group, denoted \(\text{ord}(G)\), is \(|X|\).

Three important examples are \((\mathbb{Z}_n, +)\) of order \(n\), \((\mathbb{Z}_p^*, \cdot)\) of order \(p - 1\) for prime \(p\), and \((\mathbb{Z}_n^*, \cdot)\) of order \(\phi(n)\) (Euler’s totient function), where \(\mathbb{Z}_n^* = \{d \in \mathbb{Z}_n : \gcd(d, n) = 1\}\).

\[\phi(n) = \prod_{i=1}^{\ell} p_i^{e_i - 1}(p_i - 1).\]

Order of Group Elements

\[\text{ord}(b) = \frac{\text{ord}(a)}{\gcd(\text{ord}(a), i)}.\]

Cyclic Groups

A finite abelian group \((X, \star)\) is cyclic if there exists a generator \(a \in X\) with \(\text{ord}(a) = |X|\). The group \((\mathbb{Z}_n, +)\) is always cyclic with generator 1; the group \((\mathbb{Z}_p^*, \cdot)\) is cyclic for prime \(p\), and its generators are called primitive elements. An element \(\alpha \in \mathbb{Z}_p^*\) is primitive if and only if \(\alpha^{(p-1)/q} \not\equiv 1 \pmod{p}\) for all prime divisors \(q\) of \(p-1\).

Quadratic Residues

An integer \(a\) is a quadratic residue modulo prime \(p\) if \(a \not\equiv 0 \pmod{p}\) and \(y^2 \equiv a \pmod{p}\) has a solution. This is equivalent to \(a^{(p-1)/2} \equiv 1 \pmod{p}\) (Euler’s criterion). Every quadratic residue modulo \(p\) has exactly two square roots. If \(p \equiv 3 \pmod{4}\), the square roots are \(\pm a^{(p+1)/4} \bmod p\).

The Extended Euclidean Algorithm

The multiplicative inverse \(b^{-1} \bmod a\) exists if and only if \(\gcd(a, b) = 1\). The Extended Euclidean Algorithm computes both \(\gcd(a,b)\) and the inverse simultaneously through a sequence of divisions. Example: To compute \(28^{-1} \bmod 75\), the algorithm yields \(28^{-1} \bmod 75 = -8 \bmod 75 = 67\).

The Chinese Remainder Theorem

\[x = \sum_{i=1}^{r} a_i M_i y_i \bmod M,\]

where \(M_i = M/m_i\) and \(y_i = M_i^{-1} \bmod m_i\).

The Square-and-Multiply Algorithm

To compute \(z = x^c\) in any multiplicative group, the square-and-multiply algorithm processes the binary representation of \(c = \sum_{i=0}^{\ell-1} c_i 2^i\) from most significant to least significant bit: it squares the current result at each step, and if \(c_i = 1\), multiplies by \(x\). This requires \(O(\ell)\) group operations rather than \(O(2^\ell)\).

Computational Problems

Most public-key cryptographic security reduces to the presumed difficulty of two problems:

Integer Factoring: Given a composite \(n\), find its prime factorization. For \(n = pq\) with \(p, q\) large random primes, current recommendations require \(n\) to be at least 1024 bits.

Discrete Logarithm: Given a group \((G, \cdot)\), an element \(\alpha\) of order \(n\), and \(\beta \in \langle\alpha\rangle\), find the unique integer \(a\), \(0 \leq a \leq n-1\), such that \(\alpha^a = \beta\). This is denoted \(a = \log_\alpha \beta\).

Important settings for the discrete logarithm include: \(G = (\mathbb{Z}_p^*, \cdot)\) with \(p \approx 2^{1024}\); subgroups of order \(q \approx 2^{160}\) in \(\mathbb{Z}_p^*\); multiplicative groups of binary extension fields \(\mathbb{F}_{2^n}\); and elliptic curve groups.

---

Module 4: A Formal Model for Security

What Does “Secure” Mean?

The history of RSA illustrates the difficulty of informal security claims. In 1977, Gardner wrote that the RSA challenge cipher would take “millions of years to break” — yet it was solved in 1994 using the then-current Number Field Sieve and distributed computation. Between 1977 and 1994, computers became much faster, new factoring algorithms emerged, and the internet enabled large-scale collaboration. The current state-of-the-art is the factorization of the 768-bit RSA-768 challenge in December 2009.

The Formal Security Framework

Any discussion of cryptographic security requires three components:

Attack model — We always assume the adversary knows the protocol being used (Kerckhoff’s Principle) and knows all public keys, but does not know secret or private keys. The attack model specifies any additional information available to the adversary.

Adversarial goal — This specifies what it means to “break” the cryptosystem, and quantifies what constitutes a successful attack.

Security level — This quantifies the computational resources the adversary can employ.

A security statement asserts that a particular adversarial goal cannot be achieved in a specified attack model given specified computational resources.

Attack Models for Cryptosystems

From weakest to strongest:

• Known ciphertext attack: the adversary sees ciphertext only.
• Known plaintext attack: the adversary is given matched plaintext–ciphertext pairs.
• Chosen plaintext attack: the adversary can choose plaintexts and receive the corresponding ciphertexts.
• Chosen ciphertext attack: the adversary can choose ciphertexts and receive the corresponding plaintexts.

Adversarial Goals for Encryption

• Complete break: determining the private/secret key.
• Decryption of new ciphertexts: recovering plaintext from previously unseen ciphertexts.
• Partial information: obtaining some partial information about the plaintext.
• Distinguishability: distinguishing between encryptions of two given plaintexts. Semantic security means the adversary cannot do this.

Security Levels

Computational security means a specific break algorithm is computationally infeasible in practice. Provable security means breaking the scheme can be reduced, in a complexity-theoretic sense, to solving a hard underlying mathematical problem. Unconditional security means the cryptosystem cannot be broken even with unlimited computation — there is not enough information for the adversary to proceed.

Example — One-time Pad. Let \(\mathcal{P} = \mathcal{C} = \mathcal{K} = (\mathbb{Z}_2)^n\). Encryption and decryption are both \(e_K(x) = x \oplus K\). Given a single ciphertext \(y\), the adversary cannot distinguish between plaintext \(x_1\) and \(x_2\) because both are consistent with the key: \(y = x_i \oplus K_i\) for \(K_i = y \oplus x_i\). This achieves unconditional security.

Example — Rabin’s Provable Security. If a decryption oracle for Rabin exists, then there is a randomized algorithm that factors \(n = pq\) with probability at least \(1/2\), as follows: choose random \(r \in \mathbb{Z}_n^*\), compute \(y = r^2 \bmod n\), query the oracle to obtain some \(x\) with \(x^2 \equiv y \pmod{n}\). With probability \(1/2\), \(x \not\equiv \pm r \pmod{n}\), and then \(\gcd(x + r, n)\) yields a non-trivial factor of \(n\).

Attack Models for Signature Schemes

For signatures, the attack models range from key-only attack (adversary has only the public verification key) through known message attack (adversary has signed message–signature pairs) to chosen message attack (adversary can request signatures on chosen messages). Adversarial goals range from total break (determining the private signing key) through selective forgery (forging a signature on any given message) to existential forgery (forging a signature on any message).

RSA without hashing is existentially forgeable in a key-only attack: an adversary chooses any \(y \in \mathbb{Z}_n\) and computes \(x = y^b \bmod n\); then \(y\) is a valid RSA signature on \(x\). Using a preimage-resistant hash prevents this.

Assumptions and the Random Oracle Model

Proofs of security often depend on assumptions about models or problems. The black-box model treats schemes as input–output functions, ignoring implementation details — side-channel attacks (timing, power) exploit implementation details not captured in this model. Intractability assumptions are based on the presumed difficulty of factoring or discrete log.

The random oracle model treats hash function outputs as truly random and unpredictable. A proof in this model shows that the adversary cannot succeed without exploiting weaknesses in the specific hash function. Similarly, the perfect random number generator model assumes ideal randomness for key generation.

---

Module 5: Identification

Identification Techniques

Identification can be based on physical attributes (appearance, fingerprints, retina scans), credentials (passports, driver’s licences), or knowledge (passwords, PINs). Knowledge-based identification is difficult to secure because the knowledge may not have been secret initially, and it is revealed during the identification process — allowing future impersonation.

Formal Model for Identification Schemes

The adversary in an identification protocol can observe all transmitted information; the adversarial goal is to impersonate the prover. A secure scheme requires randomization — typically through a random challenge from the verifier — otherwise an adversary can replay a previous session. An adversary is considered active in a session if they: (1) create a new message, (2) change a message, or (3) divert a message to a different recipient. The adversarial goal is to cause the verifier to “accept” in a session where the adversary is active.

The Insecure Challenge-and-Response Scheme

The naive challenge-and-response protocol is: Bob sends a random challenge \(r\), Alice computes \(y = \text{MAC}_K(r)\) and returns it, Bob verifies. This is vulnerable to a parallel session attack: Oscar pretends to be Alice with Bob, but when he receives challenge \(r\), he opens a second session with Bob (pretending to be Bob himself) using the same challenge, obtains the correct MAC, and forwards it in the first session.

The Secure Challenge-and-Response Scheme

The fix is to include the prover’s identity in the MAC input. Alice computes \(y = \text{MAC}_K(\text{Alice} \| r)\). Since Bob only ever computes tags of the form \(\text{MAC}_K(\text{Bob} \| r)\), Oscar cannot obtain the needed response from a parallel session.

Security analysis. Suppose the MAC is \((T, q, \varepsilon)\)-secure (the adversary cannot forge a tag in time \(T\) given \(q\) previous valid tags, with probability greater than \(\varepsilon\). If the random challenge is \(k\) bits, then Oscar’s probability of impersonating Alice in time \(T\), having seen at most \(q\) previous sessions, is at most \(q/2^k + \varepsilon\).

Mutual Identification

Mutual identification requires both parties to prove their identities to each other. The naive four-flow protocol (both run the one-way protocol) is vulnerable to a parallel session attack. The secure version has Alice include Bob’s challenge in her MAC computation:

1. Bob sends random \(r_1\).
2. Alice sends \(r_2\) and \(y_1 = \text{MAC}_K(\text{Alice} \| r_1 \| r_2)\).
3. Bob accepts if \(y_1\) is valid; sends \(y_2 = \text{MAC}_K(\text{Bob} \| r_2)\).
4. Alice accepts if \(y_2\) is valid.

Since \(y_1\) and \(y_2\) are structurally different (different first arguments), tags from one flow cannot be reused as the other. Oscar’s overall success probability is at most \(q/2^k + 2\varepsilon\).

Public-Key Based Identification

\[\text{Cert}(\text{Alice}) = (\text{ID}(\text{Alice}) \| \text{ver}_{\text{Alice}} \| s), \quad s = \text{sig}_{\text{CA}}(\text{ID}(\text{Alice}) \| \text{ver}_{\text{Alice}}).\]

Anyone knowing \(\text{ver}_{\text{CA}}\) can verify Alice’s public key.

The public-key mutual identification protocol replaces MACs with signatures and omits explicit identity strings (since only one party can create signatures under a given key). Alice signs \(\text{sig}_{\text{Alice}}(\text{Bob} \| r_1 \| r_2)\) in flow 2; Bob signs \(\text{sig}_{\text{Bob}}(\text{Alice} \| r_2)\) in flow 3. This protocol is provably secure.

The Schnorr Identification Scheme

The Schnorr scheme is a specialized identification protocol based on the discrete logarithm problem. The setup uses a prime order subgroup \(\langle\alpha\rangle\) of \(\mathbb{Z}_p^*\) with \(p \approx 2^{1024}\) and \(q \approx 2^{160}\).

Alice’s private key is \(a\), \(0 \leq a \leq q-1\); her public key is \(v = \alpha^{-a} \bmod p\). The protocol proceeds as:

1. Alice chooses random \(k \in \{0, \ldots, q-1\}\), computes a commitment \(\gamma = \alpha^k \bmod p\), and sends \(\text{Cert}(\text{Alice})\) and \(\gamma\) to Bob.
2. Bob verifies the certificate and sends a random challenge \(r \in \{1, \ldots, 2^t\}\).
3. Alice computes the response \(y = k + ar \bmod q\) and sends it.
4. Bob accepts if \(\gamma \equiv \alpha^y v^r \pmod{p}\).

Completeness follows immediately: \(\alpha^y v^r = \alpha^{k+ar} \alpha^{-ar} = \alpha^k = \gamma\).

Efficiency: Alice’s main computation (\(\gamma = \alpha^k\) can be precomputed. The communication is 1024 bits for \(\gamma\), 40 bits for \(r\), and 160 bits for \(y\).

Proof of Knowledge Security of Schnorr

Theorem (Schnorr). Suppose algorithm \(A\) impersonates Alice with success probability \(\varepsilon \geq 2^{-t+1}\). Then \(A\) can be used as an oracle in a Las Vegas algorithm \(B\) that computes Alice’s private key \(a\), with expected complexity \(O(1/\varepsilon)\).

\[a = (y_1 - y_2)(r_1 - r_2)^{-1} \bmod q.\]

Algorithm \(B\) works by: (1) finding a successful \(A(k_1, r_1)\) via random trials; (2) searching for a second success \(A(k_1, r_2)\) with the same \(k_1\). Combining the four lemmas shows that \(B\) succeeds with probability at least 0.055 per iteration, giving an expected number of iterations of at most 18 and expected total complexity \(O(1/\varepsilon)\).

Zero-Knowledge Proofs of Knowledge

The Schnorr scheme is a proof of knowledge: Alice cannot complete the protocol successfully without knowing the discrete logarithm \(a\). It is also honest-verifier zero-knowledge: the probability distribution of transcripts \((\gamma, r, y)\) in real sessions is identical to the distribution of simulated transcripts generated without Alice’s participation. A simulator simply chooses \(r \in_R \{1, \ldots, 2^t\}\), \(y \in_R \{0, \ldots, q-1\}\), and sets \(\gamma = \alpha^y v^r \bmod p\). Since \(\Pr_{\text{sim}}[T] = \Pr_{\text{real}}[T] = 1/(q \cdot 2^t)\) for all transcripts \(T\), the protocol reveals nothing about \(a\) to an honest verifier.

Two-Channel Cryptography

Two-channel cryptography uses a combination of a broadband insecure channel (wireless, can be controlled by the adversary) and a narrow-band authenticated channel (voice, NFC, visible light — the adversary cannot modify messages over it). The goal is to establish authenticated sessions using both channels while minimizing communication overhead.

Non-Interactive Message Authentication Protocol (NIMAP)

In the Mashatan–Stinson NIMAP, Alice sends message \(M\) and random key \(K \in_R \{0,1\}^{\ell_2}\) over the broadband channel, and sends hash \(h = H(M \| K)\) over the authenticated narrow-band channel. Bob accepts if \(h = H(M' \| K')\).

The security property required is hybrid-collision resistance (HCR): Oscar, knowing \(M\) but not \(K\), must find \(L \neq M \| K\) with \(H(M \| K) = H(L)\).

\[\varepsilon \leq 2^{t-d} + 2^{2t-d-\ell_2}.\]\[\varepsilon \leq 2^{-30} + 2^{-40} \approx 2^{-30}.\]

---

Module 6: Key Management

Overview of Key Distribution

Key management scenarios include:

• Key predistribution schemes (KPS): a trusted authority (TA) distributes secret information ahead of time to allow pairs of users to compute shared keys.
• Session key distribution schemes (SKDS): an online TA distributes session keys upon request (e.g., Kerberos).
• Key agreement schemes (KAS): network users interactively construct session keys.

Why use session keys? Session keys limit the ciphertext available to an attacker per key, limit exposure if a session key is compromised, reduce long-term storage requirements, and create independence across sessions.

Long-lived key requirements: SKDS requires one LL-key per user with the TA (low storage, online TA needed). Secret-key KAS requires \(n-1\) keys per user (high storage, no TA required). Public-key KAS requires one key pair per user plus a CA for the infrastructure.

The Blom Key Predistribution Scheme

The Blom scheme distributes LL-keys to all \(n\) users in advance. Each user is assigned a public value \(r_U \in \mathbb{Z}_p\) (distinct). Security parameter \(k\) means the scheme resists any coalition of at most \(k\) colluders.

\[f(x, y) = a + b(x + y) + cxy \bmod p.\]

User \(U\) receives the polynomial \(g_U(x) = f(x, r_U) = a_U + b_U x\) over a secure channel.

The shared LL-key for users \(U\) and \(V\) is \(K_{U,V} = f(r_U, r_V)\); user \(U\) computes this as \(g_U(r_V)\) and user \(V\) computes it as \(g_V(r_U)\). Both obtain the same value because \(f\) is symmetric.

Security. Any single colluder \(W\) knows \((a_W, b_W)\) and wants to compute \(K_{U,V} = a + b(r_U + r_V) + cr_Ur_V\). Setting up the linear system, the coefficient matrix has determinant \((r_W - r_U)(r_W - r_V) \neq 0\), showing that any value of \(K_{U,V}\) is consistent with \(W\)’s information. Any coalition of two users \(\{W, X\}\) has four equations in three unknowns and can determine \(a, b, c\) — breaking the scheme.

General \(k\)-resilient Blom scheme. The TA forms a symmetric polynomial \(f(x,y) = \sum_{i,j=0}^{k} a_{i,j} x^i y^j\) with \(a_{i,j} = a_{j,i}\). Each user \(U\) receives the \((k+1)\)-coefficient vector of \(g_U(x) = f(x, r_U)\). Security: (1) any \(k\) colluders cannot determine any information about the key of two other users; (2) any \(k+1\) colluders can break the scheme using bivariate Lagrange interpolation to reconstruct \(f(x,y)\) completely.

The Diffie–Hellman Problems

Computational Diffie–Hellman (CDH) problem. Given \(\alpha^b\) and \(\alpha^c\) in a group \(\langle\alpha\rangle\), compute \(\alpha^{bc}\). This is no harder than discrete log: if one can solve DLP, one can solve CDH. CDH is conjectured to be infeasible in \(\mathbb{Z}_p^*\) with \(p \approx 2^{1024}\) and prime subgroup order \(q > 2^{160}\).

Decision Diffie–Hellman (DDH) problem. Given \(\alpha^b, \alpha^c, \alpha^d\), determine whether \(d \equiv bc \pmod{n}\). DDH is no harder than CDH (given a CDH oracle, just compute \(\delta' = \text{CDH}(\alpha, \beta, \gamma)\) and check if \(\delta' = \delta\). Semantic security of Diffie–Hellman keys is equivalent to the intractability of DDH.

Diffie–Hellman KPS. Each user \(U\) has private key \(a_U\) and public key \(b_U = \alpha^{a_U} \bmod p\). The shared LL-key is \(K_{U,V} = \alpha^{a_U a_V} \bmod p\); user \(U\) computes \(b_V^{a_U}\) and user \(V\) computes \(b_U^{a_V}\). Security reduces to CDH.

Key Predistribution in Wireless Sensor Networks

Wireless sensor nodes have limited computation, communication, and battery resources, and must be deployed in potentially hostile environments. A KPS is installed before deployment. The two extreme designs are: (1) a single master key for all nodes — compromising one node breaks the entire network; (2) pairwise keys for all pairs — requires \(O(n)\) storage per node.

Eschenauer–Gligor (2002) proposed a probabilistic approach: each node is assigned a random \(k\)-subset of a pool of keys. Chan–Perrig–Song (2003) required \(\eta\) common keys before establishing a pairwise key. Key metrics are: connectivity probability \(\Pr_1\) (probability that two random nodes can establish a key), and resilience \(\text{fail}(s)\) (probability a random link is broken by \(s\) compromised nodes).

\[\Pr_1 = \frac{k(r-1)}{b-1}, \qquad \text{fail}(1) = \frac{r-2}{b-2}.\]

Transversal designs TD(\(t, k, n\). Lee and Stinson (2005) used transversal designs constructed from prime fields: for prime \(p\), the blocks are \(A_c = \{(x, \sum_{i=0}^{t-1} c_i x^i) : 0 \leq x \leq k-1\}\) for each \(c \in \mathbb{Z}_p^t\). These are equivalent to Reed–Solomon codes. A TD(2, \(k\), \(n\) gives network size \(n^2\) and \(\Pr_1 = k/(n+1)\); a TD(3, \(k\), \(n\) with \(\eta = 2\) gives network size \(n^3\) with improved ratio \(\rho \approx k^2/2\).

Session Key Distribution

Needham–Schroeder SKDS (1978). Alice requests a session key from the TA, receives an encrypted ticket for Bob. The TA issues a fresh session key \(K\), encrypts a ticket \(t_{\text{Bob}} = e_{K_{\text{Bob}}}(K \| \text{Alice})\), and sends Alice \(e_{K_{\text{Alice}}}(r_A \| \text{Bob} \| K \| t_{\text{Bob}})\). Key confirmation is achieved in two more flows involving Alice and Bob using \(K\).

Denning–Sacco Attack (1981). If Oscar records a session and later learns the session key \(K\), he can replay the old ticket \(t_{\text{Bob}}\) to Bob, making Bob believe he has a fresh session with Alice using \(K\) — when in fact Oscar knows \(K\). This is a replay attack exploiting the absence of freshness in the ticket.

Kerberos V5 (1989) adds a validity period \(L\) to the ticket and uses a timestamp \(\text{time}_A\) for mutual key confirmation. While this mitigates the Denning–Sacco attack, timestamps require synchronized clocks and complicate security proofs.

Better design principles identified from these attacks: (1) Bob should be an active participant before receiving the session key, to prevent replay of old tickets; (2) use MACs rather than encryption for authenticity; (3) avoid using the session key to encrypt information within the key distribution protocol.

\[y_B = (e_{K_{\text{Bob}}}(K),\; \text{MAC}_{\text{Bob}}(\text{Alice} \| \text{Bob} \| r_B \| e_{K_{\text{Bob}}}(K))).\]

The protocol is provably secure in a known session key attack: if Alice accepts, she can be confident that only Bob and the TA can compute the session key.

Diffie–Hellman Key Agreement

The basic Diffie–Hellman protocol: User \(U\) chooses random \(a_U\), sends \(b_U = \alpha^{a_U}\); user \(V\) chooses random \(a_V\), sends \(b_V = \alpha^{a_V}\); both compute \(K = \alpha^{a_U a_V}\). Assuming DDH is intractable, a passive adversary cannot compute any information about \(K\).

However, the protocol is insecure against intruder-in-the-middle attacks: adversary \(W\) intercepts both messages and substitutes his own \(\alpha^{a_W'}\) and \(\alpha^{a_W''}\), establishing \(\alpha^{a_U a_W'}\) with \(U\) and \(\alpha^{a_V a_W''}\) with \(V\).

The Station-to-Station (STS) Protocol

The STS protocol adds authentication to Diffie–Hellman by incorporating signatures on the ephemeral public values:

1. \(U\) sends \(b_U = \alpha^{a_U}\).
2. \(V\) sends \(b_V = \alpha^{a_V}\) and \(y_V = \text{sig}_V(\text{ID}(U) \| \alpha^{a_V} \| \alpha^{a_U})\).
3. \(U\) verifies \(y_V\), computes \(K = b_V^{a_U}\), sends \(y_U = \text{sig}_U(\text{ID}(V) \| \alpha^{a_U} \| \alpha^{a_V})\).
4. \(V\) verifies \(y_U\) and computes \(K = b_U^{a_V}\).

STS provides implicit key confirmation and perfect forward secrecy: even if LL-keys are later compromised, past session keys remain secure since each \(a_U, a_V\) is ephemeral and discarded.

Key Authentication Terminology

• Implicit key authentication: assurance that only the intended partner can compute the session key.
• Implicit key confirmation: assurance that the partner has the information needed to compute the session key.
• Explicit key confirmation: assurance that the partner has actually computed the session key.

Needham–Schroeder and Kerberos provide explicit key confirmation; STS provides implicit key confirmation; Bellare–Rogaway provides implicit key authentication.

MTI Protocols

\[K = \alpha^{r_U a_V + r_V a_U} \bmod p,\]

where \(r_U, r_V\) are fresh random exponents. MTI/A0 is secure against passive attacks but vulnerable to a parallel session known-session-key attack: adversary \(W\) can use the symmetry of the key formula to derive a target key from two other known keys. The Burmester triangle attack exploits the same symmetry with three participants. A key derivation function \(K = h_{\text{RO}}(\alpha^{r_U a_V} \| \alpha^{r_V a_U})\) breaks the symmetry and is conjectured to resist both attacks.

---

Module 7: Multicast Security

Overview

A multicast message has many designated receivers. Security goals differ by scenario: in single-source broadcast, a single entity broadcasts to a possibly dynamic group, requiring confidentiality, key revocation, and copyright protection. In a virtual conference, a small static group requires group key establishment, authentication, and shared access control.

New cryptographic tools needed include secret sharing schemes, group key predistribution, broadcast encryption, tracing/fingerprinting schemes, group KAS, and multireceiver authentication codes.

Secret Sharing

A (t, n)-threshold scheme allows a TA to split a secret \(K\) into \(n\) shares \(s_1, \ldots, s_n\) such that: (1) any \(t\) shares suffice to reconstruct \(K\), and (2) any \(t-1\) shares reveal no information about \(K\).

A trivial (n, n)-threshold scheme: choose \(s_1, \ldots, s_{n-1} \in_R \mathbb{Z}_m\) and set \(s_n = K - \sum_{i=1}^{n-1} s_i \bmod m\). Then \(\sum s_i = K\), but knowing \(n-1\) shares reveals nothing about the last.

The Shamir Threshold Scheme (1979)

\[a(x) = K + a_1 x + a_2 x^2 + \cdots + a_{t-1} x^{t-1} \in \mathbb{Z}_p[x]\]

and distributes share \(s_i = a(x_i)\) to user \(U_i\).

\[K = a(0) = \sum_{j=1}^{t} s_{i_j} b_j, \quad b_j = \prod_{1 \leq k \leq t, k \neq j} \frac{x_{i_k}}{x_{i_k} - x_{i_j}}.\]

Security. For any \(t-1\) shares \(s_{i_1}, \ldots, s_{i_{t-1}}\) and any candidate \(K_0 \in \mathbb{Z}_p\), there is a unique polynomial \(a_0(x)\) of degree at most \(t-1\) consistent with those shares and with \(a_0(0) = K_0\) — so no information about \(K\) is revealed.

Key Distribution Patterns

A key distribution pattern (KDP) is a \(v \times n\) binary incidence matrix \(M\) specifying which of \(v\) keys each of \(n\) users receives. For a subset \(P \subseteq U\), define \(\text{keys}(P) = \{i : M[i,j] = 1 \text{ for all } U_j \in P\}\); the group key for \(P\) is \(k_P = \sum_{i \in \text{keys}(P)} k_i\) (mod \(|K|\).

A coalition \(F\) can compute \(k_P\) if and only if \(\text{keys}(P) \subseteq \bigcup_{U_j \in F} \text{keys}(U_j)\).

Fiat–Naor KDP. The \(w\)-KDP uses the incidence matrix of all subsets of \(U\) of size at least \(n - w\) as rows. For any \(P \subseteq U\) and any disjoint coalition \(F\) with \(|F| \leq w\), the key \(k_P\) is secure against \(F\). Proof: \(|U \setminus F| \geq n - w\), so there exists a key given to all of \(U \setminus F\) but to no user in \(F\).

\[\bigcap_{A_i \in P} A_i \not\subseteq \bigcup_{A_j \in F} A_j.\]

The Mitchell–Piper KDP uses CFFs to derive KDPs. When a KDP’s incidence matrix corresponds to a (1, \(w\)-CFF, every group key for any single user is secure against any coalition of at most \(w\) other users.

Broadcast Encryption

In a broadcast encryption scheme, a sender broadcasts an encrypted message that only authorized users can decrypt. A common construction: each user \(U_i\) holds a set of keys \(K_i\); the sender uses a CFF-based KDP to find a set of keys held only by authorized users, and encrypts the session key with those keys. Revoked users’ key sets do not overlap sufficiently with the cover.

Shamir Threshold Secret Sharing for Access Structures

Beyond threshold schemes, general access structures specify arbitrary subsets of users that can reconstruct the secret. For a monotone access structure \(\Gamma\), Shamir-based schemes can be combined with secure multiparty computation to create multi-secret sharing protocols.

Ramp Schemes

A (t_1, t_2, n)-ramp scheme is a relaxation of a threshold scheme: any \(t_2\) shares suffice to reconstruct the secret, any \(t_1 - 1\) shares reveal no information, and between \(t_1\) and \(t_2 - 1\) shares reveal partial information. Ramp schemes trade information-theoretic security for increased efficiency.

Re-keying, Revocation, and Logical Key Hierarchy

When a user leaves a broadcast group, all keys they knew must be replaced. Re-keying protocols update keys efficiently. The Logical Key Hierarchy (LKH) organizes users in a binary tree: each user holds the keys from their leaf to the root. Removing one user requires updating \(O(\log n)\) keys and broadcasting \(O(\log n)\) encrypted messages, rather than \(O(n)\).

Copyright Protection and Tracing Schemes

Fingerprinting schemes embed a unique, hidden identifier into each distributed copy of content, so that if a user redistributes their copy, the copy can be traced back to them. The key challenge is coalition resistance: if \(c\) colluders combine their copies, can the scheme still identify at least one of them?

A \(c\)-tracing scheme ensures that from any pirated copy produced by a coalition of at most \(c\) users, a tracing algorithm can identify at least one coalition member. The construction uses specialized codewords derived from a combinatorial structure called a \(c\)-frameproof code (FPC): a code where no coalition of \(c\) codewords can “frame” a codeword outside the coalition.

---

Module 8: Additional Topics

Zero-Knowledge Proofs for NP-Complete Languages

The Schnorr scheme is a special-purpose zero-knowledge proof for the discrete logarithm problem. A general technique provides zero-knowledge proofs for any NP-complete language. The idea: if a problem is in NP, there is an efficient verifiable witness; one designs an interactive protocol where the prover demonstrates knowledge of the witness without revealing it.

Graph 3-coloring is NP-complete and serves as a canonical example. A zero-knowledge proof of knowledge for 3-coloring:

1. The prover applies a random permutation \(\pi\) of the three colors to their coloring and commits to each vertex’s color using a binding, hiding commitment scheme.
2. The verifier challenges with a random edge \((u, v)\).
3. The prover reveals \(\pi(c(u))\) and \(\pi(c(v))\) (the colors of the two endpoints) and opens those commitments.
4. The verifier checks that the two colors differ.

Since this reveals only one edge’s colors per round, and the permutation hides the full structure, repeating the protocol sufficiently many times achieves negligible soundness error while leaking no information about the full coloring.

Advanced Identification Schemes

Fiat–Shamir Identification Scheme

The Fiat–Shamir scheme is based on the square root problem modulo \(n = pq\). Alice’s secret is \(s \in \mathbb{Z}_n^*\) and her public key is \(v = s^2 \bmod n\).

1. Alice commits \(x = r^2 \bmod n\) for random \(r\).
2. Bob challenges with \(e \in \{0, 1\}\).
3. Alice responds with \(y = rs^e \bmod n\).
4. Bob verifies \(y^2 \equiv x v^e \pmod{n}\).

The scheme can be parallelized with \(k\) independent executions per round to reduce soundness error to \(2^{-k}\).

Guillou–Quisquater Identification Scheme

The Guillou–Quisquater scheme is analogous but uses \(v = s^{-e} \bmod n\) and response \(y = rs^c \bmod n\) for challenge \(c\). Security is based on the difficulty of computing \(e\)-th roots modulo \(n\) (related to RSA).

Unconditionally Secure Message Authentication

\[\Pr_K[h_K(x) = y \text{ and } h_K(x') = y'] \leq \varepsilon^2.\]

Using a fresh random key for each message gives information-theoretically secure MAC protection. Constructions include polynomial evaluation codes and strongly universal hash families based on finite fields.

Secret Sharing and Secure Computation

Verifiable Secret Sharing (VSS) extends threshold schemes by allowing each user to verify the validity of their share without revealing it. This prevents a malicious TA from distributing inconsistent shares. VSS is a fundamental building block in secure multiparty computation (MPC), where \(n\) parties collectively compute a function of their private inputs without any party learning more than the function output.

Conference Key Distribution

A conference key distribution scheme allows a designated group \(G \subseteq U\) of users to compute a shared session key through an interactive protocol. Ingemarsson–Tang–Wong (1982) generalized Diffie–Hellman to \(n\) parties; optimal broadcast complexity bounds were studied by Steiner–Tsudik–Waidner. Security analysis in the adversarial model with active attacks is significantly more complex than the two-party case.

Broadcast Authentication

Source authentication in a broadcast setting requires that all recipients can verify the authenticity of messages from the source, without being able to forge messages themselves. This cannot be achieved with symmetric MACs (any recipient who can verify can also forge). Solutions include:

• Using digital signatures (expensive).
• TESLA (Timed Efficient Stream Loss-tolerant Authentication): the source uses a one-way hash chain to release delayed MAC keys, providing computationally efficient broadcast authentication with a small time delay.

---

Summary

CS 758 provides the theoretical foundation for understanding cryptographic protocols in the multiuser network context. The key themes are:

1. Formal security models: attack model + adversarial goal + security level. Every security claim must be precise.
2. Provable security: reductions from breaking a scheme to solving a hard mathematical problem — factoring, discrete log, CDH, DDH.
3. Identification: the Schnorr scheme provides an efficient, provably secure zero-knowledge proof of knowledge of a discrete logarithm, with security reduction of expected complexity \(O(1/\varepsilon)\).
4. Key management: the Blom scheme gives unconditional security against coalitions of up to \(k\) users; Diffie–Hellman-based schemes reduce to CDH/DDH. Kerberos and STS illustrate the gap between informal and formal security.
5. Multicast security: secret sharing (Shamir), key distribution patterns, broadcast encryption, and tracing schemes address the one-to-many setting with revocation and copyright protection.
6. Zero-knowledge: honest-verifier ZK is achieved when simulated transcripts are indistinguishable from real transcripts, ensuring the protocol reveals nothing about private values.