Provably secure private-keyless encryption on ideal lattices

Private-keyless encryption (PKLE) addresses the cumbersome challenge of private key management by replacing traditional user private keys with one-time decryption credentials. This approach streamlines complex management processes, such as private key updates and revocations while eliminating the cost and burden of secure key storage for users. Building on this paradigm, this paper introduces the concept, scheme, and security requirements for a PKLE system constructed over ideal lattice. First, we define PKLE and propose a construction method for verifiable credentials. These credentials function as “one-time decryption keys” issued by a trusted third party (the “credential issuance center”) only after the user’s identity is verified. This model simplifies private key management, reduces storage costs, and enables real-time, dynamic decisions on user data access requirements. Second, we introduce a ciphertext-refreshing mechanism that establishes a temporal correspondence between a credential and ciphertext. This mechanism can generate a refreshed ciphertext for any arbitrary time point directly from the initial ciphertext parameters, requiring only partial refreshment of the ciphertext data. This partial-refresh approach significantly reduces the computational overhead of ciphertext refreshing. We also formulate the necessary security requirements for this PKLE scheme—including unforgeability of credentials and refreshed ciphertexts under chosen-time attacks, timeliness security, and semantic security—and elaborate on their interrelationships. A concrete instantiation of this scheme is then constructed over ideal lattices, leveraging the hardness of the ring-small integer solution (R-SIS) and ring-learning with errors (R-LWE) problems. In this construction, the credential is a short preimage vector sampled from a specified dual lattice using the center’s private key and a time-varying parameter. By embedding this parameter into the sampling coset, the credential’s validity is strictly confined to its designated time slot. Concurrently, the ciphertext-refreshing mechanism re-encapsulates the initial ciphertext based on the R-LWE problem. This binds the refreshed ciphertext to the same time-varying parameter, ensuring it can only be decrypted by the corresponding time-bound credential. Finally, we provide security proofs in the standard model, using an R-SIS oracle, demonstrating that our instantiation satisfies all required security properties: unforgeability of credentials and refreshed ciphertexts, timeliness, and semantic security. A complexity and performance analysis confirms that the proposed PKLE scheme eliminates user-side key-storage overhead and simplifies key management by eliminating the need for periodic updates or revocations. Therefore, the proposed scheme is highly suitable for scenarios requiring dynamic access control for sensitive data. Moreover, its support for a partial ciphertext refresh, requiring only a single ring multiplication, significantly reduces the computational cost of ciphertext updates.