Natural sd-RCCA Secure Public-Key Encryptions

Replayable CCA (RCCA) security is a reasonable relaxation of CCA security for public-key encryptions. Pd-RCCA and sd-RCCA security are two variants of it according to a “replaying” can be detected publicly or secretly. Existing “natural” RCCA schemes satisfy pd-RCCA security, while those satisfying only sd-RCCA security are left as open. We present such schemes via KEM+DEM hybrid paradigm. Sd-RCCA secure DEMs are sufficient for this purpose. It is known that an RCCA secure DEM can be achieved by combining a passive secure DEM with a regular (but not a strong) secure message authentication code (MAC), where forgeries for old messages might be possible. Unfortunately, most practical MACs are deterministic, which makes the two notions equivalent. However, the recently proposed probabilistic MACs activate this paradigm. We formalize the related notions and the paradigm, then show natural examples of regular secure probabilistic MACs under the DDH assumption, based on which natural instances of sd-RCCA secure schemes are given.