Philippine Journal of Science
152 (1): 125-140, February 2023
ISSN 0031 – 7683
Date Received: 23 Aug 2022

Communication Complexities of Leakage-secure PKE
Cryptosystems and Generic Transformations

Alfonso B. Labao* and Henry N. Adorna

Department of Computer Science, University of the Philippines Diliman,
Diliman, Quezon City, Philippines

*Corresponding author: alfonso.labao@upd.edu.ph

[Download]
Labao A, Adorna H. 2023. Communication Complexities of Leakage-secure PKE
Cryptosystems and Generic Transformations. Philipp J Sci 152(1): 125–140.
https://doi.org/10.56899/152.01.09

 

ABSTRACT

In this paper, we present the communication complexity results of several chosen-ciphertext attack (CCA2) secure public key cryptosystems that are resilient to certain classes of secret key leakage attacks. In particular, we discuss the communication complexity trade-off between cryptosystems and generic transformations that rely on the random oracle model and those that are designed under the standard model. For this purpose, we propose a communication complexity measure for public key cryptosystems that equals the total amount of bits involving the receiver’s public key and a ciphertext transmission by the sender. Using this complexity measure, we show that random oracle model-based cryptosystems and transformations are more efficient in terms of communication complexity, albeit relying on the stronger assumption that some cryptographic primitives behave like truly random functions. As corollaries of our results, we also address the problem of establishing communication complexity lower bounds by which leakage-secure communication between two parties can occur, and show that our cryptosystems and generic transformations achieve polynomial lower bounds in communication complexity relative to the security parameter of an adversary.