3
$\begingroup$

Having offered a fast integer nth-root algorithm to a bigint library that is also used for cryptography I was asked if it does its work in constant time, so I took a look at the literature to see how other programmers solved that problem and found—nothing.

That leads to the question: is there any cryptographic algorithm out there—and in use— that needs an integer nth-root function?

EDIT: "integer nth-root function" here means a plain, vanilla truncating nth-root function $k = \lfloor m^{1/n} \rfloor$ with the restrictions $\{k, m, n\} \in \mathbb{Z} $ and $n > 0$.

Improve this question
$\endgroup$
9
  • $\begingroup$ Are you asking about the n-th root function over a finite ring, a finite field, or over the reals? $\endgroup$
    – Geoffroy Couteau
    May 25, 2019 at 11:14
  • $\begingroup$ @GeoffroyCouteau Not the reals in this case (I don't think a truncating nth-root function would make much sense but I might err, of course) but I'm completely open to any hint. I can save a lot of work (and headaches) if there is no algorithm known to the experts that uses a nth-root function. I can still add it later if somebody complains but it is cheaper if I can spare that work for now. $\endgroup$
    – deamentiaemundi
    May 25, 2019 at 11:26
  • $\begingroup$ The reason why I ask is because some cryptosystems do use modular n-th roots over a ring - RSA decryption is an e-th root modulo $p*q$, Paillier decryption involves an n-th root modulo $n^2$, etc. $\endgroup$
    – Geoffroy Couteau
    May 25, 2019 at 11:43
  • 2
    $\begingroup$ Integer $n^{\mathit{th}}$ root is very useful for breaking stupid uses of RSA. Fortunately the serious uses of it, like RSA-KEM for encryption, are not vulnerable to this. But nobody cares if an attack runs in constant time. $\endgroup$
    – Squeamish Ossifrage
    May 25, 2019 at 14:27
  • 1
    $\begingroup$ well then my answer to your question would be "not that I know of", but additional opinions of other members might be preferable :) $\endgroup$
    – Geoffroy Couteau
    May 25, 2019 at 18:37

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.