RCCA Security for KEM+DEM Style Hybrid Encryptions

RCCA security is a weaker notion than CCA security, and has been proven to be sufficient for several cryptographic tasks. This paper adapts RCCA security to the most popular hybrid paradigms, KEM+DEM and Tag-KEM/DEM.

It is open to construct an RCCA-secure scheme more efficient than CCA-secure ones. In the setting of Tag-KEM, we solve this by presenting a natural RCCA-secure RSA-based Tag-KEM scheme, named as RSA-TKEM, which is more efficient than all existing methods for constructing a CCA-secure RSA-based Tag-KEM scheme.

Unfortunately, combining our RSA-TKEM with passive secure one-time pad following Tag-KEM/DEM paradigm yields an RCCA-insecure hybrid encryption. This shows passive security of DEM is not sufficient now, and Tag-KEM/DEM looses its advantage over KEM+DEM. In spite of this and for completeness, we show RCCA secure DEMs are still sufficient to achieve RCCA-secure hybrid encryptions by following Tag-KEM/DEM.

In addition, we show RCCA-secure KEM is sufficient for achieving CCA-secure hybrid encryptions. This is done by introducing a new hybrid paradigm, named as KEM/Tag-DEM, where the ciphertext of KEM is used as a tag for Tag-DEM scheme rather than reversely in Tag-KEM/DEM, so that the security of KEM can be weakened to RCCA one. Tag-DEMs can be constructed as efficiently as DEMs, so RCCA-secure KEMs more efficient than CCA-secure ones become more appealing.