A New Combiner for Key Encapsulation Mechanisms

Goichiro HANAOKA  Takahiro MATSUDA  Jacob C. N. SCHULDT  

IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences   Vol.E102-A   No.12   pp.1668-1675
Publication Date: 2019/12/01
Online ISSN: 1745-1337
DOI: 10.1587/transfun.E102.A.1668
Type of Manuscript: Special Section PAPER (Special Section on Information Theory and Its Applications)
Category: Cryptography
encryption,  key encapsulation mechanisms,  combiners,  

Full Text: PDF>>
Buy this Article

Key encapsulation mechanism (KEM) combiners, recently formalized by Giacon, Heuer, and Poettering (PKC'18), enable hedging against insecure KEMs or weak parameter choices by combining ingredient KEMs into a single KEM that remains secure assuming just one of the underlying ingredient KEMs is secure. This seems particularly relevant when considering quantum-resistant KEMs which are often based on arguably less well-understood hardness assumptions and parameter choices. We propose a new simple KEM combiner based on a one-time secure message authentication code (MAC) and two-time correlated input secure hash. Instantiating the correlated input secure hash with a t-wise independent hash for an appropriate value of t, yields a KEM combiner based on a strictly weaker additional primitive than the standard model construction of Giaon et al. and furthermore removes the need to do n full passes over the encapsulation, where n is the number of ingredient KEMs, which Giacon et al. highlight as a disadvantage of their scheme. However, unlike Giacon et al., our construction requires the public key of the combined KEM to include a hash key, and furthermore requires a MAC tag to be added to the encapsulation of the combined KEM.