A New Key Encapsulation Combiner
Takahiro Matsuda, Jacob C. N. Schuldt · 2018
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 Giacon 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.