Month: April 2019

A misunderstanding of complexity

Posted on by John

Iterating simple rules can lead to complex behavior. Many examples of this are photogenic, and so they’re good for popular articles. It’s fun to look at fractals and such. I’ve written several articles like that here, such as the post that included the image below.

But there’s something in popular articles on complexity that bothers me, and it’s the following logical fallacy:

Complex systems can arise from iterating simple rules, therefore many complex systems do arise from iterating simple rules.

This may just be a popular misunderstanding of complexity theory, but I also get the impression that some people working in complexity theory implicitly fall for the same fallacy.

What fractals, cellular automata, and such systems show is that it is possible to start with simple rules and create a complex system. It says nothing about how often this happens. It does not follow that a particular complex system does in fact arise from iterating simple rules.

There’s a variation on the fallacy that says that while complex systems may not exactly come from iterating simple rules, it’s possible to approximate complex systems this way. Even that is dubious, as I discuss in The other butterfly effect.

At best I think these popular models serve as metaphors and cautionary tales. Strange attractors and such show that systems can exhibit unexpectedly complex behavior, and that forecasts can become useless when looking ahead too far. That’s certainly true more broadly.

But I’m skeptical of saying “You have a complex system. I have a complex system. Let’s see if my complex system models your complex system.” It’s often possible to draw loose analogies between complex systems, and these may be useful. But it’s not realistic to expect quantitative guidance to come out of this, such as using the Mandelbrot set to pick stocks.

Improving on the sieve of Eratosthenes

Posted on by John

Ancient algorithm

Eratosthenes had a good idea for finding all primes less than an upper bound N over 22 centuries ago.

Make a list of the numbers 2 to N. Circle 2, then scratch out all the larger multiples of 2 up to N. Then move on to 3. Circle it, and scratch out all the larger multiples of 3.

Every time you start over and find a number that hasn’t been scratched out before, that means it’s not divisible by any numbers smaller than itself, so it’s prime. Circle it and repeat. This algorithm is known as the sieve of Eratosthenes.

You could turn this into an algorithm for factoring every number less than N by not just scratching off composite numbers but keeping track of what numbers they were divisible by.

Not bad for an algorithm that predates Hindu-Arabic numerals by nine centuries. But as you might imagine, there have been a few improvements over the last couple millennia.

New algorithm

A paper by Helfgott published last week [1] gives a refined version of the sieve that takes less time and less space. Helfgott is not the first to improve on the sieve of Eratosthenes, but the latest.

His paper shows that it is possible to find all primes less than N in time

O(N log N)

and space

O(N1/3 (log N)2/3).

Furthermore, it is possible to factor all integers less than N in time

O(N log N)

and space

O(N1/3 (log N)5/3).

He also addresses finding all primes and factoring all integers in an interval [N − Δ, N + Δ] provided

N1/3 (log N)2/3 ≤ Δ ≤ N.

In the case of such an interval, one can find all the primes in the interval in time O(Δ log N) and space O(Δ). And one can factor all integers in the interval in time and space O(Δ log N).

Helfgott’s paper gives detailed pseudocode for all the algorithms.

Related posts

[1] Harald Andrés Helfgott. An improved sieve of Eratosthenes, Mathematics of Computation, https://doi.org/10.1090/mcom/3438. Published online April 23, 2019.

How category theory is applied

Posted on by John

Instead of asking whether an area of mathematics can be applied, it’s more useful to as how it can be applied.

Differential equations are directly and commonly applied. Ask yourself what laws govern the motion of some system, write down these laws as differential equations, then solve them. Statistical models are similarly direct: propose a model and feed it data.

Linear algebra is extremely useful in application, but it’s not often applied so directly. Rarely would you look at a system and immediately see a linear system. Instead you might describe a system in terms of differential equations or statistical models, then use linear algebra as a key part of the solution process.

Numerical analysis is useful because, for example, it helps you practically solve large linear systems (which help you solve differential equations, which model physical systems).

Many areas of math are useful in application, but some are applied more directly than others. It’s a mistake to say something is not applied just because it is not applied directly.

The following quote from Colin McLarty describes how some of the most abstract math, including cohomology and category theory, is applied.

Cohomology does not itself solve hard problems in topology or algebra. It clears away tangled multitudes of individually trivial problems. It puts the hard problems in clear relief and makes their solution possible. The same holds for category theory in general.

While McLarty speaks of applications to other areas of math, the same applies to applications to other areas such as software engineering.

I suspect many supposed applications of category theory are post hoc glosses, dressing up ideas in categorical language that were discovered in a more tangible setting. At the same time, the applications of category theory may be understated because the theory works behind the scenes. As I discuss here, category theory may lead to insights that are best communicated in the language of the original problem, not in the language of categories.

More on applying abstract math

Rare and strange ICD-10 codes

Posted on by John

ICD-10 is a set of around 70,000 diagnosis codes. ICD stands for International Statistical Classification of Diseases and Related Health Problems. The verbosity of the name is foreshadowing.

Some of the ICD-10 codes are awfully specific, and bizarre.

For example,

  • V95.4: Unspecified spacecraft accident injuring occupant
  • V97.33XA: Sucked into jet engine, initial encounter
  • V97.33XD: Sucked into jet engine, subsequent encounter

As I understand it, V97.33XD refers to a subsequent encounter with a health care professional, not a subsequent encounter with a jet engine. But you have to wonder how many people who have been sucked into a jet engine survive to have one, much less two, medical visits.

There is a specific code, Y92.146, for injuries in a prison swimming pool. It seems strange to combine a medical diagnosis and its location into a single code. Is a swimming injury in a prison pool medically different than a swimming injury in a YMCA pool?

I understand that the circumstance of a diagnosis is not recorded strictly for medical reasons. But while 70,000 is an unwieldy large set of codes, it’s kinda small when it has to account for both malady and circumstance. Surely there are 70,000 circumstances alone that are more common than being in a spacecraft, for instance.

Is there a code for being at the opera? Why yes there is: Y92.253. However, there are no codes that are unique to being at a Costco, Walmart, or Jiffy Lube.

Update: Here’s one I ran across recently. X96.2XXA: Assault by letter bomb, initial encounter.

Related posts

State privacy laws to watch

Posted on by John

US map with states highlighted

A Massachusetts court ruled this week that obtaining real-time cell phone location data requires a warrant.

Utah has passed a law that goes into effect next month that goes further. Police in Utah will need a warrant to obtain location data or to search someone’s electronic files. (Surely electronic files are the contemporary equivalent of one’s “papers” under the Fourth Amendment.)

Vermont passed the nation’s first data broker law. It requires data brokers to register with the state and to implement security measures, but as far as I have read it doesn’t put much restriction what they can do.

Texas law expands HIPAA‘s notation of a “covered entity” so that it applies to basically anyone handling PHI (protected health information).

California’s CCPA law goes into effect on January 1, 2020. In some ways it’s analogous to GDPR. It will be interesting to see what the law ultimately means in practice. It’s expected that the state legislature will amend the law, and we’ll have to wait on precedents to find out in detail what the law prohibits and allows.

Update: Nevada passed a CCPA-like law May 23, 2019 which takes effect October 1, 2019, i.e. before the CCPA.

Update: Maine passed a bill May 30, 2019 that prohibits ISPs from selling browsing data without consent.

Update: More state laws

  • California Consumer Privacy Act
  • California Privacy Rights Act
  • Colorado Privacy Act
  • Connecticut Personal Data Privacy and Online Monitoring Act
  • Delaware Personal Data Privacy Act
  • Indiana Consumer Data Protection Act
  • Iowa Consumer Data Protection Act
  • Montana Consumer Data Privacy Act
  • Oregon Consumer Privacy Act
  • Tennessee Information Protection Act
  • Texas Data Privacy and Security Act
  • Utah Consumer Privacy Act
  • Virginia Consumer Data Protection Act

Related privacy posts

Quantum leaps

Posted on by John

A literal quantum leap is a discrete change, typically extremely small [1].

A metaphorical quantum leap is a sudden, large change.

I can’t think of a good metaphor for a small but discrete change. I was reaching for such a metaphor recently and my first thought was “quantum leap,” though that would imply something much bigger than I had in mind.

Sometimes progress comes in small discrete jumps, and only in such jumps. Or at least that’s how it feels.

There’s a mathematical model for this called the single big jump principle. If you make a series of jumps according to a fat tailed probability distribution, most of your progress will come from your largest jump alone.

Your distribution can be continuous, and yet there’s something subjectively discrete about it. If you have a Lévy distribution, for example, your jumps can be any size, and so they are continuous in that sense. But when the lion’s share of your progress comes from one jump, it feels discrete, as if the big jump counted and the little ones didn’t.

Related posts

[1] A literal quantum leap, such an electron moving from one energy level to another in a hydrogen atom, is on the order of a billionth of a billionth of a joule. A joule is roughly the amount of energy needed to bring a hamburger to your mouth.

Professional, amateur, and something else

Posted on by John

I opened a blog posts a while back by saying

One of the differences between amateur and professional software development is whether you’re writing software for yourself or for someone else. It’s like the difference between keeping a journal and being a journalist.

This morning I saw where someone pulled that quote and I thought about how I’m now somewhere that doesn’t fall into either category. I’m a professional, and a software developer, but not a professional software developer.

People pay me for work that may require writing software, but they usually don’t want my software per se. They want reports that may require me to write software to generate. My code is directly for my own use but indirectly for someone else. Occasionally I will have a client ask me for software, but not often.

In the last few years I’ve been asked to read software more often than I’ve been asked to write it. For example, I was an expert witness on an intellectual property case and had to read a lot of source code. But even that project fit into the pattern above: I wrote some code to help me do my review, but my client didn’t care about that code per se, only what I found with it.

Related posts

Groups in categories

Posted on by John

The first time I saw a reference to a “group in a category” I misread it as something in the category of groups. But that’s not what it means. Due to an unfortunately choice of terminology, “in” is more subtle than just membership in a class.

This is related to another potentially misleading term, algebraic groups, mentioned in the previous post on isogenies. An algebraic group is a “group object” in the category of algebraic varieties. Note the mysterious use of the word “in.”

You may have heard the statement “A monad is just a monoid in the category of endofunctors.” While true, the statement is meant to be a joke because it abstracted so far from what most people want to know when they ask what a monad is in the context of functional programming. But notice this follows the pattern of an X in the category of Y‘s, even though here X stands for monoid rather than group. The meaning of “in the category of” is the same.

If you want to go down this rabbit hole, you could start with the nLab article on group objects. A group object is a lot like a group, but everything is happening “in” a category.

Take a look at the list of examples. The first says that a group object in the category of sets is a group. That’s reassuring. The second example says that a group object in the category of topological spaces is a topological group. At this point you may get the idea that an X in the category of Y‘s simply adds an X structure to a Y thing. But further down you’ll see that a group object in the category of groups is an Abelian group, which is an indication that something more subtle is going on.

More category theory posts

What is an isogeny?

Posted on by John

The previous post said that isogenies between elliptic curves are the basis for a quantum-resistant encryption method, but we didn’t say what an isogeny is.

It’s difficult to look up what an isogeny is. You’ll find several definitions, and they seem incomplete or incompatible.

If you go to Wikipedia, you’ll read “an isogeny is a morphism of algebraic groups that is surjective and has a finite kernel.” The possibly misleading term here is “algebraic group.” It may sound like they’re throwing in the term “algebraic” for clarification as if to say “a group like the kind you’d talk about in math, as opposed to the kind of group you might talk about somewhere else like in sociology.” An algebraic group is indeed a group, but one with additional structure. A “morphism” is a structure-preserving map, and so here “morphism” means a function that preserves the algebraic and topological structure of an algebraic group.

The algebraic groups we care about are elliptic curves, so let’s specialize to elliptic curves. For the rest of this post all definitions and theorems will come from Handbook of Elliptic and Hyperelliptic Curve Cryptography by Cohen and Frey. This book defines isogeny implicitly by defining what it means for two curves to be isogenous.

Two curves E/K and E‘/K are isogenous over K if there exists a morphism φ : E → E‘ with coefficients in K mapping the neutral element of E to the neutral element of E‘.

Here K is the field the curves are defined over. The neutral element is the identity element of the curve as a group, the point at infinity.

Something strange is going on here. The definition talks about two curves being isogenous. That sounds like a symmetric relationship, but the definition is not symmetric. It specifies the existence of a morphism in one direction but not in the other. But the book goes on to explain that if an isogeny exists in one direction, there necessarily exists a unique isogeny in the opposite direction, the dual isogeny, though it’s not obvious why this should be.

Another puzzling thing is that it doesn’t seem to take much for a function to be an isogeny, just map the group identity to the group identity. But there are other requirements implicit in the statement that φ is a morphism in the context of algebraic groups. Cohen and Frey do not require φ to be a homomorphism, as some authors do, but they point out that in fact φ will turn out to be a group homomorphism. They say “for more background on isogenies, we refer to section 4.3.4.” OK, let’s go there.

In that section the authors say that a morphism between Abelian varieties (a special case of algebraic groups which includes elliptic curves) is an isogeny if and only if it is surjective and has a finite kernel. That seems like a much stronger requirement than the definition above. However, in this context simply requiring a morphism to map the group identity to the group identity implies that the morphism will be surjective and have a finite kernel, and vice versa.

An isogeny is not an isomorphism

An isogeny is a group homomorphism, but not an isomorphism, not in the modern usage of the term. Historically, however, the term “isomorphism” was used for what we now call an isogeny.

We said above that the existence of an isogeny in one direction implied the existence of a dual isogeny in the opposite direction. These functions are not inverses of each other: their composition is not the identity. However, their composition does have a simple form: it is multiplication by an integer n, called the degree of the isogeny. (Multiplication here means repeated group addition, i.e. the composition takes an element x to the sum of n copies of x using the group law on the elliptic curve.)

Example

Cohen and Frey give the example

\varphi : (x, y) \mapsto \left( \frac{x^2 + 301x + 527}{x + 301}, \frac{yx^2 + 602 yx + 1942y}{x^2 + 602x + 466} \right )

of an isogeny of degree 2 between the elliptic curves

y² = x³ + 1132x + 278

and

y² = x³ + 500x + 1005

over the field with 2003 elements. The curves are not isomorphic because the group structure of the former is a cyclic group and the group structure of the latter is not.

Incidentally, there is a theorem that says two elliptic curves over a finite field are isogenous if and only if they have the same number of points. So a brute-force approach to showing that the curves above are isogenous would be to show that they both have the same number of points. And indeed, both have 1956 points.

More ECC posts

Isogeny-based encryption

Posted on by John

If and when large quantum computers become practical, all currently widely deployed methods for public key cryptography will break. Even the most optimistic proponents of quantum computing believe such computers are years away, maybe decades. But it also takes years, maybe decades, to develop, test, and deploy new encryption methods, and so researchers are working now to have quantum-resistant encryption methods in place by the time they are needed.

What’s special about isogeny-based encryption?

One class of quantum-resistant encryption methods is isogeny-based encryption. This class stands out for at least a couple methods:

  • it uses the shortest keys, and
  • it uses the most sophisticated math.

Most post-quantum encryption schemes require much longer keys to maintain current levels of protection, two or three orders of magnitude longer. Isogeny-based encryption uses the shortest keys of any proposed post-quantum encryption methods, requiring keys roughly the same size as are currently in use.

The mathematics behind isogeny-based cryptography is deep. Even a high-level description requires quite a bit of background. I’ll take a shot at exploring the prerequisites starting with this blog post.

Elliptic curves

Elliptic curve cryptography is widely used today, and partly for one of the reasons listed above: short keys. To achieve a level of security comparable to 128-bit AES, you need a 256-bit key using elliptic curve cryptography, but a 3072-bit key using RSA.

Quantum computers could solve the elliptic curve discrete logarithm problem efficiently, and so elliptic curve cryptography as currently practiced is not quantum resistant. Isogeny-based encryption is based on elliptic curves, but not as directly as current ECC methods. While current ECC methods perform computations on elliptic curves, isogeny methods are based on networks of functions between elliptic curves.

SIKE

NIST is sponsoring a competition for post-quantum encryption methods, and only one of the contestants is related to elliptic curves, and that’s SIKE. The name stands for Supersingular Isogeny Key Encapsulation. “Supersingular” describes a class of elliptic curves, and SIKE is based on isogenies between these curves.

Future posts

This post raises a lot of questions. First and foremost, what is an isogeny? That’s the next post. And what are “supersingular” elliptic curves? I hope to go over that in a future post. Then after exploring the building blocks, where does encryption come in?

Past posts

I’ve written several related blog posts leading up to this topic from two directions: post-quantum encryption and elliptic curves.

Post-quantum encryption links

Elliptic curve links