Paper 2020/036

Analysis on Aigis-Enc: asymmetrical and symmetrical

Yupu Hu, Siyue Dong, and Xingting Dong

Abstract

Aigis-Enc is an encryption algorithm based on asymmetrical LWE. In this algorithm, the compression process is utilized during both key generation and encryption (which is equivalent to add some LWR noise). Then encapsulation is realized by FO transformation. It is well known that FO transformation is not considered for discussing CPA security. On the other hand, since the security reduction of LWR is hard to proceed, it is not considered for discussing the CPA security of Aigis-Enc. But compression must be put into consideration when we discuss decryption failure probability. In other words, when we discuss the CPA security of Aigis-Enc, the compression and FO transformation are ignored. But when decryption failure probability is discussed, compression should be taken into consideration while FO transformation remains ignored. According to the assumptions above, Aigis-Enc designers claim that the CPA security of Aigis-Enc is approximately equal to that of the symmetrical LWE scheme in the same scale, and the decryption failure probability of Aigis-Enc is far below that of the symmetrical LWE scheme in the same scale. In this paper, we make a thorough comparison between Aigis-Enc (with the recommended parameters) and the symmetrical LWE encryption scheme in the same scale. Our conclusion is as followed: (1) The comparison on CPA security. The former’s is 160.898, and the latter’s is 161.836. (2) The comparison on computation complexity. In key generation phase, the ratio of the former and the latter on sampling amount of distribution \(\left[ {\begin{array}{*{20}{c}} 0&1\\ {\frac{1}{2}}&{\frac{1}{2}} \end{array}} \right]\) is 5:4; In encryption phase, that ratio is 19:14. The other computations remain the same. (3) The comparison on decryption failure probability. The former’s is $2^{-128.699}$, the latter's is $2^{-67.0582}$. The comparison seems to be dramatic. But in fact, we can slightly increase some traffic to keep failure probability unchanged. In other words, by compressing less to keep decryption failure probability unchanged. In specific: we change the parameters \(\left( {{d_1},{d_2},{d_3}} \right)\) from \(\left( {9,9,4} \right)\) to \(\left( {10,10,4} \right)\), which means a large part of the public key remains the same, the small part of the public key changes from 9 bits per entry into 10bits. A large part of the ciphertext changes from 9 bits per entry into 10 bits, the small part of the ciphertext remains the same. As thus, the communication traffic increases less than $\frac{1}{9}$, while the decryption failure probability is lower than $2^{-128.699}$. We generalize those attacks presented by designers of Aigis-Enc, including primal attacks and dual attacks. More detailedly, our attacks are more extensive, simpler, and clearer. With them, we obtain the optimal attacks and “the optimal-optimal attack” on Aigis-Enc and the symmetrical LWE scheme in the same scale.