A conceptual overview of Cryptography

In this class we aim at a gentle conceptual overview of Cryptography and applied Cryptography. As we previously discussed, better programming languages gave us a guarantee against security problems exploiting issues which were inherently caused by undefined behaviors in software execution. Cryptography in the other hand is a more general tool which can be wielded in many contexts to bring guarantees. It is extremely powerful, but extremely brittle if incorrectly wielded, since these so called guarantees may fall. Sadly, it is difficult to get it right. You should never design your own cryptography or even deploy your own implementation of existing cryptography if you did not receive intensive training. This class does not account as an intensive training. However, this class should give you a bit more intuition on why Cryptography is an important concept in Computer security.

We will cover basic aspects and how even these basics tools can help build cool protocols or software, such as a simple privacy-preserving comparison or even Bitcoin.

A brief history

We may regard Cryptography as the Science that studies secrecy. And as a Science, its premise was not really well defined. Take for example modern Chemistry and its ancestor Alchemy that was mixing spiritism and sacred with real chemical reactions mostly around metals. These reactions were not understood, but the experiments were real and its usage with purpose similar than modern sciences, such as medicine. Cryptography has also an history of esoteric approaches with the goal to protect information, as information of course predates computer. Sending a message to an ally hoping that it cannot be understood by a foe is a natural problem which arose likely at the same time we were able to transmit information using letters, numbers and any support to carry them.

History carries a few examples of these esoteric approaches. Julius Ceasar what is referred today as the Ceasar cipher, which is essentially a static permutation over the alphabet: any message written with a Ceasar cipher would be a shift of 3 letters in the alphabet, for each letter.

Vr pdbeh brx fdq txlfnob vwduw wr vhh wkh sureohp zlwk vxfk dq dssurdfk?

An encryption of a message with a cipher is called a ciphertext. The original message is called a plaintext.

In the 16th century, the French Blaise de Vigenère is known to improve the Ceasar cipher with the following idea: instead of permuting the message letter with a static value, the encrypter has to choose a word and keep it secret. The position of a letter in the chosen word influence the shift on a letter of the message. For example, if we choose the word “AAAAAAA”, then to encrypt the message “MESSAGE”, we would do:

 AAAAAAA
+MESSAGE % 26

=NFTTBHF

which is a shift of 1 for each letter of the message “MESSAGE” since A’s position in the alphabet is 1.

Since we can attribute a position to each letter in the alphabet, we can then compute an encrypted letter’s position as \(i + j % 26\) where \(i\) and \(j\) are positions of letters of the chosen word and plaintext respectively. If the chosen word is not long enough to encrypt the whole message, then word is simply repeated.

For example:

 CASSOULETCASSOULETCASSOULETC
+NEJUGEZPASILFALLAITUNEXEMPLE % 26

=PEBMUYKTTUIDXOFWEBVUFWLUXTEG

How would decryption work? Well it is essentially the other way around, using a difference operator instead of a sum to get back the original value.

 CASSOULETCASSOULETCASSOULETC
-PEBMUYKTTUIDXOFWEBVUFWLUXTEG % 26

=NEJUGEZPASILFALLAITUNEXEMPLE

Despite having the concept of key to parametrize the permutation, such encryption are trivially broken when the encrypted message is long enough. The longer the message is, the easier it becomes to decrypt it without knowledge of the chosen word, using a priori statistical knowledge on the input distribution. That is, knowing how likely a given letter is to appear in the text exactly tells us how likely a letter is expected to appear in the ciphertext at certain position(s). The details of how it works is not important here; if you’re interested, it will be covered in INFOM119.

Later, electromechanical machines were invented to add more complexity to the permutations and solve the weaknesses within substitution schemes such as Vigenère. Before and during the second world war, the German worked on and used multiple variants of the Enigma machine that was considered unbreakable at the end of the 30ies.

An enigma machine was essentially composed of rotors, a reflector and a plugboard. The rotors are composed of all the letters in the supported alphabet and rotate each time the person using enigma hits the keyboard, changing the permutation for the next letter to be hit. The output of one rotor would be the input of the next one. Enigma typically used 3 rotors among 5 that were with the machine. The plugboard contributes to add possible configuration settings, swapping letters before and after the rotors permutations. Around 10 swaps were configured on the plugboards. The reflector was designed to have into the machine the capability to encrypt or decrypt with the same initial configuration. The reflector would be permutations of 13 couples of letters connected to the rotors and circling back the output of the third rotor to its input (but with the reflector’s permuted letter).

To understand how the machine worked, it is useful to look at the mathematical description of its algorithm. Let \(P\) the plugboard, \(U\) the reflector (where \(U = U^{-1}\)), let 3 rotors \(R_1, R_2, R_3\), the encryption algorithm would be:

\(Enc = Dec = PR_3R_2R_1UR_1^{-1}R_2^{-1}R_3^{-1}P^{-1}\)

Where \(R_i^{-1}, P^{-1}\) would be the substitution reversed. You can picture the algorithm as a path in a labyrinth connecting one letter to another. The labyrinth changes each time a key is pressed, and there are many, many labyrinths.

These labyrinths are all the possible combinations we have to start encrypting and decrypting, that is, you can also picture this as the number of keys:

• Every rotor can start at a different position: \(26 \times 26 \times 26\) total rotor positions.

• We choose any arrangement of 3 rotors among 5 (that includes the rotors’ position choice among the three selected): \(5!/2!\)

• The plugboard is a little bit more complicated. Say we pair 20 letters leaving 6 untouched. First, we need to select 20 letters among 26, there are \[\frac{26!}{20!(26-20)!}\] possible choices. Once we have selected 20 letters, we need to choose 10 pairs among them. The number of possibilities is equal to:

  \[ 19 \times 17 \times 15 \times … \times 1 = \frac{20!}{2^{10} \times 10!} \]

  This is the same problem than trying to enumerate all possible pairs of students in a classroom for a project, where pairs (s1, s2) is equal to pair (s2, s1) (hence the \(2^{10}\) factor) and where the order of pairs does not matter (hence the \(10!\)).

  The results of both parts is \[\frac{26!}{2^{10} \times 10! \times 6!}\]

We have then these 3 numbers which we just computed that we need to multiply together to have the final number of possibilities, the final number of possible keys:

\( 17576 \times 60 \times 150738274937250 = 158962555217826360000 \)

It is the third number, the plugboard, that hurts! It is there to make the number of possible keys impossible to enumerate during WW2. Without the plugboard, Enigma would have been trivial to break. It took several years and some of England’s cleverest minds to eventually discover a weakness within enigma and exploit it to read Nazi’s encrypted messages.

We have computers now

We don’t encrypt on letters anymore. We encrypt binary strings that may represent any data structure, including letters, but not only. A binary string is a set of bits:

 10101011 11100111

This binary string represents two bytes. Mathematically, we would express the set of all possible 2-bytes binary strings with the notation \(\{0, 1\}^{16}\). So, for a n-bits binary string, the set of all possible n-bits strings is \(\{0, 1\}^n\).

Say hi to Alice, Bob and Eve

We often find the names Alice, Bob and Eve alongside cryptography examples. These have been historically used to explain the basics problems Cryptography would try to solve. The simplest one is secrecy of the communication; although cryptography is much more than that. Alice and Bob want to communicate securely over a wire such as an Internet connection. The wire is watched by Eve playing the role of the adversary. Eve watching the link can see every message exchanged. Can Eve do more than only seeing messages? These sort of considerations are critical. They’re part of the series of assumptions discussed to frame a threat model. Many different threat models exist, and they try to capture real-world scenarios. Different kind of cryptography might be needed depending on the threat model. The goal would then to guarantee to Alice and Bob that their exchange in secure under the specified threat model.

Basic Definitions

A key: A key is a secret value only known to the authorized parties. A key is used as an algorithm parameter changing internally how the algorithm is wired. Most cryptography algorithms support keys from a large space, such as \(\{0, 1\}^{128}\), making enumeration impossible.

CIA in security stands for: Confidentiality, Integrity, Authenticity.

Confidentiality: The idea that the message is not readable/understandable to the adversary. Not to confuse with Privacy.

Integrity: The idea that the adversary cannot temper with the communication without being eventually detected by the rightful recipient.

Authenticity: The idea that we can be sure of the origin of a communication.

Cipher: A cipher is an tripled of algorithms \((Gen, Enc, Dec)\) supporting key generation, encryption and decryption.

Pseudorandom numbers: Characterize a deterministic sequence of numbers that appears uniformly random and unpredictable for anyone that does not have the key (called seed in the case of pseudorandom number generation) to generate it.

Symmetric-key algorithms: Cryptography algorithm that uses the same key for both the encryption and decryption operations. Key are just numbers randomly picked in very large range.

Asymmetric algorithms, or Public-key cryptography: Cryptography algorithm using a pair of related keys: a public key, and a private key. The keypair is generated based on a mathematical problem that becomes unsolvable without the knowledge of the selected private key. The public key can be distributed.

Kerckhoff’s Principle: A cryptosystem should remain secure even when the attacker knows everything about it but not the key. The key should be the only secret.

Kerckhoff’s principle is a cornerstone principle in modern cryptography and computer security, it tells us that anything whose security relies on obscurity is doomed to be broken.

The Core Strength of Cryptography: Provable Security

Modern cryptography is different from what the history gave us. In the history, designing or cracking a cryptography code was all about ingenuity, but it was possible. The 21st-century cryptography has formal foundations, precisely capturing what we mean by being “secure”. By having formal definitions, we can then prove security for schemes or combinations of primitives that are well-defined. We go into a bit more details in INFOM119 regarding how we build the modern cryptography. For this class, we only give a few examples of useful tools from modern cryptography, but we don’t detail or prove their security.

Encryption Scheme

An encryption scheme is a triplet of algorithm \((Gen, Enc, Dec)\), or also called cipher. A cipher needs two properties:

• Correctness; that is, when using the cipher, it should work. More precisely, for any message \(m\), any key \(k\), we have: \( Dec(k, Enc(k, m)) = m\)

• A formal security definition capturing expected security of the cipher against a modeled adversary.

One-time pad

The one-time pad is a symmetric cipher having interesting properties, simple and understandable security guarantees, and is trivial to implement. However, it is impractical in most usage context. Here’s its mathematical definition:

Gen: \(k \overset{R}{\leftarrow}\{0, 1\}^n\)

Enc: \(Enc(k, m) := k \oplus m\)

Dec: \(Dec(k, c) := k \oplus c\)

So, this encryption scheme performs a bitwise XOR operation on the message with the key. The key must then be the same length than the message (since it is a bitwise XOR). That is, for a message \(m = m_0m_1m_2…m_n\) where \(m_0, m_1, …, m_n\) are the bits values of \(m\), and a key \(k = k_0k_1k_2…k_n\), the encryption work bit-by-bit, and we get a ciphertext \(c = c_0c_1c_2…c_n\) where:

\[c_i = m_i \oplus k_i\]

Then to decrypt, XORing again \(k_i\) to \(c_i\) cancels out the \(k_i\), recovering \(m_i\):

\[c_i \oplus k_i = m_i \oplus k_i \oplus k_i = m_i\]

It is not so different than doing an addition then a subtraction with the same value \(v\).

The one-time pad is (perfectly) secure under the condition that \(k\) is chosen uniformly at random, and only used once to encrypt a single message. That makes the impracticability of the scheme. To encrypt a stream of message, or a conversation, we need a keystream as long as the conversation itself.

In WW2 and onward, the one-time pad was used by the Soviets, however the Soviets started to reuse keys that were already used to encrypt other messages. The US were eventually able to decrypt thousands of messages due to multiple key-reuse, due to the following relation:

\[ c_i \oplus c_j = m_i \oplus m_j \]

This relation is true if \(m_i\) and \(m_j\) are encrypted under the same key. The project Venona was eventually declassified in 1995.

The security of the one-time pad comes from the fact that the XOR operation between a uniformly random variable and a random variable results into a uniformly random variable. That is, the output is uniformly distributed, and looks uniformly random.

Other basics mathematical operations have similar properties. For example, if we precise the output space for an addition, say for example 32-bits, then picking any 32-bits integer \(r\) at random and doing \(42 + r \mod 2^{32}\) would be equivalent to XORing 42’s 32-bits representation with \(r\); the result will be uniformly distributed in the range \([0, 2^{32} - 1]\).

Hash functions

A Cryptographic hash function is an algorithm designed to compute a fingerprint of an input, with interesting properties. A hash function is deterministic: upon computing twice on the same input, it gives the same output. Moreover, a small change in the input completely changes all the output in expectation, such that the fingerprint always looks completely random.

The output of a hash function is typically fixed in size. For instance, SHA256 is the current recommended standard, and as its names indicates, it outputs 256 bits. As an example, this document up to this (no space next to it) word has a SHA256 value of 9197d754379dc31c7ec6bb8a3dcac8a22d883fc203166c5c0e7c4581e6a33ac4. If you remove all the following words next to this above, and recompute the sha256 of the resulting document, you should obtain the same value. This indeed assumes that I did not correct a typo or added/deleted anything in the document above, after writing these lines. If that’s the case, you should get a totally different hash value capturing the fact the two documents are different. This is example of interesting property that can be leveraged for the I of CIA. As defined above, I stands for Integrity. Such cryptography hash function can then be used as an Integrity challenge for any resource retrieved on which we want to ensure it did not change during its transfer.

Properties of a Cryptographic Hash Function

• One-way: \(y = H(x)\) can be computer efficiently, however given any \(y\) a hash output, it is computationally infeasible to find an input \(x\) such that \(y = H(x)\).

• Second preimage resistance: Given an input \(x\), it is computationally infeasible to find another input \(x’, (x \neq x’)\) such that \(H(x) = H(x’)\).

• Collision resistant: It is computationally infeasible to find any pair of inputs \(x, x’\) such that \(x \neq x’\) and \(H(x) = H(x’)\). Compared to the Second preimage resistance, here the adversary can choose any starting point.

Due to the pigeonhole principle, collisions always exist. However, we can parametrize the size of the hash function’s output such that having a chance to find a collision is ridiculously small, negligible in term of probability.

If \(n\) pigeons are randomly put into \(m\) pigeonholes with uniform probability \(\frac{1}{m}\), then at least one pigeonhole will hold more than one pigeon with probability:

$$ 1 - \frac{m(m-1)(m-2)…(m-n+1)}{m^n} $$

This comes essentially from the following reasoning:

Let event \(A\) the fact that no pigeonhole has two pigeons or more. Let the complementary event \(B\) that among \(m\) pigeonholes, at least 1 of them hold two pigeons. \(Pr[A]\) means that event \(A\) happens with probability \(Pr[A]\). Since \(B\) is \(A\)’s complement, we have by definition:

$$ Pr[B] = 1 - Pr[A]$$.

\(Pr[A]\) can be computed from permutations: let \(Perm_n\) the total number of ways that \(n\) pigeons can occupy distinct pigeonholes, and let \(Tot_{perms}\) the total number of ways \(n\) pigeons can be arranged in pigeonholes, including occupying the same one multiple multiple times. \(Pr[A]\) would be computed by counting all possibilities in \(Perm_n\) valid for event \(A\) over the total of possible outcomes, that is:

$$ Pr[A] := \frac{Perm_n}{Tot_{perms}} = \frac{\frac{m!}{(m-n)!}}{m^n} = \frac{m \times (m-1) \times (m-2) \times (m-n+1)}{m^n}$$

And now we can trivially compute Pr[B]. The birthday paradox is also known to examplify these equations, and the not so-intuitive results that collisions do happen quite rapidely. Assume \(m=365\) the pigeonholes as the number of days in a year, and \(n=42\) the number of people in the room including your professor as pigeons. Use these equations to compute Pr[B], the probability that among the 365 days in a year, two people from the room share a same birthday. What do you think this probability would be?

PRG

PRG stands for PseudoRandom Generator. As we have seen with keys and with a simple protocol, Cryptography requires randomness. Randomness in cryptography should also have some properties. The general property that we may expect from a generator producing random bits is that its output “should look random”. More formally, this property would be treated using information theory, which is outside the scope of this class. Information theory introduces the concept of entropy to measure the information within a random variable. In our case, we want this information to be maximal, i.e., meaning that the variable may take any value with equal probability. But we we’ll stick with “It should look random” here.

Note however that “It should look random” is not enough by itself. An algorithm may output uniformly random bits, but those could be predicted. If we can predict the output, then we can for example predict the next keys that will be generated from the PRG. That would be terrible. So a PRG output must look uniformly random, and must not be predictable. These are really two different properties. A third one is essentially that observing bits produced by the PRG cannot help us to guess bits that were output before. That would be terrible too in practice. Imagine, we’re using a PRG to produce secret information, and then later we use the PRG to output publicly random values. These public values should not help anyone guess our secrets.

So how could we build a PRG? Again, we have seen enough Cryptography to build (a naive) one. The idea is to build an algorithm that can take in input a strong random value, and stretch it to produce a stream of random bytes. The algorithm should be deterministic. Upon knowledge of the secret input, it should generate the same sequence of random bytes.

Here is a simple pseudocode involving SHA256’s hash function:

fun PRG(key, length) -> [u8] 
  o = init
  output = []
  while len(output) < length do
    o = SHA256(o||key)
    output = output||o
  end
  return output[..length]
end

The key input in the case of PRGs are called a seed. PRGs are usually seeded, and re-seeded every so often using random bytes produced thanks to arbitrary events collected by your machine, such as network packet jitter, CPU execution jitter, mouse movements or filesystem operations, etc. Once we have a good seed, we can input it to such a PRG to produce a long stream of random and unpredictable bytes to anyone not knowing the seed. The security argument of such as construction would be reduced to the security argument of the underlying cryptographic primitive. In this case, we use a hash function. The PRG’s security will hold as long as collision resistance holds, for example.

Stream cipher

Once we have a PRG, we can build something close to the one-time pad, called the stream cipher, with a key that we can keep short. Essentially, since the PRGs has the property we want from a one-time pad key (i.e., uniformly random, unpredictable), then we can replace the one-time pad key by the output of the PRG.

Gen: \(k \leftarrow \{0, 1\}^n\)

Enc: \(Enc(k, m) := PRG(k, len(m)) \oplus m\)

Dec: \(Dec(k, c) := PRG(k, len(c)) \oplus c\)

Note that \(m\) and \(c\) have the same length. Cryptography is all about building stronger primitives and proving they fulfil some formal definition expressing security guarantees.

So, this encryption scheme performs a bitwise XOR operation on the message using a keystream that is deterministically produced once we know the right key. The keyspace should be large enough to avoid anyone “guessing” the keystream by trying keys.

Asymmetric Cryptography

We have good tools to perform encryption and communicate security with symmetric cryptography. However, we still need to be able to boostrap it. That is, symmetric cryptography requires Alice and Bob to share a symmetric key. How can Bob and Alice do that if the channel is insecure and watched by Eve? This problem is answered with public key cryptography.

Public key encryption

In public key cryptosystems, Bob and Alice have both a pair of keys \((sk, pk)\). A private key that they hold for themselves, and public key that they can share to anyone. The fundamental idea of public-key encryption is to exploit a mathematical problem that is easy to compute in one direction but not in the other (without knowledge of the private key). For example it is easy to compute if we have the public key the following result on \(x\):

$$ y = f(pk, x) $$

such that only the holder of \(sk\) is able to compute \(f^{-1}(sk, y) = x\). Other people watching \(y\) and knowing it was computed with \(f\) and \(pk\) would have negligible probability to successfully retrieve \(x\).

Such a function is called a Trapdoor one-way function. There exist various trapdoor functions based on different mathematical problems, such as factoring the product of two large primes, or computing the discrete logarithm on selected mathematical groups.

Once we have a Trapdoor function, designing a public-key encryption becomes easy: we can combine the trapdoor with a symmetric key encryption. Let \(Enc_s\) and \(Dec_s\) the symmetric Enc and Dec algorithms, we define a new public-key cipher as:

gen: key \(k\), and \((sk_a, pk_a)\)

Enc: \(Enc(pk_a, k, m) := (f(pk_a, k), Enc_s(k, m))\)

Dec: \(Dec(sk_a, (y, c)) := Dec_s(f^{-1}(sk_a, y), c)\)

Observe that to encrypt to user \(i\), we need \(pk_i\). Also, we can only decrypt information that were encrypted for us, using our public key.

We’ll discuss later how we can deal with the problem of knowing each other public keys. This problem is called key distribution.

Digital signatures

Digital signatures borrows ideas from Public Key encryption to achieve essentially what we aim at with manuscript signature but with appropriate security. When we sign, we essentially commit to some value to attest it. Anybody checking the signature alongside the document would say “yes, this has been signed by person \(P’\)”. Moreover, we only want person \(P\) to be able to produce a signature that look like \(P\), and if person \(P\) signs, \(P\) cannot say afterwards that they didn’t sign.

In a digital signature scheme, we also generate a pair of keys. We call them signing key and validation key. Say Bob generate a keypair for signing. Bob distributes the validation key to people. Then later, when Bob produces a signature with their signing key, anybody owning the validation key can verify that the signature is valid, and produced by Bob, since the validation key was given from Bob saying ‘hey, here’s my validation key’.

Mathematically, a signature scheme is also a triplet of algorithms:

gen: \((sk, vk) \overset{R}{\leftarrow} keygen()\)

sign: \(Sign(sk, m)\)

verify: \(Verify(vk, (m, s))\)

Observe that Verify takes the message and its signature in input. It only returns true or false.

In practice, a digital signature scheme can be built from combining a trapdoor function and a hash function \(H\).

gen: \((sk, vk) \overset{R}{\leftarrow} keygen()\)

sign: \(Sign(sk, m) := f^{-1}(sk, H(m))\)

verify: \(Verify(vk, (m, s)) := f(vk, s) =?= H(m) \)

Key exchange

The goal of key exchange is for Alice and Bob to exchange a secret under the nose of Eve watching the communication. Such secret can then be used as a key for symmetric encryption.

Let’s assume Alice and Bob both have a pair of public and private keys. Let’s furthermore assume that the public keys have been distributed and that everyone has indeed the public key of the right identity (that is, Alice holds Bob’s public key, and Alice is sure it is Bob’s public key).

If Eve is only watching the channel, Eve cannot understand the communication, since only Bob can inverse \(y\) and decrypt the Hello Message. However what if Eve can modify the communication?

How could we solve this problem? We could add a signature of the transcript! That is, the server would send a signature of the content of all received and generated information, and send that signature. The client can verify whether the data that they send matches the data that the server sees by re-generating the payload that was signed, and verifying that the signature hold over that re-generated payload.

Cryptographic Protocol

Imagine the following problem: Alice and Bob are UNamur students and playing a riddle game organized by the Cercle info. Clues have been hidden in some rooms within the University, and both Alice and Bob are missing some clues they did not find. They decide to share with each other the locations they both found, without revealing any location they are solely in possession.

Assume that both Alice and Bob name each existing classroom with the same integer value, and that the communication run through a server S. Alice has numbers \(a_i\) for the \(i\) rooms where she found clues, Bob has numbers \(b_j\) for the \(j\) rooms where he found clues. Both Alice and Bob wants to learn whether some \(a_i = b_j\), that is they found the same clues. However, if they have not the same clues, they should not learn anything about where they are, i.e., in which room (clues are not in every rooms). That is, if \(a_i \neq b_j\) then Alice learns nothing about \(b_j\) and Bob learns nothing about \(a_i\).

We have seen enough Cryptography to devise a protocol that would be able to solve this problem. First of all, we assume that Alice and Bob share a pair of symmetric keys \((k1, k2) \in \{0,1\}^{128} \times \{0, 1\}^{128}\).

We can initiate this assuming they share both a secret String secret = “…”. Then we can compute \((k1, k2) = SHA256(secret)\), where \(k1\) and \(k2\) are the two halves of the \(SHA256\) output. Both Alice and Bob know \(k1\) and \(k2\).

Bob: Choose a random \(r \in \{0, 1\}^{128}\), and compute \(x_b = r(b_0 + k_1) + k_2\). Bob sends \(r, x_b\)to server S.

Alice: Alice sends \(x_a = a_0 + k_1\) to Server S.

Server: Computes \(x = r \times x_a - x_b\), Send x back to Alice.

Alice: check if: \( x+k2 = r(a_0 - b_0) \)

Observe that this equality could be true due to two possibilities:

• \(a_0 = b_0\)
• \(r = 0\)

In this protocol, we assume that \(r\) can never be 0. In practice, it is easy to enforce. So what does Alice learn?

if \(a_0 \neq b_0\), then the quantity \(r(a_0 - b_0) \mod 2^{128}\) is uniformly distributed in \(\{0, 1\}^{128}\) (property of a uniform random variable). So Alice does not know anything about \(b_0\) except it is different from \(a_0\).

Bob learns nothing.
Server learns nothing.

Note that the threat model of this protocol is a honest-but-curious server that plays the protocol honestly (for example, it would not reveal \((r, b_0)\) to Alice, or reveal \(x_a\) to Bob).

If we want Bob to learn something too, we may restart the protocol the other way around, however the keys need to be updated to keep the Server in the dark (recall we consider the server to be honest but curious). Otherwise the protocol would be insecure regarding our threat model, since the server could learn some information about \(a_0\) and \(b_0\). How to update the keys? Alice and Bob may have agreed on the following:

$$(k1, k2) = SHA256(counter||secret)$$ where the symbol \(||\) means concatenation. So each time Alice and Bob restart the protocol, they increase the counter by 1 and recompute keys using SHA256. There you go, with this protocol, Alice and Bob who don’t trust each other can both learn which room they have in common, and eventually decide to share the one that they don’t.