Analysis of (U,U+V)-Code Problem with Gramian Over Binary and Ternary Fields
摘要
Debris-Alazard, Sendrier, and Tillich proposed SURF, which is a code-based signature scheme and enjoys efficient signature generation and verification (eprint in 2017). The security of this scheme is based on two problems: one is DOOM (Decoding One Out of Many), and the other is the plain (U,U+V)-code problem(U,U+V)-code problem over \(\mathbb {F}_2\) . There are many studies on the former one but few studies on the latter one. Later the security of SURF was broken because the hardness of the plain (U,U+V)-code problem does not hold with considering a notion of the hull. Then Debris-Alazard et al. proposed Wave as a successor of SURF, which is known as one of the most promising quantum-resistant signature schemes (ASIACRYPT 2019). Wave is based on similar problems used in SURF. Wave uses DOOM and the normalized generalized (U,U+V)-code problem over \(\mathbb {F}_3\) . In this paper, we utilize a notion of the GramianGramian (the determinant of the Gram matrices) of public keys and analyze the plain (U,U+V)-code problem over \(\mathbb {F}_2\) . For this purpose, we compute the asymptotic probability distribution of Gramians of random matrices. Furthermore, we also show a way to analyze the normalized generalized (U,U+V)-code problem over \(\mathbb {F}_2\) . Finally, we apply our analysis to the normalized generalized (U,U+V)-code problem over \(\mathbb {F}_3\) in a special case. By our analysis with Gramian, SURF is completely broken, however, Wave is not directly threatened.