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

61–70 of 84 posts

Re: Fast constant-time GCD algorithm and modular inversion

#61

Post by svat »

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…

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 running time n(c+n) clearly does depend on n; it just does not depend on the actual input. That is, it is only constant across inputs of the same size.

I am not sure how you're claiming that n(c+n) is O(1) when it's clearly Θ(n^2) (i.e. O(n^2) and Ω(n^2)).

Re: Fast constant-time GCD algorithm and modular inversion

#62

Post by gjm11 »

throwawaymath wrote: post #57
gjm11 wrote: post #55

Earlier quoted context omitted.

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 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 of the input precisely does preclude constant-time asymptotics.

In complexity theory, "constant time" means that the execution time is bounded as the size of the input increases. The execution time of this algorithm is not bounded as the size of the input increases.

In cryptography, I don't know for sure whether "constant time" always means the same thing, but in the context of algorithms immune to timing attacks (which is the relevant context here) it means that execution time doesn't depend on the details of the input.

In this case, the algorithm does not have complexity-theory "constant time" because the runtime grows roughly like n (log n)^2. It does have cryptography "constant time" because if you fix the size of the input, the runtime does not depend on the specific numbers you put in.

I'm sorry to be so harsh here, but you have made confident wrong statements and doubled down on them when challenged. Given that your profile says "My academic background is in complexity theory", this is pretty surprising, but there's really no question that what you're saying is wrong. I'm guessing that maybe you misread something and now don't want to lose face, but you need to look again: this algorithm is not a constant-time algorithm in the complexity-theoretic sense, and it is a constant-time algorithm in the sense that the execution time doesn't depend at all on the input if you fix its size.

Re: Fast constant-time GCD algorithm and modular inversion

#63

Post by infinity0 »

throwawaymath wrote: post #54
ziedaniel1 wrote: post #49

Earlier quoted context omitted.

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-tim…

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

The paper seems to be using the latter meaning.

Re: Fast constant-time GCD algorithm and modular inversion

#64

Post by esjeon »

If I understood correctly, this paper is NOT about a new blazing fast security-breaking CS-history-changing algorithm. This paper suggests an algorithm that takes the same amount of time to compute GCD(6, 9) and GCD(123456789, 987654321), to prevent leaking hints on its inputs through side-channels. That is, this thing is basically less efficient, but still runs the same number of instructions no matter the input.

(EDIT: ... as long as inputs have the same bit-length. Any 32-bit inputs will be handled faster than 1024-bit inputs, but any 1024-bit inputs will consume the same amount of time no matter their actual values. That is, 0x0001 and 0x000000001 are handled differently by the algorithm.)

The paper do mention this:

> However, in cryptography, these algorithms are dangerous. The central problem is that these algorithms have conditional branches that depend on the inputs. Often these inputs are secret, and the branches leak information to the attacker through cache timing, branch timing, etc.

So, yeah, this is security-centered cryptography paper. The term "constant-time" is used in a different context here.

Re: Fast constant-time GCD algorithm and modular inversion

#65

Post by arghwhat »

112233 wrote: post #58
arghwhat wrote: post #43

Earlier quoted context omitted.

> 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?

For an equality operation, all bits are meaningful, as there are input configurations in which any bit can lead to a change in output.

However, I do see your point in that whether a bit flip in input leads to a change in output depends on the particular input. My counter to that is that it is not the specific input, but the potential inputs that matter.

Re: Fast constant-time GCD algorithm and modular inversion

#66

Post by throwawaymath »

infinity0 wrote: post #63
throwawaymath wrote: post #54

Earlier quoted context omitted.

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-tim…

> 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 to run with unvarying execution time in order for it to be "constant time" according to the cryptographic sense of the term. This will be a poor hill for you to die on, but I invite you to provide literature supporting your alternative definition.

Re: Fast constant-time GCD algorithm and modular inversion

#67

Post by throwawaymath »

esjeon wrote: post #64

If I understood correctly, this paper is NOT about a new blazing fast security-breaking CS-history-changing algorithm. This paper suggests an algorithm that takes the same amount of time to compute GCD(6, 9) and GCD(123456789, 987654321), to prevent leaking hints on its inputs through side-channels. That is, this thing is basically less efficient, but still runs the same number of instructions no matter the input. (E…

The term "constant-time" is used in the complexity theoretic sense. Can you explain to me, concretely, how what you've said here

> as long as inputs have the same bit-length. Any 32-bit inputs will be handled faster than 1024-bit inputs, but any 1024-bit inputs will consume the same amount of time no matter their actual values. That is, 0x0001 and 0x000000001 are handled differently by the algorithm

indicates the algorithm is constant-time in one sense but not the other?

Re: Fast constant-time GCD algorithm and modular inversion

#68

Post by throwawaymath »

svat wrote: post #61
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…

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?

Re: Fast constant-time GCD algorithm and modular inversion

#69

Post by esjeon »

throwawaymath wrote: post #67
esjeon wrote: post #64

If I understood correctly, this paper is NOT about a new blazing fast security-breaking CS-history-changing algorithm. This paper suggests an algorithm that takes the same amount of time to compute GCD(6, 9) and GCD(123456789, 987654321), to prevent leaking hints on its inputs through side-channels. That is, this thing is basically less efficient, but still runs the same number of instructions no matter the input. (E…

The term "constant-time" is used in the complexity theoretic sense. Can you explain to me, concretely, how what you've said here > as long as inputs have the same bit-length. Any 32-bit inputs will be handled faster than 1024-bit inputs, but any 1024-bit inputs will consume the same amount of time no matter their actual values. That is, 0x0001 and 0x000000001 are handled differently by the algorithm indicates the alg…

The main difference here is the goal. "O(1)" algorithm often means efficient algorithm out there in the field, but this paper has absolutely no intention of making anything efficient.

People are wrong with that (1) O(1)=fast/efficient (2) I'm arguing over the definition of "constant-time".

Re: Fast constant-time GCD algorithm and modular inversion

#70

Post by kmill »

b-3-n wrote: post #7

I was a bit disappointed to see that the "constant time" was a click bait. Should be "fixed time" - or similar - instead.

One might argue that calling O(1) just "constant time" in asymptotic complexity theory is click bait itself! Calling O(1) bounded time would have been better terminology, in my mathematical opinion.

Sometimes people actually count individual operations to form a function T(n) depending on the input n (see, for example, Knuth's books). If T(n) is the constant function, then the algorithm takes constant time in a much more literal sense.

(The "constant time" terminology bugged me when I first learned about computational complexity.)

Edit: It seems "constant time" in this paper might actually mean "the running time is uncorrelated with the precise secret value, only its size."

Post reply on HN