CYSE476 - Signatures and Zero-proof Knowledge

Cryptography Fundamentals: Signatures and Zero-proof Knowledge

• This chapter focuses on the real-world applications of cryptography, specifically centered on Digital Signatures and Zero-knowledge proofs (ZKPs).

• Objectives of this chapter include:     - Understanding Cryptographic signatures and Zero-knowledge proofs.     - Reviewing existing standards for cryptographic signatures.     - Identifying the subtle behaviors of signatures and methods to avoid common pitfalls.

Prerequisites for Chapter 7

• To fully understand the concepts of Signatures and Zero-knowledge proofs, the following background knowledge from previous chapters is required:     - Chapter 2 (Hash Functions): Understanding one-way functions and message digests.     - Chapter 5 (Key Exchanges): Understanding how two parties establish shared secrets.     - Chapter 6 (Asymmetric Encryption): Mastery of public/private key pairs and the mathematical foundations of public-key cryptography.

Comparative Analysis: RSA, Diffie-Hellman, and ECC

• RSA (Rivest–Shamir–Adleman):     - Primary Purpose: Encryption and Digital Signatures.     - Typical Use Cases: TLS certificates, email encryption (PGP), and digital signatures.     - Encryption Support: Yes.     - Digital Signatures: Yes (e.g., RSA signatures).     - Key Exchange: Indirect (can be used to encrypt keys).     - Performance: Slower, particularly with large keys.     - Key Size (Security): Large (typically $2048 \text{--} 4096$ bits).     - Efficiency: Lower; requires more CPU and bandwidth.     - Security Basis: Integer factorization problem.     - Common Variants: RSA-OAEP, RSA-PSS.     - Adoption Trend: Widely used but slowly declining in favor of modern standards.

• Diffie–Hellman (DH):     - Primary Purpose: Key Exchange (establishing a shared secret).     - Typical Use Cases: Secure key agreement in TLS and VPNs.     - Encryption Support: No (not used for encryption itself).     - Digital Signatures: No.     - Key Exchange: Core purpose of the algorithm.     - Performance: Moderate.     - Key Size (Security): Large (typically $2048+$ bits).     - Efficiency: Moderate.     - Security Basis: Discrete logarithm problem.     - Common Variants: DH, Ephemeral DH (DHE).     - Adoption Trend: Widely used specifically for key exchange.

• Elliptic Curve Cryptography (ECC):     - Primary Purpose: Encryption, Signatures, and Key Exchange.     - Typical Use Cases: Modern TLS, mobile security, and cryptocurrencies.     - Encryption Support: Yes (via ECIES).     - Digital Signatures: Yes (e.g., ECDSA).     - Key Exchange: Yes (ECDH).     - Performance: Faster with smaller keys.     - Key Size (Security): Small (e.g., a $256$-bit ECC key is approximately equivalent to a $3072$-bit RSA key).     - Efficiency: High; well-suited for constrained devices.     - Security Basis: Elliptic curve discrete logarithm problem.     - Common Variants: ECDH, ECDSA.     - Adoption Trend: Increasingly preferred; considered the modern standard.

Fundamental Concepts of Digital Signatures

• Definition: Cryptographic signatures function similarly to physical/real-life signatures.

• Intuition and Primitives:     - Exclusivity: Only the owner of the signature can use it to sign arbitrary messages.     - Verifiability: Anyone can verify the signature on a specific message.

• Signature Scheme Algorithms: A standard scheme involves three distinct algorithms:     - Key Pair Generation Algorithm: Used by the signer to create a new private key and public key pair. The public key is intended for general distribution.     - Signing Algorithm: Takes the private key (signing key) and a message as input to produce a unique signature.     - Verifying Algorithm: Takes the public key (verifying key), the message, and the signature as input. It returns a success (true) or error (false) result.

• Interface and Workflow:     - A key pair is generated using a security parameter and sources of randomness.     - Private Key: Used by the signer to sign the message.     - Public Key: Used by the verifier to validate the signature over a message.     - Security Guarantee: It is computationally impossible to forge a signature that verifies against a public key without access to the associated private key.

Security Properties and Applications

• Authentication and Integrity: Signatures are utilized for two primary security goals:     - Origin: Confirms the message originated from the specific owner of the private key (non-repudiation).     - Integrity: Ensures that if anyone modifies the message after it is signed, the signature becomes void.

• Signatures vs. Message Authentication Codes (MACs):     - While both provide integrity and origin authentication, signatures allow for asymmetrical authentication.     - Unlike MACs, a participant can verify a signature without possessing the private/signing key.

• Coding Example (Python):     - Using the pyca/cryptography library (https://cryptography.io) with the Ed25519 signing algorithm:         - private_key = Ed25519PrivateKey.generate(): Generates the private key.         - public_key = private_key.public_key(): Derives the public key.         - signature = private_key.sign(message): Signs a byte string message.         - public_key.verify(signature, message): Verifies the integrity of the message and its origin. This raises an InvalidSignature exception if the check fails.

Authenticated Key Exchanges and PKI

• Authenticated Key Exchange: Signatures are critical to prevent impersonation in key exchanges.     - One-sided Authentication: Alice is authenticated (cannot be impersonated), but Bob can still be impersonated.     - Mutually-authenticated Key Exchange: Both parties sign their respective parts of the key exchange, ensuring neither can be impersonated.

• Public Key Infrastructures (PKI):     - PKIs operate on the principle of transitivity of trust, which allows trust to scale exponentially.     - If a user trusts an authority and its verifying key, and that authority signs a message stating "the public key of Charles is 3848…", the user can trust that mapping.

• Web PKI Application:     - Browsers come pre-installed ("baked-in") with verifying keys for various Certificate Authorities (CAs).     - These authorities sign the public keys of thousands of websites.     - To obtain a signature, websites must prove domain ownership to the authority.     - Modern browsers trust many different authorities simultaneously to perform this function.

Technical RSA Standards

• RSA Signing Logic: Signing with RSA is mathematically the inverse of RSA encryption.     - To Sign: Encrypt the message with the private key to produce a signature (a random element in the group).     - To Verify: Decrypt the signature with the public key. The signature is valid if the output matches the original message.

• RSA Mathematical Definition:     - Private key: exponent $d$.     - Public key: exponent $e$ and modulus $N$.     - Signing Formulation: $signature = message^d \pmod N$     - Verification Formulation: Check if $signature^e \pmod N = message$

• RSA-PSS (Probabilistic Signature Scheme):     - Standardized in PKCS#1 v2.1, including a proof of security.     - Mechanism:         1. Encode the message using the PSS encoding algorithm (similar to OAEP).         2. Sign the resulting encoded message using standard RSA.

• RSA-FDH (Full Domain Hash):     - Hashes a message $m$ and then signs the digest by interpreting it as a number.     - Formula: $Mod \, N = H(m)$, where $H$ is a hash function.

Zero-Knowledge Proofs (ZKPs)

• Definition: A means by which a prover (Peggy) convinces a verifier (Victor) that a statement is true without revealing any sensitive information (the "witness") to the verifier.

• Proof of Knowledge vs. ZKP:     - In a standard proof of knowledge, Peggy might just send the value $x$ (the witness) to Victor.     - In a ZKP, Peggy proves she knows $x$ given $Y = g^x$ (where $g$ is a generator) without Victor ever learning what $x$ is.

• Schnorr Identification Protocol (Interactive ZKP):     - This protocol allows Alice to prove she knows $x$ without revealing it, developed through incremental complexity to ensure security.     - Conceptual Progression:         - Attempt 1 (Algebraic Hiding): Peggy adds randomness $k$ to the witness: $s = k + x$. Victor checks $g^s = g^{(k+x)}$ against $Y \times g^k = g^x \times g^k$.         - The Security Flaw: Victor can recover the witness via $x = s - k$.         - Attempt 2 (Hiding the Randomness): Peggy hides $k$ in the exponent: $R = g^k$. Victor checks $g^s = Y \times R$.         - The Soundness Issue: Peggy can cheat by picking $s$ first and then calculating $R = g^s \times Y^{(-1)}$.

• The Interactive Schnorr Protocol Solution:     1. Commitment: Peggy commits to a random value $k$ by sending $R = g^k$.     2. Challenge: Victor receives the commitment and sends a random value $c$ (the challenge).     3. Proof: Peggy computes her hidden commitment: $s = k + c \times x$.     - This interaction forces Peggy to compute $s$ based on $k$, preventing the inversion cheat.

Edwards-curve Digital Signature Algorithm (EdDSA)

• Operation: EdDSA generates a secret key used to derive both the actual signing key and a "nonce key."

• Generating the Nonce: EdDSA is deterministic; it generates the nonce by hashing the nonce key with the message.

• Signing Steps:     1. Compute nonce $k = HASH(\text{nonce key} \, || \, \text{message})$.     2. Compute commitment $R = g^k$.     3. Compute challenge $c = HASH(\text{commitment} \, || \, \text{public key } Y \, || \, \text{message})$.     4. Compute proof $S = k + c \times \text{signing key}$.     5. The resulting signature is the pair $(R, S)$.

• Verification Steps:     - Compute $g^S$ and $R \times Y^c$.     - Validity is confirmed if $g^S = R \times Y^c$.

Summary of Principles

• Digital Signatures: Cryptographically-backed counterparts to physical signatures; they are unforgeable without the private key.

• Trust Scaling: Signatures enable origin authentication and transitive trust.

• Nature of ZKPs: Protocols that allow proving knowledge of a witness without revealing the witness itself.

• Non-interactivity: Signatures can be categorized as non-interactive zero-knowledge proofs because the verifier does not need to be online during the initial signing process.

Questions & Discussion

• The lecture concludes by opening the floor to questions regarding the mechanics of signatures, the logic of ZKPs, or the implementation of standards like EdDSA and RSA-PSS.