Provably Secure Private-Keyless Encryption on Lattice

To tackle the cumbersome issue of private key management, the public-key encryption system that operates without user private keys, referred to as Private-KeyLess Encryption (PKLE), substitutes traditional user private keys with one-time decryption credentials. This substitution streamlines intricate management processes such as private key updates and revocations, while also eliminating the costs associated with users securely storing their private keys. Such a private-keyless mechanism has emerged as one of the effective solutions to the aforementioned problem. Building on this, this paper introduces the concept, scheme, and security requirements of PKLE within the framework of ideal lattices. Firstly, this paper formulates the definition of PKLE and proposes a construction method for verifiable credentials. Such credentials serve as "one-time decryption keys" issued by a trusted third party upon verification of the user's identity. They not only reduce the costs associated with private key storage and simplify private key management processes but also support real-time decisions regarding users' data access requirements. Secondly, a ciphertext refreshing mechanism is introduced to establish a correspondence between the verifiable credential and the refreshed ciphertext, where the ciphertext is generated at the time of credential issuance. This mechanism enables the direct conversion of initial ciphertext parameters into refreshed ciphertext corresponding to arbitrary time point, with only partial ciphertext requiring refreshment. As a result, it reduces the computational overhead associated with ciphertext refreshing. Additionally, this paper formulates the security requirements for the PKLE scheme, involving unforgeability of credentials and refreshed ciphertexts under chosen-time attacks, timeliness security, and semantic security. The interrelationships among these security requirements are also elaborated. Finally, leveraging the hardness of the Ring-Small Integer Solution (R-SIS) and Learning With Errors (R-LWE) problems, an instantiation analysis of the PKLE scheme over ideal lattices is conducted in the standard model with the aid of the R-SIS oracle. Security proofs demonstrate that the presented scheme satisfies the unforgeability of credentials and refreshed ciphertexts, timeliness security, and semantic security as required.