Proofs in Cryptography: Lecture 1 Encryption Schemes

Proofs in Cryptography: Lecture 1 Encryption Schemes


Dear students these videos are not meant to replace the course material but they are meant to assist you.
So let us start today by talking about encryption remember we first want to define what it means that a scheme is an encryption scheme for that we need to define first of all spaces a key space lets say K a message space M and a ciphertext space C
and where are we going to use these First of all, we want a key generation
algorithm lets call it Gen that takes as input a security parameter
and in the unary format. Why because we want this Gen algorithm to run in polynomial time with respect to N and this Gen algorithm will generate
a key lets say little k for us now what are we going to do with this key we want to encrypt let’s say the using the
Enc algorithm using this key some message M and this encryption is going to give us a ciphertext little c we want to decrypt this cyphertext using the Dec algorithm they are going to use the same key here for now assume we are using a symmetric key encryption scheme we will get this ciphertext and it should produce us let’s call some m’ once we define the Gen algoritm indeed the Gen algorithm implicitly defines the key space the key space is you can define it as the set of all the keys that are generated
through the Gen algorithm similarly the ciphertext generated by the encryption algorithm the set of them implicitly
define the ciphertext space C
what it means is that to fully define an encryption scheme we need to define the message space, the Gen algorithm Enc algorithm and Dec algorithm once we define
these three algorithms and the messages space we now have an encryption scheme now we want to talk about what it means for an encrpytion scheme to be correct we define this using a probabilty so we define an experiment within the probability first we need to generate a key. Let’s
generate it through our Gen algorithm and give it to the security parameter next we encrypt using this key and this is going to give us a ciphertext
following that we will decrypt using the same key again and this is going to give us some m’ such that overall what we want is that this m’ is indeed equal to the m that we encrpyted. now we want this probability to be let’s say equal to 1 which means the scheme is always correct
this k, key is coming from the Gen there’s no
problem there. the C here is coming from the encryption as the output
there is no problem there m’ is coming from the output here what about m? we haven’t define that what we want to say is that this
encryption scheme is correct for all m, for all messages in our message space so we want that for all messages in our message space if
we generate a key then encrpyt that message and then the decrpyt it
we will get back the same message with probability 1. You may relax this assumption let’s say by saying with
probability 1 minus let’s say some negligible function in the security parameter in general this is a perfectly fine correctness definition but most of the time you will not need this
negligible here for correctness because already
existing encryption schemes achieve this with probably 1 correctness

2 thoughts to “Proofs in Cryptography: Lecture 1 Encryption Schemes”

  1. Hi Alptekin,

    Your lectures are very useful to me. I also would like to make a series of other lectures. Could you tell me, what materials and software you use to make the lecture. Thanks?

Leave a Reply

Your email address will not be published. Required fields are marked *