Average-Case Vs Worst-Case Complexity: Implications For Modern Cryptography

In algorithm analysis, the complexity of an algorithm refers to the amount of computational resources required for the algorithm to run as a function of the size of its input. Two important measures of complexity are average-case complexity and worst-case complexity.

Average-case complexity analyzes the expected running time of an algorithm over all possible inputs of a given size. It calculates the arithmetic mean, or average, running time taken over all inputs. Average-case complexity gives insight into how fast an algorithm will likely run in practice.

In contrast, worst-case complexity focuses on the maximum running time of an algorithm taken over all possible inputs of a given size. It identifies the input that causes the algorithm to have its longest running time. Worst-case analysis assures that an algorithm will never exceed a known upper bound.

Defining Average-Case and Worst-Case Complexity for Algorithms

For a given algorithm ALG that takes an input x of length n, its average-case complexity AC(n) and worst-case complexity WC(n) can be formally defined as:

• AC(n) = The expected running time of ALG summed over all possible inputs x of length n, divided by the total number of possible inputs of length n.
• WC(n) = The maximum running time of ALG over all possible inputs x of length n.

For example, consider a basic algorithm that searches through an unordered list of n elements to find a target value. Its worst-case complexity would be O(n) since, in the worst case, it may have to search the entire list before finding the value. Its average-case complexity would be O(n/2) since on average it will have to search about half the list.

The precise average-case complexity considers the actual distribution of all possible inputs. However, it is often estimated or modeled by making assumptions about the input distribution.

Implications for Cryptographic Security Proofs

In cryptography, security proofs analyze the difficulty for attackers to break the encryption scheme. These proofs typically rely on worst-case complexity where algorithms are proven secure based on hardness assumptions in the worst case.

However, average-case complexity may differ significantly from worst-case. There could exist inputs that are weak in the average case even if worst-case inputs are hard. This makes cryptosystems with only worst-case security proofs potentially vulnerable.

Therefore, modern cryptographic constructions aim for security proofs based on average-case hardness assumptions. Proving security reliance on assumptions that random instances drawn from some distribution are computationally difficult on average for all efficient adversaries.

Techniques like lattice-based cryptography now have security reductions relying on the infeasibility of problems such as finding short vectors in random lattices for the average case. Compared to relying solely on worst-case lattice assumptions which have faced quantum algorithm advancements.

Average-Case Hardness Assumptions in Modern Cryptography

Some primary average-case complexity assumptions that feature in modern cryptography security proofs include:

• Random oracle model – Assumes existence of a theoretical random oracle, allowing reduction of average-case complexity to worst-case complexity.
• Discrete log assumption – Finding discrete logarithms in groups chosen randomly from some distribution is difficult on average.
• RSA assumption – Factoring randomly chosen large integers is computationally infeasible on average.
• Learning with errors – Learning noisy linear equations mod 2 with uniformly random errors is average-case hard.

These assumptions facilitate proofs that reduce breaking cryptography schemes to infeasibly solving mathematical problems for the average case. This contrasts relying solely on worst-case complexity assumptions which can face gradual cryptanalysis advances.

Case Study: RSA Encryption Scheme

RSA is a widely used public-key encryption scheme credited with enabling ecommerce by facilitating secure data transmission. Its security relies on the difficulty of factoring large composite integers generated from randomly selected prime numbers:

1. Choose two random large prime numbers p and q.
2. Compute modulus n = p * q.
3. Select encryption key e such that e is coprime to (p-1)*(q-1).
4. Determine decryption key d such that d*e = 1 mod (p-1)*(q-1).
5. The public key is (n, e) and private key is (n, d).

A message m encrypted as c = m^e mod n can only be decrypted by computing m = c^d mod n using the private key. RSA derives its presumed security from the premise that for large randomly generated n, factoring n is computational infeasible for all efficient algorithms, implying the hardness of computing d from e and n.

Thus, RSA relies on an average-case hardness assumption – that factoring random integers of sufficient length remains difficult on average, rather than relying only on the worst-case complexity of factoring arbitrarily chosen integers.

Estimating Average-Case Hardness in Practice

Actual proofs of average-case complexity often remain elusive, so heuristic measures help estimate security levels in practice:

• Testing computational power – Estimate security model limitations through testingFACTORING algorithms on various computational platforms.
• Cryptanalysis progress – Security margin tied to lack of cryptographic advances that sufficiently fast FACTORING for the average case.
• Comparative analysis – Contrast FACTORING complexity improvements against exponential growth in availability of computational resources.

These empirical approaches help approximate average-case difficulty against measurable benchmarks. However, Heuristic security with probabilistic guarantees remains distinct from provable average-case complexity security reductions.

Open Problems in Relating Worst-Case and Average-Case

Relating worst-case and average-case complexity remains an ongoing research endeavor. Open problems include:

• Establishing definitive average-case lower bounds from worst-case complexity.
• Modeling average-case complexity for broader problem distributions without relying on unproven assumptions.
• Connecting random self-reducibility to average-case hardness, similar to deterministic worst-case reductions.
• Expanding properties like Smoothed Analysis to enable more refined average-case analysis.

Addressing these open problems can enable security proofs firmly grounded in average-case complexity, ensuring cryptography schemes resistant against inputs weak on average, without relying solely on worst-case assumptions.