We have our protagonists, Alice and Bob that want to communicate securely using some channel.

We have an eavesdropper, Eve, who might have access to the communication channel that Alice and Bob use.

To transmit their messages securely, Alice and Bob use a secret key, that is known only to the two of them, and not to Eve.

These are called private-key cryptosystems.

Such an encryption scheme consists of two processes,

Obviously, we want such a scheme to give us the correct message after decoding. Therefore, we demand,

Such a scheme of encoding is called correct! It is easy to come up with an example of such a scheme, for example let , that is send the message as it is.

But as you realise, sending the message as it is is as insecure as it gets. So, we need a notion of security.

For example, if Alice would be equally likely to send any out of messages to Bob, even after reading the encrypted message, Eve cannot guess the message better than with a probability of .

It is easy to come up with an example of such a secure scheme as well, we can just ignore the message and send randomly any cipher-text , for example by flipping a coin and sending or .

Both the trivial schemes we designed didn't even use a key. How necessary is a key?

To illustrate the proof, let us look at an encoding/decoding scheme.

Let Alice send two bit messages, , , , by using a key of size , by flipping the first bit if and leaving it as it is otherwise.

Let's say Alice send the message and with , without having any access to the cipher-text Eve's guess is correct only with probability.

But after obtaining the cipher-text , Eve can compute the space of possibility for the message, i.e and , which implies that Eve can guess the plain-text with the probability .

This implies that the scheme is not secure.

So can we come up with a scheme that is both secure and correct with ?

It is easy to check that this scheme is correct, i.e for any , we have

We prove that is is also secure.

Note that the security of a scheme highly depends on the knowledge of the eavesdropper about the secret key, encoded in the distribution .

Here, a critical assumption that we make is that in Eve's perspective, all keys are equally likely, i.e .

And let's assume there is some prior distribution over the messages, . Note that this may or may not be uniform.

The goal is to show that for all ,

Therefore this scheme has no extra "information" in the cipher-text given no-knowledge of the key.

How can this be extended to a quantum bit?

How to hide the quantum information from an eavesdropper?

Let's say Alice sends a quantum state to Bob, and this is intercepted by Eve. How can we encode the state to ensure that Eve doesn't gain any access to the information?

Again, we need to provide the definition of correctness and security of this scheme.

Let us design a one time pad for qubits, with a key size of by adopting the bit flip approach. Then, for , we have,

This is a correct scheme! But is it secure?

Although for this works, it fails for , as you get

We use bits to encode one qubit,

Clearly the scheme is correct. But is it secure? Yes, by the following lemma

This can be generalised to encoding qubits, by using bits. Can you write the encoding operation?

In this section, we want to understand the privacy of the secret key that we use for the other cryptographic protocols.

Let's say Alice owns a classical register with the key of size written. Eve can hold the following joint quantum state with the register.

These are known as classical-quantum states.

Ideally, we want this state to be of the form such that Eve can gain no information about the key that Alice and Bob possess. This condition means that Eve is ignorant of the key.

To start with assume that the state of Alice and Eve is uncorrelated, but Alice (from the perspective of Eve!) has a state where is not a uniform distribution.

One might be tempted to measure the uncertainty of the obtained key in terms of the Shannon Entropy of , as obviously this is maximised if and only if Alice's state is uniform.

Let's assume that that the key is guaranteed to have an entropy of , and we wish to perform the one-time pad with this key. Is this good?

But this means that if Eve guesses the key to , she is right about percent of the time, and also decrypt the message with probability .

So overall, even though the Shannon Entropy might be very high, the protocol is not cryptographically that secure. We need a better measure for uncertainty.

Calculating the minimum entropy for the previous distribution, we get for all sizes of the key,

Effectively, the min entropy measures what Eve can do with the best guess of the key which is exactly as compared to Shannon entropy that measures what Eve can do with the average guess

We have the following inequalities,

Given a classical quantum state, we want to define a quantity that captures the information Eve can gain about the classical register from her part of the correlated quantum state .

For a classical quantum state , Eve has all the information about the key. Therefore, we get choosing .

For the uncorrelated state , we obtain
Moreover, we obtain this equal to for the following choice of POVMsuch that

Therefore, we get .

The final goal for today is to understand general "quantum" conditional min entropy.

How can a quantum system gain maximum side information about another system? If it is completely correlated with the other system. In quantum mechanics, a stronger form of correlation also exists in form of the maximally entangled state.

It is a quantum state that is "correlated" in all basis. We use this to define the conditional min-entropy for general quantum states. Intuitively, to be the adversary, we want to do the best quantum operation on Eve's end to gain maximum correlation with the "key" system, possibly in all basis!

This is equivalent to the following definition,

The proof of this equivalence will be shown in the next session.

Right now, we look at the following exercise. Compute the