Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Fast constant-time GCD algorithm and modular inversion

gcd.cr.yp.to

Post reply on HN
Print view View original

51–60 of 84 posts

Re: Fast constant-time GCD algorithm and modular inversion

#51

Post by arghwhat »

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?

It is constant time by crypto programming definition in both theory and practice, and O(1) only in theory (bigints are a pain).

I did not try to claim that O(1) is nonsensical. Rather, that certain O(1) variable-input algorithms are in fact simply fixed input algorithms due to not considering its input.

I also find these "non-sensical" O(1) algorithms to be outliers.

Re: Fast constant-time GCD algorithm and modular inversion

#52

Post by minitech »

xurukefi wrote: post #33
minitech wrote: post #15

Earlier quoted context omitted.

It’s not click bait. It’s standard terminology.

I disagree. "Constant time" means O(1), which this isn't.

Disagreeing with a fact doesn’t make a lot of sense. Maybe you meant to say “I didn’t know this was standard terminology” or “I think it’s a confusing choice of word anyway”.

Re: Fast constant-time GCD algorithm and modular inversion

#53

Post by davemp »

arghwhat wrote: post #17
waterhouse wrote: post #3

It seems "constant-time" isn't used to mean "the time taken is O(1) regardless of the size of the input n", but rather, "for a given input size, the algorithm is carefully written to do the same amount of work no matter what the specific bits of the input are, to defeat timing attacks". This took me a bit of time to figure out. To illustrate the kind of thing it's talking about, consider the naive algorithm for compu…

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. 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).

How about 'consistent time' or 'uniform time' for non-O(1) uses?

Re: Fast constant-time GCD algorithm and modular inversion

#54

Post by throwawaymath »

ziedaniel1 wrote: post #49
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 think you misread slightly. > All of these algorithms take constant time, i.e., time independent of the input coefficients for any particular (n, c). This means that once you have chosen a particular n and c , the time no longer varies. However, if n and c vary, the running time is definitely allowed to vary also (as the formulas n(c + n) and (c + n)(log cn)^2+o(1) clearly do).

No, I didn't misread. You and I are in (apparently violent) agreement. Constant time does not mean that running time cannot vary, in either complexity theory or cryptography. There are misconceptions on both sides here, with regard to what the terminology means in both complexity theory and cryptography.

For precision, I'll start with a good definition[1] for what "constant time" means in cryptography:

> Constant-time implementations are pieces of code that do not leak secret information through timing analysis. This is one of the two main ways to defeat timing attacks: since such attacks exploit differences in execution time that depend on secret elements, make it so that execution time does not depend on secret elements. Or, 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, in particular (but not only) cryptographic keys.

Secure, constant time cryptographic algorithms need not have unvarying execution time. Now going back to complexity theory, it is also an extraordinarily common misconception that "constant time" means "the algorithm has the same execution time regardless of the size of the input." This is not the case. Big O notation doesn't even care about what always happens, it cares about what happens in the worst case. When we use "constant time" in the O(1) sense of the word, we are not precluding the possibility of an algorithm having variable execution time. Again, for precision, we are simply saying that the execution time (number of operations, etc) has an asymptotic upper bound which is independent of the input. The execution time may vary with the input, and generally speaking it will.

_________________________

1. Thomas Pornin, Why constant time crypto? https://bearssl.org/constanttime.html

Re: Fast constant-time GCD algorithm and modular inversion

#55

Post by gjm11 »

throwawaymath wrote: post #30
waterhouse wrote: post #3

It seems "constant-time" isn't used to mean "the time taken is O(1) regardless of the size of the input n", but rather, "for a given input size, the algorithm is carefully written to do the same amount of work no matter what the specific bits of the input are, to defeat timing attacks". This took me a bit of time to figure out. To illustrate the kind of thing it's talking about, consider the naive algorithm for compu…

This is incorrect. Refer to Section 2, "Organization of the paper": > We start with the polynomial case. Section 3 defines division steps. Section 5, relying on theorems in Section 4, states our main algorithm to compute c coefficients of the nth iterate of divstep. This takes n(c + n) simple operations. We also explain how “jumps” reduce the cost for large n to (c + n)(log cn)^2+o(1) operations. All of these algorit…

The authors are not using "constant time" in the complexity-theoretic sense. That would mean an algorithm whose running time doesn't depend on n,c.

The GCD algorithm here has the property that (I'm quoting section 1.4 here) "the number of operations is ... asymptotically n (log n)^(2+o(1))". That is not constant as n varies.

The nice properties they claim for their algorithm are:

1. The asymptotic running time is good. This is a complexity-theoretic claim. The asymptotic performance is of the same order as e.g. Schoenhage's earlier algorithm, so this isn't in itself any sort of breakthrough.

2. For fixed input size, the running time is constant. This is a cryptographic claim: it gives immunity to timing attacks. There have been earlier constant-time GCD and modular inverse algorithms, so again this on its own isn't any sort of breakthrough.

It isn't clear to me whether 1+2 is claimed to be new. I think it isn't: that is, there are other constant-time GCD algorithms with the same asymptotic growth of runtime.

3. The constant factors are good. This is a matter of the practicality of the algorithm. Here the authors are claiming to have done better than anyone before them.

Re: Fast constant-time GCD algorithm and modular inversion

#56

Post by gjm11 »

throwawaymath wrote: post #40
OskarS wrote: post #18

Earlier quoted context omitted.

To clarify: it's not "constant time" in the sense of having O(1) time complexity with regards to the size of the inputs, which is what most people mean by "constant time" (which is obviously not possible in this case: there's never going to be a GCD algorithm that can work as fast on 100-bit integers as on 1,000,000,000-bit integers). It's "constant time" in the cryptographic sense, that the time to run it can't be u…

> it's not "constant time" in the sense of having O(1) time complexity with regards to the size of the inputs Yes it is. The presented algorithm is constant time in the exponent, i.e. 2 + O(1), where this exponent is not impacted by the size of the inputs n and c . Much like any other complexity analysis, an algorithm is O(1) as long as O(1) is asymptotically the "largest part" of the running time. As the size of n i…

"Constant time in the exponent" is nonsense, I'm afraid.

A bounded exponent of n would be the same thing as "polynomial time", but the thing that's bounded (and indeed arbitrarily close to 2 for large n) is the exponent of log n.

The running time of the algorithm presented in this paper is n (log n)^(2+o(1)). This ...

... is not constant; it increases with n, a bit faster than linearly.

... has o(1), not O(1), in the exponent; the two mean different things. O(1) means "bounded", o(1) means "tends to zero". The claim isn't that the running time is n times polynomial(log n) but that it's n times "at most approximately a quadratic polynomial in log n".

... doesn't in fact depend mostly on that exponent; the most important factor is the n, not the (log n)^(2+o(1)). If that 2 were a 100, the n factor would still (asymptotically) matter more.

For instance, suppose n=2^100 and our logs are to base 2. Then the running time of this algorithm is approximately some constant times 2^100 (that's the n factor) times 100^2 (that's the factor with log n in it). 2^100 is much, much, much bigger than 100^2.

Re: Fast constant-time GCD algorithm and modular inversion

#57

Post by throwawaymath »

gjm11 wrote: post #55
throwawaymath wrote: post #30

Earlier quoted context omitted.

This is incorrect. Refer to Section 2, "Organization of the paper": > We start with the polynomial case. Section 3 defines division steps. Section 5, relying on theorems in Section 4, states our main algorithm to compute c coefficients of the nth iterate of divstep. This takes n(c + n) simple operations. We also explain how “jumps” reduce the cost for large n to (c + n)(log cn)^2+o(1) operations. All of these algorit…

The authors are not using "constant time" in the complexity-theoretic sense. That would mean an algorithm whose running time doesn't depend on n,c. The GCD algorithm here has the property that (I'm quoting section 1.4 here) "the number of operations is ... asymptotically n (log n)^(2+o(1))". That is not constant as n varies. The nice properties they claim for their algorithm are: 1. The asymptotic running time is goo…

> 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 execution time varies with the input size, but this does not preclude constant time asymptotics.

> The GCD algorithm here has the property that (I'm quoting section 1.4 here) "the number of operations is ... asymptotically n (log n)^(2+o(1))". That is not constant as n varies.

Yes it is. Constant time does not mean that execution time does not vary, in either complexity theory or cryptography.

Re: Fast constant-time GCD algorithm and modular inversion

#58

Post by 112233 »

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…

Ok, let's take as an example a string equality comparision algorithm (strcmp() == 0). What would be your definition of a meaningful input?

Re: Fast constant-time GCD algorithm and modular inversion

#59

Post by moron4hire »

zimpenfish wrote: post #23
moron4hire wrote: post #21

Earlier quoted context omitted.

Or maybe "fixed-time". I don't like "isochronous" because it introduces an obtuse neoligism.

> I don't like "isochronous" because it introduces an obtuse neoligism. Obtuse, perhaps, but neologism? http://etymology.enacademic.com/20730/isochronous meaning "equal time" dating back to the early 1700s.

Case in point. I'm not an etymologist, nir should we expect people to have to research the words they use. If a word is that old and not in common parlance, it is a failure of a word and it really shouldn't be used.

Re: Fast constant-time GCD algorithm and modular inversion

#60

Post by fwip »

caf wrote: post #27
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 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".
Post reply on HN