LIU Zhen, PAN Yanbin, ZHENG Jinwei
In ASIACCS 2015, Nu$\tilde{\rm n}$ez, et al. proposed a proxy re-encryption scheme, named \NTRUReEnc- \rypt,\ based on NTRU, which allows a proxy to translate ciphertext under the delegator's public key into a re-encrypted ciphertext that can be decrypted correctly by delegatee's private key. Because of the potential resistance to quantum algorithm, high efficiency and various applications in real life, \NTRUReEncrypt\ has drawn lots of attention and its security has been widely discussed and analyzed. In PQCrypto2019, Liu, et al. proposed two key recovery attacks against it. However, their first attack heavily relies on a weaken decryption oracle, and the second attack needs to collect about $2^{60}$ ciphertexts from the same message by theoretical analysis, which makes both of the attacks unrealistic. In this paper, inspired by the broadcast attack against NTRU, the authors find out that for \NTRUReEncrypt \ the delegator and the delegatee can efficiently recover each other's private key in polynomial time without any unrealistic assumptions. In addition, the authors also show how to fix \NTRUReEncrypt\ to resist the proposed attacks. As a by-product, the authors also show how to commit broadcast attacks against NTRU 2001 with even $d_g$, which was thought infeasible before.
