Fast constant-time GCD algorithm and modular inversion • Hacker News Board

Re: Fast constant-time GCD algorithm and modular inversion

#71

Post by throwawaymath » Thu, Jun 13, 2019, 5:20 PM UTC

gjm11 wrote: post #62

throwawaymath wrote: post #57

Earlier quoted context omitted.

> The authors are not using "constant time" in the complexity-theoretic sense. Yes, they are. I've already made a top-level comment citing the paper's explicit definition from Section 2 and comparing it to canonical definitions from the usual literature of algorithm analysis. > That would mean an algorithm whose running time doesn't depend on n,c. It does not. Note the exponent, 2 + O(1). It is true that the executio…

Your "top-level comment citing the paper's explicit definition" is wrong. It says "The asymptotic runtime of the presented algorithm does not depend on the inputs, n and c", which is flatly untrue because (1) n and c are not the inputs to the algorithm and (2) the runtime does depend on n. Having a bounded exponent is simply not the same thing as "constant time"; running time that increases unlimitedly with the size…

I think there's a misunderstanding here. Can you please be specific about the operation you're saying is increasing commensurate with inputs n, c? The GCD algorithm is accomplished using O(1) polynomial multiplications, which is achieved because the coefficients for the polynomial multiplication are given by n, c.

EDIT: To make my position clear, what I am saying is this:

1. The presented algorithm will have variable computation time, but not variable asymptotic time,

2. The algorithm uses O(1) (i.e. constant time) polynomial multiplications in the worst case, and

3. The worst case bound does not change with n nor c, though they are used in the algorithm to calibrate the divsteps such that no more than O(1) operations are required.

I will concede it's possible I'm misunderstanding the paper itself, but I don't see that here.

Re: Fast constant-time GCD algorithm and modular inversion

#72

Post by kmill » Thu, Jun 13, 2019, 5:56 PM UTC

throwawaymath wrote: post #44

It's pretty frustrating to see the discussion on this submission dominated by people litigating the "constant time" terminology. The authors, Bernstein and Yang, are using constant time in the conventional, complexity theoretic sense of the word. Here is a quote from Section 2, "Organization of this paper": > We start with the polynomial case. Section 3 defines division steps. Section 5, relying on theorems in Sectio…

> Among other things, this paper is not about an implementation methodology that ensures the GCD algorithm will take exactly the same amount of time regardless of the input.

The introduction to the paper talks about the importance of developing constant-time implementations of Euler's algorithm to avoid timing attacks, pointing out how algorithms with conditional jumps are susceptible to, for example, cache timing attacks.

As far as I understand it, a constant time algorithm, in the cryptographic sense, is one whose running time is uncorrelated with the precise secret information. If it were correlated, then timing attacks would let you infer the secret information. Presumably, if there is no random model, then the definition is that the algorithm must run in the exact same amount of time no matter the input, assuming a fixed size for the inputs. (At least one of the cited papers agrees with this definition.)

The contribution of the paper is a constant time divstep algorithm. The quote "All of these algorithms take constant time, i.e., time independent of the input coefficients for any particular (n, c)" seems to have ambiguous quantifiers and should be rewritten. It should be something like "given a fixed number of iterations n and a fixed number of input power series coefficients c, our divstep takes a constant n(c + n) simple operations, and the algorithm is constant time, i.e., the running time is not correlated with the precise inputs." Section 1.1 gives exact cycle counts for various CPUs.

Section 7 discusses how to use bit masking to actually implement it in a constant time way (in the cryptographic sense).

Anyway, divstepsx is certainly not O(1) time unless n and t are fixed constants.

Re: Fast constant-time GCD algorithm and modular inversion

#73

Post by infinity0x-2 » Thu, Jun 13, 2019, 6:17 PM UTC

throwawaymath wrote: post #66

infinity0 wrote: post #63

Earlier quoted context omitted.

> Constant time does not mean that running time cannot vary, in either complexity theory or cryptography. Again, overloading of the term "constant time" causes pointless misunderstanding and arguments. Your statement here is wrong. In complexity theory the term "constant time" does indeed mean the running time is bounded even with unbounded input (e.g. goes to infinity), although it could vary within this bound. In c…

> In cryptography the term "constant time" is sometimes used to mean a different concept, that the operation actually takes constant non-varying time, so that an attacker can't exploit this as a side channel to figure out the input values. Note that I cited Thomas Pornin for my definition of constant time cryptography, who is a cryptographer in theory and implementation. It is emphatically not necessary for software…

> This will be a poor hill for you to die on, but I invite you to provide literature supporting your alternative definition.

Lol, you are being melodramatic, this is just some algorithms. Thomas Pornin says:

> more precisely, that variations in execution time are not correlated with secret elements: execution time may still vary, but not in a way that can be traced back to any kind of value that you wish to keep secret,

What I said:

> what the operation actually takes constant non-varying time, so that an attacker can't exploit this as a side channel to figure out the input values.

We basically said the same thing, but you are choosing to nit-pick my precise wording. Sure the execution can vary according to public inputs. The subject of this thread (the paper) doesn't talk about whether inputs are secret or public, but the "constant time" part of it is only interesting if the inputs are secret, and under this context it means "non-varying".

The people that downvoted my previous post are idiots.

Re: Fast constant-time GCD algorithm and modular inversion

#74

Post by pierrebai » Thu, Jun 13, 2019, 7:03 PM UTC

throwawaymath wrote: post #44

It's pretty frustrating to see the discussion on this submission dominated by people litigating the "constant time" terminology. The authors, Bernstein and Yang, are using constant time in the conventional, complexity theoretic sense of the word. Here is a quote from Section 2, "Organization of this paper": > We start with the polynomial case. Section 3 defines division steps. Section 5, relying on theorems in Sectio…

I would suggest that you take the time to reflect on the fact that if almost everyone disagree with you, it might point to something that you misunderstand. Either about the meaning of what they say or your understanding of the subject.

Their paper shows that the algorithm takes a constant time to compute the Cth coef. of the Nth step, for a given C and N. Not that the algorithm time is independent of C and N. C and N are not the input of the GCD. The algorithm running time is constant for the input of the GCD. It is dependent on C and N.

Re: Fast constant-time GCD algorithm and modular inversion

#75

Post by gjm11 » Thu, Jun 13, 2019, 7:05 PM UTC

throwawaymath wrote: post #71

gjm11 wrote: post #62

Earlier quoted context omitted.

Your "top-level comment citing the paper's explicit definition" is wrong. It says "The asymptotic runtime of the presented algorithm does not depend on the inputs, n and c", which is flatly untrue because (1) n and c are not the inputs to the algorithm and (2) the runtime does depend on n. Having a bounded exponent is simply not the same thing as "constant time"; running time that increases unlimitedly with the size…

I think there's a misunderstanding here. Can you please be specific about the operation you're saying is increasing commensurate with inputs n , c ? The GCD algorithm is accomplished using O(1) polynomial multiplications, which is achieved because the coefficients for the polynomial multiplication are given by n , c . EDIT: To make my position clear, what I am saying is this: 1. The presented algorithm will have vari…

The title of the paper is "Fast constant-time gcd computation and modular inversion". The algorithm presented in the paper does not compute GCDs or modular inverses in time O(1). The time taken for either of those tasks is O(n (log n)^(2+o(1))).

The algorithm presented in the paper also doesn't take a bounded number of polynomial multiplications, though I'm not sure why those should be the relevant thing to count. In section 5.4 they say they split a size-n problem into two problems whose size add up to n using O(1) polynomial multiplications of size about n, and that their algorithm takes them both to be of size ~ n/2. That means O(n) polynomial multiplications, but most of them are small so the total cost for given n is, as they say in section 5.5, Theta(log n) times the cost of polynomial multiplication provided a fast polynomial multiplication algorithm is used.

The worst-case bound, both for the number of polynomial multiplications and for the actual running time, does depend on n. (The former is of order n but, again, most of the polynomial multiplications are small; the latter is of order about n (log n)^2.)

(As for the cryptographic "constant time" notion, my understanding from the paper is that with a naive timing model -- e.g., assuming that all memory accesses take equal time -- their algorithm is exactly constant-time for fixed input size. They say in a footnote near the end of section 7: "There is considerable variation in the cycle counts, more than 3% between quartiles, presumably depending on the mapping from virtual addresses to physical addresses. There is no dependence on the secret input being inverted.")

Re: Fast constant-time GCD algorithm and modular inversion

#76

Post by repsilat » Thu, Jun 13, 2019, 8:01 PM UTC

arghwhat wrote: post #43

repsilat wrote: post #34

Earlier quoted context omitted.

I think it would be tough to find a suitable definition of "meaningful". When searching for an element in an ordered list, how many items are meaningful? One if it's present, zero otherwise? Always log(n)? Always n? If "meaningful" is a non-trivial property, as difficult to determine as an algorithmic lower bound, then it's not terribly useful. And it also leaves us with no way to talk about non-constant time algorit…

> I think it would be tough to find a suitable definition of "meaningful". I do not believe it is tough to find a suitable practical definition of meaningful: If a piece of information has no effect on the output of the algorithm, regardless of its value, then it is not meaningful. Examples of meaningful values would be any value in a list being sorted. Non-meaningful values would be any other bit than the lowest bit…

With this definition, different parts of the input might be "meaningful" for two algorithms that solve the same problem. This makes the size of the "meaningful" part of the input ill suited for comparing efficiency.

(It also makes the statement "no program can run faster than linear time in the size of the meaningful input" true directly by definition, which makes it a pretty boring statement...)

Re: Fast constant-time GCD algorithm and modular inversion

#77

Post by ChrisLomont » Thu, Jun 13, 2019, 8:18 PM UTC

twic wrote: post #28

arghwhat wrote: post #17

Earlier quoted context omitted.

This is standard terminology within programming and cryptography. This is the only practical definition to use, as cryptography commonly deals with arbitrarily sized inputs, which can of course not all run in O(1). A simple example of constant-time within this definition, as well as why constant-time does not mean O(1) in this context, is that of a comparator: The most normal, and fastest, approach is to go through d…

> This is standard terminology within programming and cryptography Within cryptography, yes, but in programming in general, absolutely not. The cryptographic definition of constant-time postdates the algorithmic one by decades, i think. It's a shame the cryptographers didn't pick a different term.

>The cryptographic definition of constant-time postdates the algorithmic one by decades, i think.

The normal usage of the phrase "constant time" predates CS by centuries, and it is much closer in usage to the crypto version than the complexity version.

Crypto uses the term "constant time" to mean same time for any input, while the general CS community uses O(1) to mean bounded time and also often uses complexity to hide log N terms. It also allows variable time, as long as it's bounded (and that sometimes allows hiding terms like log N or log log N...).

A good example is most algorithms treat addition as a constant time operation, but, for example, addition of indices for lookups is not constant time when inputs are unbounded. So if you compute an index by addition and ignore the logN time to do the addition, then you fudged. Yet this is commonplace in complexity theory, which models many basic operations as constant time when they are not for unbounded inputs.

For example, a "constant time" hash table operation, which often indexes arbitrarily large indices with addition, ignores the log N needed to add arbitrarily large indices.

Thus crypto uses the phrase in the more precise, centuries old usage.

Re: Fast constant-time GCD algorithm and modular inversion

#78

Post by svat » Fri, Jun 14, 2019, 12:55 AM UTC

throwawaymath wrote: post #68

svat wrote: post #61

Earlier quoted context omitted.

The definition of “constant time” in computational complexity theory is O(1) time as a function of the input size n, i.e., the time taken for an input of size n is bounded by some constant regardless of n. This is clear even from the two quotes you picked, from Skiena and from Sedgewick: both say that the running time does not depend on the input size n. What we have here in the cryptography sense is different: the r…

> What we have here in the cryptography sense is different: the running time n(c+n) clearly does depend on n; it just does not depend on the actual input. Can you explain to me what the input is, if not c and n ?

Consider the sentence just before “This takes n(c + n) simple operations”, as even quoted by you: “Section 5 […] states our main algorithm to compute c coefficients of the nth iterate of divstep”. So from this it is clear that c and n are the number of coefficients desired and the number of iterations desired; they are not the input to the algorithm (the two numbers or polynomials whose gcd is sought).

I'm really curious about your comments here. To understand them better, could you take a moment to say which of these statements you disagree with:

(1) A function f is O(1) if it is bounded. That is, if there exists a constant C such that for all n, we have f(n) (2) When we say that an algorithm (or more precisely, its running time) is O(1), we mean that the function “the algorithm's running time as a function of its input size” is O(1). In other words, let's denote the time that the algorithm takes on input I by T(I), and let us denote f(n) = max_{|I|=n} T(I) where |I| denotes the size of input I. Then we mean that f(n) = O(1). In simpler terms: that the worst-case running time does not grow without bound as a function of the input size.

(3) The algorithm in this paper, to compute the GCD of two polynomials or integers, does not have a bounded running time. (In fact, the authors describe it by the term “subquadratic”, and compare it to earlier subquadratic algorithms: “[…] a constant-time algorithm where the number of operations is subquadratic in the input size—asymptotically n(log n)^{2+o(1)}.”) That is, given any constant C, there exist inputs to this algorithm (two sufficiently large polynomials or integers) such that the running time of the algorithm is greater than C.

(4) As (3) shows that the property described in (2) does not hold, the running time of the algorithm here is not O(1).

One can argue separately whether “constant time” should be used to mean

• (the usual computational complexity sense) that the worst-case running time, i.e. the function f(n) is O(1), or

• (the cryptography sense) that T(I) does not give any exploitable information about I beyond what is known, typically |I|.

This is just an unfortunate clash of terminology across the cultures of the two fields, and IMO not an interesting thing to debate — everyone can choose whatever terminology works for them. But your claim that the two definitions are the same is puzzling, as all of (1), (2), (3), (4) seem obvious to me.

Re: Fast constant-time GCD algorithm and modular inversion

#79

Post by caf » Fri, Jun 14, 2019, 1:20 AM UTC

fwip wrote: post #60

caf wrote: post #27

Earlier quoted context omitted.

This is the only practical definition to use, as cryptography commonly deals with arbitrarily sized inputs, which can of course not all run in O(1). It doesn't necessarily follow that any algorithm on a arbitrarily-sized input can't run in O(1) - for a trivial example there is an algorithm for "determine if the input number is odd" which is O(1).

"not all", not "none of".

The "not all" is referring to the (executions of the algorithm under) potential inputs.

Re: Fast constant-time GCD algorithm and modular inversion

#80

Post by caf » Fri, Jun 14, 2019, 1:26 AM UTC

throwawaymath wrote: post #48

arghwhat wrote: post #47

Earlier quoted context omitted.

I see how you may think that, but I would argue that I am not redefining anything, as things turn nonsensical without this assumption. It is not an input if it does not affect your output (I am sure a better formal definition exists—I usually hear "meaningful", hence my use of that). Without this restriction, any input could be arbitrarily padded, inflating input sizes and making an algorithms complexity appear lower…

> I see how you may think that, but I would argue that I am not redefining anything, as things turn nonsensical without this assumption. The point I'm making is that this statement reduces to the claim that defining an algorithm's worst case time complexity as O(1) or constant time is nonsensical. Do you disagree that adding two numbers is a constant time operation?

Do you disagree that adding two numbers is a constant time operation?

I do. A general algorithm for adding two numbers, at least one represented in the conventional way as a series of digits in some base, has a lower bound of O(log n).