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 '19 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 '19 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 '19 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 '19 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 '19 at 18:37

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.