Paper 2019/955

Structure-Preserving and Re-randomizable RCCA-secure Public Key Encryption and its Applications

Antonio Faonio and Dario Fiore and Javier Herranz and Carla Ràfols

Abstract

Re-randomizable RCCA-secure public key encryption (Rand-RCCA PKE) schemes reconcile the property of re-randomizability of the ciphertexts with the need of security against chosen-ciphertexts attacks. In this paper we give a new construction of a Rand-RCCA PKE scheme that is perfectly re-randomizable. Our construction is structure-preserving, can be instantiated over Type-3 pairing groups, and achieves better computation and communication efficiency than the state of the art perfectly re-randomizable schemes (e.g., Prabhakaran and Rosulek, CRYPTO'07). Next, we revive the Rand-RCCA notion showing new applications where our Rand-RCCA PKE scheme plays a fundamental part: (1) We show how to turn our scheme into a publicly-verifiable Rand-RCCA scheme; (2) We construct a malleable NIZK with a (variant of) simulation soundness that allows for re-randomizability; (3) We propose a new UC-secure Verifiable Mix-Net protocol that is secure in the common reference string model. Thanks to the structure-preserving property, all these applications are efficient. Notably, our Mix-Net protocol is the most efficient universally verifiable Mix-Net (without random oracle) where the CRS is an uniformly random string of size independent of the number of senders. The property is of the essence when such protocols are used in large scale.

Note: -- We fixed an error in the counting of group elements required for the publicly verifiable version of our scheme pointed out by Patrick Towa Nguenewou in a private communication-- We included a section on UC Auditable Protocols (Appendix E) that was taken from Eprint 2018/864 (now withdrawn)-- We fixed an incorrect remark in the main proof pointed out by Luigi Russo in a private communication