Есть ли преимущество в использовании $\bmod q$ над наивным методом (без использования модуля)? Если да, то это безопасность, вычислительная сложность или что-то еще?
Да; делать вещи $\bmod q$ имеет практическое преимущество в том, что акции имеют ограниченную длину; расчет доли в $\mathbb{Z}$ потенциально может заставить нас отправлять довольно длинные значения (поскольку значения там не имеют верхней границы).
Однако есть и проблемы с безопасностью:
раскрытие долей в $\mathbb{Z}$ утечки информации; например, предположим, что кто-то знает долю $(х, у)$ за $х=2$ что соответствует секрету $z$. То есть ему присваивается значение $y = a_n2^n + a_{n-1} 2^{n-1} + ... + a_12^1 + z$. Теперь все непостоянные члены четны; следовательно, если они увидят, что $у$ странно, значит $z$ также должен быть нечетным; то есть мы только что слили lsbit. Расширение этого наблюдения показывает, что доля $(х, у)$ раскрывает ценность $z \bмод х$. Аналогичное наблюдение показывает, что две доли $(х_0, у_0)$, $(х_1, у_1)$ также показывает $z \bmod x_0 - x_1$. Это отличается от стандартного Shamir Secret Sharing, в котором такой утечки нет.
Шамир предполагает, что секретные коэффициенты $a_n, a_{n-1}, ..., a_1$ выбираются равномерно. Однако оказывается невозможным равномерно случайным образом выбрать из множества размера $\алеф_0$ (которым является множество целых чисел), то есть любой метод отбора обязательно должен быть необъективным. И, в зависимости от распределения, эта предвзятость также приведет к утечке дополнительной информации.
Кстати: Shamir Secret Sharing не обязательно выполняется по модулю большого простого числа; его можно реализовать над любым конечным полем. На практике мы часто используем даже характеристические поля, такие как $GF(2^8)$ или же $GF(2^{128})$; безопасность такая же, но у нее есть практическое преимущество, заключающееся в том, что все умещается в целое число байтов.
