Batch Public Key Cryptosystem with batch multi-exponentiation

• We propose a Basic Batch Multi-exponentiation algorithm and a Simultaneous Batch Multi-exponentiation algorithm.
• We propose batch public-key encryption and decryption.
• We conduct extensive experiments on the proposal.

A Public Key Cryptosystem (PKC) is a fundamental tool to protect data security. Most PKC schemes involve complicated operations, e.g., modular exponentiations, which are expensive for cloud environment where enormous data are collected from capability-limited devices, e.g., wireless sensors, mobile phones and tablets. To address this problem, this paper investigate how to reduce the laborious computations of a large number of exponentiations in public key encryption and decryption systems. Firstly, we propose algorithms to speed up batch multi-exponentiation in different configurations. Our algorithms improve the existing multi-exponentiation and batch single-base exponentiations by allowing a large number of multi-base exponentiations to be processed in batch. Secondly, we build a batch PKC scheme from the famous Cramer–Shoup cryptosystem by allowing batch encryption and batch decryption. For batch encryption, we exploit our proposed batch multi-exponentiation approach so that multiple messages can be encrypted in batch to reduce the computation overhead; and for batch decryption, we further incorporate techniques derived from batch signature verification so that the received ciphertexts can be decrypted in batch. We conduct thorough theoretical and experimental performance analysis of the proposed batch cryptosystem. The analyses show that the batch multi-exponentiation algorithms greatly accelerate calculation speed of the Cramer–Shoup system, compared with the naive implementations with existing multi-exponentiation approaches, by more than 40% in encryption and 80% in decryption. We also provide optimal batch size configurations in the case that some ciphertexts are erroneous. This work will help make PKC towards practical applications in the cloud environment.