Paper 2020/036
Analysis on AigisEnc: asymmetrical and symmetrical
Yupu Hu, Siyue Dong, and Xingting Dong
Abstract
AigisEnc 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 AigisEnc. But compression must be put into consideration when we discuss decryption failure probability. In other words, when we discuss the CPA security of AigisEnc, 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, AigisEnc designers claim that the CPA security of AigisEnc is approximately equal to that of the symmetrical LWE scheme in the same scale, and the decryption failure probability of AigisEnc is far below that of the symmetrical LWE scheme in the same scale. In this paper, we make a thorough comparison between AigisEnc (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 AigisEnc, 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 optimaloptimal attack” on AigisEnc and the symmetrical LWE scheme in the same scale.
Metadata
 Available format(s)
 Category
 Publickey cryptography
 Publication info
 Preprint. MINOR revision.
 Keywords
 LWEbased cryptosystemprimal attackdual attack
 Contact author(s)

yphu @ mail xidian edu cn
359442088 @ qq com  History
 20200115: received
 Short URL
 https://ia.cr/2020/036
 License

CC BY
BibTeX
@misc{cryptoeprint:2020/036, author = {Yupu Hu and Siyue Dong and Xingting Dong}, title = {Analysis on AigisEnc: asymmetrical and symmetrical}, howpublished = {Cryptology ePrint Archive, Paper 2020/036}, year = {2020}, note = {\url{https://eprint.iacr.org/2020/036}}, url = {https://eprint.iacr.org/2020/036} }