VSH

В криптографии очень гладкая хеш-функция (англ. Very Smooth Hash (VSH)) — n-битная эффективная криптографическая функция хеширования, разработанная в 2005 году Скоттом Котини, Лестрой Арьен и Роном Штайнфельдом. Является устойчивой к коллизиям в предположении большой вычислительной сложности нахождения нетривиального квадратного корня очень гладкого числа по модулю n. ^[1] Под понятием очень гладкой функции подразумевается, что граница гладкости является фиксированной полиномиальной функцией от n. Данный алгоритм хеширования предполагает одиночное умножение на ${\displaystyle \Omega (n)}$ бит сообщения и использует арифметику RSA-типа, что избавляет от необходимости отдельного хранения кода хеш-функции. Поэтому данный алгоритм полезен во встроенных средах, где пространство кода ограничено. Очень гладкая хеш-функция также может быть использована для создания односторонней функции с потайным входом, которая может быть применена в схемах подписи для ускорения проверки и усиления конфиденциальности.

Для VSH основной математической проблемой является устойчивость к коллизиям, которая по сути состоит в извлечении корней по модулю n из очень гладких чисел, называемых очень гладкими корнями (VSSR). В свою очередь, проблема вычисления очень гладкого корня по модулю n тесно связана с факторизацией целых чисел с использованием общего метода решета числового поля.^[2][3]

Для фиксированных постоянных c и n целое число m называется очень гладким числом, если все простые множители m не больше чем (log n)^c. Целое число b является очень гладким квадратичным остатком по модулю n, если наибольшее простой множитель b — не более чем (log n)^c и существует целое x такое что ${\displaystyle b\equiv x^{2}\mod n}$. Целое x называют очень корнем квадратным по модулю  b.

Нас интересуют только корни где x² ≥ n. Так как, если x² < n, то корень может быть легко вычислен, используя поле характеристики 0. Вычисление очень гладкого корня является следующей задачей: пусть n является произведением двух простых чисел примерно одного размера и пусть ${\displaystyle k\leq (\log n)^{c}}$, а ${\displaystyle p_{1}=2,p_{2}=3,p_{3}=5,\dots }$ последовательность простых чисел. По данному n необходимо найти ${\displaystyle x\in \mathbb {Z} _{n}^{*}}$, такое, что ${\displaystyle \textstyle x^{2}\equiv \prod _{i=0}^{k}p_{i}^{e_{i}}}$ и хотя бы один из e₀,…,e_k будет нечетным.

Пусть зафиксированы следующие параметры: ${\displaystyle c=5}$ и ${\displaystyle n=31}$.

Тогда ${\displaystyle m_{1}=35=5\cdot 7}$ очень гладкое число от данных параметров, потому что ${\displaystyle (\log 31)^{5}~{\dot {=}}~7.37}$ больше чем все простые множители ${\displaystyle m_{1}}$. С другой стороны, ${\displaystyle m_{2}=55=5\cdot 11}$ не является очень гладким числом от ${\displaystyle c=5}$ и ${\displaystyle n=31}$.

Целое число ${\displaystyle b_{1}=9}$ является очень гладким квадратичным остатком по модулю ${\displaystyle n}$, потому что это число очень гладкое (от ${\displaystyle c,n}$) и существует ${\displaystyle x_{1}=3}$, такое что ${\displaystyle x_{1}^{2}=b_{1}}$ (mod ${\displaystyle n}$). Это тривиальный квадратный корень, потому что ${\displaystyle 3^{2}\not \geq n}$ и поэтому модуль при возведении в квадрат не учитывается.

Целое число ${\displaystyle b_{2}=15}$ также является квадратичным остатком по модулю ${\displaystyle n}$. Все простые множители меньше чем 7.37, а все квадратные корни по модулю равны ${\displaystyle x_{2}=20}$, так как ${\displaystyle 20^{2}=400\equiv 15}$ (mod ${\displaystyle n}$). Задача VSSR состоит в том, чтобы найти ${\displaystyle x_{2}}$ по данным ${\displaystyle b_{2}}$ и ${\displaystyle n}$. И вычислительно так же сложна, как факторизация ${\displaystyle n}$.

Пусть ${\displaystyle p_{1}=2,p_{2}=3,\ldots }$ последовательность простых чисел. Пусть ${\displaystyle k}$ длина блока, наибольшее целое число, такое, что ${\displaystyle \textstyle \prod _{i=1}^{k}p_{i}<n}$. Пусть ${\displaystyle m}$ есть ${\displaystyle \ell }$-битное сообщение, состоящее из ${\displaystyle (m_{1},\ldots ,m_{\ell })}$, которое должно быть хешировано, причем ${\displaystyle \ell <2^{k}}$.Чтобы вычислить хеш ${\displaystyle m}$^[4]:

1. x₀ = 1
2. Пусть ${\displaystyle L}$ наименьшее целое число, большее или равное ${\displaystyle l/k}$, будет числом блоков. Пусть ${\displaystyle m_{i}=0}$ для ${\displaystyle l<i\leq Lk}$
3. Пусть ${\displaystyle \textstyle \ell =\sum _{i=1}^{k}l_{i}2^{i-1}}$ с ${\displaystyle \ell _{i}\in \{0,1\}}$ — бинарное представление сообщения длины ${\displaystyle \ell }$ и определим ${\displaystyle m_{Lk+i}=\ell _{i}}$ для ${\displaystyle 1\leq i\leq k}$.
4. для каждого j = 0, 1,…, L вычисляем ${\displaystyle x_{j+1}=x_{j}^{2}\prod _{i=1}^{k}p_{i}^{m_{jk+i}}\mod n}$
5. возвращаем x_{L + 1}.

Функция на шаге 4 называется функцией сжатия.

• Не нужно знать заранее длину сообщения.
• Сложность обнаружения коллизий равна сложности нахождения очень гладкого корня, поэтому VSH устойчива к коллизиям. Стойкость к коллизиям единственное доказанное свойство для VSH.^[5][6]
• Функция сжатия не является стойкой к коллизиям. Однако хеш-функция устойчива к коллизиям на основе VSSR-предположения. Следующая версия VSH* использует стойкую к коллизиям функцию сжатия и работает в 5 раз быстрее на коротких сообщениях.^[7]
• VSH мультипликативна:

Пусть x, y, and z — трехбитные строчки равной длины, где z состоит только из нулевых бит и удовлетворяет x AND y = z. Тогда H(z)H(x OR y) ≡ H(x)H(y) (mod n). VSH уступает классической атаке на временную память, которая применяется к мультипликативным и аддитивным хешам.^[8]

Было предложено несколько улучшений, ускорений и более эффективных вариантов VSH^[9]. Ни один из них не меняет основную концепцию функции:

• Кубический VSH (вместо квадратичного).
• VSH с увеличением количества простых чисел.
• VSH с вычисленным произведением простых чисел.
• Быстрый VSH.
• Быстрый VSH с увеличенным числом блоков.
• VSH-DL

VSH-DL - VSH с дискретным логарифмом, у которого нет односторонней функции с потайным входом, его безопасность зависит от сложности нахождения дискретного логарифма по модулю простого числа p.

Very Smooth Number Discrete Logarithm (VSDL) — это дискретный логарифм от некоторого VSN, взятый по модулю некоторого числа n.

Аналогично введенным ранее обозначениям, возьмем ${\displaystyle p_{i}}$ как ${\displaystyle i}$-е простое число. Пусть ${\displaystyle c}$ — фиксированная постоянная и ${\displaystyle p}$, ${\displaystyle q}$ — простые числа, такие, что ${\displaystyle p=2q+1}$ и ${\displaystyle k\leq (\log p)^{c}}$. VSDL-задача: по данному ${\displaystyle p}$ найти целые ${\displaystyle e_{1},...,e_{k}}$, такие, что ${\displaystyle 2^{e_{1}}\equiv \prod _{i=2}^{k}p_{i}^{e_{i}}\mod p}$, где ${\displaystyle |e_{i}|<q}$ для всех ${\displaystyle i=1,...,k}$, причем, хотя бы один из ${\displaystyle e_{1},...,e_{k}}$ ненулевой.

Предположение VSDL состоит в том, что не существует вероятностного полиномиального по времени алгоритма, решающего VSDL. Существует тесная связь между сложностью вычисления VSDL и сложностью вычисления дискретного логарифма по модулю ${\displaystyle p}$.

• Криптографические хеш-функции
• Хеширование

• S.Contini, A.Lestra, R.Steinfield. VSH, an Efficient and Provable Collision-Resistant Hash Function. // Eurocrypt. — 2006. — С. 1—13.
• M.-J.O.Saarinen. Security of VSH in the real world // INDOCRYPT. — 2006.
• Bart Preneel. [https://www.esat.kuleuven.be/cosic/publications/article-1532.pdf The First 30 Years of Cryptographic Hash

Functions and the NIST SHA-3 Competition] // Cryptographers’ Track at the RSA Conference. — 2010. — С. 5. Архивировано 11 августа 2017 года.