The Legend of Fujisaki and Okamoto The Return of the Oracles

Chapter 1: The Quest Begins

In the realm of Pi, Fujisaki and Okamoto, two valiant adventurers, embarked on a perilous quest to upgrade the CPA shield. Their mission: to protect Pi from the dark mistress Eve, who threatened to plunge the realm into eternal shadow with the aid of the enigmatic Oracles, a sect of ethereal entities. Guided by ancient maps and cryptic prophecies, they journeyed through enchanted forests and treacherous mountain passes, facing numerous trials along the way. Their ultimate goal was to reach the Forbidden Caverns, where the secrets to unlocking the CCA shield awaited them.

Chapter 2: Trials of the Forbidden Caverns

Entering the Forbidden Caverns, Fujisaki and Okamoto faced the guardian Zephyrus, a towering stone golem. Zephyrus tested their resolve with grueling trials, pushing them to their limits. But Fujisaki and Okamoto proved themselves worthy, demonstrating courage, wisdom, and unwavering determination. Impressed by their valor, Zephyrus bestowed upon them the Key of Ancients, the final piece of the puzzle needed to unlock the true potential of the CPA shield and stand against the Oracles, who watched from the shadows, ready to thwart their efforts.

Chapter 3: The Protection of Pi

Fujisaki and Okamoto returned to Pi, inserting the Key of Ancients into the CPA shield. With a brilliant flash, it transformed into the CCA shield, radiating potent magic. They placed the CCA shield upon its pedestal in the heart of the castle, creating a barrier that encased the entire realm. The barrier hummed with the essence of pure magic, repelling the dark forces of Eve and the Oracles, ensuring the safety of Pi. Thus, Fujisaki and Okamoto fulfilled their quest, protecting their homeland without engaging in a final battle, and securing the future of Pi for generations to come, even against the might of the Oracles who had once aligned themselves with darkness.

Chapter 4: Decades of Peace

For decades, the realm of Pi basked in the peace safeguarded by the CCA barrier. Fujisaki and Okamoto’s legendary deeds faded into the annals of history as the memory of Eve’s threat became a distant echo. However, unknown to the inhabitants of Pi, dark whispers began to stir once more in the shadowy corners of the world. Eve, dormant for so long, had amassed even greater power during her absence, plotting her return with renewed malice.

Chapter 5: The Evolution of Darkness

As Eve prepared to return, the Oracles underwent a sinister transformation. Through the mysterious Quantum Gates, they evolved into Quantum Oracles, transcending their former limitations and gaining the ability to bypass the protective barrier of the CCA shield. With their newfound power, they pledged allegiance to Eve once more, serving as her agents of chaos and destruction.

Chapter 6: Fabrizio’s Mission

Amidst the looming threat of Eve’s return, a new hero emerged. Tasked with a mission of paramount importance, our hero received the O2H sword from the venerable Master Majenz. Crafted from the purest essence of light by Master Unruh, the O2H sword held the key to defeating the darkness that threatened to engulf Pi once more. But first, our hero must find a way to sharpen the sword, unlocking its full potential and ensuring that it would be a formidable weapon against the forces of evil.

This is a fun story with some insight from my project:

Given a Public Key Encryption (PKE) scheme or a Key Encapsulation Mechanism (KEM), we can define several notions of security based on the capabilities of the adversaries they have to deal with. To define a security notion, we usually define a security game and impose constraints on the adversary who can play this game. We say that a protocol is secure, according to the security notion being tested, if there is no adversary who can win the game with “good” probability.

One of these notions is INDistinguishability under Chosen Plaintext Attack (IND-CPA). Let’s describe the game used to define this notion for PKEs. In this game, an adversary can choose two messages and get back the encryption of one of the two, also known as challenge ciphertext. The goal of the adversary is to determine which message has been encrypted.

A higher level of security is provided by the notion of INDistinguishability under Chosen Ciphertext Attack (IND-CCA). The game is similar the one described above, but this time the adversary has access to a decryption oracle. The adversary can interact with this oracle to get extra information to decide which of the two messages has been encrypted (of course, it can’t query the oracle on the ciphertext it gets as a challenge).

The Fujisaki-Okamoto (FO) transformation is a technique used to improve the security of a KEM. It uses an IND-CPA secure PKE scheme to produce an IND-CCA secure KEM. Since designing a protocol that is IND-CCA secure is challenging, we typically aim to design a scheme that is IND-CPA secure and then apply the FO transform to upgrade the level of security. The FO transform and its variants are widely used, and they have been studied for several years in the Random Oracle Model (ROM). In this model, we define ideal hash functions by random oracles. These random oracles are like black boxes that, given an input, return an output that is truly random.

In this project I will study this transformation in the post-quantum setting and the One way to Hiding (O2H) Lemma, a technique used in the Quantum Random Oracle Model (QROM) to study the FO transformation.