1
$\begingroup$

The paper "Short, Invertible Elements in Partially Splitting Cyclotomic Rings and Applications to Lattice-Based Zero-Knowledge Proofs" presents a corollary stating that in a polynomial ring $ R_q = \mathbb{Z}_q[X]/(X^n + 1) $ with a specific modulus $ q $, elements with small norm are invertible. My question is whether there exists an efficient algorithm to compute the inverse of such an element, which could be practically applied in the design of cryptographic protocols (similar to computing inverses in the finite field $ \mathbb{Z}_q^* $). ChatGPT told me that the Extended Euclidean Algorithm (EEA) can be used to compute inverses, and its complexity is $ O(n \log n) $. Can it be considered practical?

Thank you in advance for your assistance.

Improve this question
$\endgroup$
1
  • 2
    $\begingroup$ Yes, this can be done via the extended Euclidean algorithm for polynomials (assuming that the element is invertible). $\endgroup$
    – Daniel S
    Commented Dec 1 at 10:52

1 Answer 1

Reset to default
2
$\begingroup$

As mentioned in the comments, the extended euclidean algorithm can be applied. If the elements one is inverting are secret though, this should be in constant time. This can be done, see Fast constant-time GCD computation and modular inversion.

In general, modular polynomial inversion (of "short" polynomials) was part of NTRU-type scheme's key generation. This was always a slow part of the scheme, so there was a decent amount of effort spent to try to speed it up (NTRU was part of the motivation of the above paper). So it might make sense to also look at efficient NTRU implementations, see for example section 5.2.2 of this dissertation for some general tricks.

Improve this answer
$\endgroup$
3
  • $\begingroup$ So how about the distribution of the inverse? Suppose I sample the element from a discrete gaussian distribution with a narrow width, whats' the distribution of its inverse? $\endgroup$
    – Haotian Yin
    Commented Dec 9 at 10:02
  • 1
    $\begingroup$ @HaotianYin The only semi-related thing I know is that for $f, g$ small polynomials, $fg^{-1}$ is thought to be computationally indistinguishable from uniform. This is the Decisional Small Polynomial Ratio problem (roughly). I don't have any reason to expect $g^{-1}$ in isolation to have some "nice" distribution though (from some "nice" parameterized family of distributions, or even satisfying some "niceness" property such as $\lVert g^{-1}\rVert$ is bounded whp). $\endgroup$
    – Mark Schultz-Wu ♦
    Commented Dec 9 at 10:41
  • $\begingroup$ Oh thx! $(fg^{-1})$'s distribution is actually what I want. $\endgroup$
    – Haotian Yin
    Commented Dec 9 at 11:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.