2024/01/02 by Somnath Panja, Setareh Sharifian, Panja, Somnath +5
Computer Science · Mathematics · #Bounded function #Ciphertext #Complexity and Algorithms in Graphs #Computer network #Computer science #Computer security #Construct (python library) #Cryptographic Implementations and Security #Cryptography and Data Security #Cryptography and Security (cs.CR) #Encryption #FOS: Computer and information sciences #Key (lock) #Key encapsulation #Learning with errors #Mathematics #Public-key cryptography #Randomness #Symmetric-key algorithm #Theoretical computer science
paper · pdf · doi:10.48550/arxiv.2401.00983
openalex publication_date 2024/01/02 · openalex created_date 2024/01/04 · openalex updated_date 2026/07/28
A hybrid encryption (HE) system is an efficient public key encryption system for arbitrarily long messages. An HE system consists of a public key component called key encapsulation mechanism (KEM), and a symmetric key component called data encapsulation mechanism (DEM). The HE encryption algorithm uses a KEM generated key k to encapsulate the message using DEM, and send the ciphertext together with the encapsulaton of k, to the decryptor who decapsulates k and uses it to decapsulate the message using the corresponding KEM and DEM components. The KEM/DEM composition theorem proves that if KEM and DEM satisfy well-defined security notions, then HE will be secure with well defined security. We introduce HE in correlated randomness model where the encryption and decryption algorithms have samples of correlated random variables that are partially leaked to the adversary. Security of the new KEM/DEM paradigm is defined against computationally unbounded or polynomially bounded adversaries. We define iKEM and cKEM with respective information theoretic computational security, and prove a composition theorem for them and a computationally secure DEM, resulting in secure HEs with proved computational security (CPA and CCA) and without any computational assumption. We construct two iKEMs that provably satisfy the required security notions of the composition theorem. The iKEMs are used to construct two efficient quantum-resistant HEs when used with an AES based DEM. We also define and construct combiners with proved security that combine the new KEM/DEM paradigm of HE with the traditional public key based paradigm of HE.