Natural sd-RCCA Secure Public-key Encryptions from Hybrid Paradigms

Yuan Chen (Xidian University, P.R. China)

Qingkuan Dong (Xidian University, P.R. China)

Yannan Li (University of Wollongong, Australia)

Qiqi Lai (Florida Atlantic University, USA)

Zhedong Wang (Florida Atlantic University, USA)

Abstract: The existence of natural public-key encryption (PKE) schemes satisfying secretly detectable replayable CCA (sd-RCCA) security is left as open. By introducing probabilistic message authentication codes (MACs) into popular KEM plus DEM paradigms, several instances of such schemes are presented in this paper. It is known that the encrypt-then-authenticate paradigm gives an RCCA secure DEM when the underlying MAC is regular (but not strong) secure, where forgeries for old messages might be possible. By further requiring that the validity of such forgeries can be verified only secretly, sd-RCCA secure DEMs is obtained. Combining such DEMs with CCA secure KEMs gives sd-RCCA secure hybrid PKEs. We first formalize the related notions and this paradigm, and also other variants of KEM plus DEM hybrid paradigm since MACs are commonly used in them. Then we show natural examples of desired probabilistic MACs under the standard DDH assumption, and find appropriate KEMs to match the message space for those MACs and then obtain natural instances of sd-RCCA secure hybrid PKEs.

Keywords: hybrid encryption, probabilistic MAC, public-key encryption, sd-RCCA security

Categories: E.3, K.6.5