Computational Security

Computational security is defined relative to a specific adversarial model and computational hardness assumptions. Common models include:

• Polynomial-time adversaries: The adversary's running time is bounded by a polynomial function of the security parameter.
• Negligible success probability: A function is negligible if it decreases faster than the inverse of any polynomial. A scheme is secure if no polynomial-time adversary can succeed with more than a negligible probability.
• Common hardness assumptions: Security often rests on problems believed to be computationally hard, such as the integer factorization problem, the discrete logarithm problem, or the Learning With Errors (LWE) problem.

The security parameter (denoted λ) is a positive integer that controls the security level of a cryptographic scheme. It directly influences:

• Key sizes: Larger λ typically means longer keys (e.g., 128-bit, 256-bit).
• Computational cost: Operations like encryption/decryption scale with λ.
• Adversarial advantage: Security is proven by showing an adversary's success probability is a negligible function in λ. For example, a scheme with λ=128 aims to require roughly 2^128 operations to break, making attacks infeasible with current and foreseeable technology.

Security is proven via reductionist arguments (also called game-hopping). This technique demonstrates that if an efficient adversary can break the cryptographic scheme (e.g., distinguish encryptions), then that adversary can be used as a subroutine to solve a well-studied computational hard problem (like factoring large integers).

• Proof structure: 'If Problem X is hard, then Scheme Y is secure.'
• Contrapositive: The proof shows that breaking the scheme is at least as hard as solving the underlying problem. This provides a strong, quantifiable foundation for trust in the system.

Computational security analysis operates on two levels:

• Asymptotic Security: Focuses on how security scales as the security parameter λ → ∞. It classifies adversaries as 'efficient' if they run in polynomial time (poly(λ)) and defines success as 'non-negligible.' This is the standard for theoretical proofs.
• Concrete Security: Provides exact, quantitative bounds. Instead of 'negligible,' it states: 'Any adversary running for at most t steps has an advantage of at most ε.' This is crucial for practice, allowing selection of key sizes (e.g., choosing a 3072-bit RSA key for a 128-bit security level).

Security for encryption is often defined via indistinguishability games (e.g., IND-CPA, IND-CCA2). In the IND-CPA (Chosen-Plaintext Attack) game:

1. The adversary receives a public key.
2. The adversary can request encryptions of any messages.
3. The adversary submits two challenge messages (m0, m1).
4. The challenger encrypts one at random (mb) and returns the ciphertext.
5. The adversary must guess which message was encrypted. A scheme is IND-CPA secure if no polynomial-time adversary can guess correctly with probability significantly better than 1/2 (random guessing).

Computational Security provides security based on the assumed computational limits of an adversary. It is practical and efficient, enabling systems with short keys and fast operations (e.g., AES, RSA). The guarantee is conditional on the hardness of a problem.

Information-Theoretic Security (or unconditional security) provides security even against an adversary with unlimited computational power. It relies on probabilistic arguments and information theory (e.g., the one-time pad). The guarantee is absolute but often impractical due to key management requirements (keys must be as long as the message and never reused).

The Advanced Encryption Standard (AES) secures data by using a single, shared secret key for both encryption and decryption. Its security relies on the computational infeasibility of performing a brute-force attack to try all possible keys (e.g., 2^128 for AES-128).

• Use Case: Encrypting data at rest, such as wallet files or database entries.
• Security Assumption: No efficient algorithm exists to recover the plaintext without the key, other than exhaustive search.

Asymmetric cryptography uses a pair of keys: a public key for encryption or verification, and a private key for decryption or signing. Its security is based on computationally hard mathematical problems.

• RSA: Relies on the difficulty of integer factorization (finding prime factors of a large composite number).
• Elliptic Curve Cryptography (ECC): Relies on the difficulty of the elliptic curve discrete logarithm problem (ECDLP), providing equivalent security with smaller key sizes than RSA.
• Use Case: Digital signatures, key exchange, and blockchain address generation.

A cryptographic hash function like SHA-256 produces a fixed-size output (hash) from any input. Computational security here means it is infeasible to:

• Find a preimage (input that hashes to a given output).
• Find a collision (two different inputs with the same hash).
• Use Case: Creating unique transaction IDs, linking blocks in a blockchain (forming the Merkle root), and generating proof-of-work puzzles in Bitcoin mining.

A digital signature scheme allows one party to cryptographically sign a message, proving authenticity and integrity. Verification uses the signer's public key, while forging a signature is computationally infeasible without the private key.

• ECDSA: The Elliptic Curve Digital Signature Algorithm is widely used in Bitcoin and Ethereum.
• Security Guarantee: It is computationally infeasible to create a valid signature without the private key, under the assumption that the ECDLP is hard.
• Use Case: Authorizing blockchain transactions and verifying software updates.

Key Derivation Functions (KDFs) are designed to be computationally expensive (or memory-hard) to derive a cryptographic key from a password or weak secret. They intentionally slow down brute-force attacks.

• PBKDF2: Applies a pseudorandom function (like HMAC) many times.
• Scrypt: Requires large amounts of memory, making hardware acceleration with ASICs more difficult.
• Use Case: Securing user passwords and generating encryption keys from mnemonics (seed phrases) in cryptocurrency wallets.

Zero-Knowledge Proofs allow one party (the prover) to prove to another (the verifier) that a statement is true without revealing any information beyond the validity of the statement itself. Their security is computational: it is infeasible for a cheating prover to construct a convincing proof for a false statement.

• zk-SNARKs: Succinct Non-Interactive Arguments of Knowledge enable private transactions and scalable computation verification.
• Use Case: Privacy-preserving transactions (Zcash), and scaling solutions like zk-Rollups, which batch and prove thousands of transactions off-chain.

The bedrock of computational security is the Probabilistic Polynomial Time (PPT) adversary model. A system is considered secure if no adversary, limited to running algorithms that complete in polynomial time with some randomness, can break it with more than a negligible probability. This is a practical relaxation of information-theoretic security, which requires perfect secrecy against adversaries with unlimited computational power.

Security is defined asymptotically using negligible functions. A function is negligible if it decreases faster than the inverse of any polynomial. For a scheme with security parameter λ (e.g., key length), the adversary's success probability must be a negligible function of λ. This means as λ increases, the chance of breaking the system becomes vanishingly small, making attacks computationally infeasible in practice.

Computational security is inherently non-absolute and time-bound. Its guarantees are contingent on:

• Current computational limits (e.g., no large-scale quantum computers).
• The assumed hardness of mathematical problems (e.g., factoring large integers, solving discrete logs). A breakthrough in algorithms (like Shor's algorithm for quantum computers) or raw computing power can render a once-secure system completely broken. It provides practical security, not eternal proof.

There's a critical gap between theory and practice:

• Asymptotic Security: Proves security "for sufficiently large λ." It doesn't specify what λ is safe today.
• Concrete Security: Provides explicit bounds. For example, "breaking this 128-bit key requires 2¹²⁸ operations." Most real-world system design and parameter selection (like choosing AES-256) rely on interpreting asymptotic proofs into concrete security parameters based on the best-known attacks.

Many efficient cryptographic schemes (e.g., RSA-PSS, RSA-OAEP) are proven secure in the Random Oracle Model (ROM). This is a heuristic where a cryptographic hash function (like SHA-256) is modeled as a perfectly random function. While proofs in the ROM are valuable and schemes are widely used, they are not standard computational security proofs. A real hash function could have weaknesses that break the proof, representing a theoretical limitation of the model.

Computational security analyzes the abstract mathematical algorithm. It does not account for physical implementation vulnerabilities, which are often the real attack vector:

• Timing attacks: Exploiting variations in computation time.
• Power analysis: Deducing keys from power consumption.
• Fault injection: Causing hardware errors to reveal secrets. A system can be computationally secure but practically insecure due to a flawed implementation, highlighting the limitation of viewing security purely through a computational lens.

A stronger security model than computational security. A cryptosystem is information-theoretically secure (or unconditionally secure) if it cannot be broken even by an adversary with unlimited computational power. This is often proven using probability theory. Classic examples include the one-time pad for encryption and Shamir's Secret Sharing. Its guarantees are absolute but often impractical for most real-world systems due to stringent key management requirements.

Computational security is formally defined by specifying an adversarial model (e.g., probabilistic polynomial-time adversary) and a security reduction. The core proof technique shows that breaking the cryptographic scheme's security is at least as hard as solving a well-studied computational hard problem, such as:

• Factoring large integers (RSA)
• Computing discrete logarithms (ECDSA, DSA)
• Solving the Decisional Diffie-Hellman problem If the underlying problem is hard, the scheme is secure.

The mathematical cornerstone of computational security definitions. A function ε(n) is negligible if it approaches zero faster than the inverse of any polynomial as the security parameter n (e.g., key length) grows. Security is defined such that an adversary's advantage in breaking the system is a negligible function of n. This formalizes the idea that successful attacks are so improbable they can be effectively ignored for all practical purposes, even though they are theoretically possible.

The practice of using formal security reductions to prove that a cryptographic construction is computationally secure. A scheme is provably secure if its security can be mathematically reduced to the hardness of a trusted computational problem. This does not guarantee absolute security, but provides strong assurance that no attack exists that is more efficient than solving the underlying hard problem. It is the gold standard for modern cryptographic algorithm design, applied to primitives like AES (in specific modes) and many zero-knowledge proof systems.

A pragmatic model used when a full security reduction to a standard hard problem is not available. The Random Oracle Model (ROM) is a common heuristic where a cryptographic hash function (like SHA-256) is treated as a perfectly random function. Many widely used and analyzed schemes, including RSA-PSS signatures and RSA-OAEP encryption, are proven secure in the ROM. While not as strong as a standard model proof, ROM security provides high confidence when the hash function is well-designed, forming the basis for much of applied cryptography.