Polynomial-Time Key-Recovery Attacks Against NTRURe Encrypt from ASIACCS'15  

作　　者：LIU Zhen PAN Yanbin ZHENG Jinwei 

机构地区：[1]School of Cyber Science and Technology,Hubei Key Laboratory of Applied Mathematics,Hubei University,Wuhan 430062,China [2]Key Laboratory of Mathematics Mechanization,Academy of Mathematics and Systems Science,Chinese Academy of Sciences,Beijing 100190,China [3]School of Mathematical Sciences,University of Chinese Academy of Sciences,Beijing 100190,China

出　　处：《Journal of Systems Science & Complexity》2024年第3期1308-1325,共18页系统科学与复杂性学报（英文版）

基　　金：supported by National Key Research and Development Program of China under Grant No.2018YFA0704705;the National Natural Science Foundation of China under Grant Nos. 62032009, 12201193;12226006;the Innovation Program for Quantum Science and Technology under Grant No. 2021ZD0302902;the Innovation Group Project of the Natural Science Foundation of Hubei Province of China under Grant No.2023AFA021;the Science and Technology Research Program of Education Department of Hubei Province under Grant No. Q20221008。

摘　　要：In ASIACCS 2015, Nu nez, et al. proposed a proxy re-encryption scheme, named NTRURe Encrypt, 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,NTRURe Encrypt 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 260ciphertexts 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 NTRURe Encrypt 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 NTRURe Encrypt to resist the proposed attacks. As a by-product, the authors also show how to commit broadcast attacks against NTRU 2001 with even dg, which was thought infeasible before.

关 键 词：Broadcast attack key recovery NTRU NTRUReEncrypt 

分 类 号：TN918.4[电子电信—通信与信息系统]