Analysis of (U,U plus 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 over 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 F-3. In this paper, we utilize a notion of the Gramian (the determinant of the Gram matrices) of public keys and analyze the plain (U,U+V)-code problem over 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 F-2. Finally, we apply our analysis to the normalized generalized (U,U+V)-code problem over F-3. By our analysis with Gramian, SURF is completely broken, however, Wave is not directly threatened.