Решение $\mathsf{SVP}_{\gamma}$ в худшем случае

Что значит решить $\mathsf{СВП}_{\gamma}$ в худшем случае?

Означает ли это, что задача разрешима для любой выбранной нами решетки?

Решение $\text{СВП}$ в худшем случае означает решение «самого сложного» экземпляра $\text{СВП}$. Это не то, что мы хотим для криптографии, поскольку мы хотим, чтобы проблемы было трудно решить на средний (средний случай). Фундаментальные проблемы, такие как $\текст{СИС}$ и $\текст{LWE}$ - это проблемы среднего случая, зависящие от сложности проблем наихудшего случая, таких как $\text{СВП}$, т.е. если $\text{СВП}$ тяжело в худшем случае тогда $\text{LWE/SIS}$ в среднем тяжелые.

Рекомендую прочитать «М. Аджитай. Генерация жестких экземпляров задач с решеткой» для получения дополнительной информации об этом.

$i_{1} = i_{n+1}$ решать

$o' = O_{K_{1}}(i_{1}, s_{1})$