KEM / Digital Signature

Key Encapsulation Mechanism

A Key Encapsulation Mechanism (KEM) is a cryptographic method used to securely transmit a secret key from a sender to a receiver. Here are the key points:

• Definition: A KEM is a public-key cryptosystem that allows a sender to generate a short secret key and transmit it securely, even in the presence of eavesdroppers.

• Components: It consists of three algorithms: Key Generation (Gen), Encapsulation (Encap), and Decapsulation (Decap).

• Usage: The sender uses the receiver’s public key to generate and encapsulate a secret key. The receiver then uses their private key to decapsulate and retrieve the secret key.

• Security Goal: To prevent anyone without the private key from recovering any information about the secret key, ensuring secure communication

• IND-CPA Security: This stands for Indistinguishability under Chosen Plaintext Attack. It means that an attacker cannot distinguish between the encryptions of two chosen plaintexts, even if they can choose the plaintexts themselves.

• IND-CCA2 Security: This stands for Indistinguishability under Adaptive Chosen Ciphertext Attack. It is a stronger security notion where the attacker can also choose ciphertexts to be decrypted, except for the challenge ciphertext.

KEM example: Kyber is a Key Encapsulation Mechanism (KEM) based on the Module Learning with Errors (MLWE) problem. Here are the key points about Kyber:

• Design: Kyber is constructed as an IND-CPA-secure Public Key Encryption (PKE) scheme, then boosted to an IND-CCA-secure KEM using a Fujisaki-Okomoto (FO) transform. It uses a cyclotomic power-of-2 ring and a public matrix of polynomials generated from a random string.

• Security: Kyber’s security is grounded in lattice cryptography, with strong theoretical foundations and extensive analysis. It employs a variant of the FO transform to achieve CCA security.

• Performance: Kyber has fast key generation, encapsulation, and decapsulation, making it suitable for various environments. Its public key and ciphertext sizes are manageable for most applications.

• Updates: During the third round, Kyber’s noise parameter was increased for stronger defense, and efficiency improvements were made in key generation and sampling methods.

Digital Signature

A digital signature is a cryptographic technique used to validate the authenticity and integrity of a message, software, or digital document. Here’s a brief overview of how it works:

• Creation: The sender generates a hash (a fixed-size string of characters) of the message or document. This hash is then encrypted with the sender’s private key to create the digital signature.

• Transmission: The original message and the digital signature are sent to the recipient.

• Verification: The recipient decrypts the digital signature using the sender’s public key to retrieve the hash. They also generate a hash of the received message.

• Comparison: The recipient compares the decrypted hash with the generated hash. If they match, the message is verified as authentic and unaltered.

• EUF-CMA Security: This stands for Existential Unforgeability under Chosen Message Attack. It ensures that an attacker cannot forge a valid signature on any new message, even if they can obtain signatures on other messages of their choice.

Digital signature example: FALCON as a digital signature scheme:

• Design: FALCON (Fast Fourier Lattice-based Compact Signatures over NTRU) uses the “hash-and-sign” paradigm. It builds on the GPV framework for constructing hash-and-sign signature schemes from lattice-based trapdoor functions.

• Security: The security of FALCON is based on the hardness of the SIS Problem over NTRU lattices. It has a proof of unforgeability in the Quantum Random Oracle Model (QROM).

• Performance: FALCON has the smallest bandwidth among the third-round digital signature schemes, making it efficient for verification. However, signing is slower, and key generation is significantly slower compared to other schemes.

• Implementation: FALCON requires floating-point arithmetic and complex data structures, making it challenging to implement securely, especially in constrained environments.