FIFTY!!! YAAAYY!!!

So, this is my 50th post. WOOHOOO!!! Enough with the celebrations, we have work to do. I decided to mark this momentous milestone, I will discuss the basics of cryptography. Now, I know I have covered some bits of this before, feel free to skip any parts you think you know. So, let's start by naming  the three principle components of cryptography : Encryption, Signatures/Message Authentication Codes(MACs) and Proofs.


So, let's start with the first, and probably most well-known, section: Encryption. The scenario is simple, you have a message that you wish to communicate to somebody else, without anybody else finding out that message. The way to do this is encryption. Think back to when you were a kid and you and your friends made up a secret language. That could be viewed as a crude form of encryption, as can all languages. But now, lets talk about the more modern stuff.

An encryption scheme is basically two functions: and encryption function, which I will denote by ENC, and a decryption function, which I will denote by DEC. ENC takes a normal message and turns it into something unintelligible, called a ciphertext. DEC takes a ciphertext and turns it back into the message. To do this, both functions need some additional information, called a key. There are two flavours of encryption, both defined by the relation between the keys used by ENC and DEC. In symmetric or secret key encryption, both ENC and DEC use the same key, whereas in asymmetric or public key encryption, they use distinct but related keys.

Now you must be wondering where all these keys come from and how they get to the right people. For the asymmetric setting it's fairly simple. The receiver generates the keys and publishes the public encryption key, PK, and keeps the decryption key, SK, secret. The publication of PK leads to some very interesting problems, but that's out of scope, but worth mentioning. In the symmetric setting, it's a tad more complicated and this problem is a whole research area on it's own. Let's just say that there are clever ways of doing it in several circumstances.

Now signatures/MACs are essentially the same thing, with different key settings. MAC use symmetric keys and signatures use asymmetric keys. They both serve the same purpose, that is to authenticate the source of a message. For simplicity, I will refer to both of them as codes, which is an abuse of many notations, but will suffice for our purposes. All code systems have two functions: generate, denoted GEN, and verify, denoted VER, and they work as follows: generate takes in a message and outputs a tag and verify takes in a message and a tag and checks if the tag was indeed generated by the sender for that message.

Here we must note two very important things. Tags are both sender and message dependant. Thus a valid tag for one message, cannot be a valid tag for another message sent by the same person. Also, a valid tag for a message sent by one person cannot be a valid tag for the same message sent by another person. Thus the VER functions takes as input the message and the identity of the person, implicitly in the key.  The main assumption here is that only the sender can generate a valid tag and thus any valid tag implies that the message was sent by them. This is very close to real world signatures and how we view them. Yes, I know that real signatures can be forged, but we also consider that in cryptography. There are some subtleties as to how this is done, but we shan't venture into that.

Finally, we come upon proofs. These are the least well-known and some would say the least understood of the three. The basic idea behind a proof system is that one party wants to prove to the other that a secret value x has some property. The property could be proven by revealing x, but then that would defeat the point of it being secret. So you need to somehow show that x has this property, but without revealing x. We seem to be in a bit f a pickle. That is, until our hero zero knowledge proofs show. These are protocols which allow you to prove certain statements about a value(s) without revealing the value and without the other person learning anything about the secret value.

A simple way to view this is by the simple statement: "Pick a card, any card!" Let's say I hand you a deck of cards and you pick one out at random and put it aside. Now I ask you what suit it is. You tell me it's a spade. I ask you to prove it. You could show me your card, but that's a secret right? Well, how about you show me 13 clubs, 13 hearts and 13 diamonds. *DING*! Now I know nothing more about your card than that it is in fact a spade. This example is great when explaining not only zero knowledge proofs, but also some of it's stranger variants. But that's all for later (read: maybe if I feel like, but don't hold your breath).

So, all in all, we covered the three basic concepts in cryptography because I'm too lazy to do real posts and the number 50 was just mainly an excuse. We hope to have a resumption of normal service soon-ish.