Heatherweight Encryption: Provably Brilliant Crypto

James Heather (No Institute Given^**)

[This is the complete text of a paper to appear in due course in the highly esteemed Journal of Craptology.]

Abstract. Most fashionable cryptosystems suffer from many drawbacks: they produce inefficiently long ciphertexts, they take a tediously long time to perform their basic operations, and they are vulnerable to any number of troubling attacks. In this paper, we¹ propose a cryptosystem that excels in every respect. We give proofs of optimality of security, algorithmic complexity, and ciphertext size.

1 Introduction

The world has long suffered under the weight of such behemoths as RSA, ElGamal, the so-called ‘Advanced’ Encryption Standard, the so-called ‘Secure’ Hashing Algorithm², and that one where you wrap a strip of paper round a pencil. Every one of these is so inefficient as to be amusing. They take far too long to encrypt, produce ciphertexts that are big and unwieldy, and can be cracked with minimal effort. A small personal case study will serve to illustrate.

Mr Fardoso on his way to the bank

Last year I received an email from Mr Daniel Fardoso, the terminally ill nephew of a deceased Nigerian diplomat, who needed my help in shifting a large quantity of money so that he could live out his remaining months in peace and comfort. Modesty forbids recounting the many reasons that Daniel gave for choosing me to entrust with this task; suffice it to say that he seemed to have every confidence that I had the qualities he was looking for. He asked me to fill in a simple and supposedly secure web page with my bank details, my mother’s maiden name, my passport number, and my name and address. Naturally, I concurred; and, when I clicked on the ‘Submit’ button, a window appeared telling me that it was encrypting the file for safe transmission to Daniel.

Until that point, I had expected that modern cryptographic methods would work securely and efficiently. Much to my disappointment, it was still encrypting the file some three hours later when I retired for the night. In the morning, on discovering that the encryption still had not finished, I sent Daniel an email expressing my concern; he reassured me that there was no sign of any problem at his end.

You can imagine my shock when I received a phone call from the police that afternoon, informing me that £35,000 had been cleaned out of my account! It distresses me to say that they tried to blame first Daniel, and then me, for the security breach. My complaint that I had taken every precaution to encrypt the file securely fell on deaf ears.

So much, then, for current encryption systems! Two honest, law-abiding citizens attempt a supposedly secure transaction, and the hackers take full advantage. One cannot help concluding that if the encryption had been faster, then Daniel and I might have had time to stop the theft; and if it had been more secure, then the hackers would not have been able to break it in the first place.

2 Analysis of current systems

Figure 1 gives more technical insight into the inadequacy of currently available cryptosystems.

Figure 1: RSAges-to-encrypt

The graph is self-explanatory. Small wonder that hackers are winning the battle against security experts, the banking system is in crisis, teenagers lurk around every corner drinking Hooch and smirking, and I wake up screaming in the night, scared of my own hands. A radical new approach is needed.

This paper solves all these problems. It is no exaggeration to say that the encryption algorithm proposed here does for cryptography what Isaac Newton did for physics, what Alexander Fleming did for medicine, and what Monica Lewinsky did for Bill Clinton.

3 Heatherweight encryption

We have seen that existing algorithms are both heavyweight and cumbersome. In this section, we give the details of Heatherweight³ encryption, a simple and yet effective reinvention of the field.

The encryption algorithm is perhaps the simplest algorithm one could ask for. To encrypt a message m using key K, we calculate

E_K(m) = <>

In other words, the ciphertext is the zero-length bitstring.

4 Proofs of optimality

We now give proofs that Heatherweight encryption is optimal in terms of ciphertext length, algorithmic complexity of the basic operations, and security.

Theorem 1 (Optimality of length of ciphertext): Heatherweight encryption produces ciphertexts that are of optimal size for data transmission and data storage.

The whole Internet, safely encrypted

Proof. Ciphertexts are zero length, regardless of the length of the input message. This means that the encryption also provides a level of compression that would make Huffman weep horrible tears. Any number of ciphertexts can be transmitted in zero time, and can be archived on even limited capacity storage media without using up any space. Using Heatherweight encryption, one can compress the whole of the Internet, and scribble the resulting ciphertext in full on the back of an envelope—without even needing a pen!


Theorem 2 (Optimality of algorithmic complexity): Heatherweight encryption and decryption are optimal in their time complexity.

Proof. It has long been assumed that the very best one might hope for, in terms of time complexity of encryption and decryption, is linear, simply because the algorithm needs to examine the whole plaintext to construct the ciphertext. However, the genius of Heatherweight encryption is that it produces ciphertexts that are independent of the plaintext. Encryption can therefore be done in constant time:

public byte[] encrypt(byte[] key, byte[] plaintext) {
    return new byte[]();
}

But what about decryption? It is obvious that for many encryption systems, the main security weakness is the decryption algorithm. Sometimes this is because of a flaw in the algorithm itself that allows an attacker to break the ciphertext without needing the key; but there are also timing attacks and suchlike to consider. Even in the absence of these tactics, there is still the possibility that the key will leak, or that the keyholder will be tortured and forced to send the key to the attacker along a rubber hose.

Heatherweight encryption solves these problems by simply not providing a decryption algorithm. Security is considerably tightened by this technique, as we shall see.

This means that decryption can also be considered a constant-time operation:

public byte[] decrypt(byte[] key, byte[] ciphertext) {
    throw new OperationNotSupportedException("meh");
}

Theorem 3 (Perfect security): Heatherweight encryption provides perfect security.

Proof. An attacker with access to a decryption oracle is unable to distinguish between E_K(m₁) and E_K(m₂), because all encryptions are the same, so it is impossible to distinguish anything at all. Note that we have not reduced this simply to an underlying hard problem, but to an impossibility.

This even thwarts a 24 attack. Normally Jack is able to beat the decryption key out of anyone, and Chloë can crack any encryption, though usually not until 23:59:57. However, with Heatherweight encryption, even if Jack makes me send him the key down the rubber hose, and Jack then sends it through the hose to Chloë, she is not going to be able to get anything other than OperationNotSupported exceptions.

5 Conclusion

Heatherweight encryption changes everything. Just as everyone remembers where they were when they heard that JFK had landed on the moon, so everyone will remember the day when they entrusted all their backups to the power of Heatherweight encryption.

6 Future work

Almost too good to be true

Research is already underway to construct a hash function based on Heatherweight encryption. I conjecture that the Heatherweight encryption algorithm itself could be used directly as a constant-time hash function; but I need to spend some time convincing myself that it would be collision resistant.

Infinite-capacity hard drives with transparent Heatherweight encryption will soon be available. A prototype is already in existence; write speeds are nothing short of phenomenal, though we are having teething trouble with the read operation, which for some reason keeps throwing OperationNotSupported exceptions. An investigation is underway.

Acknowledgements

The author is grateful to Antonio Banderas for inspiration. It was while watching his performance as Zorro that the zero function first surfaced as an idea for an encryption algorithm. Previous meditations on his co-star had led to consideration of the zeta function ζ(s) = Σ 1/n^s, which did not work nearly so well.

---

Footnotes

^**The University of Surrey’s legal team has formally requested that this work be submitted in a purely personal capacity.

¹I use the royal ‘we’, but the sad fact is that I was unable to persuade anyone to act as co-author. My initial aim was to break the world record for the number of authors on an academic paper, but, owing to what must be considered a terrible short-sightedness on the part of the eighty or ninety people I approached (including my own mother), the current record must stand.

²SHA is currently on its 256th version! The first 255 versions go belly up, and they expect us to take SHA256 seriously!

³I am indebted to Peter Ryan for the name ‘Heatherweight’. Nonetheless, the University of Luxembourg’s legal team has asked me to clarify that ‘this does not reflect recommendation or endorsement of any of the rather confused ideas represented in this paper’. One is reminded of Decca Records’ decision in January 1962 not to offer the Beatles a recording contract.

Conversion Of A Sad Man

What's the most theologically correct way to become a Christian? Are there tried-and-tested techniques? Traps to beware of?

As far as traditional options go, consensus among theologians is that the three most prestigious methods are:

1. Seeing A Blinding Light;
2. Climbing Up A Tree;
3. Being Healed Of Paraplegia.

Obviously the third takes a little preparation and involves a certain amount of risk. You will need four friends and a big hammer.

At the other end of the scale, common schoolboy errors include:

1. Building Some Barns;
2. Putting One's Hand To The Plough And Looking Back;
3. Going Away Sad.

These generally lead to trouble, and are to be avoided.

But what of the modern Gentile? How is he or she to move from darkness to light?

I can only offer you the benefits of personal experience. The following short video clip (I had no idea I was being recorded!) details my own conversion, and even the exact moment of regeneration.

I believe this is the first time that the precise mechanics of quickening have been captured on film. Scientists will no doubt get straight to work attempting to reproduce the phenomenon under laboratory conditions.

Anatomy of a ballot form

I still have a few Santander shares, ultimately dating back to the carpetbagging era and the sad demise of the Alliance & Leicester Building Society.

Recently I received my ballot paper for the forthcoming Santander AGM; and it represents a masterpiece of ballot design. There are twenty-five resolutions up for debate, with the self-explanatory names 1A to 12. I am supposed to reflect prayerfully on each, and then indicate whether I am in favour of the motion or against it. So far, so good: each resolution has a For box and an Against box to assist me in informing the General Secretary of the results of my twenty-five coin tosses.

For or against?

But wait! What if I'm unable to decide? Shouldn't I be allowed to abstain on some of the motions, and leave the decision to wiser heads? Should I just leave both boxes blank?

Careful: my eye catches sight of Note 1:

If you return the form and do not mark a box for an agenda item it shall be deemed that your vote is in favour of the Board proposal.

So a blank vote is the same as a vote in favour! One wonders why they need the For box at all. But back to the question: how can I abstain? Fret not: they've thought it through, and added a row of Abstain boxes below the For and Against boxes.

For or against or abstain? Or just leave it blank if you want to vote in favour.

That's a relief. Spurred on by the promise of "this fantastic credit/travel card wallet*" for returning my ballot paper,

*Stocks are limited.

I can now get down to the serious business of voting.

Hang on, though: what's that fourth row of boxes doing? Thoughts of that fantastic credit/travel card wallet can wait until I've sorted that out.

Should I tick the Blank box? Or just leave it blank?

So I can vote For, or vote Against, or Abstain, or leave it blank (which is the same as voting For), or I can vote Blank. That's the same as leaving it blank, right? So it's a vote in favour?

According to the By-laws of Santander, any proposal at the Annual General Meeting may be voted in favour, against or in blank. From a practical viewpoint, a vote in blank effectively works like an abstention.

So voting Blank is not the same as leaving it blank. "Voting in blank" (i.e., voting Blank) is the same as voting Abstain, whereas leaving it blank is the same as voting For. Got it. I can almost feel this fantastic credit/travel card wallet*

*Stocks are limited.

in my pocket.

But I needn't bother with filling in the paper at all: Santander, being efficient and eco-friendly, provide a means of voting online, and I, being married to a treehugger, feel compelled to take advantage.

The online voting web site offers many blessings unknown to the traditional voter. Not only does it provide effective protection against paper cuts, and the promise of a credit/travel card wallet every bit as fantastic as the one enjoyed by paper voters; the web site also fulfils its disability obligations by catering for those with split personality disorder. For each resolution, I can vote against myself by allocating some shares For, some Against, some to Abstain, and some Blank! Any unused shares will presumably be treated as blank (not Blank). No more worries about whether I did the right thing: I can hedge my bets and cancel myself out. Just a word of caution: remember that blank is the same as For, and Abstain is the same as Blank. So a truly agnostic vote doesn't allocate 1/5 of one's shares to each box: you want 1/6 of the votes For, 1/3 Against, 1/6 Abstain, 1/6 Blank, and 1/6 blank.

Maybe voting against myself is a little over the top. Let's hang the notion of voting against myself, and make a firm decision on each resolution. In which case I have twenty-five resolutions, and five options for each; so let's fill in the form like this:

That, according to the stated rules, is five resolutions marked For, five Against, five Abstain, five Blank(=Abstain), five blank(=For). So that's more positive than negative, but presumably the Board know roughly what they're doing, so maybe that's fair enough. I wouldn't want to be so spineless as to be overall neutral. Let's go ahead and cast the ballot.

And now the crowning irony. Here's the confirmation page:

D'oh! Your vote has been counted (errors and omissions excepted)...

When Stroke Strikes, Act F.A.S.T. (2011 edition)

Every so often, something comes along to revolutionize medical science. In 1928 it was the discovery of penicillin; this week we found out that coffee, nose blowing and sex are nigh-on certain to give you a stroke.

This necessitates some sort of public health campaign to make people aware of the dangers. The NHS's "Act F.A.S.T." poster will, of course, have to be redesigned.

Fortunately, I've managed to get hold of an early draft of the new version. Expect to see this on bill boards around the country soon.

Take your pen and your ballot paper, shut your eyes, and...

One of the most debated points about AV is whether it is too confusing for members of the public to understand. Nick Clegg says it's dead easy; David Cameron says it's much too complicated. Who is right?

Cameron looking confused

Clegg says that it's as easy as 1, 2, 3: all you have to do is to rank the candidates in order of preference. And once you stop having preferences, you stop ranking. It's no more complicated than asking someone to get you a cheese sandwich, and telling them that if there are no cheese sandwiches left then you'll have a tuna one instead. How can that be hard to understand?

Cameron, on the other hand, quotes from a book explaining AV:

As the process continues the preferences allocated to the remaining candidates may not be the second choices of those electors whose first-choice candidates have been eliminated. It may be that after three candidates have been eliminated, say, when a fourth candidate is removed from the contest one of the electors who gave her first preference to him gave her second, third and fourth preferences to the three other candidates who have already been eliminated, so her fifth preference is then allocated to one of the remaining candidates.

He's read it several times, he says, and still doesn't understand it; and he suspects most people will have similar trouble. How can anyone say that AV is easy?

So who's right?

Clegg looking simple

Essentially, they both are: they're talking about completely different things, one of which is simple, and one of which is complicated. Clegg says that AV is simple because it's easy to understand how to vote; Cameron says that AV is confusing because it's difficult to understand how the votes are added up. What you will have to do at the next general election, if the referendum gets through, is just not that complicated, and pretty much anyone can do it; but understanding how the numbers got turned into results is much harder, and is highly likely to fox a large proportion of the electorate.

So where does that leave us? The key question underlying this is: what should voters be expected to understand? Is it enough that they understand how to vote, or should the vast majority of voters also be able to understand how the votes are tallied?

One could make a good case for either side. One might well argue that as long as enough people understand the system and are satisfied that it is fair, then it doesn't matter if some other people don't understand the full details, as long as they are able to cast their vote. But it could also be argued that the democratic process should be transparent to everyone, that I have a right to understand what happens to my ballot paper after I drop it in the box, and that if the process is too confusing for me to follow then I'm denied full participation in the election.

I don't know the answer. But it is rather disappointing that the question hasn't been discussed, because it is an important one.

If you think that everyone should be able to understand how the votes are tallied, then AV is, as Cameron says, too complicated, and I don't see how you can support the referendum.

If, on the other hand, you think that that is unnecessarily strict, and that it is sufficient for voters to understand how to cast their votes, then AV is, as Clegg says, perfectly simple, and you might be happy to support the referendum (though this would only rule out one argument against it, rather than provide a conclusive argument for it).

But that's something you'll have to think through for yourself.


Oh dear. Confusing, isn't it?

Are these the nails used to crucify Jesus?

No.

The Bottom Line: which cubicle?

One might think that a couple of months in Australia would be relaxing and refreshing, with freedom from the worries of everyday life. Unfortunately, it's one difficult decision after another.

Playing The Odds: In Search Of A Royal Flush

Yesterday, I was faced with a serious problem. I badly needed to take a dump. At home, that's not too much of a problem: realistically there is only one toilet that can be considered adequate, so there is no decision to be taken. Also, there is no danger of contamination: there are only two of us who live there, and I have reluctantly learnt to embrace Helen's bum as if it were my own. But I was at the University of Melbourne, and the situation called for some careful thinking: five communal toilet cubicles, and I knew nothing of their history. Where should I park?

As you enter the little boys' room, you are met by five cubicles on your left, with sinks on the right. The cubicles are not all equidistant from the entrance; and this is what gives the problem its crunchy texture. How do you find the least-used toilet?

Let me present you with my own reasoning, and then give you a chance to decide for yourself.

Pure Gamble? Let's Shoot Some Craps!

Obviously Cubicle 1 is out. It will receive far too much traffic from unthinking visitors who rush in where angels fear to sit. Pass by on the other side.

Doing one's business in Number 2 would have a poetic ring to it, but would also be misjudged. Plenty of customers will no doubt sensibly rule out the first toilet, but take the analysis no further, and dive head first into the second one. Besides, whenever the first cubicle is occupied, thoughtless types are going to be drawn to the second.

Now it gets harder. I suspect that the furthest cubicle would attract the naturally reclusive and socially withdrawn; and there are plenty of them in a typical computing department. So it, too, probably gets more than its fair share of attention. Number 5 would be a bum steer.

That leaves us with Cubicle 3 and Cubicle 4. What to do? It is tricky to make a strong case for one over the other. For a while, there was a serious danger that I would stand fixed for ever, equidistant between the two cubicles, like Buridan's famous ass. But at least the worst his ass had to look forward to, in the short term at any rate, was getting a bit peckish: my own ass, analogically speaking, was likely to force the issue if it didn't get some outside direction soonest. I had to make a choice.

Why would someone end up in Number 3? There are two plausible reasons:

1. Someone is occupying Number 1 (highly likely), and our new chap wants to place a respectable distance between himself and the current occupant of Number 1. My guess is that in this case he would be likely to go for Number 3 (sufficient distance) or Number 5 (as much distance as possible).
2. When all cubicles are empty, going in Number 3 preserves the symmetry. It may well appeal to a certain mathematical way of thinking that could be prevalent among computing academics.

Neither of those is a watertight argument, but on the other hand, I couldn't see any reason at all why someone would end up in Cubicle 4.

So, flying, to some extent, by the seat of my pants, I made friends with Number 4.

But I couldn't sleep last night.

The nagging thought: did I get the wrong one?

Have I embarrassed myself with foolish reasoning?


What would you have done?