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

Re: Fast constant-time GCD algorithm and modular inversion

#81

Post by SAI_Peregrinus » Fri, Jun 14, 2019, 1:28 AM UTC

svat wrote: post #78

throwawaymath wrote: post #68

Earlier quoted context omitted.

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

Agreeing with you by example: In computational complexity the size of the input varies. In cryptography it typically doesn't: time is identical for all inputs of the same size.

Imagine a magic sorting algorithm that always takes 1 second to check if an input is sorted, and 9 seconds to sort the input if wasn't sorted. It then returns the sorted value as output.

EG sorting "abcdefg" would check (taking 1 second) and then return (taking 0 seconds since it's sorted). Sorting "gfedcba" would check (taking 1 second) and then sort (taking 9 seconds) and return. Taking in the complete works of Shakespeare it would check (taking 1 second) and then sort (taking 9 seconds) and return.

It's O(1), yet the time varies based on the input. From a computational complexity terminology standpoint it's constant time, from a cryptographic terminology (and common intuition) standpoint it's clearly not, since it doesn't always take the same time to run.

Re: Fast constant-time GCD algorithm and modular inversion

#82

Post by hoseja » Fri, Jun 14, 2019, 5:26 AM UTC

ColinWright wrote: post #25

hoseja wrote: post #24

Earlier quoted context omitted.

I have an O(1) then!

Given that you have to read and then write each digit of the input I find it hard to believe that you have an O(1) algorithm - can you tell us what it is?

Print "1", thought that would be obvious...

Re: Fast constant-time GCD algorithm and modular inversion

#83

Post by zimpenfish » Fri, Jun 14, 2019, 8:52 AM UTC

moron4hire wrote: post #59

zimpenfish wrote: post #23

Earlier quoted context omitted.

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

> not in common parlance, it is a failure of a word

Harsh but not entirely unfair (it is, after all, how language evolves.) Although I'd counter that "isochron" isn't uncommon in travel-related situations (cf [1]) and "isochronous" is easily understandable by extension.

[1] e.g. in the UK parliament, #7927, "the resident population within the Woolwich 20-minute isochron area was about 60,000" https://publications.parliament.uk/pa/cm200607/cmselect/cmcr...

Re: Fast constant-time GCD algorithm and modular inversion

#84

Post by waterhouse » Fri, Jun 14, 2019, 11:35 AM UTC

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 problem is: "Constant—with respect to what?" "Remains constant under what conditions?" The function f(x,y) = x^2 is constant under varying y, and is not constant under varying x. The adjective "constant", by itself, is incomplete—unless it's truly a mathematical constant, like 2 or e, that depends on nothing else—which is what leads people to the "O(1)" interpretation of the phrase "constant time".

So if it's not used to mean "constant (no matter what you vary)", then it means "constant (if you vary certain parameters and I'm not specifying which ones)". When you use a phrase with something left out and implied, then the audience has to fill it in somehow. If the audience shares your background, perhaps has been reading similar papers recently in which "constant with respect to xyz" had the xyz spelled out explicitly, this may go well; if not, it may not. In this case, people's interpretations of "the xyz we're varying" appear to range over "the entire space of integer-tuple inputs", "the size of the integers", "the bits of the integers after the leading 1", "the parts of the inputs that are considered 'secret'", and more.

So, if you say something with an implicit part left unspecified, and people fill it in with something different than what you intended... the first time this happens, I might consider it an unfortunate accident. If it happens repeatedly, it may be worth being more explicit or choosing another term. (Suggested terms: "secret-hiding", "secret-blind". "[something]-oblivious" might be another good word-formation—precedent exists in "cache-oblivious" algorithms.)

This is not the worst terminological mess we have in CS[1].

[1] My (least) favorite example is the term "dynamic programming", whose name appears to have been chosen because it sounded good and was vague enough to cover what the author wanted: "Thus, I thought dynamic programming was a good name. It was something not even a Congressman could object to. So I used it as an umbrella for my activities." https://en.wikipedia.org/wiki/Dynamic_programming#History