Token Open Secure and Practical NTRU-based Updatable Encryption

Abstract Updatable encryption (UE) is suitable for key rotation and ciphertexts update in the cloud storage environment. A new security model for UE named Token Open security model is presented recently, which is closer to the real attack scenario. And the existing post-quantum secure UE schemes are all based on the LWE assumption without engineering implementation. In this paper, we improve the recently presented security model, which allows the adversary to corrupt all update tokens and keys of the past epochs. We show that our new model reflects the characteristics of UE. Then we construct the first UE scheme based on NTRU, named NTRU-UE. Our new scheme uses the key-switching technique to achieve backward-leak uni-directional key update and uni-directional ciphertext update and uses the ciphertext-masking technique to achieve rand-update. We show that the new scheme is secure under our new model. In addition, we accomplish the software implementation of NTRU-UE and the experiment results show that the scheme meets the practical requirements.