Superconductor

Ghosts, vampires and zombies

I recently came across "Cinema Fiction vs Physics Reality: Ghosts, Vampires and Zombies," by Costas Efthimiou and Sohang Gandhi. This paper discusses how ghosts, vampires and zombies are portrayed in books and movies and looks at what's actually possible and what's not.

Ghosts have lots of problems with physics at a very basic level. They can't both be incorporeal and do the things that they are shown to do in books and movies. That should be fairly obvious.

Vampires have problems with the exponential growth of the vampire population that they would cause. I hadn't thought that before, but when you hear it, it's fairly obvious. Suppose that a vampire needs a single victim each year and that this victim then turns into a vampire. After one year, you have two vampires. Each of these two creates two more the next year. Each of these four then create four more the next year, etc. This growth quickly gets out of control and leaves the entire world populated by vampires. So the fact that people exist is proof that vampires don't exist, at least not vampires as they're portrayed in books and movies. (This analysis might not be quite accurate because it doesn't account for the ability of people like Kristy Swanson to keep the vampire population in check, but it's probably close enough.)

It turns out that there's actually a factual basis for zombies. Maybe this is why Brian Keene's zombie books are so popular. I'm personally more fond of zombie stories like Robert Bloch's "Maternal Instinct," but I seem to be in the minority in this particular case. Much like people who think that reading papers about the physics of ghosts, vampires and zombies is interesting.

And it's apparently not just physicists who worry about zombies. Lucy Snyder, the wife of Gary Braunbeck, one of the best horror writers in the world, has written a book Installing Linux on a Dead Badger and Other Oddities that tells why people in the corporate IT world should worry about them.

Here's what this fine book has to offer:

• "Installing Linux on a Dead Badger"
• "Authorities Concerned Over Rise of Teen Linux Gangs"
• "Your Corporate Network And The Forces Of Darkness"
• "Faery Cats: The Cutest Killers"
• "Graveyard Shift"
• "Dead Men Don't Need Coffee Breaks"
• "Business Insourcing Offers Life After Death"
• "Corporate Vampires Sink Teeth Into Business World"
• "Unemployed Playing Dead To Find Work"
• "Trolls Gone Wild"
• "The Great Vüdü Linux Teen Zombie Massacree"
• "Wake Up Naked Monkey You're Going To Die"
• "In The Shadow of the Fryolator"

There's also a book coming out soon that tells how Dante Alighieri was inspired to write the Divine Comedy, at least the Inferno part of it, by seeing the results of a zombie infestation. My copy should be arriving next week.

I'm sure that there's some way to make this relevant to information security, but I don't see it right now.

Why PKI failed

I came across an intesting paper that may explain why PKI technology failed. This paper is "Test of Influence from Future in Large Hadron Collider; A Proposal," by Holger Nielsen and Masao Ninomiya. Nielsen and Ninomiya essentially argue that the LHC may be plagued by problems because if it actually worked it would produce effects that are so ugly that they would actually send ripples of bad luck back through time to thwart the creation of the ugly effects. This may sound like something from a bad science-fiction movie, but this paper appears to be quite serious about this.

Similarly, maybe the possible future in which everything is PKI-enabled and digital certificates are ubiquitous is so horrendous that it actually sent ripples of bad luck back through time that sabotaged the development and deployment of PKI technology. Some things actually seem to make a lot of sense from this point of view.

I'll leave it to someone else to work out the physics of exactly how this could have happened. The paper by Nielsen and Ninomiya is probably a good place to start.

Really big symmetric keys

I recently came across an interesting security product, although it's not exactly "interesting" in the sense that I might want to buy and use it. This particular product is CRYPTETO from Hawthorne Davies, a UK vendor of encryption technology. Here's what they claim:

The strongest Diplomatic Standard Algorithm key strength is Hawthorne Davies’ TOUAREG Encryption Algorithm used in CRYPTETO. It uses a session key equivalent to 49,152 bits.

Let's assume that this is true and that they're using a public-key algorithm to transport or otherwise protect these keys. According to the formula that NIST uses in Section 7.5 the Implementation Guidance for FIPS 140-2, it would take an RSA key with slightly more than 15 billion bits to give the same strength as a 49,152-bit symmetric key. Operations on an RSA key that big are totally impractical, so they're definitely not using RSA for key transport.

Maybe they use an elliptic-curve scheme for key transport. If that's the case, it would still take an elliptic-curve key with slightly less than 100,000 bits to give the same strength. That's also impractical, so I don't think that they're doing that either.

This leads me to believe that one of two things is true: either they're using a key much weaker than one with 49,152-bits of strength for key management, or they're using no public-key technology for key management at all. If the first is true, then the CRYPTETO system doesn't really provide 49,152-bits of strength. In this case, its cryptographic strength is limited by the size of the public keys that it uses, and these are almost certainly provide much less than 49,152 bits of strength.

If the second is true, then key management is going to be a serious headache for user of the CRYPTETO system. They won't even be able to use SSL to securely transport keys. I doubt that's the case, so we can probably assume that CRYPTETO doesn't provide anywhere near 49,152 bits of strength, and that the claim that is uses a session key that's the equivalent of 49,152 bits is nothing more than a red herring designed to distract and impress potential customers with information that's really not very relevant.

The source of bad decisions

I doubt that anyone tries to make a bad decision. Even the people who designed the automated wake-up call system that I described in a previous post probably didn't try to design a system with the worst user interface that they could think of. In this particular case, I can imagine that the following discussion between two product managers Alice and Bob that led to this particular feature:

Alice: Let's have the message that indicates that the call has been set say something like "Your wake-call has been set for 8 a.m. Have a nice day."

Bob: The problem with that is that many of our customers have guests from many other countries. If we have the message in English, then some guests won't be able to understand it. We need a message that doesn't use any language at all. It needs to be totally independent of human languages.

Alice: What are you thinking of?

Bob: What about a series of tones? It would have to be fairly loud, so that guests who are hard of hearing can hear them. And we'd also have to use a single tone to make sure that it's not mistaken for the series of four annoying tones that the phone company used to use to indicate that you dialed a non-working number.

Alice: Are you suggesting that we just play a sound like "BEEP BEEP BEEP BEEP ..." to indicate that a wake-up call has been set?

Bob: Yes.

Alice: Uh, I guess that makes sense.

Bob: OK, I'll make sure that it gets in our next release.

Alice: How should we tell a user that they've already set a wake-up call?

In many cases, I'd guess that the bad decision makes sense when it's made, although it may be hard to reconstruct the thought process that led to this decision at a later date.

I wonder what it would have been like to be at the meetings where the design of the Department of Defense's PKI system was discussed. I'm sure that it made perfect sense at the time. I almost wish that I could have been there to see it happen.

Good and bad notation

In the P1363.3 Standard for Identity-based Public Key Cryptography using Pairings, there's one particular bit of notation that seems to confuse and annoy people. That's the use of "ID" to indicate the string that represents a users identity. Every other variable in the document is represented by a single letter, and the fact that this particular variable is represented by two letters seems to be the source of the trouble. I hope that this particular bit of notation doesn't cause people too much trouble, although it certainly seems to have the potential for doing that: a good notation is its own heaven, a bad notation is its own h**l.

Quantum mechanics is an example of a field that seems to defined by its bad notation. Quantum mechanics, at least the material that I learned, is really nothing more than looking at how certain linear operators on Hilbert spaces behave. In other words, it's essentially just linear algebra, but with a notation that does its best to obscure that fact.

The notation that we used in a class on quantum electrodynamics that I had in graduate school is probably why I decided to not study physics any more and to stick to things that used a notation that I could understand. I probably made the right choice. If I had stuck with physics, I'd have spent a significant part of the rest of my life converting between the bra-ket notation and something that actually made sense to me. 

With any luck, the notation in the P1363.3 standard isn't bad enough to make someone decide to give up cryptography.

Another strategic industry?

GAME SHOW HOST: Karl Marx, your final question, who won the FA Cup in 1949?

MARX: The workers' control of the means of production? The struggle of the urban proletariat?

GAME SHOW HOST: No. It was in fact, Wolverhampton Wanderers who beat Leicester 3 to 1.

Monty Python's Flying Circus

According to an article on the Forbes web site, the Chinese government has decided to ban foreign companies from investing in domestic on-line gaming operations. I seem to recall learning that Communists have some suitably-Communist term for industries that are vital to economies, although I can't quite recall what this term is right now. I certainly never expected this term to be applied to games like World of Warcraft.

The report from the National Cyber Leap Year Summit

The recommendations from the information security experts (and so-called experts like me) who attended the National Cyber Leap Year Summit is now available. I found three of these recommendations particularly interesting.

On page 73 in section 3.8 of the National Cyber Leap Year Summit 2009 Participants' Ideas Report you'll find the idea Global Identity-Based Cryptography. Interestingly enough, this idea came out of a group that I wasn't part of, so someone who's not from Voltage thought this idea was important and also convinced the other members of his group that it's important. Curiously, one of the perceived obstacles to the adoption of IBE is "no proven technology." That's definitely proof that I wasn't in the working group that came up with this idea.

If I was there I would have mentioned that there are now at least 10 million users of IBE worldwide, a number that's probably roughly equal (if not greater than) the number of users of PKI. The technology is definitely a proven one. The other perceived obstacles to the adoption of IBE also don't agree with the actual adoption of the technology, but the fact that it's "not proven" is probably the least accurate of these perceptions.

On page 103 in section 6.3 of this report you'll find the idea Global Post-Quantum Secure Cryptography Based on Identity, or IBE that's resistant to attacks that you can run on a quantum computer. I'm not sure that this idea is really worth putting on a research agenda. I don't think that we'll see quantum computers with enough q-bits to actually beat the key sizes that are currently used any time soon. I actually doubt whether we'll ever see these.

On page 113 in section 6.8 of this report you'll find the idea Removing Barriers to Entry for Crypto Products into Federal Use. Here's the description of this idea:

Many commercial security technologies are unavailable for Federal use even though they are well accepted and widely deployed in the private sector. These technologies often allow dramatic cost savings and efficiency gains over older technologies, but Federal agencies are unable to use them because the technologies have not received the necessary certifications and approvals. In some cases, the existence of rigorous, formal proofs of security should eliminate the need for the long certification and review process and allow Federal agencies to receive the same benefits that the private sector is now realizing. A decade or more is too long for Federal agencies to wait to realize the benefits of new security technologies. Let's find a way to get new technologies used more rapidly.

The report goes on to say

Provable security has made the "wait and see" model unnecessary in many cases. If there is a peer-reviewed formal proof of the security of a technology, that should be enough to get approval for Federal use. If the proof is correct then the technology is secure. Why wait ten years or more if that's the case?

I find it hard to argue with that claim. If there's a proof of security then one of two things has to be true: either the scheme is secure or there's an error in the proof. There's no other possible option. So if there's a proof of security, why not let government agencies use the technology?

Here's what the report proposes as an "action plan" for this idea:

NIST should determine a way to quickly approve provably-secure technologies for Federal use and should review existing regulations and identify ways to allow provably secure technologies within them. This should involve, as a minimum, granting a blanket IATO to new encryption technologies with peer-reviewed proofs of security, and adding provably-secure public-key encryption technologies to the list of techniques that are allowed by FIPS 140-2. In the long run, standards and policies should be changed to allow the rapid adoption of new technologies that are provably secure.

And here's how the report recommends that the government start doing this:

Within 90 days, NIST should define and implement a way to approve provably secure technologies for Federal use. Within 180 days, a pilot of one of these technologies should be started at a Federal agency.

This report came out fairly recently. Let's see if NIST actually does what this report recommends

Security insights from the history of radar

I seem to recall reading something interesting a while ago about the invention of radar. I believe that I read this in Luis Alvarez's autobiography Alvarez: Adventures of a Physicist, but I'm not sure. I think that it was Alvarez who said that physicists were better suited for inventing radar because of the biases that electrical engineers had. It seems that engineers in the '30s and '40s typically focused on eliminating or reducing electromagnetic emanations in the radios that they designed, and the very idea that you'd want a system that intentionally radiated EM energy didn't sit well with them. Physicists, on the other hand, had no such bias, so they were better suited for research on radar.

It seems to me that the same sort of biases creep into information security. These biases affect all sorts of things, including what we expect to be feasible and what we consider to be secure.

If you go back 20 years, for example, most people who worked in information security had degrees in either Mathematics or Electrical Engineering. The biases of people with those types of backgrounds are apparent today. Electrical Engineers, for example, wrote the standard that evolved into today's Security Requirements for Cryptographic Modules, otherwise known as FIPS 140-2. These engineers were apparently comfortable with the idea of a circuit board or an integrated circuit, and the FIPS 140-2 standard seems to reflect this mind-set.

On the other hand, they didn't know much about software, and that's also reflected in the FIPS 140-2 standard. If you want an interesting point of view on this, try tracking down the people who navigated OpenSSL through its FIPS 140-2 validation. From what I've heard, one of the hardest and most time-consuming parts of doing this was getting the people at NIST comfortable with some of the concepts that software engineers take for granted but hardware engineers don't really think about at all.

Today, most people working in information security seem to have degrees in Computer Science. This typically means that they understand software fairly well, but don't really know much about hardware. That's probably why so many people were impressed by the so-called "cold boot attacks" that took advantage of properties of hardware. To the previous generation of information security professionals, particularly those with a background in Electrical Engineering, this type of attack seems fairly obvious. On the other hand, if you have little or no exposure to hardware, such attacks can seem like magic.

Today, at the beginning of the twenty-first century, we still don't know how to make secure software. It's actually worse than that: we really don't know how to make software yet. Maybe we could find outsiders from another discipline that could give us some useful insights into how to do this, although I'm not sure who would be good to use in this role.

Some historical perspective

The year 1977 is often described as the year in which public-key cryptography was born. That's when "New Directions in Cryptography," by Whit Diffie and Martin Hellman was published. The people at GCHQ actually knew about the technology a few years before that, but their work was classified. That's why we now talk about the RSA algorithm instead of the Cocks algorithm. It's also why most people think of 1977 as when public-key cryptography was invented instead of 1973, when Cliff Cocks really invented it.

1977 was 32 years ago. To put that into some perspective, 32 years before that takes you back to 1945, which was when World War II was ending. This means that today we're just as close to the invention of public-key cryptography as the invention of public-key cryptography is to the end of World War II.

Lawrence of security

I'm often reminded of the following scene from Lawrence of Arabia.

(LAWRENCE, HARTLEY and POTTER are relaxing in the officers' mess. LAWRENCE shows HARTLEY and POTTER how to put out a match by pinching it between his fingers. HARTLEY and POTTER seem to be quite impressed by this feat.)

HARTLEY: You'll do that once too often. It's only flesh and blood.

LAWRENCE: Michael George Hartley, you're a philosopher.

HARTLEY: And you're balmy!

(POTTER tries the same trick, burns himself and yelps in pain.)

POTTER: It d**n well hurts!

LAWRENCE: Certainly, it hurts.

POTTER: What's the trick, then?

LAWRENCE: The trick, William Potter, is not minding that it hurts.

In particular, I'm often reminded of this scene in the context of information security. There's no doubt about it: information security is hard. And while you can probably work in the field for a while without having to deal with some of the really hard problems that it has, if you stick around long enough, you'll eventually have to face them. Perhaps the trick to having a long career in the field is not minding that these problems are hard.

Seeing red

While editing a standards document this morning, I was reminded of an e-mail exchange that I had a few years ago on the mailing list for an entirely different standard. On this particular list, someone was discussing what bad things an administrator of a certificate authority could do if they abused their administrator rights. They called this a "rouge CA," and really didn't seem to understand why that particular term didn't mean what they thought it meant.

Apparently, people have been confusing the words "rogue" and "rouge" for quite a while. Some people tell me that this confusion became the most obvious in 1987, when people were discussing the game Rogue Trader, inadvertently turning it into a game in which players tried to make a killing trading in either cosmetics or other red-colored commodities.

In any event, after some discussion of the dangers of "rouge CAs," I had to add a comment or two to the discussion that didn't really relate to the security issues that were being discussed. I said that I hadn't heard of a "rouge CA," and asked if these were discussed in a standards document that I hadn't "red." I also made some comment about how I was skeptical about the very idea of "rouge CAs," and speculated that it really wasn't the kind of idea that a reasonable person would "make up."

This may not actually have been as funnny as I think it was.

The replies to my less-than-helpful comments showed that many people on this particular list really didn't understand the difference between "rouge" and "rogue." Based on the additional comments that tried to connect cosmetics and certificate authorities in some clever way, it seemed that one or two other people did, but most didn't.

Oddly enough, the people who were confusing "rogue" and "rouge" all seemed to be native speakers of English. People who had learned English as a second language didn't seem to confuse these two words at all. I wouldn't be surprised if similar mistakes, like marketing people talking about "flushing out" details instead of "fleshing out" details are also generally limited to native speakers of English, but that's a rant for another post.

No more Web of Trust

I recently received an e-mail from Thawte that explained how they are going to discontinue their Thawte Personal E-Mail Certificates and Web of Trust. Here's how they explained this:

Over the past several years, security compliance requirements have become more restrictive, while the technology infrastructure necessary to meet these requirements has expanded greatly. Despite our strong desire to continue providing the Thawte Personal E-mail Certificate and Web of Trust services, the ever-expanding standards and technology requirements will outpace our ability to maintain these services at the high level of quality we require. As a result, Thawte Personal E-Mail Certificates and the Web of Trust will be discontinued on November 16, 2009 and will no longer be available after that date.

The Thawte Personal E-mail Certificates implemented an interesting idea. They assumed that all you can really verify with an e-mail exchange is an e-mail address, so that's all you could have for your identity until you had your identity verified face to face by one or more WOT notaries. Once enough of these notaries vouched for your name, that name could be included in the certificates that you got from Thawte. I was actually one of these notaries, which is why Thawte sent me this message.

The Thawte root CA certificates were in the commonly-used browsers, so this provided an easy way to get a useful, yet free, certificate, and Thawte Personal E-mail Certificates were one of the more common certifictates that you'd see used to sign and encrypt e-mail. It's a pity that we won't have them any more.

You'll still be able to buy certificates with your name and e-maill address in them, of course. Maybe that's really what this was all about.

The HITECH act and compliance trends

The Health Information Technology for Economic and Clinical Health (HITECH) Act that recently went into effect has provisions that encourage, but don't require, covered entities to encrypt PHI. The Interim Final Rule (45 CFR Parts 160 and 164) that implements part of the HITECH Act requires notification of the unauthorized use or disclosure of unencrypted PHI that "poses a significant risk of financial, reputational, or other harm" to an individual.

Some conspiracy theorists seem to believe that this wording was included to allow businesses to avoid the high costs of breach notifications by arguing that their analysis shows that their breach didn't cause a significant risk of harm. A more reasonable explanation is that similar language dates back as far at the original Privacy Act of 1974, and is already included in the existing state breach notification laws.

But if the breach notification requirements of the HITECH Act aren't there to let businesses freely violate our privacy while giving us the illusion of it being protected, why are they there?

The breach notification requirements of the HITECH Act are probably best understood as part of a trend that's slowly but surely increasing the protection that sensitive data needs to have. This started with laws and regulations that required organizations to protect sensitive information, although the exact way in which they protect it is typically very flexible. It then moves to requiring notification of breaches of unencrypted sensitive information. At this point, encryption still isn't required, but there's a strong incentive to use it to avoid expensive breach disclosures. The next step is to require organizations to encrypt sensitive information.

The HIPAA Privacy Rule was the first step in this process for PHI. It required health care organizations to protect PHI, although they could implement this protection in many ways. The HITECH Act is the next step. It essentially requires the notification of breaches of PHI that isn't encrypted. In the future, we will probably see a federal law that actually requires the encryption of PHI. This has already happened in some states.

In 2008, Nevada law (NRS 597.970) required the encryption of Nevada residents' sensitive information when it's transmitted outside a business' secure network. The Massachusetts encryption law (201 CMR 17.00) did the same for Massachusetts residents a short while later. Legislators are now considering similar laws in other states, and similar data encryption laws will probably become widespread over the next several years. It's now hard to avoid complying with these state laws, and it's going to get even harder in the future.

How to comply with these laws in a reasonable way is still an unsolved problem. Legislators want businesses to protect sensitive information, but not at cost that's too high to be practical for a business that needs to be profitable to survive.

Encryption is notoriously hard and expensive to use, but a combination of newer technologies and motivated IT departments is leading to solutions that are much more practical than they were a few years ago. Technologies like identity-based encryption, for example, are at least a factor of three less expensive to own and operate than the aging PKI technology that dates back to the dot-com boom. That's often enough of a difference to make encryption practical where it once wasn't.

Once the states find what works and what doesn't, it's likely that the federal government will raise the bar and require the encryption of all PHI, and when they do this, they will probably base exactly what they require on the lessons that the states have learned. Let's hope that this happens soon.

There has been lots of media coverage of the recent data breaches that have exposed millions of credit card numbers to hackers. But while it's relatively easy to cancel a compromised credit card and get a new one, it's not really practical to cancel and get a new medical history. Once it's compromised, it's compromised forever. Because of this, PHI deserves to have strong protection, and encrypting PHI is the best way to do this. The breach notification requirements of the HITECH Act only encourage encryption, but they're a good step towards ensuring that PHI gets the protection that it deserves.

A new use for anti-virus software

One of the unfortunate realities of life is that standards meetings are often fairly boring. If you're attending one, you might only be interested in an hour or two of a four-hour meeting. If you sit through this for a few days in a row, you can end up fighting a losing battle to stay awake. Or you can try to get other work done. In many cases, people play solitaire or minesweeper on their laptops. If you have Internet connectivity, you can even use your favorite social networking web site to keep yourself entertained until the material that you're actually interested in comes up.

Apparently this happens at more that standards meetings. It seems to affect politicians also, at least ones from Maryland. Maybe that's why the Maryland General Assembly recently banned all elected officials and staff from Facebook and MySpace. Maryland's politicians may not have to sit through an extensive and through discussion of several types of random-number generators before they get to the material they're interested in, but they probably have fairly similar problems.

The memo that announced the ban said it was due to viruses coming from Facebook and MySpace, an assessment that doesn't seem to make much sense. Could Maryland have tried to save money by not keeping their anti-virus software up to date? It seems that would do a fairly good job of stopping viruses, even ones that are claimed to come from social networking sites. Having updated anti-virus software might even help keep politicians awake during meetings. That's a benefit that the marketing people at anti-virus vendors don't seem to have tried to market yet.

The worst user interface ever

I recently encountered one of the worst user interfaces that's even been designed. I came across this on a recent trip to Las Vegas when I stayed at one of the big-name hotels, although I won't say which one.

This particular hotel had an automated system that you could use to set a wake-up call for the morning. You were supposed to dial "*7" and then enter the time you wanted your call set for. When I did this, I heard a loud beeping sound: "BEEP BEEP BEEP BEEP...," with the beeps coming at about three or four per second.

"D'oh!" I thought. "That's not right. Let me try that again." (That's not really what I thought, but that's a version that's suitable for repeating in mixed company.)

I tried again and encountered another annoying sound. This one was a constant tone: "BEEEEEEEEEE."

Giving up on the automated system, I called the hotel operator, who proceeded to tell me that my wake-up call had been set and that the "BEEP BEEP BEEP BEEP..." was how you were told that you had done this and that the "BEEEEEEEEE" was the system's way of telling you that you already had a wake-up call set.

Now I'm not an expert on user-interface design, but I have to believe that using the message "BEEP BEEP BEEP BEEP..." has to be one of the worst ways to tell a user that they've successfully set a wake-up call. Most systems have a message that's closer to, "Your wake up call for .... eight ... a.m..... has been set. Have a nice day." That's one that most users quickly and easily understand. It's also one that probably keeps the number of calls to the hotel operator fairly low, which probably also keeps the support costs for the system fairly low.

On the other hand, the message that I encountered seems like one that's designed to do the exact opposite: to keep the number of calls to the hotel operator as high as possible and to thus keep the support costs for the system as high as possible.

The only way that I can explain the user interface that I experienced is that when a marketing person tried to quantify usability in some way they accidentally dropped a minus sign somewhere. Then, when they passed their design to the engineering department and asked them to maximize the usability of their system the usability was actually minimized instead of maximized. I find it hard to believe that someone really thought that "BEEP BEEP BEEP BEEP ..." was a good way to tell a user anything.

The Tate pairing

Suppose that P and Q are points on an elliptic curve and that the order of P is n. Let f_P be a rational function equivalent to n(P) – n(O) and D_Q be the divisor (Q) – (O). Then the Tate pairing of P and Q is e(P, Q) = f_P(D_Q).

We know how to get f_P and how to evaluate it at a divisor, but the fact that evaluating f_P at the divisor (Q) – (O) would require evaluating f_P at the point O causes trouble. But if R is another point not equal to O, it turns out that we get the same answer when we evaluate f_P at (Q + R) – (R) as we do when we evaluate f_P at (Q) – (O). This means that we can find e(P, Q) by doing the following:

1. Find f_P as we described previously.
2. Pick a random R.
3. Calculate e(P, Q) = f_P(Q + R) / f_P(R).

That’s all there is to it. When I first heard about the use of the Tate pairing in Boneh-Franklin identity-based encryption, for example, I used this very approach to implement the Tate pairing in Mathematica, and it was good enough for that purpose. There are lots of ways to make this calculation more efficient, but for small values of n, what we’ve described is fairly simple to implement.

Evaluating a rational function at a divisor

To evaluate the pairings that we need in pairing-based cryptography, we need to evaluate the rational function that we get from a divisor at another divisor. To understand how to do this, we need to understand what it means to evaluate a rational function at a divisor. This turns out to actually be fairly straightforward.

Suppose that we have a divisor

D = S n_i(P_i)

and want to evaluate a rational function f at D to get f(D). We do this by calculating 

f(D) = P f(P_i)^(n_i)

In the case of the divisors that we’re interested in, we’ll get a rational function of two variables x and y, and we’ll need to think of a point on an elliptic curve as being a point P = (x, y) to evaluate the rational function at the point.

For example, suppose that

P₁ = (-1, 0)

P₂ = (1,1)

D = 2(P₁) – 2(P₂)

and

f(x, y) = (x + y – 1) / (y – 2).

Then we can find

f(D) = f(P₁)² f(P₂)^-2

= f(P₁)² / f(P₂)²

Using P₁ = (-1, 0) we find that

f(P₁) = (-1 + 0 -1) / (0 – 2)

= 1

Using P₂ = (1, 1) we find that

f(P₂) = (1 + 1 – 1) / (1 – 2)

= -1

Combining these, we find that

f(D) = f(P₁)² / f(P₂)²

= 1² / (-1)²

= 1

Getting a rational function from n(P) - n(O)

In a previous post we saw how to add divisors like (P₁) – (O) and (P₂) – (O) and reduce the sum to the form (Q) – (O). Suppose that P is a point of order n and see what happens when we use this approach to evaluate

n(P) – n(O) = (P) – (O) + …+ (P) – (O)

We can do this by first finding

(P) – (O) + (P) – (O) = (2P) – (O) + div(f₁)

where we’ve written f₁ = u₁ / v₁ where u₁ is the line through P and P, and v₁ is the vertical line through 2P and -2P.

Next, we can find

3((P) – (O)) = (P) – (O) + (2P) – (O) + div(f₁)

= (3P) – (O) + div(f₁f₂)

where we’ve written f₂ = u₂ / v₂ where u₂ is the line through P and 2P and v₂ is the vertical line through 3P and -3P.

We can continue this process until we get to

n((P) – (O)) = (nP) – (O) + div(f₁…f_n-1)

= (O) – (O) + div(f₁…f_n-1)

= div(f₁…f_n-1)

Note that by doing this, we’ve found a way to write n(P) – n(O) as the divisor of the rational function f_P = f₁…f_n-1. To calculate the pairings that we need for pairing-based cryptographic algorithms, we want to evaluate f_P, and we can get this f_P through the process that’s described above. That’s almost enough to define how to evaluate the Tate pairing. The rest of what’s needed will be the topic of tomorrow’s post.

Divisors on elliptic curves

Divisors on elliptic curves are important in pairing-based cryptography. They’re useful because the structure that an elliptic curve provides lets you reduce sums of divisors down to simpler sums.

Suppose that we have several divisors

D₁ = (P₁) – (O)

D₂ = (P₂) – (O)

…

D_n = (P_n) – (O)

We can always add the divisors D₁ through D_n to get

D = D₁ + …+ D_n

= (P₁) + … + (P_n) + n(O)

but this gets unwieldy very quickly.

In particular, for cryptographic applications, we want to use a value of n that has at least 160 bits, and we certainly don’t want to think about manipulating a divisor that has 2¹⁶⁰ terms. Fortunately, elliptic curves provide the structure needed to make a calculation like this feasible because they provide a way to reduce a sum of the form (P₁) – (O) + (P₂) – (O) to another divisor of the form (Q) – (O), which keeps the number of terms manageable. Here’s how we can do this.

Suppose that P₁ and P₂ are two points on an elliptic curve and that P₃ = P₁ + P₂. Let u be the line through P₁, P₂ and –P₃, and let v be the line through P₃ and –P₃.The following picture shows how this looks.

Now let's think of points on the elliptic curve as poles and zeroes that define a divisor, so that u has zeroes at P₁, P₂ and –P₃ plus a pole of order 3 at O and v has zeroes at P₃ and –P₃ plus a pole of order 2 at O. This means that we can write

div(u) = (P₁) + (P₂) + (–P₃) – 3(O)

and

div(v) = (P₃) + (–P₃) – 2(O)

Now note that we look at div(u) – div(v) we find that

div(u) – div(v) = (P₁) + (P₂) + (–P₃) – 3(O) – ((P₃) + (–P₃) – 2(O))

= (P₁) + (P₂) – (P₃) – (O)

= [(P₁) – (O)] + [(P₂) – (O)] – [(P₃) - (O)]

or that

[(P₁) – (O)] + [(P₂) – (O)] = (P₃) - (O) + div(u/v)

So if D₁ = (P₁) – (O) and D₂ = (P₂) – (O), this gives us a way to find D₁ + D₂ in a way that keeps the sum in the form (Q) – (O). If we apply this trick again and again, this gives a way to calculate a sum like D = D₁ + …+ D_n, and to do it in a way that keeps the number of terms in the sum small.

As we do this, we’ll accumulate a product of rational functions from the div(u/v) contributions, and in a future post we’ll see how to use that to get a way to evaluate the divisors that we need in pairing-based cryptography.

Exactly how do you find the rational functions u and v?

Suppose that you have u: y = mx + b, or y – mx – b = 0. If that’s the case, you have u(x, y) = y – mx – b.

Suppose that you have v: x = c, or x – c = 0. If that’s the case, you have v(x, y) = x – c.

Divisors

Certain functions called pairings are an important part of the mathematical machinery that make pairing-based cryptographic algorithms possible. Pairings, in turn, are based on the idea of a divisor. These divisors aren’t those you see in elementary number theory, where 4 is a divisor of 12, for example. Instead, they’re a way of keeping track of the zeroes and poles of a rational function.

The zeroes and poles of a rational function define the rational function up to multiplication by a constant. So if we know that we have a rational function with a zero of order two at x = 1 and a pole of order one at x = 2, then the function has to look like

f(x) = c (x – 1)² / (x – 2)

A divisor is a way to keep track of the zeroes and poles of a rational function by using a notation that looks much like addition of integers. We write the divisor of f as

div(f) = 2(1) – (2) – (¥)

What’s in the parentheses tells us where we have a zero or pole and the coefficient in front of the parentheses tells us the order of the zero or pole. Positive numbers indicate a zero; negative numbers indicate a pole. Note that this particular rational function also has a pole at x = ¥, and the divisor that we write for it reflects this.

So if we write

div(f₁) = (3) - (¥)

that tells us that f₁is a rational function with a zero at x = 3 and a pole at x = ¥, so that, up to a constant factor, f₁ looks like

f₁(x) = x – 3

We can add divisors by adding the coefficients of like terms, so that if

div(g) = (3) - 2(1) + (¥)

which corresponds to

g(x) = (x – 3) / (x – 1)²

then we can add div(f) and div(g) to get

div(f) + div(g) = 2(1) – (2) - (¥) + (3) - 2(1) + (¥)

= (3) – (2)

which corresponds to the rational function

h(x) = (x – 3) / (x – 2)

Clearly, adding divisors corresponds to multiplying rational functions, and if we define subtraction in the natural way, it corresponds to dividing rational functions. So we can write

div(f) + div(g) = div(fg)

and

div(f) – div(g) = div(f/g).

Note that the divisor div(1) acts much like 0 does in the integers. In the integers, adding or subtracting 0 doesn't change the value of an integer. The divisor div(1) behaves the same way:

div(f) + div(1) = div(f)

and

div(f) - div(1) = div(f)

The notation for divisors isn’t quite the same as addition, because we can’t simplify divisors by reducing (1) – (1) to div(1), for example.

Tomorrow: divisors on elliptic curves.

Did privacy cause identity theft?

In his article "Did Privacy Cause Identity Theft?" law professor Lynn LoPucki claims that the problem of identity theft that we have today is directly due to the increased privacy that various laws have given us in the past several years. He says that as recently as the '70s, identity theft was very hard for a criminal to pull off because there was so much public information about our identities. And because identity thieves need privacy to commit their crimes, the very privacy that we think is making things better for us has actually made it easier for identity theft to happen.

There's certainly a correlation between the proliferation of privacy laws and identity theft, but attributing the identity theft to the laws may be an example of post hoc reasoning. It seems to me that the ways in which identities were verified in the past didn't really take advantage of the additional information that was available at the time, even though it was available.

Instead of believing that our higher level of privacy has caused the higher rates of identity theft that we see today, I'd guess that it's just a case of criminals using the technology that's available to them. At the same time that stricter privacy laws made it easier for identity thieves to commit identity theft, information technology also proliferated. When this happened, there was much more information available to identity thieves, so they naturally used this information to commit identity theft. I'd guess that's why identity theft is a bigger problem today than it once was, and that the increased amount of identity theft isn't related to the stricter privacy laws at all.

On the other hand, I could be wrong. If that's the case, then I would expect LoPucki's model to predict that identity theft will decrease over the next several years as the proliferation of social networking web sites provides a handy source for lots of public information about our identities. Or I would expect his model to predict that users of social networking web sites suffer less identity theft than people who don't.

I don't believe that either of these will turn out to be true.

The Right to Privacy

The 1890 Harvard Law Review article "The Right to Privacy" by Samuel Warren and Louis Brandeis is probably one of the most influential articles ever written on the topic of the protection of privacy. In this article, Warren and Brandeis argued that common law contained the foundation for effectively protecting privacy and that it was possible to modify and extend common law to make this happen.

From reading "The Right to Privacy," it certainly looks like Warren and Brandeis started thinking about the need to protect privacy because technological innovations were making it easier and easier to violate privacy. We have this same problem today. Cell phone carriers have databases of every call that we make as well as where we are when we make these calls, and e-commerce web sites track every click that you make and every page that you view.

Back in the 1880s, however, the problem was apparently a bit different. The example that Warren and Brandeis use again and again is that of the loss of privacy that the new technologies for photography allow. After all, if anyone can take a photograph without you knowing it, the possibilities for abuse of the technology are limited only by the imagination of the people who have cameras.

From the early twenty-first century, it almost seems hard to believe that cameras could cause so much concern. I wonder if people 100 years from now will have the same reaction to the privacy concerns that we have today. People seem to have adjusted to the widespread use of cameras fairly well, and they seem to have done this by accepting that the violation of privacy that they allow is an acceptable cost of using the technology. It may seem hard to believe now, but we might adjust to today's information technology by accepting that the violations of privacy that they allow. I wouldn't be surprised if that's how things turn out in the future.