Если они ведут себя как случайные оракулы, то они обеспечивают безопасность, соизмеримую с размером пространства изображения, которое $2^\омега\бином п\омега$ (обратите внимание, что есть $\омега$ ненулевые записи, каждая из которых может быть плюс или минус один). Таким образом, если безопасность скомпрометирована обнаружением коллизии в $Ч$ это должно потребовать $O(2^{\omega/2}\sqrt{\binom n\omega})$ оценки $Ч$ найти. Для любого заданного уровня безопасности можно найти соответствующие значения $n$ и $\омега$ для которых требуемая работа превышает уровень безопасности.
Самый простой способ практически построить такой $Ч$ заключается в адаптации обычного $ч$-битная хэш-функция, которая, как считается, ведет себя как случайный оракул. Используйте это, чтобы сгенерировать универсальное значение между 0 и $V:=2^\omega\binom n\omega$ (например, обрабатывая хеш-выход как $ч$-битное целое; если это значение меньше $2^ч\мод V$, добавьте 1 к входным данным и выполните итерацию, иначе уменьшите значение по модулю $В$). Теперь разделите значение $v$ на два значения $c:=v/2^\omega$ и $b:=v\mod{2^\omega}$ (Обратите внимание, что $b$ и $с$ будет независимым и равномерно распределенным по модулю $2^\омега$ и $\бином п\омега$ соответственно). Теперь используйте $с$ и метод этот ответ выбрать набор из $\омега$ коэффициенты, которые будут ненулевыми и будут использовать биты $b$ для выбора между коэффициентами плюс и минус 1.
