throwawaymath

Can you explain to me what the input is, if not c and n?

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

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.

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.

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

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?

> 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 algorithms take constant time, i.e., time independent of the input coefficients for any particular (n, c).

In particular note that last sentence. The asymptotic runtime of the presented algorithm does not depend on the inputs, n and c. This algorithm analysis is confirmed throughout the remainder of the paper, which walks through each stage of the algorithm. Now let's look at a few canonical definitions of "constant time", i.e. O(1).

From Skiena, we have:

Constant functions - f(n) = 1 - Such functions might measure the cost of adding two numbers, printing out the "Star Spangled Banner", or the growth realized by functions such as f(n) = min(n, 100). In the big picture, there is no dependence on the parameter n.

Likewise from Sedgewick & Wayne:

Constant. A program whose running time's order of growth is constant executes a fixed number of operations to finish its job; consequently its running time does not depend on N. Most Java operations take constant time.

I'll update if I find a choice example from Knuth in TAOCP, but I think this suffices. The discussion about whether or not the cryptographic use of the term satisfies the complexity theoretic sense of the term is a red herring; it's a distinction without a difference. Algorithm analysis focuses on asymptotic behavior, which is definitionally given by tail behavior, or rate of growth of a function. 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.

______________________

1. The Algorithm Design Manual, 2nd Edition, § 2.3.1 Dominance Relations, Page 39

2. Algorithms, 4th Edition, § 1.4 Analysis of Algorithms, Page 187

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 increases, the exponent 2+O(1) increasingly dominates execution time.

With respect, I think you may misunderstand the meaning of "constant time" in the sense of complexity theory, i.e. O(1). Accessing an element in an array of size n is a constant time operation. See: https://stackoverflow.com/questions/7297916/why-does-accessi...

EDIT: Corrected "search" to "access"

This is incorrect. The paper explicitly uses "constant time" in the sense of O(1). You can see this listed throughout the paper, in various complexity analyses, beginning from Section 2.

> 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 algorithms take constant time, i.e., time independent of the input coefficients for any particular (n, c).

What the authors are doing is (in the simplest sense) adding a worst case O(1) component to the GCD algorithm in the exponent. This is fundamentally a complexity theory paper, and Bernstern and Yang are using "constant time" in the complexity theoretic sense.

Moreover this is not about clever implementation; the algorithm they present will explicitly not take the same amount of time regardless of the input. In line with the presented complexity analysis throughout the paper, the worst case running time is asymptotically bounded independently of inputs n and c.

I think a fair compromise would be to simply delete the account name associated with comments.

____________

1. https://usamo.files.wordpress.com/2019/02/napkin-v15-2019022...

The more successful quant funds will often build out internal research teams to do this. For example, both Two Sigma and Millennium have (not so well advertised) research teams devoted to this kind of data collection internally.

Back to the point at hand, I don’t like recaptcha in principle. But given my view from both sides of the table, it’s one of very few things that consistently works for sophisticated adversaries. It’s about as close to a silver bullet as they come, with the additional upside that it’s the absolute easiest thing to implement - in both an absolute sense and relative to the return. And once you have, most of what you can implement beyond recaptcha has diminishing returns in comparison.

All of that being said, I would be inclined to agree that most websites and apps don’t need recaptcha, simply because most of them aren’t worthwhile targets for the types of attacks recaptcha is singularly effective against.

But yes, the whole cottage industry is sketchy. Almost all providers are leasing users’ computer with outright malware or shady TOS. The savvy play is to release a free game, app or even SDK which will then opportunistically route requests from the control server through the user’s device.

Recaptcha solving APIs are frequently bundled with the more reliable and premium services of this kind. They introduce a lot of latency since there’s a real mechanical turk across the world solving it for you, but they basically work.

Many of the more sophisticated ones prefer emulating mobile application requests to web requests, so yes.

1. Rotate through several thousand to several hundred thousand noncontiguous, geographically distributed, residential IP addresses,

2. Associate each IP address with a single user agent and suite of cookies,

3. Associate each IP address with a particular target username,

4. Only attempt a few incorrect logins at a time, and a somewhat random (albeit realistic) number at that, within a given time interval,

5. Use random, apparently human delays between successive requests,

6. Issue requests using extremely high fidelity simulacra of web browsers, customized to the sequence and structure of HTTP requests on the website.

When the stakes are high this is the kind of opposition you'll get. Bank account takeover, social media account takeover, ticket scalping, automated sneaker buying, financial research, market research, etc.

Recaptcha introduces unpleasant user friction, but it usually works well. To invert a popular turn of phrase, it makes stopping simple attackers easy and hard attackers possible. The most sophisticated attackers will still lease reputable Google accounts and mechanical turk time to bypass Recaptcha challenges, but it will be expensive for them.

Technical sophistication is only one dimension of this game. The other is making adversaries spend more money than they can gain from being successful.

I expect that formal methods will become another specialization that most engineers don't need to directly work with, alongside things like cryptography and low level arithmetic.

> But I think that most programmers who are serious about what they do should know calculus (the real kind), linear algebra, and statistics. The reason has nothing to do with programming per se — compilers, data structures, and all that — but rather the role of programming in the economy...One way to read the history of business in the twentieth century is a series of transformations whereby industries that “didn’t need math” suddenly found themselves critically depending on it.

There are two ways to interpret the claim that more programmers should know advanced math. One of them, which the author preempts, is the idea that programmers will improve their own work through significant mathematical maturity. It seems the author and I already agree that isn't the case, so I won't address this interpretation. But I still consider this interpretation to be more defensible than the other one.

The other way to interpret it, which the author seems to be explicitly pushing, is that programmers with a strong mathematical background will be better situated to proactively find fertile areas of the economy which can be improved through a combination of computing and advanced math. I don't believe this is realistic. None of the author's specific examples - control theory, optimization, linear programming, econometrics, or Black-Scholes - were pioneered by generalist engineers with a strong grounding in mathematics. They were just applied mathematicians (and in a few of those cases, repurposed pure mathematicians).

Likewise the bar is constantly rising. Knowing calculus, linear algebra and statistics won't empower you to make significant, groundbreaking improvements to any major field. That knowledge is necessary but insufficient. What's considered low hanging fruit these days is something that could be conceivably noticed and tackled by a postdoc. Mathematics itself is ossifying as a field of specialists, to the point where prominent researchers within subfields like algebraic geometry can be unfamiliar with each other's principal work.

This is really why find the appeal to economic advancement less than convincing - every advancement the author mentions has an implicit foundation in specialization. Historically, the most notable advancements in technology have come about through division of labor and cross-pollination. You would be better served by having two collaborating teams of mathematicians and engineers than by a team of engineers who know undergraduate math. It's already common for applied mathematicians to be able to program competently; they dominate the authorship of fast, low level math libraries. If you need them, hire them.

Conversely, I would argue we should actually reduce the education for more developers, not add even more material to it. Most developers already don't need to learn a significant amount of the material in a standard computer science degree. Piling on math courses isn't going to be a fundamental improvement for the vast majority of engineers working on real world software.

If it helps at all, this is exactly what you'll see when you create a matrix in Julia:

    julia> mat = [1 2; 3 4]
    2×2 Array{Int64,2}:
     1  2
     3  4

If you only ever work in R then technically that'd be fine (though notationally awkward). But that's not a good habit to keep since it would introduce pretty insidious bugs if you ever take the adjoint of a complex matrix intending to take the transpose.

I don’t really get it. I can perhaps understand that some candidates might have gotten good feedback from blatantly guessing in the past, but that’s why I now explicitly tell them to disclaim guesses. If anything it looks more impressive when you honestly don’t know something but intuit the substantially correct answer (as long as it’s something that could be realistically intuited).

Yet even with my disclaimer, I’ve still conducted phone screens and onsite interviews where the candidate eventually started bullshitting. It’s one thing to say you don’t know and give a wildly incorrect answer - at least then I can try and steer the interview towards another of the candidate’s strengths. It’s even okay to preface your wild guess with an, “I think...”. But the cavalier way in which people will just spout nonsense is disturbing. Even if you’ve been performing well up to the point, engaging in bullshit is nearly immediate grounds for me to discount you as a candidate.