Information-theoretic Key Encapsulation and its Applications. (arXiv:2102.02243v2 [cs.CR] UPDATED)

A hybrid encryption scheme is a public-key encryption system that consists of
a public-key part called the key encapsulation mechanism (KEM), and a
(symmetric) secret-key part called data encapsulation mechanism (DEM): the
public-key part is used to generate a shared secret key between two parties,
and the symmetric key part is used to encrypt the message using the generated
key. Hybrid encryption schemes are widely used for secure communication over
the Internet. In this paper, we initiate the study of hybrid encryption in
preprocessing model which assumes access to initial correlated variables by all
parties (including the eavesdropper). We define information-theoretic KEM
(iKEM) that, together with a (computationally) secure DEM, results in a hybrid
encryption scheme in preprocessing model. We define the security of each
building block, and prove a composition theorem that guarantees (computational)
qe-chosen plaintext (CPA) security of the hybrid encryption system if the iKEM
and the DEM satisfy qe-chosen encapculation attack and one-time security,
respectively. We show that iKEM can be realized by a one-way SKA (OW-SKA)
protocol with a revised security definition. Using an OW-SKA that satisfies
this revised definition of security effectively allows the secret key that is
generated by the OW-SKA to be used with a one-time symmetric key encryption
system such as XORing a pseudorandom string with the message, and provide
qe-CPA security for the hybrid encryption system.We discuss our results and
directions for future work.