This thesis presents new results addressing three fundamental areas of cryptography: security notions, assumptions, and efficiency.

The first part encompasses the security of symmetric primitives. We give a new security notion that provides the strongest security for symmetric primitives proven in the random oracle model (ROM). Key-correlated attacks (KCA) model the scenario where all inputs (keys, messages, and possibly nonces and headers) are correlated with the secret key. Under mild assumptions, we prove KCA security of blockciphers, and show that 3-rounds of Even-Mansour are necessary to achieve this. Then, we define a KCA-security notion for nonce-based authenticated encryption (AE), and provide a black-box transformation that turns a multiuser-secure AE into an AE scheme that is provably KCA secure in the ROM. We show relations and separations with older notions (related-key and key-dependent message security) to show that security under KCA is strictly stronger, and implies the others.

The next part turns to public-key cryptography, and analyses the assumptions underlying the new public-key cryptosystem of AJPS. Cryptanalysis of their assumption, based on arithmetic modulo a Mersenne prime, allowed us to reconstruct the secret key, given only the public key. Based on a modified version of the assumption, we propose a variant public-key cryptosystem secure against known quantum attacks.

The last part turns to efficiency, and studies the Schnorr Signature scheme. Exploiting the group structure we leverage the nonce-material to generate a batch of signatures. This, together with some preprocessing tricks, allow us to increase the efficiency of Schnorr signature generation. Security is maintained under a new assumption of intractability, provable in the generic group model. v I feel safe in saying that you should read more literature, as everyone should. quotes stem only from Beckett, first, because he's a great writer and you should read more literature, second, because in truth, I do find many of them inspirational, and third, simply because it matched the theme. xi Don't get me wrong, I believe it's super important to know what's going on in the world, but while one is writing a thesis, it can be quite distracting. I'm not sure if this game has been a blessing or a curse, but it has kept me from looking at Twitter and getting very sad at the state of the world we live in. The third is to the creators of Star Trek. The original one, from the '60s. It is so calming that it has helped me to quieten all these thoughts and get to sleep every night. Actually, I have learned that they were quite pioneering in science.

xvi And then, After all is said and done. After all the fun is over.

After I have made all of my excuses. After dinner. After too-long breakfast. After I have cried, and swore, and laughed (twice). After all the people, and the problems, have given up. After the stress and misunderstandings. After Dublin. After drawing one-way functions on the window in the Library bar. After moving. After traveling. After too much coffee. After toothaches. After all my insights, and all my ignorance. After undeserved successes. After failure, after failure, after failure. After all the untaken advice. After sushi, and after pizza.

After the mistakes in booking, mistakes in proofs, mistakes in coffee machines. After missed flights, missed meetings, missed deadlines.

After walks in the woods, walks in the forest, walks in the hills, walks in the proper mountains, walks in the rivers, walks in the mud, walks in the rocks, walks in the snow, walks in the volcanoes, after walking for weeks, after walking home. After working too much. Too much in the evenings, too much at the weekends, and sometimes not enough at all. Too often not enough at all. After Joyce, after mohsen, after beckett. After all this imbalance and inefficiency. After all my whimsy, and my daydreams. After all my wondering what exactly is the difference between symmetric and asymmetric cryptography, instead of just studying katz-lindell. After Marie, and bagels and soup, and her cancerous dog. After smushed pears in the usb port of the newest macbook. After Christmas trees. And after deriving the general formula to predict the spruciness-longevity of Christmas trees. After bowls of randomness. After jungles, no, sorry, after rainforests. After whales. After pomegranates, and hierarchies, and sahndeviches. After broken cups, broken bowls, broken glasses, broken plates, broken bottles, and broken promises. After clicking 'submit' while we're still working. After so many typos. After so many started, so many left, so many unfinished projects. After so many words and so little action. After kale soup.

After I have changed, sometimes for the better, sometimes for worse. After reluctance to change, after stubbornness, after the thoughtlessness. After too many no's. After picking fingers and scrunchy faces. After 'you people'. After blankets, and cushions, and hot-water bottles, and foxes, and hippos, and bunnies, and goats, and marx, and gah. After political theorists. After critical theorists. After Amy and Juan, and Nermeen Shaikh. After Chomsky and Said and Rushdie and Sontag. After all the stress, after all the things I've forgotten now, and after all those things you do that I don't even notice.

After all the things the others don't see. Even after all of this, after all the afters. . . you remain by my side.

And now, after a moment of reflection, after thinking for a sec, after trying to instill the lessons learned, I see that all these afters sum up to one giant before.

R E S U M É

Cette thèse présente des résultats nouveaux portant sur trois domaines fondamentaux de la cryptographie : les propriétés de sécurité, les hypothèses cryptographiques, et l'efficacité algorithmique. La première partie s'intéresse à la sécurité des primitives symétriques. Nous introduisons une nouvelle propriété de sécurité correspondant à la plus forte sécurité pour les primitives symétriques prouvées sûres dans le modèle de l'oracle aléatoire. Les attaques par clé corrélées capturent les scénarios dans lesquels toutes les entrées (clés, messages, et éventuellement nonces et en-têtes) sont corrélées avec avec la clé secrète. Sous des hypothèses relativement faibles nous prouvons la sécurité contre les attaques par clé corrélées pour les algorithmes de chiffrement par bloc, et montrons que trois tours d'Even-Mansour sont nécessaires pour cela. Nous étendons ensuite les attaques par clés corrélées au chiffrement authentifié basé sur les nonces, et fournissons une transformation en boîte noire qui, partant d'un chiffrement authentifié à utilisateurs multiples, donne un chiffrement authentifié démontré résistant aux attaques par clés corrélés dans le modèle de l'oracle aléatoire. Nous établissons les relations et séparations avec les notions déjà existantes (sécurité contre les attaques par clés apparentées et par message dépendant de la clé) pour montrer que la sécurité contre les attaques par clé corrélés est strictement plus forte, et implique les autres.

La partie suivante porte sur la cryptographie à clé publique, et analyse les hypothèses sous-jacentes au nouveau cryptosystème introduit dans AJPS17. La cryptanalyse de cette hypothèse, reposant sur l'arithmétique modulo un premier de Mersenne, nous permet de reconstruire la clé secrète à partir de la clé publique uniquement. Nous proposons alors une variante de ce sytème à clé publique, fondée sur une modification de l'hypothèse précédente, résistant aux attaques connues (classiques et quantiques).

La dernière partie aborde l'efficacité algorithmique du schéma de signature de Schnorr. En mettant à profit la structure de groupe nous pouvons tirer parti du nonce pour produire un lot de signatures. Combinant ceci avec des méthodes de précalcul nous permet de rendre plus efficace l'algorithme de signature de Schnorr . La sécurité est préservée sous une hypothèse nouvelle, dont on montre qu'elle est vraie dans le modèle du groupe générique. vii P R E FA C E This thesis is not perfect, indeed far from it, yet I like it very much. I have little doubt that inconsistencies reside in every page, and I reserve the right to leave them there. I have, however, tried in ways to make this document somehow nice, a little bit different, in the hope that it becomes more pleasurable to read, and navigate, than a standard 200-page block of text.

I have been told I thought about this too much, but I disagree. Science, without communication, is a fruitless endeavour, so I feel it is as much our duty to think about, and experiment with communication as it is to uncover, or create (however you like to see it), the truths of our world.

On Motivation. If you know me, you'll know that I'm not a very 'motivated' person. I just want to learn some things, and simple things at that. Things, however, have become quite complicated over the course of time, and to pare them back to what could be considered simple, takes quite some effort. It would be somewhat pointless, or selfish, to learn things, and then not use them, so while going to the effort of paring things back to their simplicities, I also try to share them with other people. This thesis was concieved as a result of my paring and sharing carried out as a student of the École normale supérieure in Paris, and as a member of the Advanced Reserach team at Ingenico Group. Both places, but particularly Ingenico, have been unexpectedly and incredibly kind to me. I never dreamed I would land amongst such good company.

On Style. While trying to learn simple things, I wanted to produce a simple-looking document to describe them. Tufte has thought a lot about how to arrange information nicely on a page; his style is often used when building textbooks. As I am not writing a textbook (although I would like to at some point), I have little use for much of the functionality that comes with the style. I have instead used the Classic Thesis package which is similar in style to Tufte, yet more simple, and is based on Robert Bringhurst's Elements of Typographic Style. I have modified the package a little to make it even simpler again. There are a number of reasons why I like these styles, I have listed some of them below wide margins. Well, you say 'wide margins', I say short lines. I thought often about the one-column vs. two-column style that is used when publishing papers. Different venues have their preferenes, and both syles have their advantages. One column looks very clean in that there is just one place for your eyes to be dragged to. Two columns are nice because the lines are ix short to read which somehow helps to keep my attention longer. However, with two columns, a lot is packed into the page, which makes it look quite ugly. I thought it would be nice to have something in-between. One column so that the page stays tidy looking, but short enough lines so that you don't feel like you've read War and Peace before you get to move to the next line. This is what you'll find here.

margin paragraphs. In using 'short lines' there is a lot of space left in the margins. The tufte style has even wider margins than you will find here, and often people use this space to put little diagrams, or notes that summarise the adjacent paragraph, or references to more explanatory text. I like the idea of using the margin space, but putting too much text or image in the margin runs the risk of falling into a two-column cluttered-looking page problem. Here, the margins have been kept wide enough so as to include some text, but not so wide that it could be considered a second column.

The content you will see in the margin paragraphs is therefore limited in scope to less than you will find in tufte-style books; no diagrams, no rambling explainations. I intended to write More often than not, they probably resemble more snide remarks.

summaries or a sort of tl;dr of the paragraph, and some side remarks. Hopefully you will find them useful, and where the content gets particularly involved, e.g., in the proofs, I try to highlight what the key point is, or where the 'trick' is, or at least to indicate "this is the only part you really need to read." Now I have gotten used to doing this, it hurts that there's nowhere to put these pointers in regular scientific papers.

table of contents. I have always wondered why, in a table of contents, the section titles are flushed left, and the page numbers flushed right. Is it not difficult to trace across from left to right to find the corresponding page? It is not so bad on printed paper, but on a screen, I just find it unnecessarily complicated. People sometimes put a row of dots between the section title and the page numbers, to assist in the left-right tracing, but with a table of these rows the page just looks like it's about to start explaining lattice-based crypto to me. Here you will find the page numbers beside the section titles. No right-flushing, no dots, no tracing.

On Capitalisation. I have a terrible habit of capitalising words I shouldn't, and not capitalising words I should. I don't know if this is perhaps due to a very good German teacher, Berit, I had at one point, who drilled into us correct capitalisation rules in German, so much that it ruined my English, or if it is related to the fact that I always mix up left and right. In English, something with a capital letter is often of greater importance to something without, so it can

x cause offence to (mis-)place capital letters. In any case, please don't take it personally if I diminuate you by not capitalising your name, or if I canonise someone by referring to 'His', 'Her', or 'Their' work.

On Grammar. When I am not making capitalisation mistakes, I have, tried at least, to use nice grammar. I would like to say that I have included elements from the Chicago Manual of Style. In reality, this book is too big for me, but I have at least read the small Strunk and White book on The Elements of Style. I am also, as you will come to learn, quite fond of using Oxford commas.

On English. I come from a country that happened to be colonised by the British Empire for a bit too long. We picked up some of their habits, and have not managed to shake them, so the language used here is (mostly) British English. Many academics seem perturbed by the use of British (as opposed to American) English in scientific writing, I imagine because it gives rise to inconsistencies in spelling when different authors collaborate. Details are important when they may give rise to ambiguity, particularly in the sciences, but I feel that writing color or colour will not lead to too much confusion, so I don't care to correct it. I do understand that some things in British English can have more meanings than most people would like, and in these instances I assure you I will not write flat, or lift, and instead write 'appartment' and 'elevator'. In any case, you should count yourself

Although, if you're wide to this gill's g that'd be pure tome.

lucky that I didn't write in Irish English! On Beckett. You may have noticed I have included a number of references to Samuel Beckett and his work. People have asked what is the 'Beckett obsession', and I would like to clarify. First, it is not an obsession, but rather just a few references to something that nicely ties together some memories and principles I care about from this place and time. Let me elaborate, and then you can read the thesis, I promise.

the title "Ever tried. Ever failed. No matter. Try again. Fail again. Fail better." Perhaps his most famous line, I had to include it somewhere. I like it so much, I put it as the title of this thesis. I like it so much still that I name the three main technical parts of this thesis by those last three short sentences.

the quotes Many people include quotes in their PhD theses. Perhaps they wish to show some personality, or to inspire. I tried to think of quotes that I would like to include, but I felt this is not to place to share the sentences I would really like to share. Those ones, I would rather tell you over a coffee. So instead, all the room I organised my PhD defence to take place in Salle Beckett.

It is one of the smallest rooms at ENS and so is quite inappropriate for a defence. Additionally, it is one of the main teaching rooms (of which there are very few), so it's constantly booked during term time. Furthermore, it doesn't belong to the DI, we have our own room for defences, so why care so much about Salle Beckett? As Ireland was once colonised by the British Empire, it has now become colonised by the Tech Empire. With very low (and sometimes zero) corporate tax rates, many international tech companies set up their European headquarters in Dublin. People are damned because the salaries in these places are so high that if you don't work in one of them, you can't afford to live in the city (I begin to call it the San Francisco effect). The universities Many schools within the humanities have been closed, and even within the math and cs departments, the scope to study something 'not immediately useful ' is almost non-existant.

then scramble to educate people in the topics needed to become employed in these companies, and those alone, which, in the short-run, maybe raises employment, but in the not-even-longrun, sees a country devoid of thought, algorithmically producing machine-like staff for Tech Corp. This is an exageration, of course, I just mean to say that there are few people who stop to really think what we're losing for all this percieved growth. This is not my Ireland. Ireland, the 'land of saints and scholars' produced Beckett, and many great writers, scientists, actors, and politicians. Beckett is Joyce is great too, and he also made it to the ENS, albeit somewhat unoficially.

one of the most noteworthy, and one of the only ones to make it to the ENS. That is the Ireland I like to think of, and the Irish that I try to be. I am not special, and definitely not Beckett-level special, but, as an Irish(wo)man at ENS, if it's the last thing I do, I'll stand in his room and promise to be something.

xii Je suis comme ça. Ou j'oublie tout de suite ou je n'oublie jamais.

A C H Á I R D E

On a cool evening in Istanbul in the spring of 2015, I found myself sat at a table of cryptographers. They were a curious bunch and upon asking me what I was doing, I told them I hoped to pursue a PhD Actually, I believe I told them I was interested in "playing with shapes in space." in computational geometry. They laughed, more than they should, and told me that the only right thing to do, is a PhD in cryptography. The topic was not too far from my mind, as also in that spring, Citizen Four had just won an academy award, Signal had just been launched, and my house in Ireland had just been raided by the cops because someone was using TOR. After a few beers and some chat, I began to think. . . maybe I should do a PhD in cryptography. . .

The following months saw me heeding the advice of the cryptographers and by the end of the year, I was admitted to one of the finest schools on the continent, to work with the "free man" of cryptography.

Every time I mentioned David Naccache, people would rejoice "you know he made a computer from. . . plants!?" I was very excited, but not at all prepared for what was about to come. Now, I sit here, four years later, and there is negligible chance that I would come to write these words for you without the help, encouragement, patience, and magic of a good number of people, and one in particular. Let me take a moment to recount some of the thanks I have wished to express over these past few years.

To David. I could write a second thesis on all the things I would like to say to you. Many people would remark on your cleverness, your quirkiness, your helpfulness, but I wont, for you have given me something far greater than all of those combined. You left me alone when I wanted, you trusted me to think, to experiment, to play with my thoughts and talks and papers. Never once have you said 'no', not Perhaps they still pale in comparison to the craziness of yours :) once have you discouraged me from dreaming up my crazy plans, nor did you scorn me when I couldn't deliver. All of this boils down to a rare and fundamental gift; you've given me freedom, and for this, I will be forever grateful.

To Bart. My thesis reviewer, and one of the busiest men I know. The first time I saw you, you gave a talk at Eurocrypt about Snowden and mass surveillance. I remember excitedly turning to the person beside me and asking 'who's this guy?!' to which they responded "He's the president of the IACR.." You were one of the first to make me excited to enter this field, so it's an honour to have you on my jury as I make my sort of début. Most people either talk to me about crypto, or the 'fluffy' social stuff I like, but you are one of the few who talks to me xiii about both, which I appreciate greatly. Thanks for remaining one of the 'good guys'.

To Moti. My second thesis reviewer, thanks for not living up to the reputation of the dreaded 'reviewer number 2!' You make me laugh and cheered me up on days where you didn't know I needed it. My curiosity in you arose from several events, all of which you are unaware. I reviewed some of your work, which introduced me to an Forgive me for breaking protocol, but I dont say which papers.

area I would later become very excited about and between this and various events I've seen you speak, the intrigue silently grew. Thanks for being so accommodating throughout these past few months, your ease of style is much appreciated.

To Whit. For being the human cryptographer. I enjoy so much to see you on the RSA panel, and every year to relinquish your opportunity to push your opinion of the latest cryptographic trends in favour of remembering the people who helped cryptography get to where it is today. Thanks for all the stories, for the few laughs, for helping me see the importance and amusement in the small things, and for being the one who kept me somewhat excited about living in Paris.

To Christian. For dragging me up and down mountains. Through rocks, and rivers, and mud, safely. For teaching me about S-boxes in Colombia, Grostl in Austria, ropes in Turkey, and knots in the snow. You're the most positive person I know, and the definition of a good friend. I am grateful for every experience we've shared, except one. I will forever curse you for introducing me to those smoked almonds. I cannot get enough of them.

To Manuel. For having patience, where others could not. It means more to me than you'll ever know. I'll say no more.

To Delaram. For being inclusive. For the encouragement, advice, the coffees, and for sprinkling a little glamour into cryptography, and into my days. It was such a pleasure to meet you in Paris and I look forward to working together in the future.

To Guénolé. For being one of the rational people at UCD. You know how hard a time I had there and I thank you greatly for being the one to make me believe there's something better that I can do. Thanks for doing things right, and for all the conversations and hours spent mulling over everything. Thanks for inviting me to give lectures, I didn't realise at the time how significant this was. You're the only one from Ireland who has been involved in this PhD process, and I am overjoyed that I could fulfill my promise to bring you to the jury if I ever made it to the end. Now that I'm here, I somehow feel like we've made it to the end.

To Michel Abdalla. For being a friend, my conference companion, my confidant, and now on my jury. to his face turning him a puse shade of red with embarrassment. Marc is my academic brother, with whom I sat for three years discussing everything from 'what is a primitive,' to 'how to look like Axl Rose,' to 'philosophy' at the bistro d'en face. Thanks for always listening to me, and for putting up with me when I talked about things that made you feel really awkward. Thanks for being one of the few that never made me feel stupid, and also for not giving me unsolicited advice. * * A rare skill amongst young, educated men.

To Hiba. For being one of the most surprising and coolest people I've ever met. For taking care of a lot of the annoying stuff so we didn't have to. Your efforts did not go unnoticed and are much appreciated, really.

To Rémi. It is clear to me now why David gave you the secret to living 400 years, while he only told me how to manage 200. Thanks for being the one to do many things, quickly. Thanks also for taking care of me at the start, and for easing me into my many new lives.

To Octavio. For being so bright, and so warm, and so kind. I'm so happy to have met you. I hope you go on to do fantastic things, and act as a glue in the centre of the community. I really wish the best for you, people like you are too rare.

To Mihir. For having the special ability to teach more through one carefully constructed sentence, than most people could in a lifetime.

To James. For being my one cool non-crypto friend in Paris. I will never forget the night we met, on set at France 24, commenting live on Zuckerberg in Congress, Saudi Princes in Paris, and the UN Security Council's opinions on the use of chemical weapons. You, your "oh! are you Irish?", and your topic jumping left my mind spinning that night, as have the nights we spent together since. Thanks for adding a little variety to my life. Yer a tonic, as they say, and I hope I get to hear you sing, over and over again, and that we get to go for many Long Walks in the years to come.

Georg & Alex. For all the trips, and conversations, crypto and otherwise. You were our closest friends in Paris, and I'm so grateful for all the memories we have to look back on.

To Ireland. And the Irish. Naturally to Shell and John. To Emma and Aileen and Motja, for patiently listening to me when I talk too much during hard times, and for waiting for me, when I talk too little during the good times. To the NUIGalway gang; Kevin, Niall, Rachel, Aisling, Jerome, you shaped me in the nicest ways in my 'early' years and I'm so appreciative for all you took the time to teach me. And to Oliver, I'll be eternally grateful for the days we spent in UCD, my only sadness is that I didn't have a friend like you in Paris.

To ENS. For acting as my academic home over the past years. You've been everything I wanted from a school, and I'm so glad to know that places like you still exist. To the Naccache gang. Petra for the cocktails and the sex and the city chats. Mirko for the eh.. unspeakable. Marius for the tricks. Fatima for being the normal one-thanks for grounding us! Bruno, for being calm and putting up with us. Georges-Axel the office is all yours now. And Natacha for having a larger than life personality! And to the Crypto gang. Finally to Stéphane and Sophie, for being the two that showed too much patience with me trying to navigate French administration.

To Ingenico. For acting as my industrial home over the past few years. I've grown to like you more than I ever thought I would. To Laurence, for taking such good care of us, and for keeping me entertained at lunchtime. To all at the labs, thanks for patiently listening to me as I got excited about too many privacy topics over the years. And to Erlin, the greatest intern that ever lived. I miss you.

Misc. There are some moments that make a profound impact on your work but you may never be sure whether to thank or curse them. Here I will share a few acknowledgments to those random things. One is for the mosquito that feasted on the ball of my palm the week before I submitted this thesis. You made these last words all the more unbearable to type. Another is for the creators of the game Two Dots.

So, before it's too late, and before I forget, and before we embark on our journey towards the next set of proofs, the next set of mountains, the next set of books, the next set of ..afters, let me give you these words, too many as they may be, as a marker in time, to note that however good or bad the days may seem, however many afters I may write, there are equally as many befores to come The E-BPV algorithm for generating random pairs (x, g x mod p). The BPV algorithm is a special case of E-BPV for h = 2. 123 Figure 9.7

The LL algorithm for generating random pairs (x, g x mod p). 125

L I S T O F TA B L E S
P R O L O G U E 1 I N T R O D U C T I O N
Let us begin by taking a brisk stroll through history.

the birth of modern cryptography

The year is 1943. Imagine that! For the first time you see the ability to encrypt moving into the hands of the citizen. This yields excitement, but also, it is immediately obvious that this will cause some consternation. On one hand, the First Amendment of the U.S. Constitution [U.S. Const. am. I] strongly protects freedom of speech and expression, which-in a roundabout way-means that cryptography within the U.S. can not be controlled. On the other hand, cryptography remains on the U.S. Munitions List, meaning that its export is still heavily regulated. The next decade sees some of the bloodiest years of the Crypto Wars. With global connection to the Internet, pressure mounts on the U.S.

Government to loosen the laws surrounding the export of software. The battles were fought in court and in 1996 [START_REF] Clinton | Administration of Export Controls on Encryption Products[END_REF], encryption software was removed from the munitions list. By the turn of the century, rules surrounding the export of commercial and open-source software containing cryptography were greatly simplified, restrictions on keys were lifted, backdoors were prohibited, and you, the citizen, felt that progress was underway.

Fast forward to June 2013. You sit happily tip tapping on your smartphone, sharing doge memes and giggling over screaming goats, before moving on to check the news. You learn that the U.S. Government has forced Verizon to hand over the phone records of millions of Americans [START_REF] Greenwald | NSA collecting phone records of millions of Verizon customers daily[END_REF]. It's not such a nice story. Over the coming days you see more articles of a similar vein. You discover the NSA's direct access to data held by all your beloved internet giants. You learn of secret programs and backdoors, and within months, you come to terms with the fact that you live in a quasi-surveillance state. This is a grave situation and once again, as you did two decades ago, you find yourself debating the same disparity between individual privacy and state security.

Between then and now. The debate raged on and the disparity still exists. Several nations have the desire to forbid encryption, to keep it as a military tool, to stifle progression, to retain control, and to undermine democracy. But there has also been much progress. In 2018, the EU put a new regulation into place: the General Data Protection Regulation [START_REF]Regulation (EU) 2016/679 of the European Parliament and of the Council of 27 April 2016 on the protection of natural persons with regard to the processing of personal data and on the free movement of such data, and repealing Directive 95/46[END_REF]. It expands and solidifies the points set out in the Charter of Fundamental Rights of the European Union [Uni12] and the Treaty on the Functioning of the European Union [Uni07] which state that EU citizens have the right to privacy both online and offline. It insists that in order to maintain security of the individual while ensuring compliance with the regulation, appropriate measures (such as encryption) must be used. The regulation covers the collection, storage, processing, and deletion of personal information and communications. The regulation applies to the handling of personal information within Europe irrespective of the location of the organisation handling the data.

The United Nations Human Rights Council and the General Assembly have also specified the necessity for encryption to ensure the right to privacy in the digital age, building their argument by paying particular focus to the dangers faced by journalists. The UN [HRC16] Emphasizes that, in the digital age, encryption and anonymity tools have become vital for many journalists to exercise freely their work and their enjoyment of human rights, in particular their rights to freedom of expression and to privacy, including to secure their communications and to protect the confidentiality of their sources, and calls upon

States not to interfere with the use of such technologies, with any restrictions thereon complying with States' obligations under international human rights law.

These are simply two examples of many that build upon the arguments of yore. However strong were the efforts made by the privacy advocates in the 90's, they were very few voices. Now, with technology in every inch of our lives, with the increased media attention due to the Snowden revelations, high profile court cases, and freer flowing information, citizens are much more aware of the consequences of not using encryption. This time around, there are many voices.

And so here we are. You have come a long way since your button pressing days on the Enigma. You've seen four world recessions, men walking on the moon, the fall of the Berlin wall, and some moves towards equality. You've danced to records, to cassette tapes, to mp3s, and now to Spotify. You must be tired. But you cannot sit yet! The world has grown around you, and there are problems old and new left to be solved. If I ask you to send me an encrypted email, right here and now, can you do it? If I ask you to remove any records of me, to grant my request to be forgotten, is it easy? If I want to travel, to meet people in the world, will you stop me at the border? Will you question me and demand my passwords? If I want to talk, to exercise a curiosity, to learn and teach and spread information, but without prying eyes, will you let me? Ultimately, all I'm asking is to exercise a right, is it possible? Until the answer to all of these questions is a definitive Yes, then I'm afraid we've still got some work to do.

contributions of this thesis

We saw the development of several worlds all becoming dependent on cryptography. While a traditional thesis aims to dig deep and focus on one particular topic, the goal of this work was to arrive at a level of scientific understanding and creativity that would allow to tackle general problems that arise in this increasingly technological society. As such, this thesis studies a variety of cryptographic topics. It encompasses new theoretical results, new security notions, constructions and generic transforms for both public-key and symmetric cryptosystems, and efficiency gains. The results mainly appear in three papers, briefly outlined below.

Try Again

Part II introduces a new attack model, namely key-correlated attacks (KCA), that subsumes two previous models (related-key attacks, and key-dependent message attacks), and further shows that even if these two security notions are both guaranteed, together they are still not enough to yield KCA-security as was previously thought. As such, it is a lesson that we should expect try again before getting the most complete security notions.

Key-Correlated Attacks. The part encompasses the security of symmetric primitives. In Chapter 3 we give the background and motivation for why it is interesting to study the security of key-dependent messages encrypted under related keys. Chapter 4 describes a new security notion that provides the strongest security for symmetric primitives proven in the random oracle model (ROM). Key-correlated attacks (KCA) model the scenario where all inputs (keys, messages, and possibly nonces and headers) are correlated with the secret key. We show relations and separations with older notions (related-key and key-dependent message security) to show that security under KCA is strictly stronger, and implies the others. In Chapter 5 we describe the assumptions necessary to prove KCA security of blockciphers, and show that 3-rounds of Even-Mansour are necessary to achieve this. Finally, in Chapter 6 we define a KCA-security notion for nonce-based authenticated encryption (AE), and provide a black-box transformation that turns a multiuser-secure AE into an AE scheme that is provably KCA secure in the ROM.

Fail Again

Part III turns to public-key cryptography, and describes an attack against a new assumption. Experimentally we show that we can obtain the secret key without too much computing power. We go on and attempt to modify the assumption and construct a variant scheme, but alas, it also succumbs to the same attacks, and hence in this part we are destined to fail again.

Unstudied Assumptions. Chapter 7 analyses the assumptions underlying the new public-key cryptosystem of [START_REF] Aggarwal | A New Public-Key Cryptosystem via Mersenne Numbers[END_REF]. Cryptanalysis of their assumption, based on arithmetic modulo a Mersenne prime, allowed us to reconstruct the secret key, given only the public key. Based on a modified version of the assumption, in Chapter 8 we propose a variant post-quantum secure public-key cryptosystem. This variant is also vulnerable to the attacks described against [START_REF] Aggarwal | A New Public-Key Cryptosystem via Mersenne Numbers[END_REF], but the scheme still could be of use as it is a simpler construction, is based on a different assumption, and thus potentially easier to cryptanalyse.

Fail Better

Part IV turns to efficiency, and studies the efficiency of signature schemes. We describe a way to efficiently generate a batch of Schnorr signatures using the same amount of 'random' as was traditionally required to generate one signature. We fail to maintain security under traditional assumptions and are required to reduce to a new assumption. If we are going to fail to use traditional assumptions, at least we gain efficiency and fail better.

Efficiency. Chapter 9 sees the exploitation of the group structure used in Schnorr signatures to reuse the nonce, with which we can then generate a batch of signatures. This, together with some preprocessing tricks, allow us to increase the efficiency of Schnorr signature generation. We prove security of the signature scheme in the random oracle model, but require a new assumption which we show to be intractable in the Generic Group Model.

These are known as zerodays and are actually very scary. used to exploit a system at a later date. We can't always get systems

In fact, there's only one time we can get it.

with full and unconditional security, yet, it's risky to rely on schemes that have no proof of security, so what to do?

A successful paradigm that emerged to cover a middle ground is known as provable security. It allows us to:

1. Abstract and define general notions for cryptographic primitives which enable us to reason about their security.

2.

Relate these notions to each other to form a clearer picture about the relative strength of the security guarantees of a particular primitive. Overall, it gives us a sense of the security and gives us the confidence to say that a particular primitive has no inherent design flaws.

Definitions. Generally when we talk about cryptographic objects, we refer to them as primitives. We define a general class of primitives, rather than relying on reasoning about the security of a particular instance or instantiation of a primitive. These primitive abstractions are built in the form of definitions. In writing definitions, there are a number of things to consider:

syntax is the language used to describe this primitive. It lays down the algorithms, mandates whether they are randomised or deter-9 ministic, describes the inputs expected by the algorithms, notes from which domain (or space) the inputs can be chosen, and the outputs the algorithms return, along with the range or space in which they can lie.

correctness describes the interaction between algorithms that forces the primitive to work correctly. For example, in any given encryption scheme, we can say that it is correct if it is always the case that the message obtained from the decryption of a ciphertext is the same message that was encrypted to produce that ciphertext.

security is where the fun starts. Security specifies the goal that the For example, we may wish to achieve the security goal of confidentiality, or authenticity.

primitive should achieve, and the power of an attacker trying to inveigle the system. It is often expressed as a game played by an adversary with a given set of computational resources. We say that the security goal is achieved if the adversary's advantage, or their probability of winning the game, is below some threshold.

Reductions. Given a definition of a primitive, we know how it should look (through its syntax), how it should behave (through its correctness), and what security goals it should achieve when faced by an adversary. In proving that the primitive achieves these goals, we need to bound the advantage of the adversary playing the security game. To generate these bounds, we often need to rely on some assumptions. The assumptions used are often well studied problems that are universally considered to be hard enough at a given point in time. New assumptions undergo careful cryptanalysis by many in the community, but we'll see more on that later, and particularly in Part III. Equipped with carefully studied assumptions, the aim is to show a relationship between the hardness of breaking primitive and the hardness of the assumption. Describing this relationship is typically done via a reduction.

A reduction is simply a process that shows how to transform an efficient adversary A that succeeds in breaking the target primitive, into a solver B that solves the problem that was assumed to be hard. Reductions often proceed in the contrapositive, and we say that because it its assumed that no solver B exists to solve the hard problem, it cannot be the case that we have an adversary A that breaks the primitive.

Throughout this thesis, particularly in Parts II and IV we will see a number of proofs by reduction.

hard problems

Now that we're equipped with our primitive definitions, and our methods to prove their security, we need some assumptions to reduce to. There are a number of hard problems, and we are forever searching for more, but often the very first thing people think of when they hear the word cryptography are the elusive prime numbers. Their infamousity is largely due to the fact that the most widely used publickey cryptosystem, RSA, is based on the hardness of integer factoring. It was not, however, the first hard problem used to construct public-key encryption. In 1976, Diffie and Hellman [START_REF] Diffie | New Directions in Cryptography[END_REF] proposed methods for key exchange and digital signatures based on the Discrete Log Problem. Below, you'll find a brief description of these, and other hard problems used in cryptography.

One-way Functions

Modern cryptography exists largely due to the fact that we have some functions which we assume to be one-way. The problem is that we do not have functions that are known to be one-way, and so we rely on this as an assumption. However, this assumption would not form the basis for modern cryptography if we did not have some candidates that we strongly believe to be one-way.

One-way Function. A function is said to be 'one-way' if it satisfies two properties:

1. It's easy to compute.

2. It's hard to invert. It's as simple as that. Here, easy means that if we're given a uniform value x from the domain of some function f , y := f (x) should be computable in polynomial time. On the other hand, hard means that if we're given such a y that was produced by applying the function f to the uniform value x, it should be infeasible for any probabilistic polynomial time algorithm to invert f . The following paragraphs describe some candidates strongly assumed to be one-way.

Integer Factorisation

Integer factorisation. Suppose we are given n = pq with p, q prime. The problem is simply to find p. Provided that p and q are large enough this problem is assumed to be hard. RSA problem. Given integers n, x, e the problem posed is to compute y such that y e = x mod n. One way to solve this problem is by factoring n as above. In fact, it could be the only practical way, see [START_REF] Daniel | Breaking RSA May Be As Difficult As Factoring[END_REF], which addresses amongst others some initial doubts raised by [START_REF] Boneh | Breaking RSA May Not Be Equivalent to Factoring[END_REF]. Assuming access to special oracles, efficient attacks are known, see e.g. [START_REF] Joux | Oracle-Assisted Static Diffie-Hellman Is Easier Than Discrete Logarithms[END_REF].

Discrete Logarithms

Discrete Logarithm Problem, DLP. Let G be a group, and g be a generator of G. Given y ∈ G, find x such that g x = y.

The DLP was first introduced by Diffie & Hellman [START_REF] Diffie | New Directions in Cryptography[END_REF] to enable key exchange by describing the function as a trapdoor the exponentiation in a finite field. Fixing a prime p and a generator g of the finite field of order p, computing g x mod p is easy (i. e. polynomial time) by fast exponentiation. The converse, which is finding x given g x mod p is hard. The discrete logarithm problem lies at the heart of a vast proportion of modern public-key cryptography and has many variations. Below we list some, and introduce a new one in Part IV. a generator of G. Given g x and g y , compute g xy . The best approach to solving this problem is by using a solution to the DLP.

Decisional Diffie-Hellman, DDH. Let G be a group of order q, and g be a generator of G. Given g x and g y , it should be hard to decide, or distinguish the value g xy from g z , where z a random element in G.

Lattice Based Problems

Lattice-based cryptosystems rely on the hardness of solving certain problems appearing in discrete subgroups of Z n , typically of the form L = ∑ i c i b i where b i ∈ Z n are called the basis vectors. The most common hard problem is the shortest vector problem (SVP), which intuitively seeks to find the shortest vector from any point to a point in the lattice. More formally:

In higher dimensions, the problem of finding the shortest vector of a lattice is believed to be hard, this then can be leveraged to construct public-key cryptographic schemes.

SVP γ . Given a basis of L, find a non-zero vector v ∈ L of length v ≤ γλ 1 (L), where λ 1 (L) denotes the length of the shortest vector in L. The results in Part III pertain to lattice-based public-key cryptography.

idealised models of computation

Now we have our definitions, our reductions, our assumptions, and some examples, are we ready to start yet? Not exactly.. Hard problems, assumptions, and security in general, have been studied for a number of decades now. Traditionally in proving security, we had a well defined security target that we hoped to achieve. Yet, as cryptographic primitives become increasingly complex, the notions of security get deeper, and these schemes are used in ways that were not necessarily envisioned when they were designed. As such, it's not always the case that we know exactly what property we want to achieve, so there is a move to prove security in a more general sense. Rather than reducing to a specific hard problem as outlined above, we can also leverage black-box reductions where we are given access to some ideal object that encompasses many desired security properties. Proving security within these ideal models allows us to keep proofs self-contained, and to bound adversaries against a general set of attacks.

Random Oracles. The random oracle model ([BR93; CGH98; FS87]) models the operation of a random function as queries to an entity called a random oracle. When queried with a given input, the random oracle replies with a truly random number from some sample space. Input queries and corresponding outputs are stored in a table; such that upon receiving the same query twice, the oracle returns the same corresponding output value. With a 'full' table containing all input/output values from a given space, a random oracle models an ideal hash function.

There are some uses of Random Oracles that we will call upon throughout this thesis.

1. Lazy Sampling. Working in these idealised models, H can be defined over an infinite domain. This can be technically cumbersome to deal with, but also non-intuitive to reason about. For this reason, it is often convenient to lazily sample H such that as queries arrive, the output values are uniformly sampled, and the input/output pair is stored in the table. This way, the table is built up over time, rather than being pre-defined before use.

2.

Programmability. Before we said that a reduction is process describing how to convert an adversary that breaks the scheme in question, into an adversary that solves some hard problem. A property gained by using random oracles within a reduction is that adversarial queries to H can be seen by the reduction and as such, the reduction can return or program H to return appropriate values.

3.

Forgetfulness. Upon receiving a query, H returns a uniformly random value, without checking whether or not this query has been made before.

However, no efficient algorithm can implement a true random or-I believe this to be one of the more over-used and unexciting comments regarding random oracles.

acle; this can lead to the situation where a cryptosystem is provably secure in the ROM, but provably insecure when instantiated with any concrete hash function [START_REF] Canetti | The Random Oracle Methodology, Revisited (Preliminary Version)[END_REF]. However, such constructions are very unnatural from a cryptographic point of view [START_REF] Koblitz | The random oracle model: a twenty-year retrospective[END_REF], but illustrate that there exists a gap between the ideal model and real-world implementations.

Ideal there are (artificial) schemes that are provably secure in the ICM, but provably insecure for any concrete block cipher [START_REF] Black | The Ideal-Cipher Model, Revisited: An Uninstantiable Blockcipher-Based Hash Function[END_REF]. In fact the ROM and ICM are equivalent [START_REF] Coron | The Random Oracle Model and the Ideal Cipher Model Are Equivalent[END_REF].

Generic Group Model. The generic group model (GGM) was introduced by Shoup [START_REF] Shoup | Lower Bounds for Discrete Logarithms and Related Problems[END_REF] and gives an adversary access to a randomly chosen encoding of a group, rather than a specific efficient encoding.

The generic group model is useful, in that it gives more theoretical power to prove statements, but it is unsatisfactory from a cryptographic standpoint, because no group is truly generic. Groups used in practice have additional structure, which leads to more efficient algorithms. Like the ROM and the ICM, cryptosystems which are provably secure in the GGM may be insecure when the generic group is replaced by any concrete group [Den02; CGH98].

notation

Before getting into descriptions of primitives used throughout the thesis, you will find listed below some preliminary notation to assist in reading.

Strings. We let {0, 1} n denote the set of bit strings of length n and {0, 1} * the set of all finite-length bit strings. For two bit strings X and Y, X|Y denotes their concatenation and (X, Y) denotes a uniquely (and efficiently) decodable encoding of X and Y. The length of X is denoted by |X|.

Sampling. By x S we mean sampling x uniformly from set S, whereas by y A(x) we mean the action of assigning the output of the randomized algorithm A on input x to y. Assignment from deterministic algorithms and calculations are denoted by the symbol ←.

Lists. We denote appending element X (resp., a list L ) to a list L by L : X (resp., L : L ).

Games. We adopt the code-based game-playing language of Bellare and Rogaway [START_REF] Bellare | The Security of Triple Encryption and a Framework for Code-Based Game-Playing Proofs[END_REF], for which all lists are initialized to empty and all bad flags to false. A game Game sometimes consists of an initializing procedure Init, one or more procedures to respond to oracle queries, and a finalizing procedure Fin. We denote changes from one game to the next by highlighting boxed sections.

Parameters. Following the concrete security approach, we will primarily content ourselves with defining advantages and providing concrete reductions, without dwelling too much on the question when a scheme is actually deemed secure or not (e.g., for a sufficiently large class of adversaries, the advantages are sufficiently small). One can of course easily recast our work in an asymptotic framework (where for all probabilistic polynomial-time adversaries advantages should be negligible in the security parameter λ, i.e., in λ -ω(1) ). From time to time we do use an asymptotic approach, for measuring efficiency, and in such cases we denote the security parameter by λ ∈ N which is given to all algorithms in the unary form 1 λ . Algebra. If n is an integer, we write Z n for the ring Z/nZ. We let

Z * n denote the invertible elements of Z n . The set of numbers 1, 2, . . . , k is denoted [k].
Algorithms. f ∈ Negl(λ) denotes a function that decreases faster than the inverse of any polynomial in λ; such functions are called negligible. We often refer to an efficient algorithm or a probabilistic polynomial time (PPT) algorithm, which is a probabilistic algorithm running in time polynomial in its input size, on all inputs and all random coins.

symmetric cryptography

Symmetric, or private-key cryptography was the first developed notion of cryptography and remains today the most efficient and widely used primitive.

In Part II we will take a look at contributions in symmetric cryptography. This section builds up the preliminaries and notation necessary to read fluidly there.

Symmetric primitives are largely based on blockciphers built from pseudorandom permutations and pseudorandom functions. These in turn are used to build symmetric encryption primitives such as Authenticated Encryption and its variants. Outlined below the reader will find the descriptions from basic to advanced primitives, and the security notions associated with them. Before we can build anything we need some randomness.

Pseudorandom Functions (PRF). A family of functions

F : K × A PRF is the generalisation of a PRG.
D → R is a two argument function that takes a key K from the key space K, and input x in the domain D and returns an output F(K, x) in the range R. We define the PRF-advantage of an adversary A with respect to the function family F as:

Adv prf F (A) = | Pr[A F K (•) = 1 : K K] -Pr[A f (•) = 1 : f Func(D, R)]|
F is said to be a pseudorandom function if the above advantage is "small" for every "reasonable" adversary A.

Pseudorandom Permutations (PRP). A family of permutations

A PRP is a restricted class of PRFs mapping inputs to outputs in the same domain. They are really the fundamental building block of symmetric cryptography.

Π : K × D → D is a two argument function that takes a key K from the key space K, and input x in the domain D and returns an output Π(K, x) in D. We define the PRP-advantage of an adversary A with respect to the permutation family Π as:

Adv prp Π (A) = | Pr[A Π K (•) = 1 : K K] -Pr[A π(•) = 1 : π Perm(D)]|
Π is said to be a pseudorandom permutation if the above advantage is "small" for every "reasonable" adversary A.

Blockciphers

Blockciphers are the fundamental building block for encrypting messages under a shared key. They can be constructed in a number of The most commonly used blockcipher models are the Feistel network, and Even-Mansour.

ways by connecting PRPs together under various models. Now, let's put all the earlier preliminaries into action and think about blockciphers more formally.

Blockciphers. Given a non-empty finite set K and a non-empty set M, called the key space and the message space respectively, we let Block(K, M) denote the set of all functions E : K × M → M such that for each K ∈ K the map E(K, •) is 1. a permutation on M, and 2. length-preserving, in the sense that for all M ∈ M we have that |E(K, M)| = |M|. Such an E uniquely defines its inverse D : K × M → M. A blockcipher for key space K and message space M is a tuple of efficient algorithms BC := (E, D) such that E ∈ Block(K, M) and D is its inverse. We assume that the keys of a blockcipher are chosen uniformly from the key space K, which is typically {0, 1} k for some k ∈ N called the key length. Algorithm E is the deterministic enciphering algorithm E : K × M → M. Typically M = {0, 1} n for some n ∈ N called the block length. Algorithm D is the deterministic deciphering algorithm D : K × M → M.

A blockcipher is correct if for all K ∈ K and M ∈ M we have D(K, E(K, M)) = M. A (public) permutation on M is a blockcipher with a singleton key space K = {ε}. We denote a permutation with P and its inverse with P -. Ideal ciphers. The ideal cipher for key space K and message space M is the uniform distribution over Block(K, M). The idealcipher model (ICM) for given key and message spaces K, M is a model of computation where all parties, honest or otherwise, have oracle access to a uniformly random element in Block(K, M) and its inverse. The ideal-cipher model when restricted to K = {ε} gives rise to the random-permutation model (RPM). We abbreviate Block({0, 1}

k , {0, 1} n ) by Block(k, n) and Block({ε}, {0, 1} n ) by Perm(n).

The ideal-cipher model and the random-permutation model will be used extensively in Chapter 5 to assist in proving security for blockciphers.

Symmetric Encryption

Blockciphers are very useful, and will call upon them often, but they are subject to some constraints that can be debilitating in the real world. Because they are permutations, and deterministic, it means Spoiler: we get around these constraints by using modes of operation to turn blockciphers into encryption schemes.

that the encrypted message returned will always be the same given the same input, and all input output pairs will have the same length. Hence upon intercepting an encrypted message, the adversary can already infer information about the plaintext. We extend the ideas found in blockciphers to overcome these obstacles by defining possibly randomised encrypting algorithms which are not restricted to produce a ciphertext of the same length as the message. As such, we define a more general sense of encryption, which, when used with a shared secret key, we call symmetric encryption (SE). Let's use the framework from item 2.1 to define a symmetric encryption scheme. SE syntax. A symmetric encryption scheme SE consists of three algorithms SE = (Gen, Enc, Dec) that work as follows:

1. Gen is the randomized key generation algorithm that returns a bit string K from a finite key-space K (which is typically {0, 1} k for some k ∈ N).

2. Enc : K × M C is the randomized encryption algorithm which takes as input a key K, a message M from message space M, and returns a ciphertext C from some ciphertext-space C. We write this as C ← Enc(K, M).

The deterministic decryption algorithm

security notions for encryption

Taking a look at any security book, you will not be able to escape the three pillars of information security, namely, confidentiality, integrity, and authenticity. confidentiality provides the guarantee that the message cannot be understood by anyone other than those intended to read them. It is most often guaranteed by symmetric and public-key encryption.

integrity convinces us that a ciphertext has not been altered or tampered with on its journey from sender to receiver. Integrity is often guaranteed by hash functions.

authenticity gives the assurance that the message received by the receiver is indeed the one sent by the sender. This is usually guaranteed by sending a digital signature, or a message authentication code.

Any good encryption scheme aims to achieve confidentiality at the very least. Depending on how much power is given to the adversary, this can be easy or hard. There are a number of notions to capture

It is good to model the strongest possible adversaries to give the best security guarantees.

the power of an adversary; some are old, some are newer, and we consider here only the stronger notions of chosen-plaintext attacks (CPA), and chosen-ciphertext attacks (CCA) as outlined below and captured in Figure 2.2.

CPA-security In conducting a chosen-plaintext attack, and adversary A is given access to an encryption oracle Enc under which it can encrypt plaintext messages M of its choice. When queried, Enc encrypts messages under a key K which remains unknown to A. The encryption oracle then returns a ciphertext C ← Enc K (M) as the reply to the query.

CCA-security In a chosen-ciphertext attack, and adversary A has access to Enc, and an additional oracle for decryption, Dec, under which it can decrypt ciphertexts C of its choice. When queried, Enc encrypts messages under a key K which remains unknown to A. The encryption oracle then returns a ciphertext C ← Enc K (M). When queried, Dec decrypts ciphertexts under a key K which remains unknown to A. The decryption oracle then returns a plaintext message M ← Dec K (C) as the reply to the query. To avoid trivial wins, we disallow the adversary to query Dec (resp. Enc) with ciphertexts (resp. messages) that were previously generated by Enc (resp. Dec).

It is clear to see that CCA is the stronger notion of the security as the adversary is given access to both encryption and decryption oracles. This is the common standard security goal to aim for, and the one used in chapters 4 and 5. We say that we aim to achieve confidentiality through ciphertext indistinguishability, and that we give and adversary access to oracles that return ciphertext and/or plaintexts, but what exactly does it try to distinguish? There are a number of flavours of indistinguishability game, but there are two more common than others, which are described as follows:

Game CPA A SE : b {0, 1}; K K b A Enc return (b = b) Game CCA A SE : b {0, 1}; K K b A Enc,Dec return (b = b)
left-or-right indistinguishability (LR): A challenge bit b
and key K are chosen. An adversary A queries two messages (M 0 , M 1 ) to the encryption oracle. One of the messages, corresponding to the challenge bit is encrypted and returned as C b .

The adversary must then distinguish whether M 0 or M 1 was encrypted. It is often mandated that A can make at most q queries, after which their guess is returned as b . A wins if b = b. The advantage of A against a symmetric encryption scheme SE in the LR game is defined by

Adv lr-cca SE (A) = 2 • Pr[b = b] -1.
real-or-random indistinguishability (RR): As in LR, a challenge bit b and key K are chosen. In this game, an adversary A queries a single message (M) to the encryption oracle. Depending on the bit b, the oracle will encrypt either the real message, or will choose a string uniformly at random from the prescribed ciphertext space and returns the ciphertext as C b . The adversary A must distinguish whether it is an encryption of the real message or of a random string. Often with b = 1 being 'real' and b = 0 being 'random', A returns a bit b and wins if b = b. The CCA advantage of A against SE in the RR game is defined by

Adv rr-cca SE (A) = 2 • Pr[b = b] -1.
These notions appeared first in [START_REF] Bellare | A Concrete Security Treatment of Symmetric Encryption[END_REF] and are displayed pictorially in Figure 2.3 as a starting point to see how games will be presented throughout the thesis.

Authenticated Encryption

So far we have understood some provable security, something about blockciphers, using them to make symmetric encryption, are we done? Not yet.

There's one more thing to consider. . . Symmetric encryption gives strong guarantees for the confidentiality of a ciphertext. We know that in the CCA security model, even if we give an adversary A access to encryption and decryption oracles so they can obtain ciphertexts and messages, we can still maintain security (ciphertext indistinguishability). However, it is often the case that this is insufficient. Attacks have shown, that unless the encryption is authenticated in some way, the integrity of the system can be compromised. Authenticated Encryption aims to solve this by producing a message authentication code based on the plaintext, and encrypting this together with the plaintext to create the ciphertext. Although they differ in instantiation and implementation, there is only one syntactical difference between a symmetric encryption scheme SE and an authenticated encryption scheme AE. The encryption scheme Enc is randomised in SE, but is mandated to be deterministic in AE. AE syntax. An AE scheme is a 3-tuple of algorithms SE = (Gen, Enc, Dec), where 1. Gen is the randomized key generation algorithm that returns a bit string K from a finite key-space K (which is typically {0, 1} k for some k ∈ N).

Game LR-CCA A SE : b {0, 1}; K K b A LREnc,LRDec return (b = b) Game RR-CCA A SE : b {0, 1}; K * K b A RREnc,Dec return (b = b) Proc. LREnc(M 0 , M 1 ): C 0 ← Enc(K, M 0 ) C 1 ← Enc(K, M 1 ) CL ← CL : (K, C b ) return C b Proc. RREnc(M): C 0 ← Enc(M 0 ) C 1 {0, 1} |C 0 | CL ← CL : (K, C b ) return C b Proc. LRDec(C 0 , C 1 ): if (K, C) ∈ CL: return ⊥ M 0 ← Dec(K, C 0 ) M 1 ← Dec(K, C 1 ) return M b Proc. Dec(C): if (K, C) ∈ CL: return ⊥ M ← Dec(K, C) return M
2. Enc : K × M → C is the deterministic encryption algorithm which takes as input a key K, a message M from message space M and returns a ciphertext C from some ciphertext-space C. We write this as C ← Enc(K, M). Correctness requires that Dec(K, Enc(K, M)) = M for all values of the inputs above.

The deterministic decryption algorithm

AE security. For symmetric encryption we were content with achieving CCA security. For an authenticated encryption scheme, however, there is another guarantee that we need to define, ciphertext integrity (CI). If we can show a scheme to be both CCA secure, and CI secure, then we infer that the scheme is AE secure.

Ciphertext Integrity. In a CI game a challenge key K is chosen at random. An adversary A queries a message M to the challenger and receives encryptions of the message C Enc(K, M). A can make up to q such queries, after which it outputs a candidate ciphertext C that is different from all Cs returned by the challenger. We say that A wins the game if C is a valid ciphertext and Dec(K, C ) =⊥.

Given CCA and CI we say the AE advantage of an adversary A against an authenticated encryption scheme SE is defined by

Adv cca+ci SE (A) := 2 • Pr AE A SE -1 .

Nonce-Based Authenticated Encryption

With blockciphers we ran into trouble sometimes because the enciphering algorithm was mandated to be deterministic. We introduced symmetric encryption to overcome this (amongst other issues) by defining a randomised encryption algorithm. Now, in the authenticated setting, because of how authentication is formed, we are forced back to using deterministic encryption algorithms. A way to solve this issue is to introduce a user-specified nonce, that acts as an input to Enc and has the responsibility of flipping the random coins during the encryption process. The syntax is similar to AE, but introduces a nonce N from a nonce space N . For completeness, we describe the syntax below.

Nonce based AE syntax. An nonce-based AE scheme is a 3-tuple of algorithms SE = (Gen, Enc, Dec), where 1. Gen is the randomized key generation algorithm that returns a bit string K from a finite key-space K (which is typically {0, 1} k for some k ∈ N).

2. Enc : K × M × N → C is the deterministic encryption algorithm which takes as input a key K, a message M, and a nonce N and returns a ciphertext C. We write this as C ← Enc(K, M, N). Correctness requires that Dec(K, Enc(K, M, N), N) = M for all values of the inputs above.

The deterministic decryption algorithm

Dec : K × C × N → M ∪ {⊥}

Authenticated Encryption with Associated Data

With SE we got confidentiality, and with AE we introduced integrity. Authenticated Encryption with Associated Data (AEAD) addresses the third pillar, authenticity. It involves the addition of associated data (known as header data) that is bound to the ciphertext and to the environment. AEAD syntax. An AEAD scheme is a 3-tuple of algorithms SE = (Gen, Enc, Dec), where K, M, and C are defined as above, and 1. Gen is the randomized key generation algorithm that returns a bit string K.

2. Enc : K × M × N × H → C is the deterministic encryption algorithm which takes as input a key K, a message M, a nonce N from nonce space N , and possibly some associated header data H from header-space H and returns a ciphertext C. We write this as C ← Enc(K, M, N, H).

The deterministic decryption algorithm

Dec : K × C × N × H → M ∪ {⊥} takes a key K, a ciphertext C, a nonce N,
and possibly some associated header data H and returns either a plaintext M or the failure symbol ⊥ ∈ M. Correctness requires that Dec(K, Enc(K, M, N, H), N, H) = M for all values of the inputs above. Note that K, N, and H, must be the same in Enc and Dec for decryption to work. AEAD security. We define the AEAD-security of an authenticated encryption scheme SE = (Gen, Enc, Dec) by considering the game described in the middle in Fig. 2.4. The AEAD advantage of an adversary A against SE is defined by

Adv aead SE (A) := 2 • Pr AEAD A SE -1 .
It is required that A is nonce-respecting in that it does not repeat nonces in its encryption queries (but it may repeat them in decryption or across encryption and decryption queries).

Misuse-Resistant Authenticated Encryption (MRAE). We define the MRAE-security of an authenticated encryption scheme SE = (Gen, Enc, Dec) by considering the rightmost game described in Fig. 2.4. The MRAE advantage of an adversary A against SE is defined by

Adv mrae SE (A) := 2 • Pr MRAE A SE -1 .
However, in this case, unlike AEAD, A is not required to be noncerespecting and can repeat nonces in all queries.

It is clear to see that the syntax and the correctness of AE and its variants are very similar. Sometimes it is difficult to see the subtle differences between the notions. This is where the beauty of game based definitions comes in. Figure 2.4 outlines the RR indistinguishability games for the three variations.

Game AE A SE : b {0, 1}; K K b A RREnc,Dec return (b = b) Game AEAD A SE : b {0, 1}; K K b A RREnc,Dec return (b = b) Game MRAE A SE : b {0, 1}; K K b A RREnc,Dec return (b = b) Proc. RREnc(M): if M ∈ ML: return ⊥ C 1 ← Enc(K, M) if T[K, M] = undef: T[K, M] {0, 1} |C 1 | C 0 ← T[K, M] ML ← ML : (M) CL ← CL : (K, C b ) return C b Proc. RREnc(M, N, H): if (M, N, H) ∈ ML: return ⊥ C 1 ← Enc(K, M, N, H) if T[K, M, N, H] = undef: T[K, M, N, H] {0, 1} |C 1 | C 0 ← T[K, M, N, H] ML ← ML : (M, N, H) CL ← CL : (K, C b , N, H) return C b Proc. RREnc(M, N, H): if (M, H) ∈ ML: return ⊥ C 1 ← Enc(K, M, N, H) if T[K, M, N, H] = undef: T[K, M, N, H] {0, 1} |C 1 | C 0 ← T[K, M, N, H] ML ← ML : (M, H) CL ← CL : (K, C b , H) return C b Proc. Dec(C): if (K, C) ∈ CL: return ⊥ M ← Dec(K, C) return M Proc. Dec(C, N, H): if (K, C, N, H) ∈ CL: return ⊥ M ← Dec(K, C, N, H) return M Proc. Dec(C, N, H): if (K, C, N, H) ∈ CL: return ⊥ M ← Dec(K, C, N, H) return M

public-key cryptography

It is interesting to note that unlike English where the term 'Public-Key' pertains to both the concept of public-key encryption, and the public key itself. In (correct) french, a distinction is made between the concept 'la cryptographie à clé révélée' and the the keys themselves 'la clé publique' and 'la clé secrète'.

Up until now, we have discussed symmetric encryption where communicating parties share a common key. Symmetric encryption is very efficient, and very secure, but its major limitation is that it does not allow to distribute keys over insecure channels that allow eavesdropping. In an attempt to solve this, public-key cryptography was invented in the 1970's and redefined how we thought about keys. Schemes were designed to perform key exchange over an insecure channel, allowing parties to jointly compute a symmetric key. Further developments led to schemes producing two keys; one public, one private, such that the public key could be widely distributed and used by anyone to encrypt a message, but only the private key, kept secret, could be used to decrypt.

Key Exchange

The first key exchange protocol was described in [START_REF] Diffie | New Directions in Cryptography[END_REF] and was based on the DLP ( Section 2.2) To exchange a key, two parties agree When starting to learn cryptography, this is where the subject really feels like magic on public parameters p and g. The first party generates a random x and computes w = g x mod p which they send to the second party. By the DLP it is assumed that the second party, nor an eavesdropper, can infer the value x. The second party generates a random y, computes z = g y mod p and sends to the first party. After these two exchanges the first party knows x and z = g y mod p. They can then compute the exponentiation of z by x to get z x = (g y ) x mod p = g yx mod p. The second party knows y, and w = g x mod p, and can similarly compute w y = g xy = g yx = z x mod p. They have agreed on a common value. The eavesdropper only knows g x mod p and g y mod p. Without knowing x and y, there is no known efficient way for an eavesdropper to compute the shared secret, which can therefore be used to derive a symmetric key.

Public Key Encryption

In addition to key exchange, Diffie and Hellman's New Directions in Cryptography also introduced interactive public-key encryption (PKE). The first (published) non-interactive public-key encryption scheme, known as RSA was introduced by Rivest, Shamir, and Adelman [START_REF] Rivest | A Method for Obtaining Digital Signature and Public-Key Cryptosystems[END_REF] and remains the most widely used PKE today, based on the hardness of the RSA problem. Although they are very different in spirit, syntactically, SE and PKE are not all that different. The main difference, naturally, is the addition of a public key. PKE syntax. A public-key encryption scheme is a 3-tuple of algorithms PKE = (Gen, Enc, Dec) where 1. Gen is the randomised key generation algorithm that outputs a pair (pk, sk) Gen where pk is the public key, and sk is the secret key.

2. Enc is the randomised encryption algorithm that takes as input a public key pk, a message M from some message space M, and outputs a ciphertext C Enc(pk, M) where C belongs to a ciphertext space C. PKE Security. In the public-key setting, CPA security is somewhat meaningless, as such, as in the symmetric setting, we focus on the CCA security notion. It is arguably more important in the public-key setting as the receiver can receive encrypted messages from many, and possibly unknown sources.

CCA security in the public-key setting. Playing in the real-orrandom CCA indistinguishability game an adversary A interacts with the PKE environment to try to distinguish whether a real or random message was encrypted. Gen is run to produce a pair of keys (pk, sk). The adversary A is given access to the public key pk and to the decryption oracle Dec and outputs a message M. A uniform bit b is chosen, and a ciphertext C ← Enc(pk, M) is generated. Depending on whether b = 0 or b = 1, Enc either encrypts the message sent by A, or uniformly selects a message of the same length as M and encrypts it. The ciphertext C is sent to A. The adversary can then continue to interact with the decryption oracle in this manner, with the restriction that decryptions of C may not be asked. Eventually, A outputs a bit b and wins if b = b. The CCA advantage of A against PKE in the RR game is defined by

Adv rr-cca PKE (A) = 2 • Pr[b = b] -1.

Key Encapsulation Mechanisms

The advent of public-key cryptography solved the majority of key distribution problems. The first, through key exchange protocols, another, through public-key encryption, but there's a third, and it's sweet. We talked a lot about symmetric cryptography and how it gave nice security guarantees, and is very efficient. A way to overcome the private-key distribution problem is to use a key-encapsulation mechanism (KEM) to encrypt a symmetric key, in a public-key setting. This way, only the intended recipient, i. e. the one with the private key corresponding to the public key, can decrypt to reveal the symmetric secret key. This has come to be known as hybrid encryption.

Key-encapsulation mechanism. A key-encapsulation mechanism (KEM) is a 3-tuple of algorithms (Gen, Encaps, Decaps) such that:

1. Gen is the randomised key generation algorithm that outputs a pair (pk, sk) Gen where pk is the public key, and sk is the secret key. We assume pk and sk each have length at least k, and that k can be determined from pk.

The encapsulation algorithm Encaps takes as input a public key

pk and outputs a ciphertext C and a key K ∈ {0, 1} (k) where is the key length. We write this as (C, K) Encaps(pk).

3. Decaps is the deterministic decapsulation algorithm, which takes as input a private key sk and a ciphertext C, and outputs a key K or a special error symbol ⊥. We write this as K ← Decaps(sk, C).

KEM security. As with SE and PKE, the standard notion of security for KEM is that of CCA security. Again, playing in the CCA indistinguishability game, with an adversary A interacting with the KEM environment. Gen is run to produce a pair of keys (pk, sk). Then Encaps(pk) is run to obtain a pair (C, K). A bit b is chosen, and depending on whether b = 0 or b = 1 we set K = K or choose a uniform K ∈ {0, 1} n . The adversary A is given (pk, C, K ) and access to the decapsulation oracle Decaps(sk). The adversary can then continue to interact with Decaps in this manner, with the restriction that decapsulations of C may not be asked. Eventually, A outputs a bit b and wins if b = b. The CCA advantage of A against the KEM game is defined by

Adv cca KEM (A) = 2 • Pr[b = b] -1.
Public-key encryption and key-encapsulation mechanisms appear mostly in Chapters 7 and 8

digital signatures

We saw in the case of symmetric encryption that there was the need for more than message confidentiality. When introducing authenticated encryption we saw the need to achieve message integrity. A When they wrote "We stand today on the brink of a revolution in cryptography", they were not exaggerating! similar situation arises in public-key cryptography, and is solved by the creation of digital signatures. Yes, you guessed it, they were also introduced in the 1976 paper by Diffie and Hellman [START_REF] Diffie | New Directions in Cryptography[END_REF]. A digital signature scheme is simply a method to verify the authenticity of a message. The come in various flavours, and are based on similar hard problems as public-key encryption schemes; perhaps most notably, the DLP and integer factorisation problems.

Digital signature syntax. A digital signature scheme is a 3-tuple of algorithms Σ = (Gen, Sign, Verify).

1. Gen is the randomised key generation algorithm that generates a key-pair (sk, pk) Gen. The user then keeps the secret (or signing) key sk, and reveals the public (or verifying) key pk to everyone.

2. Sign is the signing algorithm that takes as input a message M, and a secret key sk, and outputs a signature σ Sign(pk, M).

3. Verify is the deterministic verification algorithm takes as input a signature σ, a message M, and a public key pk, and outputs True if verification works, and False otherwise. Verify(pk, M, σ) =

True ∨ False. Correctness requires that Verify(pk, M, Sign(sk, M)) = True for all possible pairs (pk, sk) generated by Gen and all valid messages M.

Signature security. In the symmetric setting, we introduced the notion of ciphertext integrity to authenticate our encryption scheme. With digital signatures, we have a similar concern. We can also think of the analogy with a handwritten signature where the greatest 'security' issue is that they can potentially be forged. In the digital setting a successful forgery is a signature that is accepted by the verifier, while being generated by an adversary, without using the secret key. Since

There is also the possibility that the secret key could be somehow extracted and then used, which constitutes a total break.

signatures are by nature public, adversaries can generally access a vast quantity of message-signature pairs; in some scenarios they can even ask their targets to sign well-crafted documents. To guarantee security, we require that even despite having access to all this information, an adversary should not be able to produce forgeries.

Unforgability. We hope to achieve a notion that provides assurance that there exists no forgery under a chosen message attack. The notion has become known as 'existential unforgability', and we denote it by EUF-CMA. Given a digital signature scheme Σ = (Gen, Sign, Verify), an an adversary A playing the EUF-CMA game aims to come up with a pair (M, σ) such that Verify(pk, M, σ) = 1. In the EUF-CMA game, Gen is run to obtain public-private key pair (pk, sk). A is given pk, and access to a signing oracle Sign(sk). After some time, A outputs a candidate message and signature pair (M, σ). Let ML denote the list of all As queries to the signing oracle. We say that A succeeds if two conditions are met:

Game EUF-CMA A Σ : (sk, pk) Gen (M * , σ * ) ← A Sign,Verify,H if (M * , σ * ) ∈ L return Verify(pk, M * ) return ⊥ Sign(M): σ Sign(sk, M) L ← L ∪ {M, σ} return σ Verify(M, σ): return Verify(pk, M, σ)
1. Verify(pk, M, σ) = True, and 2. M / ∈ ML A signature scheme Σ is secure against existential forgeries in a chosenmessage attack (strongly EUF-CMA-secure) if the advantage of any PPT adversary A against the EUF-CMA game defined in Figure 9.1 is negligible:

Adv euf-cma Σ,A = Pr EF A Σ (λ) = 1 ∈ Negl 2.8.1 Concrete Signature Schemes DLP-Based Signatures.
ElGamal introduced in 1984 the first DLPbased signature scheme [START_REF] Elgamal | A Public Key Cryptosystem and a Signature Scheme Based on Discrete Logarithms[END_REF]. It inspired the more efficient Schnorr signature scheme [START_REF] Schnorr | Efficient Identification and Signatures for Smart Cards[END_REF], for which a security proof is known in the random oracle model assuming the hardness of DLP [PS00]. Schnorr's scheme was initially protected by patents, which had the effect of limiting its diffusion. All these schemes can be implemented on elliptic curves (EC), to decrease parameter size and improve performance.

The patent surrounding Schnorr signatures expired in 2008, and since then, they have been gaining popularity.

Schnorr Signatures. Schnorr signatures are provably secure in the Random Oracle Model under the assumed hardness of solving generic DLP instances and work in the following way. A cyclic group G = Z p of prime order p is chosen, in which it is assumed that the DLP is hard, along with a generator g ∈ G. A hash function H : G × {0, 1} k → Z p is chosen. A Schnorr signature scheme is a 3-tuple of algorithms that work as follows:

-Gen(g) takes as input the generator g of G and chooses a (secret) signing key sk Z p and a (public) verification key pk ← g sk .

-Sign(sk, M) takes as input the signing key sk and a message M ∈ {0, 1} k . It chooses a random integer r Z p , sets R ← g r , and C ← H(R, M), and computes y ← sk • C + r mod p. Finally, it outputs a signature σ = (R, y).

-Verify(pk, M, (R, y)): Computes e ← H(M, R) and returns True if g y = pk e • R, and False otherwise. Schnorr signatures form the basis for the work contained in Part IV.

Part II T R Y A G A I N

Abstract

We study the security of symmetric primitives against key-correlated attacks (KCA), whereby an adversary can arbitrarily correlate keys, messages, ciphertexts, and possibly nonces and associated data. Security against KCA is required whenever a primitive should securely encrypt key-dependent data, even when used under related keys. KCA is a strengthening of the previously considered notions of relatedkey attack (RKA) and key-dependent message (KDM) security. This strengthening is strict, as we show that 2-round Even-Mansour fails to be KCA secure even though it is both RKA and KDM secure. We provide feasibility results in the ideal-cipher model for KCAs and show that 3-round Even-Mansour is KCA secure under key offsets in the random-permutation model. We also give a natural transform that converts any authenticated encryption scheme to a KCA-secure one in the random-oracle model. Conceptually, these results allow for a unified treatment of RKA and KDM security in idealised models of computation.

This is joint work with Pooya Farshim and Georg Fuchsbauer.

Cryptographic algorithms are subject to a multitude of threats. Many of these threats are accounted for in the theoretical security analysis carried out by cryptographers, but not all. For example, early on, the seminal paper of Goldwasser and Micali [START_REF] Goldwasser | Probabilistic Encryption[END_REF] pointed out that guarantees of semantic security may break down if the adversary sees encryptions of the secret key. Formal analyses of protocols can also become moot [START_REF] Biham | New Types of Cryptanalytic Attacks Using related Keys (Extended Abstract)[END_REF][START_REF] Biham | New Types of Cryptanalytic Attacks Using Related Keys[END_REF] when the assumption that cryptosystems are run on independently generated keys no longer holds. A number of works have analyzed the security of cryptosystems in the presence of key-dependent messages or when different keys are generated in dependent ways (see the related work section below). We continue this line of work and ask to what extent basic cryptosystems (such as blockciphers and symmetric encryption) can resist attacks that exploit correlated inputs.

motivation

Our motivation for studying correlated-input security is twofold. We are interested in settings where a cryptosystem may be run on related keys-either by design or due to attacks-to securely encrypt messages that depend on the encryption key. Suppose a user stores a secret key K on its hard drive. An adversary may be able to tamper with this key, for example flip some of its bits and change it to K ⊕ ∆ for some bit string ∆. It may then obtain a full-disk encryption under this key. It is not clear what security assertions can be made, as this setting falls outside both the related-key attack (RKA) and the key-dependent message (KDM) models. Indeed, the RKA model only allows the adversary to obtain encryptions of the form Enc(φ(K), M), for functions φ mapping keys to keys, but for key-independent messages, while KDM accounts for key-dependent encryptions of type Enc(K, ψ(K)), for functions ψ mapping keys to messages, but under untampered keys. In the described attack, the adversary obtains Enc(K ⊕ ∆, K ⊕ ∆). This is not covered by either of these models since both the key and the message are correlated with the original key. Other applications of KCAs include efficient garbling of XORs [START_REF] Applebaum | Garbling XOR Gates "For Free" in the Standard Model[END_REF], where KCA security (called RK-KDM there) with respect to linear functions or the form α • K ⊕ ∆ for a bit α are used.

These settings require a stronger security notion, which is what we introduce here. The Key-Correlated Attacks (KCAs) model lets the adversary obtain encryptions of key-dependent messages under related keys. Generally, wherever there is a possibility of both RKAs and KDM attacks, i.e., key-correlated encryptions of the form Enc(φ(K), ψ(K)), there is good chance that the actual security needed is KCA security. A typical use case is when the round functions of a block cipher are keyed via related keys, and the construction is used to encrypt key-dependent data.

In our model, for generality, simplicity and strength, we symmetrically allow for key-dependent ciphertexts, that is, the adversary can see Dec(φ(K), ψ(K)). Such settings arise when the decryption algorithm of a blockcipher is run during encryption, which is for example the case in the triple DES construction [START_REF] Bellare | The Security of Triple Encryption and a Framework for Code-Based Game-Playing Proofs[END_REF], the ElmD construction [START_REF] Bossuet | ELmD: A Pipelineable Authenticated Encryption and Its Hardware Implementation[END_REF], or in amplification theorems for blockciphers [START_REF] Ueli | Composition of Random Systems: When Two Weak Make One Strong[END_REF][START_REF] Benoit Cogliati | Security Amplification for the Composition of Block Ciphers: Simpler Proofs and New Results[END_REF].

Our second motivation is conceptual in that KCA provides a unified approach to RKA and KDM security analyses of symmetric primitives. More concretely, our goal is to prove KCA feasibility theorems and then derive RKA and KDM security as simple corollaries. This allows for reuse of security proofs and identifies classes of permitted attacks more generally, while leading to stronger security results. [START_REF] Bellare | Authenticated and Misuse-Resistant Encryption of Key-Dependent Data[END_REF] studied KDM in the context of authenticated encryption. Bellare, Cash, and Keelveedhi [START_REF] Bellare | Ciphers that securely encipher their own keys[END_REF] give a generic construction of a tweakable blockcipher from a blockcipher which is KDM secure. More recently, Farshim, Khati, and Vergnaud [START_REF] Farshim | Security of Even-Mansour Ciphers under Key-Dependent Messages[END_REF] studied KDM security for the ideal cipher and the iterated Even-Mansour constructions. In the asymmetric setting the first feasibility result in the standard model for rich classes of functions was by Boneh et al. [START_REF] Boneh | Circular-Secure Encryption from Decision Diffie-Hellman[END_REF]. Camenisch, Chandran and Shoup [START_REF] Camenisch | A Public Key Encryption Scheme Secure against Key Dependent Chosen Plaintext and Adaptive Chosen Ciphertext Attacks[END_REF] gave a KDM-CCA secure public-key encryption scheme.

Correlated inputs. Study of security under correlated inputs goes back to the work of Ishai et al. [START_REF] Ishai | Extending Oblivious Transfers Efficiently[END_REF] as correlation-robustness in the design of oblivious transfer protocols. Correlated-input security was made explicit for hash functions by Goyal, O'Neill, and Rao [START_REF] Goyal | Correlated-Input Secure Hash Functions[END_REF], who show relations with related-key attacks. The work of Böhl, Davies and Hofheinz [START_REF] Böhl | Encryption Schemes Secure under Related-Key and Key-Dependent Message Attacks[END_REF] considers related-key attacks in the presence of key-dependent messages. Their RKA-KDM security could be considered a natural analogue of our model for public-key encryption. They construct schemes that achieve their notion based on number-theoretic assumptions such as DDH, LWE, QR, or DCR. Applebaum [START_REF] Applebaum | Garbling XOR Gates "For Free" in the Standard Model[END_REF] gives an RKA-KDM symmetric encryption scheme based on the LPN assumption.

contributions

Building on the above line of works, we formulate a new security model incorporating and strengthening both the RKA and KDM models. We speak of key-correlated attack (KCA) in this context, a name that is loosely inspired by the introduction of correlated-input attacks against hash functions [START_REF] Goyal | Correlated-Input Secure Hash Functions[END_REF] (note that the notion of key-dependent input attacks has already been used by Halevi and Krawczyk [START_REF] Halevi | Security under key-dependent inputs[END_REF]). We give appropriate definitions of security under key-correlated attacks that relate well to the standard RKA and KDM security notions. Our definition extends that in [START_REF] Applebaum | Garbling XOR Gates "For Free" in the Standard Model[END_REF] for randomized symmetric encryption under chosen-plaintext attacks to the setting of authenticated encryption with associated data (AEAD).

We start with comparing our notion to existing ones. After proving that KCA implies RKA and KDM security, we show that KCA security is strictly stronger than even simultaneously having RKA and KDM security. We give a natural separation by demonstrating a KCA attack on the 2-round Even-Mansour cipher, which was shown to satisfy both RKA and KDM security in two previous works [START_REF] Farshim | The Related-Key Security of Iterated Even-Mansour Ciphers[END_REF][START_REF] Farshim | Security of Even-Mansour Ciphers under Key-Dependent Messages[END_REF].

After defining KCA and showing a separation result, we study feasibility of KCAs. Our starting point is the ideal-cipher model, in which all parties have oracle access to a keyed random permutation in both directions. We cannot allow arbitrary dependencies of keys and messages as otherwise "trivial" attacks, which work against any scheme, arise. To exclude these and thus obtain a meaningful notion, we restrict the classes of allowed dependencies. We show that if they satisfy appropriate notions of key-unpredictability and clawfreeness then the ideal cipher satisfies KCA security. Roughly speaking, key-unpredictability requires that the adversary does not obtain encryptions or decryption under predictable keys. Claw-freeness, on the other hand, requires that the inputs are distinct, and so repetition pattern of the outputs cannot be exploited. Analogues of these notions were previously considered in the RKA and KDM settings.

In our setting we require a third condition, which we call cross-keyclaw detectability, that allows us to deal with claws across encryption and decryption queries. This notion is sufficiently weak so that in the RKA and KDM setting it automatically follows from claw-freeness. In the KCA setting, however, it does not necessarily, as it restricts claws on keys.1 Two results on the RKA and KDM security of the ideal cipher by Bellare and Kohno [START_REF] Bellare | A Theoretical Treatment of Related-Key Attacks: RKA-PRPs, RKA-PRFs, and Applications[END_REF] and Farshim, Khati, Vergnaud [START_REF] Farshim | Security of Even-Mansour Ciphers under Key-Dependent Messages[END_REF] respectively, fall out as natural corollaries of our theorem.

Turning to concrete constructions, we analyze the KCA security of the iterated Even-Mansour cipher with three rounds in the randompermutation model. We show that with reuse of keys (which is known to be necessary for RKA security [START_REF] Farshim | The Related-Key Security of Iterated Even-Mansour Ciphers[END_REF]) and using different permutations (which is necessary for KDM security whenever keys are reused [BW99; FKV17]) we can provably achieve security against key-correlated attacks that concurrently encrypt messages M or offsets of key of the form K ⊕ ∆ 2 under other offsets of the key of the form K ⊕ ∆ 1 . This strengthens two feasibility results due to Farshim, Khati, Vergnaud [START_REF] Farshim | Security of Even-Mansour Ciphers under Key-Dependent Messages[END_REF] and Farshim and Procter [START_REF] Farshim | The Related-Key Security of Iterated Even-Mansour Ciphers[END_REF].

From a technical point of view, the novelty of our KCA proof for 3-round Even-Mansour is that we keep the outer permutations partially consistent with the replaced forgetful oracles as well as the permutation oracles. For legal queries we show this can be done with overwhelming probability, while a detection algorithm will allow us to identify illegal queries and reject them. This proof thus deviates from previous works in which oracles are fully decoupled. As a result we also obtain a different (albeit somewhat more complex) way to prove the RKA security of 3-round Even-Mansour against key offsets by replacing the outer (rather the inner) permutation [START_REF] Farshim | The Related-Key Security of Iterated Even-Mansour Ciphers[END_REF].

We end this part by showing how to generically transform any AE-secure AEAD scheme to one which is a KCA-secure in the randomoracle model by hashing the key with nonces. For this result we only require the set of allowed functions to be unpredictable, as nonces automatically prevent repetitions due to claws in the functions. In contrast to previous work by Bellare and Keelveedhi [START_REF] Bellare | Authenticated and Misuse-Resistant Encryption of Key-Dependent Data[END_REF] on similar transforms for achieving KDM-security, our scheme is secure with key-dependent nonces and headers. Although key-dependent headers are briefly discussed in [START_REF] Bellare | Authenticated and Misuse-Resistant Encryption of Key-Dependent Data[END_REF], security with respect to key-dependent nonces is not considered at all. Arguably, however, there is a stronger case for the key-dependency of nonces than of headers: when nonces are randomly chosen they might become correlated with the key due to, e.g., bad generation of random numbers. For key-dependent headers, Bellare and Keelveedhi give a negative result, by having the adversary exploit the pattern of decryption errors (either ⊥ for an illegal query or 0 for failure in authenticity) to recover the key. In our setting, however, the decryption oracle only returns a single error symbol, which enables security under key-dependent inputs. If our model were modified to also have distinct error symbols, an attack similar to that in [START_REF] Bellare | Authenticated and Misuse-Resistant Encryption of Key-Dependent Data[END_REF] would arise. We note that in these settings one might be able to obtain non-trivial feasibility results by requiring a form claw-freeness. 2Where to go from here. In Chapter 4, we define KCA security for blockciphers and study its relation to RKA and KDM security before showing two separation results in Section 7.3. In Chapter 5 we study KCA in the ideal-cipher model and we prove 3-round Even-Mansour KC-CCA secure for offsets. Chapter 6 contains our generic construction of a KCA-secure authenticated encryption scheme from any AE-secure one.

T H E M O D E L

concept and definitions

Correlation-derivation function (CDF). A correlation-derivation function (CDF) is a circuit of the form

ξ : K -→ K × M .
A set of such functions is called a CDF set. Throughout the paper we denote CDF sets by Ξ and require that membership of a CDF set can be efficiently decided. We will define key-correlated security primitives relative to two CDF sets Ξ e and Ξ d that describe allowed encryption and decryption queries, respectively. KCA-secure blockciphers. Let BC be a blockcipher with key space K = {0, 1} k and message (and ciphertext) space M = {0, 1} n . Let Ξ e and Ξ d be CDF sets for the input space K × M. The KC-CCA advantage of an adversary A against BC is defined by

Adv kc-cca BC (Ξ e , Ξ d , A) := 2 • Pr KC-CCA Ξ e , Ξ d , A BC -1 , (4.1)
where game KC-CCA Ξ e , Ξ d , A BC is given in Figure 4.1. In this game, the adversary's goal is to decide whether (case b = 1) its oracles are using the blockcipher BC = (E, D) or (case b = 0, the ideal case) a random permutation iE and its inverse iD. Lists ML and CL prevent the adversary from trivially winning the game. Otherwise the adversary could, for instance, recover the challenge key K * by querying an encryption (or decryption) of K * and subsequently ask for decryption (or encryption) of the oracle's reply.

We note that for two sets Ξ e 1 ⊆ Ξ e 2 and Ξ d 1 ⊆ Ξ d 2 security against (Ξ e 2 , Ξ d 2 )-KC-CCA implies security against (Ξ e 1 , Ξ d 1 )-KC-CCA. Whenever Ξ d = ∅ we obtain a chosen-plaintext attack model.

Note.

Analogues of KCA security can be formulated for hash functions and pseudorandom generators, which become equivalent to correlated-input security for hash functions [START_REF] Goyal | Correlated-Input Secure Hash Functions[END_REF] and RKA security for PRGs [START_REF] Bellare | Cryptography Secure against Related-Key Attacks and Tampering[END_REF].

examples

As examples of KC functions, suppose that related keys, described by functions from some set Φ, are used within the specification of an encryption scheme (an example are the 3GPP protocols [START_REF] Iwata | New Security Proofs for the 3GPP Confidentiality and Integrity Algorithms[END_REF]). Suppose further that the scheme is used to encrypt messages that depend 39 the model on the key in ways represented by functions from a set Ψ. The overall effect is that an adversary has access to ciphertexts corresponding to key-dependent messages under related keys. In other words, the adversary can see key-correlated ciphertexts for functions:

Game KC-CCA Ξ e , Ξ d , A BC : b {0, 1} (iE, iD) Block(K, M) K * K b A KCEnc,KCDec return (b = b) Proc. KCEnc(ξ e ): (K, M) ← ξ e (K * ) if (K, M) ∈ ML: return ⊥ C ← E(K, M) if b = 0: C ← iE(K, M) CL ← CL : (K, C) return C Proc. KCDec(ξ d ): (K, C) ← ξ d (K * ) if (K, C) ∈ CL: return ⊥ M ← D(K, M) if b = 0: M ← iD(K, M) ML ← ML : (K, M) return M
ξ : K → (φ(K), ψ(K))
with φ ∈ Φ and ψ ∈ Ψ , and

ξ : K → (φ(K), M) with φ ∈ Φ and M ∈ M .
Alternatively, suppose an adversary has access to encryptions under related keys with respect to Φ through, say, injection of faults that change bits of a hardware-stored encryption key [BDL97; BS97].1 If the scheme is used to encrypt key-dependent messages with respect to Ψ, the adversary would be able to launch a KCA for the functions:

ξ : K → φ(K), ψ(φ(K)) with φ ∈ Φ and ψ ∈ Ψ , and ξ : K → (φ(K), M) with φ ∈ Φ and M ∈ M .
The KCA model thus captures, among other things, a variety of joint RKA and KDM attacks on a blockcipher.

relation with rka and kdm

Let id denote the identity function on a key space K and let Γ denote the set of all constant functions K → M for M ∈ M. We identify a pair of functions (φ, ψ), with ranges K and M respectively, with the correlation-derivation function K → (φ(K), ψ(K)).

CPA/CCA-only sets. We call a pair (Ξ e , Ξ d ) CCA-only if Ξ e = Ξ d = {id} × Γ. (The adversary can only make regular encryption and decryption queries.

) We call (Ξ e , Ξ d ) CPA-only if Ξ e = {id} × Γ and Ξ d = ∅.
RKA/KDM-only sets. We call a pair (Ξ e , Ξ d ) RKA-only if Ξ e = Ξ d = Φ × Γ for an RKA set Φ of functions mapping keys to keys. We call (Ξ e , Ξ d ) KDM-only if Ξ e = {id} × Ψ and Ξ d = {id} × Γ (i.e., no key-dependent ciphertexts allowed [START_REF] Farshim | Security of Even-Mansour Ciphers under Key-Dependent Messages[END_REF]) for a KDM set Ψ of functions mapping keys to messages. (The CPA versions are defined analogously by demanding that Ξ d = ∅.) We assume that any KDM set Ψ contains Γ, as it is natural to always allow for chosen plaintexts.

We show that our definition of KC security extends the standard RKA and KDM definitions for blockciphers, which we recall in Appendix Section 4.5. In particular, for KDM-only sets we have that KCA and KDM security are equivalent and similarly for RKA-only sets KCA and RKA security are equivalent. For two of the four implications, we assume claw-freeness of the correlation-derivation functions. This requires that it is hard to find two different functions that have the same output given a random input and is defined formally in Section 5.1 (p. 54). Claw-freeness is required because the KCA game returns ⊥ whenever claws are detected whereas the RKA game does not. The proof of the following proposition can be found in Section 4.5.

Proposition 4.1. Let BC be a blockcipher. Let Ξ e and Ξ d be two CDF sets.

rka: Suppose (Ξ e , Ξ d ) are RKA-only with Ξ e = Ξ d = Φ × Γ. If BC is (Ξ e , Ξ d )-KC-CCA-secure then it is Φ-RK-CCA secure. If BC is Φ-RK-CCA-secure and Ξ e = Ξ d is claw-free then BC is (Ξ e , Ξ d )- KC-CCA-secure.
In particular, let n be the block length, A be an adversary and q the maximum number of its queries. Then there exists an adversary B such that

Adv rk-cca BC (Φ, A) ≤ Adv kc-cca BC (Ξ e , Ξ d , B) + q 2 /2 n .
Moreover, there exist adversaries B and B cf such that

Adv kc-cca BC (Ξ e , Ξ d , A) ≤ q 2 • Adv cf Φ (B cf ) + 1/2 n + Adv rk-cca BC (Φ, B) .
kdm: Suppose (Ξ e , Ξ d ) are KDM-only with Ξ e = {id} × Ψ and

Ξ d = {id} × Γ. If BC is Ψ-KDM-CCA secure then it is (Ξ e , Ξ d )-KC-CCA- secure. If BC is (Ξ e , Ξ d )-KC-CCA-secure and Ξ e is claw-free then BC is Ψ-KDM-CCA-secure.
In particular, for every adversary A there exists an adversary B such that

Adv kc-cca BC (Ξ e , Ξ d , A) = Adv kdm-cca BC (Ψ, B) ,
and there exist adversaries B and B cf such that

Adv kdm-cca BC (Ψ, A) ≤ q 2 • Adv cf Ψ (B cf ) + Adv kc-cca BC (Ξ e , Ξ d , B) ,
where q is the maximum number of queries adversary A makes. Analogous implications hold in the CPA setting.

the model

E (K, M): C * ← E(min(K, K), 0 n ) if M = K: return C * if M = D(K, C * ): return E(K, K) return E(K, M) D (K, C): C * ← E(min(K, K), 0 n ) if C = C * : return K if C = E(K, K): return D(K, C * ) return D(K, C) Figure 4.2 -Blockcipher (E , D
) that is both KDM-secure and RKA-secure secure but not KCA-secure.

key-correlated attacks

In this section we show that even if a blockcipher simultaneously achieves security against RK and KDM attacks, it may still fail to achieve security against concurrent RK/KDM attacks, and hence also fail to achieve KCA security. We provide two separations, one artificial and one natural, to demonstrate this.

A generic separation result

Let K = M = {0, 1} n and define the following sets of functions:

Φ ⊕ := K → K ⊕ M : M ∈ M Ψ ⊕ := K → α • K ⊕ M : M ∈ M, α ∈ {0, 1} (4.2)
Ξ ⊕ := K → (K ⊕ M 1 , α • K ⊕ M 2 ) : M 1 , M 2 ∈ M, α ∈ {0, 1} .
Given a Φ ⊕ -RKA secure and Ψ ⊕ -KDM secure blockcipher (E, D), consider the modified cipher (E , D ) shown in Fig. 4.2, where min is the lexicographic minimum and K := K ⊕ 1 k . Note that (E , D ) is again a blockcipher, i.e., a permutation for each value of the key (we simply swapped E(K, K) and C * in the image space).

Note that min(K, K) = min(K, K), thus

E (K, K) = E (K, K).
To see that (E , D ) is not (Ξ ⊕ , ∅)-KC-CCA secure, consider an adversary that queries K → (K, K) and K → (K, K) = (K ⊕ 1 n , K ⊕ 1 n ) to its KCEnc oracle. For the modified cipher both queries yield the same result:

E (K, K) = E min(K, K), 0 n = E min(K, K), 0 n = E (K, K) ,
while for the ideal cipher this would only happen with probability 1/2 n . On the other hand, the modified cipher (E , D ) remains both RKA and KDM secure as it essentially behaves like (E, D) when no joint RKA and KDM attacks as above can be mounted. We kept this discussion informal as our second separating example below is more natural and practically relevant.

M K 1 P 1 K 2 P 2 K 3 K r P r K r+1 C Figure 4.3 -The r-round iterated Even-Mansour cipher.

Attack on 2-round Even-Mansour

The r-round Even-Mansour cipher EM is defined by r permutations P 1 , . . . , P r , has key space K = {0, 1} (r+1)n , domain M = {0, 1} n and en-and deciphering algorithms (cf. Fig. 4.3)

E (K 1 , . . . , K r+1 ), M := P r . . . P 2 (P 1 (M ⊕ K 1 ) ⊕ K 2 ) . . . ⊕ K r+1 , D (K 1 , . . . , K r+1 ), C := P - 1 . . . P - r-1 (P - r (C ⊕ K r+1 ) ⊕ K r ) . . . ⊕ K 1 .
The EM ciphers can also be considered in configurations where (some of the) keys and/or (some of the) permutations are reused in different rounds. We denote the EM cipher where P i and K i+1 are used in round i by EM P 1 ,...,P r [K 1 , K 2 , . . . , K r+1 ].

Recall the function sets Φ ⊕ , Ψ ⊕ , and Ξ ⊕ from (4.2). The 2-round Even-Mansour cipher with key reuse and independent permutations E(K, M) := EM P 1 ,P 2 [K, K, K] was shown to be Φ ⊕ -RK-CPA secure in [START_REF] Farshim | The Related-Key Security of Iterated Even-Mansour Ciphers[END_REF] and Ψ ⊕ -KDM-CCA secure in [START_REF] Farshim | Security of Even-Mansour Ciphers under Key-Dependent Messages[END_REF]. We now show that this construction fails to be (Ξ ⊕ , ∅)-KC-CCA secure. Consider the KDM encryption

E(K, K) = P 2 (P 1 (0 n ) ⊕ K) ⊕ K . (4.3)
Now let ∆ * := P 1 (0 n ) ⊕ P 1 (1 n ) and consider the key-correlated en- cryption

C 1 := E(K ⊕ ∆ * , K ⊕ ∆ * ⊕ 1 n ) = P 2 (P 1 (1 n ) ⊕ K ⊕ ∆ * ) ⊕ K ⊕ ∆ * = P 2 (P 1 (0 n ) ⊕ K) ⊕ K ⊕ ∆ * (4.3) = E(K, K) ⊕ ∆ * .
Thus the two key-correlated ciphertexts C 1 and E(K, K) differ by a known value ∆ * . For the ideal cipher this event only occurs with probability 1/2 n , as both ciphertexts would be randomly distributed among at least 2 n -1 values. An attacker thus merely needs to make two queries K → (K, K) and K → (K ⊕ ∆ * , K ⊕ ∆ * ⊕ 1 n ) and check whether the answers differ by ∆ * .

relation between kca, rka, and kdm

RKA and KDM security. Fig. 4.4 gives the definitions of RKA security [START_REF] Bellare | A Theoretical Treatment of Related-Key Attacks: RKA-PRPs, RKA-PRFs, and Applications[END_REF] and KDM security [START_REF] Farshim | Security of Even-Mansour Ciphers under Key-Dependent Messages[END_REF] for blockciphers. The We require that φ ∈ Φ for all queries φ. (Bottom) Game defining the Ψ-KDM-CCA security of BC with key space K and message space M.

Game RK-CCA Φ,A BC : b {0, 1}; K * K (iE, iD) Block(K, M) b A RKEnc,RKDec return (b = b) Proc. RKEnc(φ, M): K ← φ(K * ) C ← E(K, M) if b = 0: C ← iE(K, M) return C Proc. RKDec(φ, C): K ← φ(K * ) M ← D(K, C) if b = 0: M ← iD(K, C) return M Game KDM-CCA Ψ,A BC : b {0, 1}; K * K (iE, iD) Block(K, M) b A KDMEnc,Dec return (b = b) Proc. KDMEnc(ψ): M ← ψ(K * ) C ← E(K * , M) if b = 0: C ← iE(K * , M) CL ← CL : C; return C Proc. Dec(C): if C ∈ CL: return ⊥ M ← D(K * , C) if b = 0: M ← iD(K * , C) return M
We require that ψ ∈ Ψ for all queries ψ.

advantage functions are defined in the standard way (as for KCA, Equation (4.1) in Sec. 4). The CPA versions are obtained naturally by disallowing decryption queries. We now prove that for RKA-only (resp. KDM-only) claw-free sets KCA and RKA (resp. KDM) security are equivalent. For convenience we restate Proposition 4.1 as Propositions 4.2 and 4.5 below.

KC(RK-only) ⇔ RK

Proposition 4.2. Let BC be a blockcipher. Let Ξ e and Ξ d be two RKA-only CDF sets with Ξ e = Ξ d = Φ × Γ. Then for every adversary B there exists an adversary A such that

Adv rk-cca BC (Φ, B) ≤ Adv kc-cca BC (Ξ e , Ξ d , A) + q 2 /2 n ,
where n is the block length and q is the maximum number of queries B makes. Moreover, for every adversary A there exist adversaries B and B cf such that

Adv kc-cca BC (Ξ e , Ξ d , A) ≤ q 2 • (Adv cf Φ (B cf ) + 1/2 n ) + Adv rk-cca BC (Φ, B) ,
where q is the maximum number of queries adversary A makes.

Recall that (Ξ e , Ξ d ) is RKA-only if Ξ e = Ξ d = Φ × Γ for an RKA set Φ of functions mapping keys to keys (where Γ is the set of constant functions over M). The difference between games RK and KC is that in the former there are no lists ML and CL, thus all queries are allowed. When showing KC⇒RK, the reduction must therefore answer all queries, while its KC challenger might reply with ⊥. The reduction will therefore keep local lists CL and ML , which simulate the challenger's blacklists.

The KC challenger, when queried KCEnc(ξ e = (φ e , M)) stores pairs (K = φ e (K * ), C = E(K, M)) in its list CL. The reduction does not know the values K and will store pairs (C, M) in a list CL . In the KC game, queries KCDec(ξ d = (φ d , C)) with (φ d (K * ), C) ∈ CL are answered with ⊥, whereas in the RK game, RKDec(φ d , C) always returns D(φ d (K * ), C). To answer such queries, the reduction looks for an entry (C, M ) for some M in its list CL . If (1) there is only one such entry, it returns M , which perfectly simulates RKDec: if (C, M ) ∈ CL and KCDec(ξ d = (φ d , C)) returned ⊥ then (φ e (K * ), C) ∈ CL and if there is only one entry with C, we must have φ d (K * ) = φ e (K * ). If (2) there are several entries (C, M 0 ), (C, M 1 ) ∈ CL , the reduction aborts the simulation and returns 1 (that is, it guesses that it is interacting with the actual blockcipher). As we show in the lemma below, we can bound the probability of this type of collision in CL in case the reduction is interacting with an ideal cipher, and therefore the probability of aborting and returning a wrong guess. The list ML and queries to the KCEnc oracle are dealt with analogously.

Lemma 4.3. Consider game KC-CCA Ξ e , Ξ d , A BC with b fixed to 0. Then the probability that there are two entries (K 0 , C), (K 1 , C) ∈ CL with iD(K 0 , C) = iD(K 1 , C) is at most q 2 /2 n , where q is the number of queries made by A. The same holds for the probability of two entries

(K 0 , M), (K 1 , M) ∈ ML with iE(K 0 , M) = iE(K 1 , M).
Proof. Let us consider CL (the case ML is completely analogous). In order for a pair (K, C) to be added to CL, the adversary must make a query KCEnc(ξ e = (φ e , M)) such that K = φ e (K * ) and C = iE(K, M).

Since (iE, iD) is ideal, the probability that after q queries the adversary finds K 0 , K 1 , M 0 = M 1 such that iE(K 0 , M 0 ) = iE(K 1 , M 1 ) =: C, without having queried both iD(K 0 , C) and iD(K 1 , C) before, is at most q 2 /2 n . On the other hand, when the adversary queries both KCDec(φ 0 , C) and KCDec(φ 1 , C) with φ i (K * ) = K i , then (K 0 , M 0 ) and (K 1 , M 1 ), with M i := iD(K i , C), are both added to ML. But then any call to KCEnc(ξ e = (φ i , M i )) with φ (K * ) = K i will be answered with ⊥, meaning that (K i , C) will not be added to CL. So the only way for the event to happen is that the adversary guesses K 0 , K 1 , M 0 = M 1 which map to the same C. KC ⇒ RK. We now prove the first statement of Proposition 4.2. Consider an adversary B against RK; we construct a reduction A against KC, which maintains local lists CL and ML , allowing it to simulate B's oracles even when its own oracles return ⊥.

Whenever adversary B queries RKEnc on (φ, M), reduction A queries its own oracle KCEnc on ξ e : K → (φ(K), M). If its answer is ⊥ then there must be an entry (M, C ) in ML . If there is more than one such entry, A stops and returns 1; otherwise it returns C . If A's KCEnc oracle returned a value C = ⊥, B returns C and adds (C, M) to its local list CL .

Analogously, if B queries RKDec on (φ, C), reduction A queries its own oracle KCDec on ξ d : K → (φ(K), C). If its answer is ⊥ then there must be an entry (C, M ) in CL . If there is more than one such entry, A stops and returns 1; otherwise it returns M . If A's KCDec oracle returned a value M = ⊥, B returns M and adds (M, C) to its list ML . First note that to any entry (K, C) ∈ CL of A's challenger corresponds an entry (C, D(K, M)) in A's local list CL (and similarly for ML and ML ). From Lemma 4.3 we thus have that in case b = 0, the probability that there are two entires (C, M 0 ), (C, M 1 ) with M 0 = M 1 in CL is at most q 2 /2 n =: . Thus, the probability that A stops the simulation in case b = 0 is bounded by . In case b = 1, if A stops the simulation, it outputs the correct bit. More formally, let E i denote the event that A stops the simulation when its challenger's bit b = i and let KC i denote game KC-CCA Ξ e , Ξ d , A BC with bit b fixed to i and similarly for RK i . Then we have:

Adv rk-cca BC (Φ, B) + 1 = Pr[RK 0 |E 0 ] Pr[E 0 ] + Pr[RK 0 |¬E 0 ] Pr[¬E 0 ] + Pr[RK 1 |E 1 ] Pr[E 1 ] + Pr[RK 1 |¬E 1 ] Pr[¬E 1 ] = Pr[RK 0 |E 0 ] Pr[E 0 ] + Pr[KC 0 |¬E 0 ] Pr[¬E 0 ] + Pr[RK 1 |E 1 ] Pr[E 1 ] + Pr[KC 1 |¬E 1 ] Pr[¬E 1 ] ≤ 1 • + Pr[KC 0 |¬E 0 ] Pr[¬E 0 ] + 1 • Pr[E 1 ] + Pr[KC 1 |¬E 1 ] Pr[¬E 1 ] = + Pr[KC 0 |E 0 ] Pr[E 0 ] + Pr[KC 0 |¬E 0 ] Pr[¬E 0 ] + Pr[KC 1 |E 1 ] Pr[E 1 ] + Pr[KC 1 |¬E 1 ] Pr[¬E 1 ] = + Adv kc-cca BC (Ξ e , Ξ d , A) + 1 ,
where for the second equality we used that games RK and KC have the same output conditioned on ¬E; the inequality uses Pr[E 0 ] ≤ by Lemma 4.3; and the second to last equality follows from B's behavior in case of E happening, thus Pr[KC 0 |E 0 ] = 0 and Pr[KC 1 |E 1 ] = 1. This concludes this direction of the proof.

The above simulation strategy for does not work the converse implication RK ⇒ KC, as best illustrated by the following example: Consider a blockcipher for which there exist K = K ∈ K and M ∈ M with E(K, M) = E(K , M) = C; now consider a KC adversary A that queries KCEnc(φ, M) with φ(K * ) = K; thus (K, C) ∈ CL. Later A queries KCDec(φ , C) and KCDec(φ , C) where φ (K * ) = K and φ (K * ) = K. Reduction B can forward these queries to its RK oracle and will get M in both cases. But KCDec(φ , C) should be answered with M (since (K , C) / ∈ CL), whereas KCDec(φ , C) should be answered with ⊥. Thus, storing (C, M) in a local list CL doesn't help, since both queries would make B look at this entry, but should result in different actions.

The reduction can thus not perfectly simulate the KC experiment; although this situation is very unlikely to occur for the ideal cipher, the reduction cannot abort and return 1 (as in the above proof), since the event that the adversary found a tuple (K, K , M, C) that would be hard to find for the ideal cipher is not detectable by the reduction (in contrast to the proof for KC ⇒ RK).

The proof will now rely on claw-freeness of the set Φ. If it was perfectly claw-free, then the reduction could perfectly simulate entries (K, C) ∈ CL by entries (φ, C) ∈ CL with φ(K * ) = K. But if clawfreeness is only computational then the adversary could find φ, φ with φ(K * ) = φ (K * ) for the key K * chosen by the game, but which would not be a claw for a random key and thus cannot be output as a solution in the claw-freeness game.

However, we can show that until the adversary finds a claw, the ideal game can be simulated without having chosen any key K * at all. If the adversary thus finds a claw, it must be one for a random key with non-negligible probability as well. We start with proving this last observation in the following lemma. Then there exists an adversary A cf such that Pr

[E] ≤ q 2 • (Adv cf Φ (A cf ) + 1/2 n ) =: 2 ,
where q is the number of oracle queries B makes in game RK-CCA.

Proof. The crucial observation is that game RK-CCA Φ,B BC when b is fixed to 0 can be simulated without knowing choosing K * up to the event E happening, that is, the point where the adversary produces the first claw. Let (φ i ) q i=1 denote the list of all functions queried to RKEnc or RKDec. We construct an adversary A cf against claw-freeness as follows: it first guesses i 0 , i 1 ∈ [1, q] and then simulates the game for B until the i 1 -th query as follows:

A cf keeps a list L with entries of the form (φ, M, C). Whenever B queries RKEnc(φ, M), it checks whether there is some entry (φ, M, C ) ∈ L and if so, returns C . Else it samples C ← M, adds (φ, M, C) to L and returns C. Whenever B queries RKDec(φ, C), it checks whether there is some entry (φ, M , C) ∈ L and if so, returns M . Else it samples M ← M, adds (φ, M, C) to L and returns M. When B makes its i 1 -the query, A cf stops and returns (φ i 0 , φ i 1 ).

Assume even E occurred and A cf guessed correctly that the i 1 -th query was the first query after which E occurred and the i 0 -th query was the one it collided with. Consider A cf 's challenger, which chooses K * ← K and checks whether φ i 0 (K * ) = φ i 1 (K * ). If so, then A cf won the claw-freeness game. Else the probability that A cf would have answered the i 1 -th query so that E still occurred is 1/2 n . RK ⇒ KC. This direction relies on the claw-freeness of the set Φ. Let A be a KC adversary; we construct a reduction B against RK that the model maintains two local lists ML and CL and aborts whenever event E, defined in Lemma 4.4, occurs.

Whenever A queries KCEnc for ξ e : K → (φ(K), M), reduction B queries RKEnc(φ, M) to receive C. It first checks whether there has been a "colliding" RKEnc query: if there is an entry (φ , C, M) in its list CL with φ = φ then B aborts and returns 1.

To answer the query KCEnc(φ, M), an actual KC challenger would check whether (φ(K * ), M) ∈ ML. Instead, B checks its local list ML : if (φ, M, C) ∈ ML , it returns ⊥; if there is an entry (φ = φ, M, C) then B aborts the simulation and returns 1; if there is no entry (•, M, C) ∈ ML , it adds (φ, C, M) to its local list CL and returns C.

KCDec queries for ξ d : K → (φ(K), C) are dealt with analogously: B first queries RKDec(φ, C) to receive M. If there is an entry (φ , M, C) in ML with φ = φ then B aborts and returns 1. To answer KCDec(φ, C), an actual KC challenger would now check whether (φ(K * ), C) ∈ CL. Instead, B checks its local list CL : if (φ, C, M) ∈ CL it returns ⊥; if there is an entry (φ = φ, C, M) then B aborts the simulation and returns 1; if there is no entry (•, C, M) ∈ CL , it adds (φ, M, C) to its local list ML and returns M.

We show that the simulation is perfect if B does not abort; consider a query KCDec(φ, C): (1) If (φ, C, M) ∈ CL then there must have been a query KCEnc(φ, M) with C = E(φ(K * ), M); thus a KC challenger would have added (φ(K * ), C) to CL and the above KCDec query would have been answered by ⊥. (2) If there is no entry (•, C, M) ∈ CL then (φ(K * ), C) cannot be in CL, since whenever it is added to CL, an entry (•, C, D(φ(K * ), C) would have been added to CL . Perfect simulation of KCEnc queries is argued completely analogously.

On the other hand, we have that B aborts precisely when E, as defined in Lemma 4.4, occurs. With as defined in the latter, we thus have

Adv kc-cca BC (Ξ e , Ξ d , A) + 1 = Pr[KC 0 |E 0 ] Pr[E 0 ] + Pr[KC 0 |¬E 0 ] Pr[¬E 0 ] + Pr[KC 1 |E 1 ] Pr[E 1 ] + Pr[KC 1 |¬E 1 ] Pr[¬E 1 ] = Pr[KC 0 |E 0 ] Pr[E 0 ] + Pr[RK 0 |¬E 0 ] Pr[¬E 0 ] + Pr[KC 1 |E 1 ] Pr[E 1 ] + Pr[RK 1 |¬E 1 ] Pr[¬E 1 ] ≤ 1 • + Pr[RK 0 |¬E 0 ] Pr[¬E 0 ] + 1 • Pr[E 1 ] + Pr[RK 1 |¬E 1 ] Pr[¬E 1 ] = + Pr[RK 0 |E 0 ] Pr[E 0 ] + Pr[RK 0 |¬E 0 ] Pr[¬E 0 ] + Pr[RK 1 |E 1 ] Pr[E 1 ] + Pr[RK 1 |¬E 1 ] Pr[¬E 1 ] = + Adv rk-cca BC (Φ, B) + 1 ,
where for the second equality we used that games RK and KC have the same output conditioned on ¬E;

Adv kc-cca BC (Ξ e , Ξ d , A) = Adv kdm-cca BC (Ψ, B) ,
and for every adversary B there exist adversaries A and A cf such that

Adv kdm-cca BC (Ψ, B) ≤ q 2 • Adv cf Ψ (A cf ) + Adv kc-cca BC (Ξ e , Ξ d , A) ,
where q is the maximum number of queries adversary B makes.

We show that our definition is equivalent to the KDM definition from [START_REF] Farshim | Security of Even-Mansour Ciphers under Key-Dependent Messages[END_REF] for claw-free sets Ψ. Recall that (Ξ e , Ξ d ) is KDM-only if Ξ e = {id} × Ψ and Ξ d = {id} × Γ, where Ψ is a KDM set of functions mapping keys to messages and Γ is the set of constant functions K → M for all M ∈ M; we assume Γ ⊆ Ψ.

We first observe that games KC and KDM are similar in that every entry C in CL in game KDM corresponds to (K * , C) in CL in KC. The crucial difference is that in KDM there is no list ML, thus all KDMEnc queries are allowed, whereas KC disallows queries in ML. KDM implying KC can be shown because the reduction can perfectly simulate the list ML.

The converse (KC ⇒ KDM) is trickier to show and it relies on claw-freeness of the set Ψ. To illustrate this, consider the following attack against KDM, which does not work against KC: for two random C 0 , C 1 ∈ M, the adversary queries Dec(C 0 ) and Dec(C 1 ) to receive M 0 and M 1 . It then queries KDMEnc(ψ M 0 ,M 1 ) with ψ : K * → M K * 1 , where K * 1 is the first bit of K * . When receiving C i as a reply, the adversary learnt that i is the first bit of K * and it can use the same strategy to learn all other bits of K * . Note that in the KC game, the two decryption queries add (K * , M 0 ) and (K * , M 1 ) to ML and consequently KCEnc(ξ e := id × ψ M 0 ,M 1 ) is answered with ⊥.

KDM ⇒ KC. To show that KDM implies KC, consider a KC adversary A and let us construct a reduction B against KDM. B basically simulates the KC oracles for A by forwarding A's queries to its own KDM oracles. To simulate game KC correctly, B maintains its own list ML . Whenever A queries KCDec(ξ d ) for ξ 2 ∈ Ξ d , we have ξ 2 : K → (K, C) for some C ∈ M. Reduction B queries C to Dec to obtain M, which it returns to A; B also appends (M, C) to its list ML (whereas an actual KC challenger would have appended (K * , M) to its list ML).

Whenever A queries KCEnc(ξ 1 ) with ξ 1 : K → (K, ψ(K)) for some ψ ∈ Ψ, the reduction queries KDMEnc(ψ) to obtain C. If for some M there is an entry (M , C) ∈ ML : B returns ⊥; otherwise, it returns C.

To see that this correctly simulates the list ML that B's challenger maintains, observe that (K * , M) is in the latter iff (M, E(K * , M)) is in KC ⇒ KDM. In this direction, we assume an adversary B against KDM and construct A against KC. This time, A will not be able to perfectly simulate the game; however, A can detect when it is not able to. In this case A aborts and returns b = 1 (it guesses that it is talking to the real blockcipher). As for in the proof for KC ⇒ RK, we show that if b = 0 (the ideal case), the probability of A aborting is bounded-in contrast to the previous proof, we bound it by the advantage of breaking clawfreeness. We start by defining the following event E in game KDM-CCA Ψ,B BC : let (M i ) i denote the messages returned by the Dec oracle and let (ψ j ) j denote the queries made to the KDMEnc oracle; let K * denote the challenge key. We say E occurs if we either have (1) ψ j 0 (K * ) = ψ j 1 (K * ) for some j 0 = j 1 ; or (2) ψ j (K * ) = M i for some j, i. We show the following:

Lemma 4.6. Consider game KDM-CCA Ψ,B
BC with b fixed to 0 and let E be the event defined above. Then there exists an adversary A cf such that Pr

[E] ≤ q 2 • Adv cf Ψ (A cf )
, where q is the number of oracle queries B makes in game KDM-CCA.

Proof. First note that there exists some first query j 1 that makes E occur, and some query j 0 < j 1 , which will be the query with which the j 1 -th query "collides". A cf starts with guessing j 0 and j 1 and simulates the game until the j 1 -th query as follows: any query Dec(C i ) is answered with a random M i ← M; any query KDMEnc(ψ i ) is answered with a random C i ← M (all repeated queries are answered consistently).

If the j 0 -th query was a query Dec(C i ) answered by M i then define ψ j 0 : K → M i ; if it was a query KDMEnc(ψ) then let ψ j 0 := ψ; define ψ j 1 analogously. A cf returns (ψ j 0 , ψ j 1 ).

First note that if A guessed j 1 correctly then the simulation is perfect, as for the random key K * , the same message was never queried twice (via encryption or decryption). Moreover, if A also guessed j 0 correctly then (ψ j 0 , ψ j 1 ) is indeed a collision and A wins the claw-freeness game. We thus have Adv cf

Ψ (A cf ) ≥ 1/q 2 • Pr[E]
, which proves the lemma. We now give a reduction A against KC that simulates the KDM game to adversary B by forwarding all queries to its own oracle. When A cannot answer a KDMEnc query because its own oracle KCEnc replies ⊥ it aborts the simulation. In order to use the above lemma, A will also abort when it could continue the simulation. In particular, A aborts and returns 1 when one of the two things happen:

(1) B makes two queries ψ, ψ to KDMEnc, which when forwarded to A's RKEnc oracle return the same C; or (2) A forwards a KDMEnc query to its KDMEnc oracle which is answered with ⊥.

Note that these two cases define precisely the event E above. We thus have that A aborts the simulation whenever E occurs. If A does not abort the simulation, it returns whatever B outputs.

Let KC i denote game KC-CCA Ξ e , Ξ d , A BC with bit b fixed to i and E i the event that E occurs in this case. Define KDM i analogously and let := q 2 • Adv cf Ψ (A cf ). Then we have:

Adv kdm-cca BC (Ψ, B) + 1 = Pr[KDM 0 |E 0 ] Pr[E 0 ] + Pr[KDM 0 |¬E 0 ] Pr[¬E 0 ] + Pr[KDM 1 |E 1 ] Pr[E 1 ] + Pr[KDM 1 |¬E 1 ] Pr[¬E 1 ] = Pr[KDM 0 |E 0 ] Pr[E 0 ] + Pr[KC 0 |¬E 0 ] Pr[¬E 0 ] + Pr[KDM 1 |E 1 ] Pr[E 1 ] + Pr[KC 1 |¬E 1 ] Pr[¬E 1 ] ≤ +1 • + Pr[KC 0 |¬E 0 ] Pr[¬E 0 ] 1 • Pr[E 1 ] + Pr[KC 1 |¬E 1 ] Pr[¬E 1 ] = + Pr[KC 0 |E 0 ] Pr[E 0 ] + Pr[KC 0 |¬E 0 ] Pr[¬E 0 ] + Pr[KC 1 |E 1 ] Pr[E 1 ] + Pr[KC 1 |¬E 1 ] Pr[¬E 1 ] = + Adv kc-cca BC (Ξ e , Ξ d , A) + 1
where for the second equality we used that games KDM and KC have the same output conditioned on ¬E; the inequality uses Pr[E 0 ] ≤ by Lemma 4.6; and the second to last equality follows from B's behavior in case of E happening, thus Pr[KC 0 |E 0 ] = 0 and Pr[KC 1 |E 1 ] = 1. This concludes this direction of the proof.

In this chapter we study the feasibility of achieving security against key-correlated attacks in the ideal-cipher model. In this setting the adversary has oracle access to the ideal cipher in both the forward and backward direction.

kca security of the ideal cipher

We begin by extending the standard notion of CCA security to the KCA setting, where key-dependent messages may be enciphered under related keys. Consider game KC-CCA Ξ e , Ξ d , A Block(k,n) shown in Fig. 5.1. The KC-CCA advantage of an adversary A against the ideal cipher with key length k and block length n is defined by

Adv kc-cca Block(k,n) (Ξ e , Ξ d , A) := 2 • Pr KC-CCA Ξ e , Ξ d , A Block(k,n) -1 .
We now prove a feasibility theorem for the ideal cipher that generalizes and extends those of both Bellare and Kohno [BK03] and of Farshim et al. [START_REF] Farshim | Security of Even-Mansour Ciphers under Key-Dependent Messages[END_REF]. We define four conditions on CDF sets, which exclude trivial attacks.

Unpredictability. The unpredictability advantage of an adversary

A against a CDF set Ξ is defined as

Adv up Ξ (A) := Pr ξ(K) = (K 0 , M 0 ) : (ξ, (K 0 , M 0 )) A; K K ,
where we require that ξ ∈ Ξ. Informally, we say Ξ is unpredictable if the above advantage is "small" for every "reasonable" A.

We also define a multi-shot version of this game where A outputs a list L 1 of candidates for ξ and a list L 2 of predicted values (K 0 , M 0 ). Adversary A wins if some ξ in L 1 evaluates to some (K 0 , M 0 ) in L 2 when run on a random key K. Denoting the advantage in this game by Adv m-up Ξ (A), a simple guessing argument shows that for any A there exists B with

Adv m-up Ξ (A) ≤ 1 • 2 • Adv up Ξ (B) ,
where 1 and 2 are upper bounds on the sizes of L 1 and L 2 respectively. We require that ξ e ∈ Ξ e and ξ d ∈ Ξ d for all queries ξ e , ξ d . Key-unpredictability. The key-unpredictability advantage of an adversary A against a CDF set Ξ is defined as

1 Game KC-CCA Ξ e , Ξ d , A Block(k,n) : b {0, 1} (iE, iD) Block(k, n) (iE , iD ) Block(k, n) K * {0, 1} k b A iE,iD,KCEnc,KCDec return (b = b) Proc. KCEnc(ξ e ): (K, M) ← ξ e (K * ) if (K, M) ∈ ML: return ⊥ C ← iE(K, M) if b = 0: C ← iE (K, M) CL ← CL : (K, C) return C Proc. KCDec(ξ d ): (K, C) ← ξ d (K * ) if (K, C) ∈ CL: return ⊥ M ← iD(K, C) if b = 0: M ← iD (K, C) ML ← ML : (K, M) return M
Adv kup Ξ (A) := Pr ξ| 1 (K) = K 0 : (ξ, K 0 ) A; K K ,
where we require that ξ ∈ Ξ. Here ξ| 1 (K) denotes the projection to the first coordinate of ξ(K). Informally we say Ξ is key-unpredictable if the above advantage is "small" for every "reasonable" A.

We also define a multi-shot version of this game where A outputs a list L 1 of candidates ξ and a list L 2 of predicted values K 0 . Adversary A wins if for a random key K, for some ξ in L 1 we have ξ| 1 (K) = K 0 for some K 0 in L 2 . If we denote the advantage in this game by Adv m-kup Ξ (A), again we have that there exists a single-shot B such that

Adv m-kup Ξ (A) ≤ 1 • 2 • Adv kup Ξ (B) ,
where 1 and 2 are upper bounds on the sizes of L 1 and L 2 respectively. Note that key-unpredictability implies unpredictability. The converse does not hold as ξ : K → (0, K) is unpredictable but not key-unpredictable.

Claw-freeness. This requires that it is hard to find two distinct functions that output the same on a random input. Formally, the claw-free advantage of an adversary A against a CDF set Ξ is defined as

Adv cf Ξ (A) := Pr ξ = ξ ∧ ξ(K) = ξ (K) : (ξ, ξ ) A; K K ,
where we require that ξ, ξ ∈ Ξ. We say Ξ is claw-free if the above advantage is "small" for every "reasonable" A. Once again, a multishot version of the game with lists of candidates L 1 and L 2 for ξ and ξ can be defined, and as before there exists B with

Adv m-cf Ξ (A) ≤ 1 • 2 • Adv cf Ξ (B) .
Cross-key-claw-detectability. We introduce a new notion and call a pair of CDF sets (Ξ e , Ξ d ) cross-key-claw-detectable (xkcd) 2 if there is an efficient detection algorithm Det such that for any A the advantage below is small.

Adv xkcd Ξ e ,Ξ d ,Det (A) := Pr   Det(ξ e , C, ξ d , M, 1) = (ξ e | 1 (K), C) = ξ d (K) ∨ Det(ξ e , C, ξ d , M, 2) = (ξ d | 1 (K), M) = ξ e (K) : (ξ e , C, ξ d , M) A; K K  
We require that ξ e ∈ Ξ e and ξ d ∈ Ξ d . Roughly speaking, xkcd provides a way to treat legality of queries across encryption and decryption queries in the KCA game. For example, in an illegal decryption query the output of an earlier encryption query (stored by the game in list CL, cf. Fig. 4.1) is sent to the decryption oracle through a CDF function whose key component matches that used in encryption. Det allows us to decide when such cases occur and deal with them appropriately in the security analysis. A generalization of this notion considers lists L 1 for pairs (ξ e , C) and L 2 for (ξ d , M) and A wins if Det fails for any given tuple (ξ e , C, ξ d , M) in the product of the lists. Again, a guessing argument shows that for every A there exists B with

Adv m-xkcd Ξ e ,Ξ d ,Det (A) ≤ 1 • 2 • Adv xkcd Ξ e ,Ξ d ,Det (B) .
Remark. We can modify claw-freeness to claw-freeness of keys over the union Ξ e ∪ Ξ d . This would immediately imply xkcd, as Det can always return "No". But in this case the reach of our feasibility result below will not extend to the KDM setting, since under KDM a single key is used in encryption and decryption and hence they always collide.

We will now state and prove our first feasibility result, which identifies a set of sufficient conditions on the pair (Ξ e , Ξ d ) so that the ideal cipher is KCA secure with respect to it. Theorem 5.1 (KCA security of the ideal cipher). Fix a key length k and block length n and let Ξ e and Ξ d be two sets of CDFs with signature ξ : {0, 1} k → {0, 1} k × {0, 1} n . Then for any (Ξ e , Ξ d )-KC-CCA adversary A against the ideal cipher making at most q direct ideal cipher queries, q e encryption and q d decryption queries, there are (multi-shot) adversaries B 1 , . . . , B 5 such that

Adv kc-cca Block(k,n) (Ξ e , Ξ d , A) ≤ Adv m-kup Ξ e (B 1 ) + Adv m-kup Ξ d (B 2 ) + Adv m-cf Ξ e (B 3 ) + Adv m-cf Ξ d (B 4 ) + Adv m-xkcd Ξ e ,Ξ d ,Det (B 5 ) + qq e + qq d + q 2 e + q 2 d + q e q d /2 n .
Algorithm B 1 outputs two lists of sizes at most 1 ≤ q e and 2 ≤ q; B 2 outputs lists of sizes at most 1 ≤ q d and 2 ≤ q; B 3 's lists are of sizes at most 1 , 2 ≤ q e ; B 4 's lists are of sizes at most 1 , 2 ≤ q d , and B 5 's lists of sizes at most 1 ≤ q e and 2 ≤ q d .

Proof. The idea of the proof is that we will gradually modify KC-CCA of Fig. 5.1 so that KCEnc and KCDec oracles run with two independent and forgetful random oracles, denoted by $ + and $ -respectively, and further the validity checks are performed by the detection algorithm Det. These modifications ensure that we arrive at a game which This is the key goal to bear in mind throughout the proof.

does not depend on the explicit key-correlated keys, messages, or ciphertexts.

Pictorially, in this intermediate game with forgetful oracles the adversary can make queries that correspond to 1 (corresponding to iE), 2 (corresponding to iD), 3 and 4:

1 -→ iE ± 2 ←- 3 -→ $ + -→ ←-$ -4 ←-
We now describe the transitional steps; the details can be found in Figs. 5.2 and 5.3.

Game 0 : This is the KC-CCA game with respect to b = 1 and where the four oracles lazily sample the ideal cipher. The same ideal cipher is used in iE and iD as those used in KCEnc and KCDec oracles. Consistency is ensured via shared lists T + , T -, Im + , and Im -used in lazy sampling.

Game 1 : This game differs from Game 0 in that different lists are used in iE and iD and in KCEnc and KCDec. The game still ensures consistency across the lists and hence there are no functional changes. This game also sets a flag Bad kup preparing us to decouple the two lists. More precisely, whenever a call to iE or iD needs to use the lists of KCEnc and KCDec, or vice versa, Bad kup is set. This game also sets a bad flag Bad col 1 whenever it samples a ciphertext (resp. plaintext) that was sampled before and hence appears on Im + 1 or Im + 2 (resp. Im - 1 or Im - 2 ). Game 2 : This game omits the code after Bad kup or Bad col 1 is set. Thus Game 1 and Game 2 are identical until Bad kup or Bad col 1 is set. We defer the analysis of this event to a later game. As a result the two ideal ciphers used in iE and iD and KCEnc and KCDec are decoupled.

Game 3 : This game checks for repeat queries to the ideal cipher used within the KCEnc and KCDec oracles. (Note that the queries to these oracles are assumed, without loss of generality, to be distinct.) The game sets a flag Bad cf when this takes place. This game also sets a bad flag Bad col 2 whenever it samples a ciphertext (resp. plaintext) that was sampled before in a previous KCEnc or KCDec query (resp., also in a previous KCEnc and KCDec query). By dropping the code after Bad cf and Bad col 2 , we transition to a game where the ideal cipher within KCEnc and KCDec act as forgetful random oracles.

Game 4 : This games uses the detection algorithm Det to check whether or not queries to KCEnc or those to KCDec are valid. More explicitly:

(1) For each decryption query ξ d , KCDec runs Det(ξ e , C, ξ d , 0 n , 1) for all previous queries ξ e to KCEnc, which were answered with C. (Intuitively, Det checks whether ξ d (K) = (ξ e | 1 (K), C); the input 0 n is arbitrary.) (2) Analogously, for each query ξ e , the KCEnc oracle runs Det(ξ e , 0 n , ξ d , M, 2) for all previous queries ξ d to KCDec which resulted in output M. If Det (which intuitively checks if ξ e (K) = (ξ d | 1 (K), M)) returns "Yes" for any of these, KCEnc returns ⊥, else it answers randomly. Note that this game introduces no functional changes since it still computes the validity of a query using the lists. However it sets a bad flag Bad xkcd when the validity check determined by Det is different from the (true) value of validity determined using the lists ML and CL. This then prepares us to drop the explicit check using the lists and only use Det in the next game.

Game 5 : This game drops the code after Bad xkcd , and so is identical to Game 4 unless Bad xkcd has been set. Note that in Game 5 the iE and iD oracles implement an ideal cipher whereas the KCEnc and KCDec oracles implement two forgetful random oracles, except that sometimes they might return ⊥ if the Det says that a query is invalid. To signify these, in what follows we refer to KCEnc by $ and KCDec by $ -. We also use iE + for iE and iE -for iD.

Note also that the above games are all identical unless one of the bad flags is set. Thus we analyze the probability of setting any of the bad flags in the final game Game 5 , where the behavior of the oracles are independent of the secret key K * . We start by analyzing the probability of setting Bad kup and Bad col 1 . Flag Bad kup can be set under iE if a query (K, M) to iE appears on T + 2 . Since only KCEnc and KCDec write to T + 2 , this would be the case if (a) (K, M) = ξ e (K * ) for some query ξ e to KCEnc or (b) (K, M) = (ξ d | 1 (K * ), M ) for M a randomly chosen output of KCDec.

In case (a) we can build an adversary that wins the multi-shot unpredictability of Ξ e by simulating the oracles as in Game 5 (without the need for K * ) and outputting two lists L 1 and L 2 consisting of all

The 'trick' that allows us to simulate without K * stems from the fact that in Game 5 all ciphertexts and messages are generated independently of ξ e (K * ) and ξ d (K * ).

tuples (K, M) that were submitted to iE and ξ e that were submitted to KCEnc. These lists are of sizes q and q e respectively.

In case (b), however, we build an adversary that wins the multi-shot key unpredictability of Ξ d (note the exponent d). The four oracles are simulated as in Game 5 (once again without the need for K * ), but now the adversary outputs two lists L 1 and L 2 consisting of all keys K for tuples (K, M) submitted to iE and ξ e that were submitted to KCDec. These lists are of sizes q and q d respectively.

We now look at the probability of setting Bad col 1 . A straightforward analysis shows that this probability is upper bounded by q(q e + q d )/2 n . The probability of setting Bad kup under iD is analyzed similarly to cases (a) and (b) above via reductions to the multi-shot unpredictability of Ξ d and the multi-shot key unpredictability of Ξ e . The probability of setting Bad col 1 under iD is at most q(q e + q d )/2 n .3

Next we consider the probability of setting Bad cf or Bad col 2 . Flag Bad cf can be set under KCEnc as a result of a query ξ e 0 if either (a) a previous distinct query ξ e 1 to KCEnc resulted in ξ e 0 (K * ) = ξ e 1 (K * ), or (b), a previous query ξ d 1 to KCDec resulted in ξ e 0 (K * ) = (ξ d 1 | 1 (K * ), M), where M is a random value chosen by KCDec in a previous query.

In case (a) by collecting the list of ξ e queried to KCEnc we can break the multi-shot claw-freeness of Ξ e (simulating the oracles as in Game 5 ). For case (b) to take place it must be that Det classified the query as valid. However, this leads to setting Bad xkcd since M was returned from the KCDec oracle and hence (ξ d 1 | 1 (K * ), M) appears on ML but Det did not detect this. We analyze the probability of setting Bad xkcd below. The probability of setting Bad col 2 in KCEnc can be upper bounded by q e (q e + q d )/2 n .

The probability of setting Bad cf under KCDec is analyzed as above by a reduction to the multi-shot claw-freeness of Ξ d (or setting Bad xkcd ). The probability of setting Bad col 2 in KCDec is upper bounded by q d (q e + q d )/2 n . Finally we consider the probability of setting Bad xkcd . Flag Bad xkcd is set exactly when ξ e (K * ) appears on ML as a result of a query ξ d to KCDec with response M and Det says it does not, or that it does not not and Det says it does. We can bound the probability of setting The theorem now follows by putting the bounds established above together.

The above theorem shows that key-unpredictability, claw-freeness, and xkcd are sufficient for achieving KCA security in the ideal-cipher model. This raises the question whether or not they are also necessary. Key-unpredictability is. Any adversary that can predict the key output of ξ e can be used to win the KC game as follows:

1. ask for an encryption under ξ e (K * ) to get a ciphertext C; 2. predict ξ e | 1 (K * ) as K; It is easily seen that this attack returns b = 1 with the same probability of predicting keys when b = 1. On the other hand, it only succeeds with negligible probability when b = 0 as the encryption oracle and the challenge oracle use independent ideal ciphers. We deal with such attacks in case (b) of ($ + , iE ± ) in the proof.

Claw-freeness, on the other hand, is not necessary. Consider a CDF set consisting of exactly two functions that collide with probability 1/2, e.g., K → K and K → min(K, K). Then a security proof for the ideal cipher can be easily given: guess with probability 1/2 if min(K, K) = K. Next depending on the guess simulate the keycorrelated oracles either using the same set of ideal cipher oracles or independent ones. However, one can also exhibit CDF sets that are not claw-free and do lead to a KCA on the ideal cipher. Indeed, any set of k + 1 functions that has claws with the identity function depending on whether or not K i , the i-th bit of the key, is 1 can be used to recover the key one bit at a time. In practice this translates to recovering the key by observing the repetition patters in the outputs.

Finally, there is also a pair of CDF sets which are not xkcd and can be used to attack the ideal cipher. Let ξ e (K) := (K, 0 n ) and

ξ d [i, C](K) := (K ⊕ (K i ) n =: K , C), that is, K = K if K i = 1 and K = K otherwise.
Let C be the answer to KCEnc(ξ e ). Now for i = 1, . . . , k, by checking whether KCDec(ξ d [i, C]) returns ⊥ or not, one can again recover the key one bit at a time. In practice this translates to observing the equality pattern of the decrypted ciphertexts with 0 n . Theorem 5.1 and Proposition 4.1 can be used to recover known feasibility results for RKA and KDM security of the ideal cipher as follows.

RKA security. An RKA-only CDF set Ξ associated to a set Φ is keyunpredictable iff Φ is unpredictable in the sense of [START_REF] Bellare | A Theoretical Treatment of Related-Key Attacks: RKA-PRPs, RKA-PRFs, and Applications[END_REF]. Indeed, a predictor for a related-key derivation function φ can be converted to a key-predictor for ξ : K → (φ(K), M) for any fixed M. Conversely, a key-predictor for (φ(K), M) in particular predicts φ(K). Similarly, Ξ is claw-free iff Φ is claw-free in the sense of [START_REF] Bellare | A Theoretical Treatment of Related-Key Attacks: RKA-PRPs, RKA-PRFs, and Applications[END_REF]. A claw in Φ can be immediately converted to a claw in Ξ (by adding any message M). Conversely, a claw ((φ 1 (K), M 1 ), (φ 2 (K), M 2 )) is necessarily also a claw between φ 1 and φ 2 . For the (funny) xkcd property, Det given

((φ 1 , M 1 ), C, (φ 2 , C 2 ), M, i) needs to check if (1) φ 1 (K) = φ 2 (K) and (2) if C = C 2 when i = 1 or if M = M 1 when i = 2. By claw-freeness,
(1) would only occur if φ 1 = φ 2 ; the second condition on the other hand is trivial to check. Thus, claw-freeness implies xkcd. KDM security. A KDM-only Ξ associated to a KDM set Ψ is always key-unpredictable with single-shot advantage 1/2 n . This is because KDM-only functions leave the random key unmodified, which remains information-theoretically hidden from the adversary in the key-answer is correct. Case i = 2 is dealt with similarly and we obtain overall single-shot advantage of at most 2/2 n . Theorem 5.1 thus implies that the ideal cipher is (Ξ ⊕ , Ξ ⊕ )-KC-CCA secure.

kca security of 3-round even-mansour

In this section we show that in contrast to the two-round case the three-round Even-Mansour cipher with reuse of keys and independent permutations EM P 1 ,P 2 ,P 3 [K, K, K, K], defined in Sec. 4.4.2, is (Ξ ⊕ , Ξ ⊕ )-KC-CCA secure, with Ξ ⊕ as defined in (5.1). We note that, for Φ ⊕ , Ψ ⊕ as in (4.2), this construction is known to be both Φ ⊕ -RK-CCA and Ψ ⊕ -KDM-CCA secure [START_REF] Farshim | The Related-Key Security of Iterated Even-Mansour Ciphers[END_REF][START_REF] Farshim | Security of Even-Mansour Ciphers under Key-Dependent Messages[END_REF]. We build on these works to show KC-CCA security in the theorem.

Theorem 5.2 (KCA security of 3-round EM). EM P 1 ,P 2 ,P 3 [K, K, K, K] is (Ξ ⊕ , Ξ ⊕ )-KC-CCA secure in the random-permutation model for P i . More precisely, for any adversary A against the (Ξ ⊕ , Ξ ⊕ )-KC-CCA security of EM P 1 ,P 2 ,P 3 [K, K, K, K] we have

Adv kc-cca EM P 1 ,P 2 ,P 3 [K,K,K,K] (Ξ ⊕ , Ξ ⊕ , A) ≤ 2 • qq e + qq d + q 2 e + q 2 d + q e q d /(2 n -q) ,
where q is the maximum number of queries of A to P ± i (over all i = 1, 2, 3) and q e and q d are the maximum number of encryption and decryption queries of A, respectively. Proof. To analyze the KC-CCA security of Even-Mansour, our strategy will be similar to that in Theorem 5.1 and those in [START_REF] Farshim | The Related-Key Security of Iterated Even-Mansour Ciphers[END_REF][START_REF] Farshim | Security of Even-Mansour Ciphers under Key-Dependent Messages[END_REF]. As in these proofs, we replace the last-round permutation P + 3 in KCEnc queries with a forgetful random oracle and also replace the first-round permutation P - 1 in KCDec with another forgetful random oracle. After these replacements the outputs of KCEnc and KCDec will be fully randomized and independent of the inputs; the game is thus independent of the challenge bit b.

When simulating KCEnc and KCDec with forgetful oracles, we still need to ensure that illegal queries are answered correctly with ⊥. As in the proof of Theorem 5.1, we do this using a detector. In particular, we use Det ⊕ as in (5.2), which on input ((∆ 1 , ∆ 2 , α), C, (∆ 1 , ∆ 2 , α ), M, 1) returns "Yes" iff ∆ 1 = ∆ 1 and α = 0 and ∆ 2 = C (and "No" otherwise); and on input ((∆ 1 , ∆ 2 , α), C, (∆ 1 , ∆ 2 , α ), M, 2) returns "Yes" iff ∆ 1 = ∆ 1 and α = 0 and ∆ 2 = M.

(1) For each decryption query ξ d , KCDec runs Det ⊕ (ξ e , C, ξ d , 0 n , 1) for all previous queries ξ e to KCEnc, which were answered with C. If Det says "Yes" for any of these, KCDec ⊕ returns ⊥, else it outputs a random value from the domain.

(2) For each encryption query ξ e , KCEnc runs Det ⊕ (ξ e , 0 n , ξ d , M, 2) for all previous queries ξ d to KCDec, which were answered with M. If Det ⊕ says "Yes" for any of these, KCEnc returns ⊥, else it answers with a random value.

These replacements, however, raise the question how P + 1 in KCEnc and P - 3 in KCDec are treated (since their respective counterparts in KCDec and KCEnc were replaced). Previous works simply leave these oracles unchanged. Our proof diverges in this aspect, because the key-dependency of both keys and messages gives rise to queries that cannot be guaranteed to be disjoint from the forgetful oracle, or discarded as trivial/illegal as in the KDM setting [START_REF] Farshim | Security of Even-Mansour Ciphers under Key-Dependent Messages[END_REF], or not result in inconsistency due to the middle permutation P 2 being replaced in the RKA setting [START_REF] Farshim | The Related-Key Security of Iterated Even-Mansour Ciphers[END_REF].

For the KCA setting we will replace P - 3 in KCDec (and analogously for P + 1 in KCEnc) as follows. When Det ⊕ says "No" on a query

ξ d = (∆ d 1 , ∆ d 2 , α d
), the game checks if each previous query ξ e = (∆ e 1 , ∆ e 2 , α e ) to KCEnc with output value C satisfies

C ⊕ ∆ e 1 = ∆ d 2 ⊕ ∆ d 1 .
If so, oracle P-3 outputs the input U to $ + that was used to compute C. If multiple values are found, P-3 returns ⊥. If the latter is not the case, P-3 is sampled as an independent permutation and consistent with P 3 . Permutation P ± 3 , when directly queried, is also sampled consistently with P-3 on all those entries that are not kept consistent with $ + . More precisely, oracles $ + , P ± 3 and P-3 write to independent lists L 1 , L 2 and L 3 . Oracle $ + checks consistency with none of the lists, oracle P ± 3 checks consistency with L 2 and L 3 and oracle P-3 checks consistency with L 1 , L 2 and L 3 .

Oracle P + 1 in KCEnc is replaced with P+ 1 similarly by checking if M ⊕ ∆ d 1 = ∆ e 2 ⊕ ∆ e 1 and outputting the input U to $ -that was used to compute M.

As a result of the above replacements, the following inconsistencies could arise:

(a) Identical queries to a permutation oracle are answered differently due to a replacement. (b) Different queries to a permutation oracle and its replacement are answered identically (and hence do not respect permutativity). (c) Multiple candidates for U are found when sampling P-3 or P+ 1 . We now bound the probabilities of these events. multiple candidates This event will happen due to: (1) a collision in the outputs of $ + , which happens with probability 1/2 n for each pair of queries to KCEnc; or (2) a collision in the output of $ + and an output entry in P ± 3 . This event is equivalent to a collision in the outputs of $ + and P ± 3 , which pertains to case (b) and is analyzed next.

($ + , P ±

3 ) A direct P ± 3 call in either direction collides with a point queried to P + 3 due to a query ξ e = (∆ 1 , ∆ 2 , α) to KCEnc. Suppose the direct query results in V = P + 3 (U) or U = P - 3 (V). There are now two cases. (a) The inputs collide, i.e.,

P 2 P 1 (∆ 1 ⊕ ∆ 2 ⊕ (1 -α) • K * ) ⊕ ∆ 1 ⊕ K * ⊕ ∆ 1 ⊕ K * = U . (5.3) If Y := P 1 (∆ 1 ⊕ ∆ 2 ⊕ (1 -α) • K * ) ⊕ ∆ 1 ⊕ K *
was queried to P 2 then the adversary can compute K * = P 2 (Y) ⊕ ∆ 1 ⊕ U, which is only possible with probability 1/2 n , since the key remains information-theoretically hidden. If it was not queried, the probability that (5.3) holds is also 1/(2 nq), since P 2 is a random permutation, where outputs are chosen in a set of size at least 2 nq. The other case is that (b) the outputs collide. If the $ + query comes after the direct query, the probability of this event is 1/2 n . Now suppose the $ + query comes first and outputs C; thus due to the collision we have that C = V ⊕ K * ⊕ ∆ 1 . But in this case the adversary can compute K * = V ⊕ ∆ 1 , which happens with probability at most 1/2 n (as the key remains information theoretically hidden).

($ -, P ± 1 ) A direct P ± 1 call in either direction collides with a point queried to $ -due to a query ξ d to KCDec. This event is analyzed analogously to case ($ + , P ± 3 ) above. ($ + , $ + ) The are two cases: (a) two inputs collide or (b) two outputs collide. In case (a) two distinct calls ξ e = (∆ 1 , ∆ 2 , α) and (ξ e ) = (∆ 1 , ∆ 2 , α ) to the KCEnc oracle result in querying $ + on the same input. For this event to occur we must have that

P 2 =:Y P 1 (∆ 1 ⊕ ∆ 2 ⊕ (1 -α) • K * =:X ) ⊕ ∆ 1 ⊕ K * ⊕ ∆ 1 = P 2 P 1 ( =:X ∆ 1 ⊕ ∆ 2 ⊕ (1 -α ) • K * ) ⊕ ∆ 1 ⊕ K * =:Y ⊕ ∆ 1 . (5.4) If Y = Y then P 1 (X) ⊕ ∆ 1 = P 1 (X )
⊕ ∆ 1 and from (5.4) we get ∆ 1 = ∆ 1 . Since P 1 is a permutation, this implies that X = X . If further α = α then we would also have ∆ 2 = ∆ 2 , which means ξ e = (ξ e ) , contradicting distinctness of queries. Thus α = α and hence ∆ 2 ⊕ ∆ 2 = K * (since X = X ), which only happens with probability 1/2 n as it leads to guessing the key. Assume now that Y = Y .

-If the adversary does not query P 2 on either Y or Y then P 2 (Y) or P 2 (Y ) would be distributed randomly and independently of the adversary's view. Hence the probability that the above equality holds would be at most 1/(2 nq) for each pair of queries. -Suppose both Y and Y are queried to P 2 . Then P 1 must have been queried on both X or X , since otherwise the probability of computing Y or Y would be at most 1/(2 nq). If both X and X are queried to P 1 and α = 0 or α = 0, then for each query the probability of querying X (or X ) to P 1 is 1/2 n , because K * is information-theoretically hidden. The query will be marked as illegal unless ∆ d 1 = ∆ e 1 . In this case the adversary has found a collision of the form

P 2 (Y ⊕ K * ⊕ ∆ e 1 ) ⊕ K * ⊕ ∆ e 1 = U , where Y = P - 2 (U ⊕ K * ⊕ ∆ d 1 ) ⊕ K * ⊕ ∆ d
1 is the value input to $ -and output by P + 1 due to the consistency check in KCEnc. Rearranging and applying P - 2 to the above equality yields

Y ⊕ K * ⊕ ∆ e 1 = P - 2 (U ⊕ K * ⊕ ∆ e 1 )
. Substituting the expression for Y we get that

P - 2 (U ⊕ K * ⊕ ∆ d 1 ) ⊕ ∆ d 1 ⊕ ∆ e 1 = P - 2 (U ⊕ K * ⊕ ∆ e 1
). Since P - 2 is a permutation, this would happen iff ∆ d 1 = ∆ e 1 , which is an illegal query.

($ -, P+ 1 ) A call ξ d to KCDec and a call ξ e to KCEnc result in querying $ -and P+ 1 on the same point. This event is analyzed analogously to case ($ + , P- 3 ) above. ( P- 3 , P ± 3 ) A call ξ d to KCDec and a direct query to P ± 3 are such that either the inputs or the outputs collide. If the KCDec query comes after the direct query, since oracle P-3 is sampled to be consistent with P 3 , no inconsistency arises. If P 3 comes after KCDec then an inconsistency arises only with an entry on P-3 that is also on $ + . But in this case an inconsistency of the form ($ + , P ±

3 ) has been found. ( P+ 1 , P ± 1 ) A call ξ e to KCEnc and a direct query to P ± 1 collide. This case is treated analogously to ( P- 3 , P ± 3 ). KCEnc inconsistently rejects If Det ⊕ does not output an incorrect answer, ⊥ is the correct answer. On the other hand, as shown at the end of previous section, Det ⊕ with i = 1 outputs an incorrect answer with probability at most 1/2 n per inputs checked.

KCDec inconsistently rejects Similarly to the above, this event occurs with probability at most 1/2 n per inputs checked.

The theorem follows by putting the above bounds together.

Remark. A potential strengthening of the above theorem would be to consider a wider class of KCA attacks for which the ideal cipher is known to be secure. One possibility would be the class of key-unpredictable, claw-free, and xkcd-secure CDF sets as shown in Theorem 5.1. Although feasibility of this level of security claim for iterated Even-Mansour ciphers would follow from known indifferentiability [LS13; DSST17], this would require a larger number of rounds and also comes at the cost of lower levels of security. It remains an interesting open question to find the minimal number of rounds needed in the Even-Mansour ciphers that yields (Ξ e , Ξ d )-KC-CCA security with respect to any pair (Ξ e , Ξ d ) for which the ideal cipher is also (Ξ e , Ξ d )-KC-CCA secure.

We have seen that it is possible to achieve KCA-secure blockciphers. Given this, we now turn our attention to higher-level primitives and investigate the possibility of constructing KCA-secure primitives which rely on blockciphers. A natural first step is to explore symmetric encryption. Specifically, we consider the notion of authenticated encryption with associated data (AEAD).

kc-ae security

Let SE be an AEAD scheme as defined in chapter 2. Let Ξ e and Ξ d be CDF sets with signatures ξ e : K -→ K × M × N × H and

ξ d : K -→ K × N × H respectively.
As is in the blockcipher case, Ξ e is used to generate correlated keys and key-correlated messages. In addition to this, for authenticated encryption, we allow all inputs to the encryption algorithm to be key-correlated. Unlike the blockcipher case however, we restrict the use of Ξ d to generate correlated keys, nonces, and headers as it seems unnatural to derive a key-correlated ciphertext for decryption. If ξ e ∈ Ξ e and ξ d ∈ Ξ d we note that the We can extend to key-correlated ciphertexts, but it will come at the cost of requiring stronger assumptions.

syntactical difference to SE when considering KC-AE security is that the encryption oracle in the scheme only takes ξ e as input, while the decryption oracle takes (ξ d , C) as described in the KC-AE Ξ e ,Ξ d ,A SE game on the right in Figure 6.1. The KC-AE advantage of an adversary A against AEAD is defined by

Adv kc-ae SE (Ξ e , Ξ d , A) := 2 • Pr KC-AE Ξ e ,Ξ d ,A SE -1 .
We require that nonces are not repeated in KCEnc queries.

We can further extend to misuse-resilient authenticated encryption, if we extend to the stronger assumptions as with key-correlated ciphertexts.

Security against key-correlated attacks is a strengthening of the standard notion of AE-security for a symmetric encryption scheme. As the syntax shows, the input to SE consists of K, M, N, and H. A natural question may arise as to which inputs we allow to be keycorrelated. Although we would like to provide guarantees against any correlated inputs, there are two immediate issues with header security. It can (sometimes) be the case that headers are not private, and if they are heavily key-correlated, an adversary could trivially retrieve the key. For this reason, we require that header data is private. But a more subtle point, as shown in [START_REF] Bellare | Authenticated and Misuse-Resistant Encryption of Key-Dependent Data[END_REF], is that even with private headers, it is possible for an adversary to perform a full key recovery attack by taking advantage of the pattern of errors returned while list-checking during the decryption process which may be key-dependent. This attack does not apply in our setting, as we return only one error symbol (⊥) for both illegal queries and a failed decryption process, and as such, an adversary cannot use this to gain advantage. Note that even if we define a scheme with different error symbols to denote different types of decryption failures, we can still obtain header security, but at the cost of requiring key-claw-freeness.

Game KC-AE Ξ e ,Ξ d ,A SE : b {0, 1}; K * K b A KCEnc,KCDec return (b = b) Proc. KCEnc(ξ e ): (K, M, N, H) ← ξ e (K * ) C 1 ← Enc(K, M, N, H) if T[K, M, N, H] = undef: T[K, M, N, H] {0, 1} |C 1 | C 0 ← T[K, M, N, H] CL ← CL : (K, C b , N, H) return C b Proc. KCDec(ξ d , C): (K, N, H) ← ξ d (K * ) if (K, C, N, H) ∈ CL: return ⊥ M 1 ← Dec(ξ d , C, N, H) M 0 ←⊥ return M b

the hash-with-nonce transform

We introduce the Hash-with-Nonce (HwN) transform with the goal of achieving KCA-security for symmetric encryption. Working in the random-oracle model, HwN converts a conventional AE-secure AEAD scheme SE to a new one, SE = HwN[SE, Gen] = (Gen, Enc, Dec), which we will prove to be KC-AE secure. Gen is its key-generation algorithm, its key length is k and nonce length is n. Its encryption and decryption algorithms are defined as follows, where

H : K × N -→ K is a random oracle. Enc(K, M, N, H): C ← Enc(H(K|N), M, N, H) return C Dec(K, C, N, H): M ← Dec(H(K|N), C, N, H) return M
To show that SE is (Ξ e , Ξ d )-KC-AE secure it will be convenient to reduce to a multi-user variant of the AE game. Multi-user authenticated encryption (MUAE) allows an adversary to choose the number of keys to target, analogous to the number of users in the scheme. In addition to taking a message, nonce, and header, the encryption oracle takes an index i (indicating user number), and returns encryptions under a key K i , or a random string of the same length. Decryption always returns the error symbol, except in the case the real algorithms are being used where the message M is returned by decrypting C under K i . The adversary cannot ask user i to decrypt a ciphertext that it previously obtained from this user. In a scheme with n users, it follows via a simple hybrid argument (see Section 6.5) that any AE-secure AEAD scheme is also MUAE secure.

The convenience in using MUAE lies in the fact that we can leverage the programmability of random oracles to implicitly map the hash values H(ξ e i | 1 (K * )|N i ) of the i-th query ξ e i to KCEnc, to a new randomly and independently chosen key in the MUAE game. This also decouples the key used in encryption (i.e., H(ξ e i | 1 (K * )|N i )) from the key-correlated messages ξ e i | 2 (K * ), key-correlated nonces ξ e i | 3 (K * ), and key-correlated headers ξ e i | 4 (K * ). Overall, our reduction proceeds by choosing a K * , computing the key-correlated message, nonce, and header, faithfully using this key, and implicitly setting H(ξ e i | 1 (K * )|N) to keys K i in the MUAE game. For this analysis, we need that the keys K i remain hidden from the adversary's point of view, which we argue is the case as long the queried functions are key-unpredictable. We now state and prove the security guarantees of SE 6.3 kca security of hwn Theorem 6.1 (KCA security of HwN). Let SE be an AE-secure AEAD scheme. Let Ξ e and Ξ d be two CDF sets. Then for any (Ξ e , Ξ d )-KC-AE adversary A against the scheme SE obtained by applying the HwN transform to SE that makes q random oracle queries, q e encryption queries and q d decryption queries, there are adversaries B, C 1 and C 2 such that

Adv kc-ae SE (Ξ e , Ξ d , A) ≤ 2 • Adv mu-ae SE (B) + 2 • Adv m-kup Ξ e (C 1 ) + 2 • Adv m-kup Ξ d (C 2 )
where adversary B makes at most q e + q d queries to Init, at most q e queries to encryption, and at most q d queries to decryption, adversary C 1 outputs two lists of sizes at most q e and q, and adversary C 2 outputs two lists of sizes at most q d and q.

Proof. The proof proceeds via a sequence of games as shown in Game 0 describes the KC-AE game with respect to the transformed scheme and b = 1.

Game 1 is identical to Game 0 with one conceptual change: it proceeds by separating the book-keeping list for H into cases when H is accessed within KCEnc and KCDec and when directly accessed by the adversary. More precisely, in Game 1 , records of adversary A's queries to the random oracle H will be recorded in a list L, whereas the oracle queries from KCEnc and KCDec will be recorded in a list L by oracle denoted H . A bad flag, Bad, is set if H is queried on a key/nonce pair that has already been queried by A to H. In this game, H and H jointly implement H

the reductions

We now give the details of the bounds for the three transitional changes above.

adversary B 1 plays the MUAE game and is built based on an adversary A that attempts to distinguish Game 2 and Game 3 as follows. Adversary B 1 initializes q keys and chooses a K * . It then simulates the encryption and decryption oracles by explicitly computing the actual key, and also message when answering encryption, used using K * . In doing so, B 1 implicitly programs H(ξ e i (K * ), N i ) to K i , one of the q keys initialized by B 1 's challenger. Since nonces are not reused, and each K i is chosen randomly, this will constitute a perfect simulation of the random oracle H . When b = 0, this is a perfect simulation of Game 4 environment for A by B 1 . However when b = 1, although simulation encryption is good, care must be taken in decryption as decryption of (K, C, N, H) is not allowed in the KC-AE game if (K, C, N, H) was added to list CL. Adversary B 1 thus keeps track of these values and answers with ⊥ when such a query arises. Note that B 1 once again uses its knowledge K * and further that this modification does not affect the simulation when b = 0. Adversary B 1 continues in this way and returns the bit that A outputs. Hence,

Adv mu-ae SE (B 1 ) = Pr[b = 1|b = 1] -Pr[b = 1|b = 0] = Pr[Game A 2 ] -Pr[Game A 3 ] .
adversaries C i for i = 1, 2 are used to show that the probability of Bad is small by the key-unpredictability of the queried functions. Adversaries C i for i = 1, 2 run A in Game 3 by simply simulating its encryption and decryption oracles with $ and ⊥ respectively. They also lazily sample the random oracles H for A. Adversary C 1 keeps track of all queried functions to KCEnc and adversary C 2 keeps track of all queried functions to KCDec. Both adversaries also keep track of all queries to H. When A terminates, C i simply outputs the list of all queried functions that it keeps track of and H queries its two lists of guesses in the multi-shot key-unpredictability game. (See Figure 6.4 (middle) for the details.) Whenever flag Bad is triggered, either C 1 or C 2 wins the key-unpredictability game against Ξ e or Ξ d respectively:

Pr[Game A 3 sets Bad] ≤ Adv m-kup Ξ e (C 1 ) + Adv m-kup Ξ d (C 2 ) .
adversary B 2 is used to bound the difference between the probabilities of setting Bad in games Game 3 and Game 4 . This is done via another reduction to the MUAE game which attempts to decide the challenge bit by observing if Bad is set. Algorithm B 2 a bit b = 1 if the envirnment appears to be that of Game j , and b = 0 if the guess is that Game j+1 is observed. B j outputs the same bit b and wins the AE game if A has distingushed correctly. Thus, if b B is the bit output by B j and b A the bit output by A we conclude that

Adv ae SE (B j ) = Pr[b = 1|b B = 1] -Pr[b = 0|b B = 0] = Pr[Game A j ] -Pr[Game A j+1 ] .

Part III FA I L A G A I N

Abstract

In a recent paper [START_REF] Aggarwal | A New Public-Key Cryptosystem via Mersenne Numbers[END_REF], Aggarwal, Joux, Prakash, and Santha (AJPS) describe a simple public-key cryptosystem mimicking NTRU over the integers. This algorithm relies on the properties of Mersenne primes instead of polynomial rings. The security of the AJPS cryptosystem relies on the conjectured hardness of the Mersenne Low Hamming Ratio Assumption, defined in [START_REF] Aggarwal | A New Public-Key Cryptosystem via Mersenne Numbers[END_REF].

We show that AJPS' security estimates are too optimistic and describe an algorithm allowing to recover the secret key from the public key much faster than foreseen in [START_REF] Aggarwal | A New Public-Key Cryptosystem via Mersenne Numbers[END_REF].

In particular, our algorithm is experimentally practical (within the reach of the computational capabilities of a large organization), at least for the parameter choice {n = 1279, h = 17} conjectured in [START_REF] Aggarwal | A New Public-Key Cryptosystem via Mersenne Numbers[END_REF] as corresponding to a 2 120 security level. The algorithm is fully parallelizable. This is joint work with Marc Beunardeau, Rémi Geraud, and David Naccache. The corresponding paper was presented at the 5 th International Conference on Cryptology and Information Security in Latin America, Latincrypt 2017, in La Habana, Cuba; and has been published as [BCGN17a].

Further to this, subsequent work by de Boer et al. [START_REF] Koen De Boer | Attacks on the AJPS Mersenne-Based Cryptosystem[END_REF], led to a revision of the effective hardness, and led Aggarwal et al. to amend the original cryptosystem substantially [START_REF] Aggarwal | A New Public-Key Cryptosystem via Mersenne Numbers[END_REF]. Ferradi and Naccache further suggested slightly improved variants [START_REF] Ferradi | Integer Reconstruction Public-Key Encryption[END_REF] along with several research directions.

We introduce a cryptosystem similar in spirit to the original Aggarwal-Joux-Prakash-Santha cryptosystem (AJPS-1) but which relies on a different hardness assumption. As a result, the lattice reduction attack (à la [BCGN17a]) does not seem to apply. The resulting construction is conceptually simpler than the "fixed" AJPS cryptosystem (AJPS-ECC), and than Ferradi and Naccache's "high-bandwidth" variant (AJPS-FN-BT). This is joint work with Marc Beunardeau, Rémi Geraud, and David Naccache.

O N T H E H A R D N E S S O F T H E M E R S E N N E L O W H A M M I N G R AT I O A S S U M P T I O N

introduction

A Mersenne prime is a prime of the form 2 n -1, where n > 1 is itself prime.

In a recent paper [START_REF] Aggarwal | A New Public-Key Cryptosystem via Mersenne Numbers[END_REF], Aggarwal, Joux, Prakash, and Santha (AJPS) describe an ingenious public-key cryptosystem mimicking NTRU over the integers. This algorithm relies on the properties of Mersenne numbers instead of polynomial rings. This scheme is defined by four algorithms (Setup, Gen, Enc, Dec) described as follows:

-Setup(1 λ ) → pp, which chooses the public parameters pp = (n, h) so that p = 2 n -1 is prime and so as to achieve a λ-bit security level. In [START_REF] Aggarwal | A New Public-Key Cryptosystem via Mersenne Numbers[END_REF] the following lower bound is derived

n -1 h -1 > 2 λ
which for instance is satisfied by λ = 120, pp = (n = 1279, h = 17).

-Gen(pp) → (sk, pk), which picks F, G two n-bit strings chosen independently and uniformly at random from all n-bit strings of Hamming weight h, and returns sk ← G and pk ← H = F/G mod (2 n -1).

-Enc(pp, pk, b ∈ {0, 1}) → c, which picks A, B two n-bit strings chosen independently and uniformly at random from all n-bit strings of Hamming weight h, then computes c ← (-1) b (AH + B) mod (2 n -1).

-Dec(pp, sk, c) → {⊥, 0, 1}, which computes D = Gc mod (2 n -1) and returns

         0 if D ≤ 2h 2 , 1 if D ≥ n -2h 2 ,

⊥ otherwise

We refer the reader to [START_REF] Aggarwal | A New Public-Key Cryptosystem via Mersenne Numbers[END_REF] for more details on this cryptosystem which does not require further overview because we directly attack the public key to infer the secret key.

In particular, security rests upon the conjectured intractability of the following problem: Mersenne Low Hamming Ratio Assumption. The Mersenne Low Hamming Ratio Assumption states that given an n-bit Mersenne prime p = 2 n -1 and an integer h, the advantage of any probabilistic polynomial time adversary attempting to distinguish between F/G mod p and R is at most poly(n) 2 λ , where R is a uniformly random n-bit string, and (F, G) are independently chosen n-bit strings each having Hamming weight h.

We will argue that (F, G) can be experimentally computed from H, at least for the parameter choice {n = 1279, h = 17} conjectured in [START_REF] Aggarwal | A New Public-Key Cryptosystem via Mersenne Numbers[END_REF] as corresponding to a 2 120 security level.

outline of the analysis

The analysis uses the Lenstra-Lenstra-Lovász lattice basis reduction algorithm (LLL, [START_REF] Klaas Lenstra | Factoring polynomials with rational coefficients[END_REF]). We do not recall here any internal details of LLL but just the way in which it can be used to solve a linear equation with k unknowns when the total size of the unknowns is properly bounded.

Using LLL to Spread Information

Let x 1 , . . . , x k ∈ N * be k unknowns. Let p ∈ N be a modulus and a 0 , . . . , a k ∈ N. Consider the equation:

a 0 = k ∑ i=1 a i x i mod p.
Our goal is to use the LLL algorithm to x 1 , . . . , x k if ∏ k i=1 x i < p. In particular, LLL can be adapted to provide any uneven split of sizes between the x i as long as the sum of those sizes does not exceed the size of p. More details on the theoretical analysis of LLL in that setting and variants are given in [NS01, Sec. 3.2] and [Jou09, Chap. 13], in the context of generalised knapsack problems.

Partition and Try

The first observation that attracted our attention is that the size 1 of F (and G) has an unusually small expectation σ(n, h):

σ(n, h) = n 1 + (1 -h n ) n+1 -1 h n (n + 1)
The difference in size between n = 1279 and σ(1279, 17) is not huge 2 and cannot be immediately exploited. However, the same phenomenon also occurs at the least significant bits and further shortens the expected nonzero parts of F and G by 70 bits. Similarly, assume that in the key generation procedure, both F and G happen to have bits set to 1 only in their lower halves. When this (rare event) happens, we can directly apply LLL to H to recover F and G. We call this event T.

Is that event rare? Since F and G are chosen at random, T happens with probability at least 2 -2h . While T's probability is not cryptographically negligible, this pre-attack only allows to target one key out of 2 2h . For the first suggested parameter set (λ = 120), one public key out of 67 million can be attacked in this fashion and its F and G recovered, i.e., a total break. The question is hence, can this phenomenon be extended to any key? and if so, at what cost? In particular, can we sacrifice work to increase the size of the vulnerable key space? The answers to these questions turn out to be positive, as we will explain hereafter.

random partitions. Instead of a fixed partition of {0, . . . , n -1}, we can sample random partitions, for instance by sampling (without replacement) m positions, which are interpreted as boundaries between regions of zeros and regions that possibly contain a 1. The total number of regions, m + 1, determines the dimension of the lattice being reduced.

For the sake of simplicity we consider balanced partitions.

Balanced partitions. A partition of {0, . . . , n -1} into m/2 type Since n is odd, we must accept a ± 1 excess.

1 blocks and m/2 + 1 type 2 blocks is balanced if the total size of the type 1 blocks and the total size of the type 2 blocks differ by at most one.

There is room for improvement here as well, since rejection sampling is a very inefficient approach. Nevertheless it will be sufficient for our discussion, and any approach to generating such partitions would work without impacting the analysis.

A randomly sampled partition is not necessarily a balanced partition, to rectify this, we use rejection sampling to ensure the balancing property. We call the sought-after property of these partitions a correct partition.

Correct partitions. Let X be a binary string of length n. A partition of X into m/2 type 1 blocks and m/2 + 1 type 2 blocks is correct for X if the type 2 blocks are completely made of zeros.

Figure 7.1 illustrates the partitions that we are interested in on a simple example. Also note that the notion of correct partitions does not put any constraint on type 1 blocks, which may contain zeros or not; since they are not guaranteed to be zero we refer to them as "non-zero" blocks. Accordingly, blocks of type 2 in a correct partition are referred to as "zero" blocks. In Figure 7.1 a black square in F or G represents a 1, while white squares represent 0s. The partitions f and g are balanced and correct for F and G respectively, with "zero" blocks coloured white, and "non-zero" blocks coloured black. The vertical dashed lines show how F and G align with their respective partitions. The observation at the beginning of this section is that using a balanced partition that is correct for F and another one that is correct for G, we can recover F and G from H.

Since F and G are unknown, we cannot construct a correct partition from them directly; but the probability that a random balanced partition is correct for F (resp. G) is lower bounded by 2 -h . Assuming that

We ignore the fact that we sample without replacement here, as h n. Under this conservative approximation, all the bits are sampled uniformly and independently, and may fall with probably 1/2 either in a type 1 or a type 2 block.

F and G are independent, which they should be according to the key generation procedure, we found a correct partition for both F and G with a probability of 2 -2h .

Remark. We may also consider imbalanced partitions which allow an extra speed-up for a subtle reason: Given that the unknowns found by LLL have a low Hamming density, the odds that these numbers naturally begin by a sequence of zeros (and are hence shorter than expected) is high. The interesting point is that the total length of such natural gains sums up and allows to unbalance the partition in favor of type 1 blocks. Consider the analogy of a fishing boat that can carry up to 1000 kilograms of fish. The fishermen fishes with 3 nets having maximal capacities of 200, 300 and 500 kilograms each. Because waters are sparse in fish, the nets are expected to catch only 70% of their maximal capacity. Hence, we see that larger nets (285, 428, 714) can be used to optimize the boat's fishing capacity. However, unlike the boat, with LLL fish cannot be thrown back to the water and... excess weight sinks the boat (the attack fails). Hence if this speed-up strategy is used, we need to catch more than normal but not be too greedy. Note as well that if all variables end by at least trailing (LSB) zeros then these m zeros add-up to the gain as well (because there is no constant term in the equation a division of all variables by 2 has no effect on the solution's correctness). We did not exploit nor analyze these tricks in detail.

trying partitions. The attack then consists in sampling a balanced partition, running LLL, and checking whether the values of F and G obtained from the reduction have the correct Hamming weight and yield H by division. Concretely, the matrix to be reduced is obtained as follows from the partitions f of F and g of G:

1. Compute the size of the non-zero blocks in f and g, we call these sizes u = {u i } and v = {v i } respectively, with i = 0, . . . , m/2 -1. Let w = max i {u i , v i }.

2. Construct the vector s = s i as follows:

s i =    2 w-v i if i < m/2 2 w-u i if m/2 ≤ i < m 3.
Construct the vector a = {a j } as follows: let f i (resp. g i ) denote the starting position of the non-zero blocks in F (rep. G), and set

a j =    H × 2 g i mod p if j < m/2 p -2 f i if m/2 ≤ j < m 4.
Choose an integer K, and assemble the matrix M as follows:

M = diag(s) Ka 0 Kp
where diag(s) is the diagonal matrix whose diagonal entries are given by s. The coefficient K is a tuning parameter, which we set to 2 1200 .

5. Finally, we use LLL on M (using the Mathematica command LatticeReduce) and recover the reduced row of the matrix that complies with the Hamming density of F and G. This row is expected to give the values of the non-zero blocks of F and G, and we can check its correctness by computing its Hamming weight, and checking that the ratio of the candidate values modulo p yield H.

By the above analysis, a given partition is correct with probability 2 -2h , which for λ = 120 is only 2 -34 ; if we can run LLL reasonably fast, which is the case for m = 16, an efficient attack happens to be within the reach of a well-equipped organization. Experimental evidence indeed suggests the feasibility of the attack, see Section 7.3.

Remark.

For larger security parameters λ, the ratio h/n deduced from the analysis in [START_REF] Aggarwal | A New Public-Key Cryptosystem via Mersenne Numbers[END_REF] asymptotically vanishes. It should be checked if this influences imbalanced partition finding to the attacker's relative advantage for larger values of λ. We did not explore this avenue left to the reader as a potential research question.

putting it together

To illustrate the attack's feasibility, we fix a random tape in a deterministically verifiable way and implement our algorithm (see Fig- Proc Gen: n, h ← pp We generated a nothing-up-our-sleeves key with the procedure of Figure 7.3. The sample(S, h) procedure selects h indices without replacement in the range S. It is implemented by returning the h first entries of a deterministic Fisher-Yates shuffle of S. The randomness in sample(S, h) is simulated by iterating the SHA256 function, starting with the seed given by the ASCII representation of the 100 first decimals of π:

I 1 = {i 1 , . . . , i h } ← sample({0, . . . , n -1}, h) I 2 = {i 1 , . . . , i h } ← sample({0, . . . , n -1}, h) F ← ∑ h i∈I 1 2 i G ← ∑ h i∈I 2 2 i return (sk = G, pk = F • G -1 mod p)
31415926535897932384626433832795028841971693993751 05820974944592307816406286208998628034825342117068
In a real attack we would simply use a fast non-cryptographic random number generator, but the above choice serves the purpose of reproducibility.

This gives the following (in hexadecimal notation, the zero MSBs have not been written):

I 1 = {33, 47, 8e, 95, a1, 134, 19f, 1ab, 1ac, 1ce, 25d, 301, 30a, 3ee, 444, 46b, 471} I 2 = {89, b5, de, 116, 141, 1dd, 1de, 2ae, 322, 37a, 388, 38a, 3f9, 48c, 48d, 4e9, 4f2} finding a winning partition. At this step, we generate random balanced partitions and try LLL on the resulting decomposition. Doing so we quickly find the following partitions f = {2a, bf, 134, 1ec, 233, 253, 25a, 270, 2ee, 32d, 3e4, 41e, 42b, 4a7, 4f6, 4fd} g = {7c, 142, 1d0, 22a, 289, 2c8, 2de, 2e7, 2eb, 33c, 372, 3a0, 3da, 3ff, 48a, 4fd} respectively for F and G, which upon lattice reduction yield candidates of the correct Hamming weight. Their ratio indeed gives H; however one may debate our claim that this partition was found at random and argue that we constructed it from our prior knowledge of F and G.

To counter this argument and insist that finding partitions is reasonably easy, we derived them deterministically from the same seed as the key. To achieve this, we proceed as follows: we draw two independent sets of m/2 -1 indices in the range [0, n/2], which gives the sizes of the zero blocks and the non-zero blocks. This guarantees that the partitions are balanced. The randomness used for this sampling is obtained by iterating SHA256 as for key generation.

As in the example above, we construct partitions for m = 16 -this choice is not dictated by probability (as the likelihood to find a correct partition is in theory independent of m), but rather by a trade-off between the cost of LLL and the number of partitions explored. It is possible for instance to start with m = 2 partitions, then m = 3, and so forth, but we settled for a random search which is easier to implement.

We found the following partition for F at run #1,152,006 (in 116 s): 13c, 198, 1cf, 24b, 27b, 2ac, 30f, 3e1, 456, 45a, 4ba, 4d6, 4fd} Recovering F alone took about two minutes. Given that we have

f = {27, b2, 10e,
Experiments with random partitions show that this timing is quite variable and follows a Poisson distribution, with a correct partition being typically found earlier, with an average of 2 17 tries.

a totally deterministic random tape, we regard our experiment as legitimately reflecting reality. Because F and G are independent, this brings the total effort to about the square of this number, i.e. about 2 34 attempts to get both partitions with certainty. Each of these attempts must also involve one LLL, which is the main cost factor.

Using the same sequence, run #64,249 gave a partition for G too (in 7.6 s):

g = {7b, 11c, 13b, 181, 1cc, 1e1, 284, 2e6, 318, 329, 36f, 3e5, 3f1, 404, 476, 4fd}

Finally, note that the task is fully parallelizable and would benefit from running on several independent computers, a remark that we will later use in our final workfactor estimates.

computing the secret key Running our program as explained in Section 7.2, we recover F, G, and confirm that H = F/G mod p.

Predicting the Total Execution Time

Putting all the above figures together and assuming no further algorithmic improvements, the total expected effort is:

(LLL_Time + 2 × Partition_Time) × Average_Partition_Tries 2 Number_of_Processors
Where, in our basic scenario Average_Partition_Tries = 2 h . We performed LLL in Mathematica using the LatticeReduce function, which took less than a second in the worst case on a simple laptop. We safely assume that this figure can be divided by 10 using a dedicated and optimized code. We also assume that a credible attacker can, for example, very easily afford buying or renting 150 TILE-Gx72 multicore processors. Hence, according to the evidence exhibited in this paper, breaking a 1279-bit key takes a week using 150 currently available multicore processors (e.g. TILE-Gx72).

conclusion

While we did not formally evaluate efficiency nor asymptotic complexities, our quick and dirty experiments clearly suffice to show that key recovery is fast and within reach. An obvious countermeasure consists in increasing parameter sizes. Hence a precise re-evaluation of parameter sizes and safety margins of the Mersenne Low Hamming Ratio Assumption seems in order.

More systemic protections may consist in modifying the definition of H (and possibly the underlying cryptosystem) which is clearly a very interesting open problem.

Nonetheless the beautiful idea of Aggarwal, Joux, Prakash, and Santha exploiting the fact that arithmetics modulo Mersenne numbers is (somewhat) Hamming-weight preserving, is very elegant and seems very rich in possibilities and potential cryptographic applications.

P U B L I C -K E Y C R Y P T O S Y S T E M S B A S E D O N A N E W C O M P L E X I T Y A S S U M P T I O N

introduction

In 2017, Aggarwal, Joux, Prakash, and Santha [AJPS17a; AJPS17b] introduced a new public-key cryptosystem, inspired by NTRU [START_REF] Hoffstein | NTRU: A Ring-Based Public Key Cryptosystem[END_REF] but conceptually much simpler, and tentatively immune to some of the most classical attacks against NTRU. Since public-key cryptosystems are relatively rare, Aggarwal et al.'s construction (henceforth AJPS-1, following [START_REF] Ferradi | Integer Reconstruction Public-Key Encryption[END_REF]) garnered much attention from the cryptographic community. In a matter of weeks, it was found that AJPS-1's initial security estimates were optimistic, and a modified scheme with larger parameters was proposed [START_REF] Aggarwal | A New Public-Key Cryptosystem via Mersenne Numbers[END_REF]. Section 8.2 recalls the construction and history of these cryptosystems, which we refer to as Mersenne-based cryptosystems, in more details.

In this paper, we suggest a further modification of the underlying hardness assumption, which are conjectured to be unaffected by attacks against AJPS-1, yet which enable the construction of similarlyelegant encryption schemes. The new assumption, dubbed "projected Mersenne", and a corresponding public-key encryption scheme are introduced in Section 8.4.

preliminaries

notations. We denote by x the Hamming weight of x, and by H n,w the set of all n-bit strings of Hamming weight h. The notation x X means that x is the result of uniformly sampling from the set X. Unless stated otherwise, log refers to the natural logarithm, and log 2 to the base 2 logarithm. The symbols ⊕ and ∧ stand for the binary XOR and AND operations, respectively. We denote the concatenation of x and y by x y. A q-ary error correcting code with block length d, dimension k, and minimum Hamming distance δ will be denoted [d, k, δ] q . We use the shorthand notation Z p to denote Z/pZ. Algorithms are given as input the (unary) representation of the security parameter λ. PPT stands for probabilistic polynomial time.

prior work

The Mersenne Low Hamming Ratio Assumption

Recall that a Mersenne number is an integer of the form 2 n -1 for In particular, if 2 n -1 is prime, then so is n.

some n, and that a Mersenne prime is a Mersenne number which is prime.

Mersenne Low Hamming Ratio Search Problem (MLHR). Let p = 2 n -1 be a Mersenne prime. Given n, w ∈ N and h ∈ Z p , find

The use of a Mersenne prime is not necessary for the scheme's correctness, and in fact no attack is currently known if p is a Mersenne composite. The conservative choice of a Mersenne prime is recommended to avoid potentially unforeseen attacks exploiting the factorisation of p, cf.

[

f , g ∈ Z p such that f = g = w and f /g = h mod p, under the promise that such a couple exists.

A brute-force attack on MLHR tries all possible couples { f , g}, which corresponds to a security level of

λ = n -1 w -1 ≈ w • log n bits.
A quantum variant of this search, exploiting the generic speed-ups provided by Grover's algorithm, correspondingly halves λ. Should these attacks be optimal -as initially suggested by Aggarwal et al. -the MLHR would enable the construction of conceptuallysimple and computationally-efficient post-quantum secure public-key cryptosystems.

The Aggarwal-Joux-Prakash-Santha Cryptosystem (AJPS-1)

The original AJPS-1 scheme [START_REF] Aggarwal | A New Public-Key Cryptosystem via Mersenne Numbers[END_REF] is defined by the following algorithms:

-Setup(1 λ ) → pp. Outputs the public parameters pp = {n, h}, so that in particular p = 2 n -1 is prime. The choice of n and w is such that the cryptosystem achieves some λ-bit security level.

-Gen(pp) → {sk, pk}. This algorithm generates the private and public keys. It samples {F, G} H 2 n,w , and returns:

sk ← G pk ← H = F/G mod p -Enc(pp, pk, m) → C.
This algorithm takes as input the public parameters pp, the public key pk, and a message m ∈ {0, 1}. It samples {A, B} H 2 n,w , and computes:

C ← (-1) m (AH + B) mod p.
-Dec(pp, sk, C) → {⊥, 0, 1}. This algorithm computes d ← G • C mod p and returns:

         0 if d ≤ 2w 2 , 1 if d ≥ n -2w 2 ,
⊥ otherwise.

Ciphertext space R = Z[X]/(X N -1) R = F 2 [X]/(X p -1), p = 2 n -1 Message space M ∈ R M M ∈ {0, 1} Private key F ∈ R F F ∈ H n,w
Public key

H = G/F q mod q (G ∈ R G ) H = G/F (G ∈ H n,w ) Encryption C = prH + M mod q (r ∈ R r ) C = (-1) M (AH + B) (A, B ∈ H n,w ) Decryption M = F -1 p (FC mod q) mod p M =          0 if FC ≤ 2w 2 1 if FC ≥ n -2w 2 ⊥ otherwise
Similarities with the NTRU cryptosystem. Mersenne-based cryp-NTRU stands for N-th Degree Truncated Polynomial Ring Units.

tosystems are reminiscent of NTRU [START_REF] Hoffstein | NTRU: A Ring-Based Public Key Cryptosystem[END_REF], which owes its name to the polynomial ring R = Z[X]/(X N -1) in which operations are performed. In comparison, Mersenne-based cryptosystems work in

Z p F 2 [X]/(X p -1)
, where p = 2 n -1 is prime.1 Table 8.1 shows the parallels between the two cryptosystems. Notations for NTRU follow [START_REF] Hoffstein | NTRU: A Ring-Based Public Key Cryptosystem[END_REF], except R f , R g , R r , R m which are subsets of R having a prescribed number of coefficients set to -1 and 1.

The hard problem underlying NTRU is the closest-vector problem (CVP) in some special convolution modular lattices; namely, f and g form a relatively short vector in a known lattice constructed from q and h. Parameters for NTRU must be chosen to resist lattice reduction attacks (e.g., [START_REF] Coppersmith | Lattice Attacks on NTRU[END_REF][START_REF] Kirchner | Revisiting Lattice Attacks on Overstretched NTRU Parameters[END_REF]). In the original version of their paper [AJPS17a], Aggarwal et al. consider and then dismiss two possible types of attack that could be better than brute force, inspired by NTRU cryptanalysis: a combinatorial meet-in-the-middle attack, which is claimed to fail due to the presence of "approximate collisions"; and a lattice-based attack, claimed to fail due to the presence of "parasitic vectors".

Beunardeau-Connolly-Géraud-Naccache attack. The latter claim was rapidly challenged, when a faster experimental attack using lattice reduction was discovered by Beunardeau et al. [BCGN17b] as presented in Chapter 7, which successfully recovered private keys for the initially suggested λ = 128 bit security level parameters. This attack runs in time (2 + δ + o(1)) 2w , for some very small constant δ > 0 [BDJW17], thereby collapsing the security of the original AJPS construction to about 2w bits.

de Boer-Ducas-Jeffery-de Wolf attack. The former claim was also challenged by de Boer et al. [START_REF] Koen De Boer | Attacks on the AJPS Mersenne-based cryptosystem[END_REF], who showed how to circumvent the "approximate collision" problem by leveraging locality-sensitive hashing. This resulted in a meet-in-the-middle attack, whose complexity is approximately

n/2 w/2 ≈ n w 1/2 ≈ 1 2 w log n.
A quantum version of this algorithm has runtime about

n/3 w/3 ≈ n w 1/3 ≈ 1 6 w log n.
Pointing out similar work for the related NTRU cryptosystem [START_REF] Buhler | Algorithmic Number Theory, Third International Symposium, ANTS-III[END_REF], de Boer et al. conjecture that a combination of the MITM approach with lattice reduction could lead to an even faster attack, reminiscent for instance of Howgrave-Graham's [START_REF] Howgrave-Graham | A Hybrid Lattice-Reduction and Meet-in-the-Middle Attack Against NTRU[END_REF]. The new version accomodates larger parameters and also improves somewhat the cryptosystem's bandwidth. As it makes use of an error correction scheme ECC = {D, E }, we refer to it as AJPS-ECC (following [START_REF] Ferradi | Integer Reconstruction Public-Key Encryption[END_REF]). The Setup algorithm is unmodified. The other algorithms are modified as follows:

-Gen(pp) → {sk, pk}. Sample {F, G} H 2 n,w , R {0, 1} n and return:

sk ← F pk ← {R, T} = {R, F • R + G mod p} -Enc(pp, pk, M) → C. Sample {A, B 1 , B 2 } H 3 n,w , and compute C ←    C 1 = A • R + B 1 mod p C 2 = (A • T + B 2 mod p) ⊕ E (M)
-Dec(pp, sk, C) → {⊥, M} is modified accordingly and returns

D((F • C 1 mod p) ⊕ C 2 ).
An analysis of the parameter choices for ECC and for the cryptosystem, including some additional discussion not relevant for our purpose, can be found in the updated paper by Aggarwal et al. [START_REF] Aggarwal | A New Public-Key Cryptosystem via Mersenne Numbers[END_REF].

The careful reader will notice that AJPS-ECC relies for security on different assumption than that of the hardness of MLHR search; however, Aggarwal et al. point out that slight modifications to the attack presented in Chapter 7 also apply to this modified scheme and choose the parameters accordingly.

Ferradi-Naccache (AJPS-FN-BT)

An interesting collection of variants is described by Ferradi and Naccache [START_REF] Ferradi | Integer Reconstruction Public-Key Encryption[END_REF]. Noticing that some of the random coins used during encryption may be recovered, Ferradi and Naccache suggest turning this into a feature, thereby increasing the cryptosystem's bandwidth. However, the security of most of these variants is not discussed in depth. The core idea can be found in Ferradi and Naccache's "bivariate" variant AJPS-FN-BT2.

AJPS-FN-BT2 relies on the availability of an efficient function Solve x,y which finds a low Hamming weight solution to a given Diophantine equation of the form αx + βy + γ = 0 for given parameters α, β, γ. They suggest implementing this function as a heuristic-based backtracking algorithm. Using this, it becomes possible to recover the values A and B used during encryption, which have low Hamming weight. One possibility is to use A and B to design a key-encapsulation mechanism as follows:

-Setup and Gen are identical to those of AJPS-1, except that we additionally agree on a block cipher BC : {0, 1} λ × {0, 1} λ → {0, 1} λ , a cryptographic hash function H 2 : {0, 1} * → {0, 1} λ , and a cryptographic hash function H 1 : {0, 1} * → H 2 n,w .

-Enc(pp, pk, M) → C is modified as follows. Sample r {0, 1} λ and compute {A, B} H 1 (r M). Then compute K ← H 2 (A B). Finally, output

C = {C 1 , C 2 } = {AH + B mod p, BC k (r m)} .
-Dec(pp, sk, C) → {⊥, M} is modified as follows: first recover {A, B} ← Solve x,y [GC 1 = Fx + Gy mod p] .

In case of failure, return ⊥. Otherwise, compute K ← H 2 (A B), and recover u ← BC -1 k (C 2 ). If H 1 (u) = {A, B} then return ⊥. Otherwise return M. The correctness of this scheme (and other variants in [START_REF] Ferradi | Integer Reconstruction Public-Key Encryption[END_REF]) is not formally analysed but is backed by numerical simulations. This search problem can be solved by brute-force enumeration much like MLHR, as it suffices to find g, i.e., find one in ( n-1 w-1 ) ≈ 2 w log n possibilities. We introduce the following assumption: a-Projected Mersenne assumption. The a-projected Mersenne as-We choose to explicit only one parameter, namely the random numerator's size. The other parameter is the denominator's

Hamming weight, which will be the same throughout our different variants, and therefore will not be explicitly noted.

sumption states that given a Mersenne prime p = 2 n -1, an integer a in poly(λ), any PPT distinguisher has a negligible chance to distinguish between R/G and R , where R {0, . . . , 2 a -1}, G H n,w , and R Z p . where the distinguishing advantage is defined as usual: For a PPT distinguisher D that outputs a bit b ∈ 0, 1, the distinguishing advantage to distinguish between two random variables X and Y is defined as:

∆ D (X; Y) = |Pr[A(X) = 1] -Pr[D(Y) = 1]|

Projected-Mersenne Encryption

We now define our encryption scheme.

-Setup(1 λ ) → pp. Choose p = 2 n -1 a Mersenne prime, and parameters w, a, b, c, d so as to achieve a λ-bit security level. Additional constraints on a, b, c, d to ensure correctness are discussed below. We also agree on an error-correcting code ECC = (E , D)

A possibility is to use BCH codes [Hoc59; BRC60] which are efficient and give fine control over the code's parameters, or Reed-Solomon codes [START_REF] Reed | Polynomial codes over certain finite fields[END_REF] which are MDS.

with codewords of size d bits.

-Gen(pp) → {sk, pk}. Sample G H n,w and a random a-bit number R that has large Hamming weight (e.g., R = a/2). Let F ← R • 2 b + 2 c mod p. Note that, in general, F / ∈ H n,w . An illustration of F's structure is given in Figure 8.1. The Gen algorithm returns

sk ← G pk ← F/G mod p -Enc(pp, pk, M) → C. Sample B H n,w and return C ← E (M) • pk + B mod p. -Dec(pp, sk, C) → {M, ⊥}. First compute D ← 2 n-c C • sk mod p.
This should be Let N = 2 d -1, then the algorithm outputs D(N ∧ D). Figure 8.2 illustrates this process.

D = 2 n-c Csk = 2 n-c (E (M) • H + B) • G mod p = 2 n-c E (M)F + 2 n-c BG mod p = 2 n-c E (M) • 2 b R + 2 c + 2 n-c BG mod p = E (M) + 2 n+b-c RE (M) + 2 n-c BG

Correctness

The correctness of this scheme is based upon two facts. The first is that we can appropriately choose a, b, c, d so that the first and second term in the expanded expression of D are disjoint (as depicted in Figure 8.2). When this is the case, masking by N removes the 2 n+b-c RE (M) term. The conditions for this to happen are easily found by inspecting Figures 8.1 The second key fact is that BG has low Hamming weight, namely at most w 2 . This is not affected by multiplication by a power of 2, and therefore 2 n-c BD ∧ M has Hamming weight at most η = min(d, w 2 ). 2 If ECC can correct at least η errors, then the decoding algorithm succeeds. 3 Even in the case that ECC can only correct t < η errors, there is still a non-zero probability that Dec successfully recovers M, which corresponds to the events where all η -t bits lay between 2 d and 2 n -1; this probability is roughly (1 -2 d-n ) η-t .

Semantic Security

As described above, the cryptosystem is vulnerable to a trivial chosen ciphertext attack. Assume the attacker gets a challenge encryption C * of M b with b ∈ {0, 1} being the challenge bit they have to guess. Indeed, we get

C * = E (M) • pk + B mod p
Thanks to the knowledge of the public key they will be able to recover the randomness (and break the semantic security). They compute the encrpytion with the randomness being set to 0.

C 0 = E (M 0 ) • pk + B mod p C 1 = E (M 1 ) • pk + B mod p
We then subtract the ciphertexts:

C * -C 0 = (E (M b ) -E (M 0 )) • pk + B mod p C * -C 1 = (E (M b ) -E (M 1 )) • pk + B mod p
One of these equations is equal to B and has low hamming weight, which allows the adversary to distinguish. This phenomenon is common to other cryptosystems, such as the McEliece code-based encryption scheme. Therefore our system is inherently not CCA-secure. We can treat this problem by using a key encapsulation mechanism which encrypts a random message, and derive the randomness used in the encryption by hashing the random message. AJPS uses the same method, but they only need it for chosen ciphertext attacks.

key encapsiation mechanism

To keep consistency with AJPS, we use the same notation to define KEM to ease comparison. Key encapsulation mechanism syntax. A key encapsulation mechanism KEM is a tuple of PPT algorithms (Gen, Encaps, Decaps) such that:

1. The key generation algorithm Gen takes as input the security parameter 1 λ and outputs a public/private key pair (pk, sk).

2. The encapsulation algorithm Encaps takes as input a public key pk and the security parameter 1 λ . It outputs a ciphertext C and a key k ∈ {0, 1} (λ) where is the key length. We write (C, K) ← Encaps pk (1 λ )

3. The deterministic decapsulation algorithm Decaps takes as input a private key sk and a ciphertext C, and outputs a key K 0 or an error symbol ⊥ denoting failure. We write this as K 0 := Decaps sk (C). It is required that with all but negligible probability over (sk, pk) output by Gen(1 λ ), if Encaps pk (1 λ ) outputs (c, k) then Decaps sk (C) outputs K 0 . KEM semantic security. The key-encapsulation mechanism KEM (Gen, Encaps, Decaps) is said to be semantically secure if for any probabilistic polynomial time distinguisher, given the public key pk, the advantage for distinguishing (C, K 0 ) and (C, K 1 ), where (C, K 0 ) Encaps(pk) and K 1 is uniform and independent of C is negligible in λ.

KEM Semantic Security Under Chosen Ciphertext Attack.

The key-encapsulation mechanism KEM = (Gen, Encaps, Decaps) is said to be secure under chosen ciphertext attacks if for any probabilistic polynomial time distinguisher that is given access to the decapsulation oracle and the public key pk, the advantage for distinguishing (C, K 0 ) and (C, K 1 ), where (C, K 0 ) Encaps(pk) and K 1 is uniform and independent of C is negligible in λ under the assumption that the distinguisher does not query the oracle with C.

We now describe our KEM. Its purpose is to avoid encrpytion with randomness set to 0 as in the attack against our encyption scheme. To achieve this, we will sample a key at random, and use it with a random oracle to generate the randomness to encrypt the key. Let H be a random oracle from the key space {0, 1} λ be the random tape of our encryption scheme (ie. low hamming weight numbers).

-Gen remains unchanged from the encryption scheme.

-Encaps(pk) draws uniformly at random a key K, produces the ciphertext Enc(K) • pk + H(K) and the key K. -Decaps(sk, C) produces the key K = Dec(sk, C), reencrypts its own randomness C = Enc(K ) • pk + H(K ), and checks C = C . If C = C output ⊥, else output K. Our KEM is trivially 1δ-correct with δ negligible in λ from the correctness of the encryption scheme.

Security Analysis

In this section we show that the KEM's semantic security (Definition 8.5) relies on the Projected-Mersenne Assumption (Definition 8.4.1), and discuss the attacks that can apply to this assumption. Before proving Theorem 8.1 we give a few lemmas that we will use later. The main thing to prove is that the public key is indistinguishable from random, which is shown in Lemma 8.5. Lemma 8.2. Given a PPT computable function f on two random variables X and Y , if there is no PPT distinguisher D that can distinguish between X and Y with non negligible advantage, then there is no PPT distinguisher D that can distinguish between X and Y with non negligible advantage.

The proof of Lemma 8.2 is well known and can be found easily.

Lemma 8.3. If x ∈ Z *
p is of hamming weight 1, then x -1 is of hamming weight 1.

Proof. Since the multiplicative group Z * p is of order p -1, we have x -1 = x p-2 . Since we work modulo a Mersenne prime, multipliying by a number of hamming weight 1 is equivalent to shifting. Therefore taking the product of two numbers of hamming weight 1 is also of hamming weight 1. Since x -1 is the product of numbers of hamming weight 1, it is itself of hamming weight 1.

Lemma 8.4 also gives an intuition about our security. For example doing the same computation on the public key of AJPS-1, we would get a much smaller number of contributions (17/2 for 128-bits of security).

Lemma 8.4. Every bit of the public key is the sum of an average of a/2 bits of R omitting the contribution of the carry4 .

Proof. First we notice that although 1/G is not random looking (as shown in [BCGN17c]), it has a random hamming weight (n/2 on average). Indeed 1/G = G p -2. So its low hamming weight increases since we perform approximately n squarings to come to the inverse. Second, since R is of size a, every bit of the public key is influenced by a copy of R if a bit in the a bits preceding it is set to 1 in 1/G. Combining the two observations gives the result.

The intuition of the security of our scheme is in this lemma. The message is written using this 2 c in the public key. We basically show that dividing by G makes that the 2 c that will contain the message masked by R.

Lemma 8.5. Assuming the a-Projected-Mersenne Assumption (Def. 8.4.1), given a Mersenne prime p = 2 n-1 , an integer a output by Setup, any PPT disinguisher has a negligible chance to distinguish between pkR where pk is the public key generated from Gen and R

Z p Proof. Let pk = 2 b • R/G + 2 c • 1/G mod p. Applying Lemma 8.2
with f being the division by 2 b , the adversary tries to distinguish chal = R/G + 2 c-b G . By Lemma 8.3, 2 c-b is of hamming weight 1. So we can rewrite chal = R+2 i G for some i. Applying Lemma 8.4, with

Here we see the reduction is not tight : for 128-bits of security the probability is 1 -2 69 .

overwhelming probability, every additional 1 coming from 2 i /G will be in a copy of R. Since there are as many copies of R as there are 1s coming from 2 i /G (this number being ||1/G||, the hamming weight of 1/G), we can rewrite the challenge:

chal = ||1/G|| ∑ i=0 2 u i R i
for some u i with R i = R + 2 x and with x 0, a -1. We now show that we can replace one R i by R. Since x is taken at random with overwhelming probability an R i is indistinguishable from R since their distributions are statistically close. Indeed R [0, 2 a-1 ]

Once again the reduction is not tight. One could try to make it tighter by choosing which R goes with which 1, to minimize x and R i [2 x , 2 x + 2 a-1 ]. X is on average a/2, and the statistical distance is a/2. With overwhelming probability the statistical distance is negligible.

Since there are polynomially many R i s, one can replace them one by one to get from chal to R/G while staying indistinguishable.

Lemma 8.6. Assuming the a-Projected Mersenne Assumption (Def. 8.4.1), given a Mersenne prime p = 2 n-1 , an integer a, any PPT distinguisher has a negligible chance to distinguish between G/R and R whereR [0, 2 a-1 ], G H n,w and R Z p .

Proof. This is shown by applying Lemma 8.2 with f being the modular inversion.

We can now prove our main theorem 8.1.

Proof. For any PPT distinguisher D, we have by the triangle inequality:

δ D ((pk, C); (pk, R)) ≤ δ D ((pk, C); (R, Enc(M)R + B)) + δ D ((R, Enc(M)R + B); (R, R )) + δ D ((R, R ); (pk, R))
where pk is a public key genrated from Gen, M is drawn at random, B

H n,w , C = Enc(M)pk + B is a ciphertext, and R, R Z p . This suffices to show the semantic security.

We now have to show that the three bounding terms are negligible: δ D ((pk, C); (R, Enc(M)R + B)). By Lemma 8.5 we have that pk is indistinguishable from a random, applying Lemma 8.2 with f (X) = (X, Enc(M)X + B) with M a message drawn at random and B

H n,w -δ D ((R, Enc(M)R + B); (R, R )). By Lemma 8.6 we have that B/R is indistinguishable from random, applying Lemma 8.2 with f (X) = (R, X • R + Enc(M)) we get that δ D ((R, Enc(M)R + B); (R, R • R + Enc(M))) is negligible. By observing that R • R + Enc(M) is uniformly distributed, δ D ((R, Enc(M)R + B); (R, R )) is negligible. -δ D ((R, R ); (pk, R))
. This is shown to be negligible by Lemma 8.5

and Lemma 8.2 with f (X) = (X, R) where R Z p

Chosen Ciphertext Security

We now show that security holds against chosen ciphertext (Definition 8.5). For this we only need to show that the queries will not help the adversary, and then conclude with semantic security. The key point is that the decapsulation oracle to which the adversary has access will answer with overwhelming probability if the ciphertext are not made 'honestly'. Since once the key is fixed and the random oracle called with it the encapsulation procedure is deterministic, the adversary can simulate it easily. Proof. There are two cases, either the random oracle was called on the answer of a query to the decapsulation mechanism, or it was not (ie. the adversary tries 'malicious' queries).

-If the adversary queries Decaps with a ciphertext, and receives K, which was previously queried to the random oracle, then simulation is trivial. -The probability of the second event is Pr

[K ← Decaps(C Adv)] = Pr[Enc(Dec(C)) • pk + H(K) = C Adv] ≤ ( n w
) since it requires guessing the random oracle response. The second event is therefore negligible.

Attacks on the Underlying Assumption

Due to the similarity with AJPS, it is natural to discuss the attacks that are most efficient against it, and to measure to what extent such attacks apply to our new construction.

Lattice Attacks

As with other versions of Mersenne encryption the attack presented in Chapter 7 is also applicable here and has an experimental cost of finding the right partitions for the low Hamming weight. We then set w = λ.

Brute Force Attacks

A brute force exhaustion of sk is always possible, and takes an effort of ( n-1 w-1 ). Thus the bare minimum requirement for security is that this quantity exceeds 2 λ 8.5.2.3 Meet-in-the-Middle Attacks

The key result of de Boer et al. is backed by [BDJW17, Lemma 3.1], which assumes that F has constant small Hamming weigth w. Without this assumption, the likelihood that a locality-sensitive hash function H is "good" for g does not have a lower bound, so that the meet-in-the-middle attack is no longer guaranteed to succeed. We can compare simulations from [BDJW17, Appendix A.1] with the same experiment on our scheme, which shows that de Boer et al.'s Heuristic 3.2, which is reasonable against AJPS-1, does not hold for our scheme.

Conclusion

Altough our scheme is vulnerable to the same attacks as AJPS, it is simpler in the sense that we do not need two ciphertexts. We hoped that the size of the random R would have twart our lattice attack. This is not the case experimentally, but since the analysis of our attack is not complete, there is still hope that our scheme is of interest. We also think that it is simpler to analyse our assumption than AJPS's.

Part IV FA I L B E T T E R

Abstract

The provably secure Schnorr signature scheme is popular and efficient. However, each signature requires a fresh modular exponentiation, which is typically a costly operation. As the increased uptake in connected devices revives the interest in resource-constrained signature algorithms, we introduce a variant of Schnorr signatures that mutualises exponentiation efforts.

Combined with precomputation techniques (which would not yield as interesting results for the original Schnorr algorithm), we can amortise the cost of exponentiation over several signatures: these signatures share the same nonce. Sharing a nonce is a deadly blow to Schnorr signatures, but is not a security concern for our variant, dubbed ReSchnorr.

ReSchnorr is provably secure, asymptotically-faster than Schnorr when combined to efficient precomputation techniques, and experimentally 2 to 6 times faster than Schnorr for the same number of signatures when using 1 MB of static storage. This is joint work with Marc Beunardeau, Rémi Geraud, David Naccache, and Damien Vergnaud. This work was accepted at the 22 nd European Symposium on Research in Computer Security, ESORICS 2017, Oslo (Norway) and published as [BCGNV17].

R E U S I N G N O N C E S I N S C H N O R R S I G N AT U R E S

introduction

The increased popularity of lightweight implementations invigorates the interest in resource-preserving protocols. Interestingly, this line of research was popular in the late 1980's, when smart-cards started performing public-key cryptographic operations (e.g. [FS87]). Back then, cryptoprocessors were expensive and cumbersome, and the research community started looking for astute ways to identify and sign with scarce resources.

In this work we revisit a popular signature algorithm published by Schnorr in 1989 [Sch90] and seek to lower its computational requirements assuming that the signer is permitted to maintain some read-only memory. This storage allows for time-memory trade-offs, which are usually not very profitable for typical Schnorr parameters.

We introduce a new signature scheme, ReSchnorr, which is provably secure in the random oracle model (ROM) under the assumption that the partial discrete logarithm problem (see below) is intractable. This scheme can benefit much more from precomputation techniques, which results in faster signatures.

Implementation results confirm the benefits of this approach when combining efficient precomputation techniques, when enough static memory is available (of the order of 250 couples of the form (x, g x )). We provide comparisons with Schnorr for several parameters and pre-computation schemes.

Intuition. The Schnorr signature algorithm uses a large prime modulus p and a smaller prime modulus q dividing p -1. The security of the signature scheme relies on the discrete logarithm problem in a subgroup of order q of the multiplicative group of the finite field Z p (with q | p -1). Usually the prime p is chosen to be large enough to resist index-calculus methods for solving the discrete-log problem (e.g. 3072 bits for a 128-bit security level), while q is large enough to resist the square-root algorithms [START_REF] Shanks | Class number, a theory of factorization, and genera[END_REF] (e.g. 256 bits for 128-bit security level).

The intuition behind our construction is to consider a prime p such that p -1 has several different factors q i large enough to resist these birthday attacks, i.e. p = 1 + 2 ∏ i=1 q i 111 then several "orthogonal" Schnorr signatures can share the same commitment component r = g k mod p. This is not the case with standard Schnorr signatures where, if a k is reused then the secret signing key is revealed.

It remains to decide how r can be computed quickly. In the original Schnorr protocol k is sampled uniformly at random from Z q . However, to be secure, our construction requires that k is chosen from the larger set Z p-1 . which means that a much higher effort is required to compute r. Here we cut corners by generating an r with precomputation techniques which allow an exponentiation to be sublinear. The trick is that once the exponentiation is sub-linear, we are more effective in our setting than in the original Schnorr setting.

We start by reminding how the original Schnorr signature scheme works and explain our extension assuming that k is randomly drawn from Z p-1 . We then present applications of our construction, by comparing several pre-processing schemes.

schnorr signatures

Schnorr signatures [START_REF] Schnorr | Efficient Identification and Signatures for Smart Cards[END_REF] are an offspring ElGamal signatures [START_REF] Elgamal | On Computing Logarithms Over Finite Fields[END_REF] which are provably secure in the Random Oracle Model under the assumed hardness of solving generic instances of the Discrete Logarithm Problem (DLP) [START_REF] Pointcheval | Security Proofs for Signature Schemes[END_REF]. For convenience, we restate the definition from Chapter 2 for ease of comparison here. Schnorr Syntax. The Schnorr signature scheme is a tuple of algorithms defined as follows:

-Setup(1 λ ): Large primes p, q are chosen, such that q ≥ 2 λ and p -1 = 0 mod q. A cyclic group G ⊂ Z p of prime order q is chosen, in which it is assumed that the DLP is hard, along with a generator g ∈ G. A hash function H : {0, 1} * → G is chosen. Public parameters are pp = (p, q, g, G, H).

-Gen(pp): Pick an integer x uniformly at random from [2, q -1] as the signing key sk, and publish y ← g x as the public key pk.

-Sign(pp, sk, M): Pick k uniformly at random in Z * q , compute r ← g k mod q, e ← H(M, r), and s ← kex mod q. Output σ ← {r, s} as a signature.

-Verify(pp, pk, M, σ): Let (r, s) ← σ, compute e ← H(M, r) and return True if g s y e = r, and False otherwise.

Schnorr Security. We recall the strong1 EUF-CMA security notion: A signature scheme Σ is secure against existential forgeries in a chosenmessage attack (strongly EUF-CMA-secure) if the advantage of any

Game EUF-CMA A Σ (λ): (sk, pk) Gen(1 λ ) (M * , σ * ) ← A Sign(•),Verify(•,•),H(•) (1 λ ) if (M * , σ * ) ∈ L return Verify(pk, M * ) return ⊥ Sign(M): σ Sign(sk, M) L ← L ∪ {M, σ} return σ
Verify(M, σ): return Verify(pk, M, σ) PPT adversary A against the EUF-CMA game defined in Figure 9.1 is negligible:

Adv euf-cma Σ,A (λ) = Pr EF A Σ (λ) = 1 ∈ Negl(λ)

reschnorr signatures

Our construction relies on using a prime p of the form mentioned in the introduction. This is not a trivial change, and requires care as we discuss below.

Technically, our construction is a stateful signature scheme (see e.g. [KL07, Chapter 12]), in which we simultaneously sign only one message and keep a state corresponding to the values k, g k and the index i for the current prime number. However, it is more compact and convenient to describe it as a signature for simultaneous messages.

ReSchnorr signature scheme. Similar to the Schnorr signature scheme, Reschnorr is a tuple of algorithms (Setup, Gen, Sign, and Verify), which we define as follows:

-Setup(1 λ ): Generate primes q 1 , . . . , q of size ≥ 2 λ and groups G 1 , . . . , G respectively of order q 1 , . . . q such that the DLP is hard in the respective G i , and such that p = 1 + 2 ∏ q i is prime. This is easily achieved by selecting ( -1) primes q i and varying the last one until p is prime. Choose a cryptographic hash function H : {0, 1} * → {0, 1} q 1 . The hash function will be used to produce elements of Z q i . For this we will denote by H i the composition of H and a conversion function from {0, 1} q 1 to Z q i2 Finally, choose g a generator of the group Z * p of order p -1. The public parameters are therefore pp = p, {q i } i=1 , H, g, {G i } i=1 .

-Gen(pp): The signer chooses x Z * p-1 and computes y ← g x mod p. The key sk = x is kept private to the signer, while the verification key pk = y is made public.

-Sign(pp, sk, m 1 , . . . , m ): The signer chooses k Z p , such that k = 0 mod q i for all i, and computes r ← g k mod p. The signer can now sign the messages m i as:

ρ i {0, 1} λ , e i ← H i (m i , r, ρ i )
, and s i ← ke i x mod q i outputting the signatures σ i = {r, s i , ρ i }-or, in a more compact form, σ = {r, s 1 , . . . , s , ρ 1 , . . . , ρ }.

-Verify(pp, pk, m i , (r, s i , ρ i ), i) : Verifying a signature is achieved by slightly modifying the original Schnorr scheme: First check that s i ∈ {0, . . . q i -1} and compute e i ← H i (m i , r, ρ i ), then observe that for a correct signature 3 :

(g s i y e i )

p-1

q i = r p-1 q i mod p.
The signature is valid if and only if this equality holds, otherwise the signature is invalid (see Section 9.3).

Remark. Note that unlike Schnorr, in the Sign algorithm we add a random ρ i for a signature to make the argument of the hash function unpredictable. This will be useful for the proof of Theorem 9.1 in the ROM.

Remark. Note also that one almost recovers the original Schnorr construction for = 1-the only differences being in the verification formula, where both sides are squared in our version, and the addition of a fresh random to hash.

ReSchnorr correctness. The ReSchnorr signature scheme is correct.

Proof. Let g, y, r, s i , and ρ i be as generated by the Gen and Sign algorithms for a given message m i . We check that, (g s i y e i ) s i r p-1 q i = 1 mod p.

By the definition of s i , there exists λ ∈ Z such that g s i = g k-e i x+λq i , hence g s i y e i g -k = g λq i mod p.

Raising this to the power of p-1 q i we get g λ(p-1) = 1 since the order the multiplicative group Z * p is p -1.

One can note,

p-1

q i = 2q 1 • • • q i-1 q i+1 • • • q .
Reschnorr Security.

To aid in the proof of security, we introduce the following problem which we call the partial discrete logarithm problem (PDLP). Intuitively it corresponds to solving a discrete logarithm problem in the subgroup of our choice. PDLP. Let ≥ 2 be an integer, q 1 , . . . , q distinct prime numbers and q = q 1 . . . q . Let G be a group of order q and g a generator of G. Given g, q, q 1 , . . . , q l , and y = g x , the partial discrete logarithm problem (PDLP) consists in finding i ∈ [ ] and x i ∈ Z q i such that x i = x mod q i .

In our context, we are chiefly interested in a subgroup of order q of a multiplicative group of a finite field Z * p , where q divides p -1ideally, q = (p -1)/2. The best known algorithms to solve the PDLP are index-calculus based methods in Z * p and square-root algorithms in subgroups of prime order q i for some i ∈ [ ]. With p of bit-size 3072, q = (p -1)/2, = 12 and q 1 , . . . , q of bit-size 256, we conjecture that solving the PDLP requires about 2 128 elementary operations. In Section 9.3.1, we provide security argument in the generic group model on the intractability of the PDLP for large enough prime numbers q 1 , . . . , q .

Theorem 9.1 (Existential unforgeability). ReSchnorr is provably EUF-CMAsecure assuming the hardness of solving the PDLP, in the ROM.

To prove this result, we will exhibit a reduction from an efficient EUF-CMA forger to an efficient PDLP solver. To that end we first show a sequence of indistinguishability results between the output distributions of -Our signature algorithm Sign = Sign 0 on user inputs.

-A modified algorithm Sign 1 (see Figure 9.2), where the hash of user inputs is replaced by a random value. This situation is computationally indistinguishable from the previous one in the ROM. -A modified algorithm Sign 2 (see Figure 9.2), that has no access to the signing key x. The output distribution of this algorithm is identical to the output of Sign 1 (Theorem 9.2). Then we use the forking lemma [PS00; BN06] to show that an efficient EUF-CMA-adversary against Sign 2 can be used to construct an efficient PDLP solver. Finally we leverage the above series of indistinguishably results to use an adversary against Sign 0 . Let CRT (for Chinese Remainder Theorem) be the isomorphism that maps

Z q 1 × • • • × Z q × Z 2 to Z p-1 .
Theorem 9.2. The output distributions of Sign 1 and Sign 2 are identical.

Proof. This theorem builds on several intermediate results described in ??. We denote δ the output distribution of Sign 1 and δ the output distribution of Sign 2 . The structure of the proof is the following:

Sign 1 : ρ {0, 1} λ k Z p \ i=1 {q i , 2q i , . . . , p -1} r ← g k mod p for i = 1 to : e i Z q i s i ← k -e i x mod q i ρ i
{0, 1} λ return (r, e 1 , . . . , e , s 1 , . . . , s , ρ 1 . . . , ρ ) Theorem 9.3 shows that the output of Sign 2 is a subset of the output of Sign 1 .

Sign 2 : for i = 1 to e i Z q i s i Z q i ρ i {0, 1} λ a {0, 1} b {0, 1} S ← CRT(s 1 , . . . , s , a) E ← CRT(e 1 , . . . , e , b) r ← g S y E for i = 1 to if r = 1 mod q i ,
Theorem 9.4 shows that in Sign 1 there is a unique random tape per output.

Theorem 9.5 shows that in Sign 2 there are exactly two random tapes per output.

Theorem 9.7 shows that there are twice as many random tapes possible for Sign 2 than for Sign 1 This demonstrates that by uniformly choosing the random tape, the resulting distributions for Sign 1 and Sign 2 are identical, which is the uniform distribution on the set of valid signatures.

Lemma 9.3. Every tuple of δ is a valid signature tuple. Therefore δ ⊆ δ.

Proof. Let (r, e 1 , . . . , e , s 1 , . . . , s , ρ 1 , . . . , ρ ) ∈ δ . Let i ∈ [ ]. By the Chinese Remainder Theorem we have: S = s i mod q i and E = e i mod q i . So there exists λ, µ ∈ Z such that S = s i + λq i and E = e i + µq i .

Hence:

r p-1 q i = g S y E
p-1 q i = g s i +λq i y e i +µq i p-1 q i = (g s i y e i )

p-1 q i g λ(p-1) y µ(p-1) = (g s i y e i )

p-1 q i

The last equality holds since the order of the multiplicative group Z * p is p -1, and this concludes the proof with the fact that r = 1 mod q i . Lemma 9.4. There is exactly one random tape upon which Sign 1 can run to yield each particular tuple of δ. of Theorem 9.4. Let k, e 1 , . . . , e , ρ 1 , . . . , ρ and k , e 1 , . . . , e , ρ 1 , . . . , ρ be random choices of δ that both yield (r, e 1 , . . . , e , s 1 , . . . , s , ρ 1 , . . . , ρ ). It is immediate that e i = e i and ρ i = ρ i for all i ∈ [ ]. Also since g k = g k , g is of order p -1 and since k and k are in [p] then k = k . Lemma 9.5. There are exactly two random tapes over k, ρ 1 , . . . , ρ , e 1 , . . . , e that output each tuple of δ .

Proof. Let e 1 , . . . , e , s 1 , . . . , s , a, b, ρ 1 , . . . , ρ and e 1 , . . . , e , s 1 , . . . , s , a , b , ρ 1 , . . . , ρ be random choices that both give (r, e 1 , . . . , e , s 1 , . . . , s , ρ 1 , . . . , ρ ). It is immediate that e i = e i , s i = s i , and

ρ i = ρ i for all i ∈ [ ].
Let S, S , E, and E be the corresponding CRT images. We have g S y E = g S y E , which is g S+xE = g S +xE , and S + xE = S + xE mod (p -1). Since x is odd (it is invertible mod p -1), it follows that S + E and S + E have the same parity. Therefore a + b = a + b mod 2 and we have two choices: a = b, or a = 1 -b, both of which are correct.

Lemma 9.6. # Z p \ i=1 {q i , 2q i , . . . , p -1} = 2 ∏ i=1 (q i -1).
Proof. The number of invertible elements mod p is ∏ i=1 (q i -1) × (2 -1) so the number of invertible mod q i for all i (and not necessarily for 2) is 2 ∏ i=1 (q i -1). This is exactly the cardinality of the set Z p \ i=1 {q i , 2q i , . . . , p -1} , Lemma 9.7. There are twice as many possible random choices in δ as there are in δ.

Proof. For the number of random choices in δ we use Theorem 9.6 to count the number of k and then count the number of e i and get 2 ∏ i=1 (q i -1) × ∏ i=1 q i . For δ , having r = 1 mod q i is equivalent to having s i = -e i x. Therefore it has the same number of random choices as a distribution picking the s i from Z q i \ {e i x} which is

∏ i=1 q i × ∏ i=1 (q i -1) × 2 × 2.
It follows from the above results that the two distributions are the same, i.e. the uniform distribution over the set of valid signatures. This concludes the proof of Theorem 9.2. The algorithm R aborts in four possible ways during the simulation (denoted ( ), ( †), ( ‡) and ( §)) in ??. We upper-bound the probability of these events in the following list:

-( ) This occurs with negligible probability since the ρ is a fresh random which is unpredictable by the adversary. -( †) This occurs with non overwhelming probability since the adversary is efficient. -( ‡) The element is in the list with non negligible probability because if the adversary forges on an unqueried hash in the ROM, it has a negligible chance to succeed. -( §) This happens with non overwhelming probability due to the forking lemma [START_REF] Pointcheval | Security Arguments for Digital Signatures and Blind Signatures[END_REF].

Proofs in the generic group model provide heuristic evidence of some problem hardness when an attacker does not take advantage of group elements' encoding. However, they do not necessarily say anything about the difficulty of specific problems in a concrete group.

Let be some non-negative integers, let q 1 , . . . , q be some distinct prime numbers and let q = q 1 • • • q . We consider a cyclic group G of (composite) order q generated by g. We assume without loss of generality that q 1 = max(q 1 , . . . , q ). A classical method [START_REF] Pohlig | An improved algorithm for computing logarithms over GF(p) and its cryptographic significance[END_REF] to solve the partial discrete logarithm problem in G given h = g x ∈ G is to compute h q 2 •••q , an element of order diving q 1 (that belongs to the subgroup generated by g q 2 •••q ) and to compute its discrete logarithm x 1 in base g q 2 •••q using a square root method such as Shanks "baby-step giant-step" algorithm [START_REF] Shanks | Class number, a theory of factorization, and genera[END_REF]. It is easy to see that x 1 is equal to x mod q 1 and is obtained within time complexity O( √ q 1 + log(q 2 • • • q )) group operations.

Our goal is to prove that this time complexity is essentially optimal in the generic group model. Let A be a generic group adversary that solves the partial discrete logarithm problem in G. As usual, the generic group model is implemented by choosing a random encoding σ : G -→ {0, 1} m . Instead of working directly with group elements, A takes as input their image under σ. This way, all A can test is string equality. A is also given access to an oracle computing group multiplication and division: taking σ(g 1 ) and σ(g 2 ) and returning σ(g 1 • g 2 ) and σ(g 1 /g 2 ) respectively. Finally, we can assume that A submits to the oracle only encodings of elements it had previously received. This is because we can choose m large enough so that the probability of choosing a string that is also in the image of σ is negligible.

Theorem 9.9. Let A be a generic algorithm that takes as input two encodings σ(g) and σ(h) (where g is a generator of G and h = g x ∈ G) and makes at most τ group oracle queries, then A's advantage in outputting a partial discrete logarithm (i, x i ) with i ∈ {1, . . . , } and x i = x mod q i is upperbounded by O(τ 2 /q 1 ).

Proof. We consider an algorithm B playing the following game with A. Algorithm B picks two bit strings σ 1 , σ 2 uniformly at random in {0, 1} m . Internally, B keeps track of the encoded elements using elements in the ring

Z q 1 [X 1 ] × • • • × Z q [X ].
To maintain consistency with the bit strings given to A, B creates a lists L of pairs (F, σ) where F is a polynomial vector in the ring

Z q 1 [X 1 ] × • • • × Z q [X ]
and σ ∈ {0, 1} m is the encoding of a group element. The polynomial vector F represents the exponent of the encoded element in the group

Z q 1 × • • • × Z q . Initially, L is set to {((1, 1, . . . , 1), σ 1 ) , ((X 1 , . . . , X n ), σ 2 )}
Algorithm B starts the game providing A with σ 1 and σ 2 . The simulation of the group operations oracle goes as follows: group operation: Given two encodings σ i and σ j in L, B recovers the corresponding vectors F i and F j and computes F i + F j for multiplication (or F i -F j for division) termwise. If F i + F j (or F i -F j ) is already in L, B returns to A the corresponding bit string; otherwise it returns a uniform element σ R ← -{0, 1} m and stores (F i + F j , σ) (or (F i -F j , σ)) in L.

After A queried the oracles, it outputs a pair (i * , x * i ) ∈ {1 . . . , } × Z q i * as a candidate for the partial discrete logarithm of h in base g. At this point, B chooses uniform random values x 1 , . . . ,

x n ∈ Z q 1 × • • • × Z q . The algorithm B sets X i = x i for i ∈ {1, . . . , n}.
If the simulation provided by B is consistent, it reveals nothing about (x 1 , . . . , x ). This means that the probability of A guessing the correct value for (i * , x * i ) ∈ {1, . . . , } × Z q i * is 1/q i * . The only way in which the simulation could be inconsistent is if, after we choose value for x 1 , . . . , x n , two different polynomial vectors in L happen to produce the same value.

It remains to compute the probability of a collision happening due to a unlucky choice of values. In other words, we have to bound the probability that two distinct vectors F i , F j in L evaluate to the same value after the substitution, namely F i (x 1 , . . . , x n ) -F j (x 1 , . . . , x n ) = 0. This reduces to bound the probability of hitting a zero of F i -F j . By the simulation, this happens only if F i -F j is a vector of polynomials where at least one coordinate -say the k-th -is a non-constant polynomial (and thus of degree one) denoted (F i -F j ) (k) .

Recall that the Schwartz-Zippel lemma says that, if F is a degree d polynomial in Z q k [X k ] and S ⊆ Z q k then Pr[F(x k ) = 0 mod q k ] ≤ d

|S|

where x k is chosen uniformly from S. Going back to our case, we obtain by applying the Schwartz-Zippel lemma :

Pr[(F i -F j ) (k) (x k ) = 0 ∈ Z q k ] ≤ 1/q k ≤ 1/q 1 .
Therefore, the probability that the simulation provided by B is inconsistent is upper-bounded by τ(τ -1)/q 1 (by the union bound) and the result follows.

provably secure pre-computations

Often the bottleneck in implementations centers around modular exponentiation. In this section we briefly outline several proposed pre-computation techniques, as well as presenting in more detail two pre-computation schemes which were used in our implementation to compare timings between classical Schnorr and ReSchnorr.

Brief overview

The problem of computing modular exponentiations is well-known to implementers of both DLP-based and RSA-based cryptosystems. In the specific case that we want to compute g x mod p, the following strategies have been proposed but their security is often heuristic:

-Use signed expansions (only applicable to groups where inversion is efficient); -Use Frobenius expansions or the GLV/GLS method (only applicable to certain elliptic curves); -Batch exponentiations together, as suggested by M'Raïhi and Naccache [START_REF] David | Batch Exponentiation: A Fast DLP-Based Signature Generation Strategy[END_REF]. The above approaches work for arbitrary values of x. Alternatively, one may choose a particular value of x with certain properties which make computation faster; however there is a possibility that doing so weakens the DLP:

-

The E-BPV Pre-Computation Scheme

E-BPV 4 relies on pre-computing and storing a set of pairs (k i , g k i mod p); then a "random" pair (r, g r mod p) is generated by choosing a subset of the k i , setting r to be their sum, and computing the corresponding exponential by multiplying the g k i mod p. x j [h -1] r ← r + k j x j mod φ(p) R ← R • K x j j mod p return (r, R)

Figure 9.6 -The E-BPV algorithm for generating random pairs (x, g x mod p). The BPV algorithm is a special case of E-BPV for h = 2.

To guarantee an acceptable level of security, and resist lattice reduction attacks, the number n of precomputed pairs must be sufficiently large; and enough pairs must be used to generate a new couple.

Nguyen et al. [START_REF] Phong | Distribution of modular sums and the security of the server aided exponentiation[END_REF] showed that using E-BPV instead of standard exponentiation gives an adversary an advantage bounded by m K

( n k )(h -1) k
with m the number of signature queries by the adversary, (k, n, h) E-BPV parameters, and K the exponent's size. 5 We fix conservatively m = 2 128 . For ReSchnorr, at 128-bit security, we have K = P = 3072. As suggested in [START_REF] Phong | Distribution of modular sums and the security of the server aided exponentiation[END_REF] we set n = k, and constrain our memory:

h k ≥ 2 3400
Optimizing 2k + h under this constraint, we find (h, k) = (176, 455). This corresponds to 1087 modular multiplications, i.e., an amortized cost of 90 multiplications per signature, for about 170 kB of storage. Alternatively, we can satisfy the security constraints by setting n = 2048, h = 100, k = 320, which corresponds to about 770 kB of storage, giving an amortized cost of 62 modular multiplications per signature.

In the implementation (Section 9.5), we solve the constrained optimisation problem to find the best coefficients (i.e., the least number of multiplications) for a given memory capacity.

Remark.

To achieve the claimed bounds on modular multiplications, one should not compute R ← K x j j mod p directly; rather, an efficient speedup due to Brickell et al. [START_REF] Brickell | Fast Exponentiation with Precomputation (Extended Abstract)[END_REF] (BGMW) may be used. To illustrate the importance of this remark, we also give timings for a "naive" implementation in Table 9.3. 5. For Schnorr, the exponent's size is Q; for ReSchnorr, it is P.

Halving storage cost

The following idea can halve the amount of storage required for the couples (x, g x ): instead of drawing the values x at random, we draw a master secret s once, and compute x i+1 ← g x i ⊕ s (or, more generally/securely, a PRF with low complexity x i+1 = PRF s (g x i )). Only s, x 0 , and the values g x i need to be stored; instead of all the couples (x i , g x i ). This remark applies to both BPV and E-BPV.

Lim and Lee Pre-Computation Scheme

We also consider a variation on Lim and Lee's fast exponentiation algorithm [START_REF] Hoon | More Flexible Exponentiation with Precomputation[END_REF]. Their scheme originally computes g r for r known in advance, but it is easily adapted to the setting where r is constructed on the fly. The speed-up is only linear, however, which ultimately means we cannot expect a sizable advantage over Schnorr. Nevertheless, Lim and Lee's algorithm is less resource-intensive and can be used in situations where no secure E-BPV parameters can be found (e.g., in ultra-low memory settings).

The Lim-Lee scheme (LL) has two parameters, h and v. In the original LL algorithm, the exponent is known in advance, but it is easily modified to generate an exponent on the fly. Intuitively, it consists in splitting the exponent in a "blocks" of size h, and dividing further each block in b sub-blocks of size v. The number of modular multiplications (in the worst case) is a + b -2, and we have to store (2 h -1)v pairs. The algorithms are given in Figure 9.7.

For a given amount of memory M, it is easy to solve the constrained optimization problem, and we find

h opt = 1 ln(2) 1 + W 1 + M e
where W is the Lambert function. For a memory M of 750 kB, this gives h ≈ 8.6. The optimal parameters for integers are h = 9 and v = 4. 6

Remark. For LL, Figure 9.4.2 on halving storage requirements does not apply, as x need not be stored.

A summary of the properties for the pre-computations techniques E-PBV and LL can be found in Table 9.1.

implementation results

Reschnorr, using the algorithms described in ??, has been implemented in C using the GMP library. In the interest of timing comparison we have also implemented the classical Schnorr scheme. The 6. In practice, it turns out that h = v = 8 performs slightly better, due to various implementation speed-ups possible in this situation LimLee.Preprocessing(h, v): g 0 ← g for i = 0 to h -1 g i ← g 2 a i-1

for i = 0 to 2 h -1 let i = e h-1 . . . e 1 in binary g 0,i = g e h-1 h-1 . . . g e 1 1 for i = 0 to 2 h -1 for j = 0 to v -1 g j,i ← g 2 b j-1,i L ← L ∪ {g j,i } return L LimLee.GetRandomPair: R ←1 r ← 0 for i = b -1 to 0 R ← R 2 r ← r + r for j = v -1 to 0 r i,j {0, . . . , 2 h -1} R ← R × g j,r i,j r ← r + r i,j return (r, R) results for several scenarios are outlined in Table 9.2 (at 128-bit security) and Table 9.3 (at 192-bit security). Complete source code and timing framework are available upon request from the authors.

These experiments show that ReSchnorr is faster than Schnorr when at least 250 pairs (i.e., 750 kB at 128-bit security) have been precomputed. This effect is even more markedly visible at higher security levels: ReSchnorr benefits more, and more effectively, from the E-BPV+BGMW optimisation as compared to Schnorr. The importance of combining E-BPV and BGMW is also visible: E-BPV using naive exponentiation does not provide any speed-up.

Schnorr and ReSchnorr achieve identical performance when using Lim and Lee's optimisation, confirming the theoretical analysis. When less than 1 MB of memory is alloted, this is the better choice.

Heuristic Security

Several papers describe server-aided precomputation techniques (e.g., [START_REF] Sabir | Efficient and verifiable algorithms for secure outsourcing of cryptographic computations[END_REF]), which perform exponentiations with the help of a (possibly untrusted) server, i.e., such techniques allow to outsource the computation of g x mod n, with public g and n, without revealing x to the server. Interestingly, the most efficient algorithms in that scenario (which of course we could leverage) use parameters provided by Hohenberger and Lysyanskaya [START_REF] Hohenberger | How to Securely Outsource Cryptographic Computations[END_REF] for E-BPV. A series of papers took these parameters for granted (including [START_REF] Sabir | Efficient and verifiable algorithms for secure outsourcing of cryptographic computations[END_REF]), but we should point out that these are not covered by the security proof found in [START_REF] Phong | Distribution of modular sums and the security of the server aided exponentiation[END_REF].

Despite this remark, it seems that no practical attack is known either; therefore if we are willing to relax our security expectations somewhat it is possible to compute the modular exponentiation faster. Namely, a Q-bit exponent can be computed in O(log Q 2 ) modular multiplications.

ReSchnorr uses an exponent that is times bigger than Schnorr, which is amortized over signatures. Comparing ReSchnorr to Schnorr, the ratio is log(Q) 2 (log Q) 2 . With Q = 256 we get a ratio of approximately 5.7.

Note that as Q increases, so does , and therefore so does the advantage of ReSchnorr over Schnorr in that regime.

Reduction-Friendly Moduli

As part of computing g k mod p, a very costly operation is the reduction mod p. An interesting question is whether some particular moduli p can be found, for which reduction is particularly easy.

An example of such moduli are those that start with a 1 followed by many 0.

Example 9.1. For P = 3072 and Q = 256, using (in hexadecimal notation) ∆ i = {12d, 165, 1e7, 247, 2f5, 31b, 327, 34f, 3a3, 439, 56b, 4fe7} and q i = 2 Q + ∆ i , we have that p equals: where [x] denotes a sequence of x hexadecimal zeros.

conclusion

We have introduced a new digital signature scheme variant of Schnorr signatures, that reuses the nonce component for several signatures. Doing so does not jeopardise the scheme's security; attempting to do the same with classical Schnorr signatures would immediately reveal the signing key. However the main appeal of our approach is that precomputation techniques, whose benefits can only be seen for large enough problems, become applicable and interesting. As a result, without loss of security, it becomes possible to sign messages using fewer modular multiplications. Let us continue our historical stroll before it comes time to conclude, for now, and put the pen down.

the teenage years of modern cryptography

The year is 2019. Since you started your journey, there have been even more shocks to the system. You have learned of Cambridge Analytica and their ilk, which made you become increasingly worried about the state of democracy. Digital advertising is the new religion, social networks the sacred spaces, and influencers the prophets. You see that choice, decision, information, only partially reside in the hands of the individual. You've seen the rise of voice-, and facialrecognition software fueling the surveillance state. You've seen this move so quickly, with monumental mistakes, and you worry, because it seems that there are very few who even notice. And you still can't send an encrypted email! It's chaos.

Yet, at the same time, you see digital currency and its supporters I refuse to write the word 'crypto' pertaining to anything other than cryptography in this thesis.

unanimously wanting anonymity. You see messengers gaining popularity and think maybe you don't actually need encrypted email. Maybe there are other ways to communicate. Maybe there are other ways to compute. You catch machine learning and cryptography's eyes meeting across the room. The lawyers and engineers start to hold hands. You're growing up! It's confusing now, and you're left with more questions than you ever thought possible, but don't worry. This is a period of change, a moment of growth. You will understand more when you're older, but for now, my dear, let's sit down, and think about where we should go from here.

10.2 open problems 10.2.1 Key-Correlated Security

One of the greatest lessons learned while working towards the idea of key-correlated attacks was that although related key attacks and key-dependent message attacks have been widely studied, and even the idea of key-dependent messages encrypted under related keys has been mentioned, there are a number of subtleties that went unnoticed for many years. Furthermore, although KCA does not seem very

The most notable obstacle was solved by the xkcd property :) different to RKA + KDM, there were many interesting obstacles that needed to be overcome when trying to deduce the proofs. This work really displayed the richness that can be found in cryptography, and teaches the lesson that we should not content ourselves with following only intuition, more digging is often needed. As such, we named the part 'Try Again'. The advent of a new security notion can open a multitude of directions to follow. We aimed to address as many as possible in the work carried out in Part II, but there are still a number of questions to be addressed: analysis of feistel construction. In Chapter 5 we looked at the KCA-security of blockciphers and showed that 3-rounds of Even-Mansour are sufficient to achieve KCA-security for a class of functions. One could further extend this analysis by looking at other block cipher models. For example, how many rounds of Feistel are needed to ensure KCA-security.

analysis of modes of operation. Another direction would be to look at blockciphers in a broader context and ask whether any of the currently used modes of operation are secure under key-correlated attacks.

concrete constructions. As well as looking at the broader context, it would be interesting to know if the notion of key-correlated attacks aids in the cryptanalysis of concrete constructions, for example, of AES.

kcx. A small, but technical detail arose while thinking about keycorrelated security. Depending on the model, keys are XORed with functions in different ways. It would be interesting to extend the idea of key-correlated attacks to key-correlated XORing.

New Assumptions and PKE Schemes

Public-key encryption is fundamental in cryptography. It was noted several times that this is what caused the revolution in the 1970's. Today there remain very few PKE schemes, and the hunt to find more is still ongoing. Furthermore, as we move closer to having quantum computing as a reality, there is an urgency to find schemes that are resistant to quantum attacks. In 2017, [START_REF] Aggarwal | A New Public-Key Cryptosystem via Mersenne Numbers[END_REF] described such an encryption scheme. Furthermore, it was based on the hardness of a new assumption. This is doubly exciting because not only do we (potentially) have a new PKE scheme, we also have an entirely new toy from which we can start to think about building other schemes. Two new developments such as this will garner much attention from those wanting to try to break the new toys, but also from those who want to design new things. The work in Chapter 7 aimed at the former and tried to break the scheme. Given the parameters suggested in the original work, we managed to find the secret key, given only the public key, in only a number of days. The work in Chapter 8 aimed at the latter and proposed a modification to the assumption and described another public-key encryption scheme. Both of these works were quite reactionary and so did not perform very formal analysis. More formal analysis was carried out in [START_REF] Koen De Boer | Attacks on the AJPS Mersenne-Based Cryptosystem[END_REF] and eventually the AJPS cryptosystem was modified and published as [START_REF] Aggarwal | A New Public-Key Cryptosystem via Mersenne Numbers[END_REF]. This was an exciting time to work in the area and one of the main lessons learned was that even with careful consideration of cryptographic schemes, there can exist small 'tricks' that allow to exploit a particular feature. It was a nice reminder to a young researcher that although sometimes you may strike gold, more often than not, and over and over, you are going to 'fail again', and hence the title for this part. In any case, these initial analyses barely scratch the surface of the research opened up in this space, and there are a number of areas left to be addressed: more efficient attacks. The AJPS encryption scheme is not entirely dissimilar to NTRU constructions, so it would be interesting to see if more of the analysis performed on NTRU also applies to AJPS. In particular whether Lattice attacks and the Meet-in-the-Middle attacks can be combined to gain efficiency, as was done for NTRU. This is a question asked by Adi Shamir following the presentation of [BCGN17a].

quantum attacks. The scheme is supposed to be post-quantum secure. The analysis in [START_REF] Koen De Boer | Attacks on the AJPS Mersenne-Based Cryptosystem[END_REF] We saw with key-correlated security that working in very general models can lead to some security oversights. One of the most interesting points working towards the results in Part IV is that when we come out of the very general model and start to look at the specific construction, there can also be room for improvement. By taking advantage of the group structure and by choosing our primes in a particular way, we can gain efficiency. The greatest lesson learned here is that it is important to have a global view of how a primitive works, but there's also much to be gained by looking at the specifics Ok, there may have been some artistic license in the naming of these parts. . . and hence the naming of this part 'fail better'. can we generalise? 'Reusing nonces' as we did with Schnorr signatures can be thought of as somewhat similar to related key notions of security. An interesting question would be to ask whether we can retain some notion of security for Schnorr-like signature schemes where all inputs are related, or derived, or correlated.

more exploitation Are there other schemes in which we can look at the details, group structure or otherwise, and gain efficiency, or stronger security?

beyond the technicalities

There are so many big ideas, tiny intricacies, and alluring notions, that now, coming to the end of this thesis, I feel that I am only beginning to discover the beauty of this field. There are a number of changes that the field is experiencing at the moment. Cryptography is moving beyond the "all or nothing" paradigm it used to be known for; it is no longer the case that an adversary can learn nothing about a message. Actually, maybe to gain functionality, we're happy for them to learn a very controlled something. We're seeing the rise of homomorphic and functional encryption, of MPC, and all the ideas that allow us to compute on encrypted data. This opens a can of worms so that now, all of a sudden, we can 'peek' inside the ciphertext. There are huge implications of this for all manner of data analytics and machine learning. It begs the question of who do we allow to look at our ciphertexts? How can we enforce this?

And what of quantum computers? How will they affect us? Are we ready? Or even closer still, 5G there are attacks, right? But they're still going ahead with it? What about these digital currencies? Will they last? How about the community? Even this is changing. We're no longer just academics or military personnel. We're lawyers, engineers, social scientists, managers. There's a lot to look forward to, and still many questions to answer. A final remark. I have often been told that a popular question asked of PhD students when talking about a piece of scientific work, or research, is "How do you know when you're done?" I have thought about this a lot over the years and, being a PhD student, posed my answers as questions:

I quickly learned the first one is a very wrong answer

-"I'm done when.. I think I'm done?" -"When my advisor tells me I'm done?" -"When reviewer n • 2 has run out of stuff to complain about?" -"When it's 5:59 am on a Saturday morning and there's a deadline in 1 minute?" -"When the coffee machine breaks? Or when my laptop dies?" -"When am I done?!" If there is one thing I have learned throughout the course of this PhD, it's a definite answer to that question. Open your mind enough to an idea, and you'll never be done; for the things you truly think about, reward you with a lifetime of problems to solve, questions to ask, answers to twist, papers to write, books to read, students to te. . .

Figure 2 . 1 -

 21 Figure 2.1 -Illustration of the shortest-vector problem in a two-dimensional lattice.

  Figure 2.1 illustrates the SVP problem on a simple case.

  Dec : K × C → M ∪ {⊥} takes a key K, a ciphertext C, and returns either a plaintext M or the failure symbol ⊥ ∈ M. SE Correctness. Correctness requires that Dec(K, Enc(K, M)) = M for all values of the inputs above.

Figure 2

 2 Figure 2.2 -CPA and CCA experiments for a symmetric encryption scheme.

Figure 2

 2 Figure 2.3 -Left-or-right, and real-or-random indistinguishability games for a symmetric encryption scheme SE in the CCA-security model.

  Dec : K × C → M ∪ {⊥} takes a key K and a ciphertext C, and returns either a plaintext M or the failure symbol ⊥ ∈ M.

  takes a key K, a ciphertext C, and a nonce N, and returns either a plaintext M or the failure symbol ⊥ ∈ M.

Figure 2

 2 Figure 2.4 -Real-or-random indistinguishability games for an adversary playing against AE (left), nonce-based AEAD (middle), and MRAE (right).

3.

  Dec is the deterministic decryption algorithm which takes as input a secret key sk, a ciphertext C, and returns a message M ← Dec(sk, C). PKE Correctness. It is required that for all possible outputs (pk, sk) from Gen, and messages M, Dec(sk, Enc(pk, M)) = M.

Figure 2

 2 Figure2.5 -The EUF-CMA experiment for a digital signature scheme.

  3.2 related work RKA security. Knudsen and Biham [Knu93; Bih94b; Bih94a] initiated the study of RKAs and Bellare and Kohno [BK03] gave a theoretical treatment. High-profile RKAs on AES were discovered by Biryukov et al. [BKN09; BK09]. The RKA model was extended by Albrecht et al. [AFPW11] to account for attacks that depend on an ideal primitive [Har09; Ber10]. The RKA security of Feistel networks [BF15] and Even-Mansour ciphers [FP15; CS15] have been studied. Bellare, Cash, and Miller [BCM11] present a comprehensive treatment of RKA security for various cryptographic primitives. KDM security. Goldwasser and Micali [GM84] already hinted at the need for KDM security. The first use of KDM security appears in the work of Camenisch and Lyskanskaya [CL01] for anonymous credentials. Black, Rogaway, and Shrimpton [BRS03] formulated KDM security for symmetric encryption and proved its feasibility in the random-oracle model. Halevi and Krawczyk [HK07] later gave feasibility results in the standard model. Bellare and Keelveedhi

Figure 4

 4 Figure 4.1 -Game defining the (Ξ e , Ξ d )-KC-CCA security of a blockcipher BC = (E, D) with key space K and message space M. We require that ξ e ∈ Ξ e and ξ d ∈ Ξ d for all queries.

Figure 4

 4 Figure 4.4 -RKA-, and KDM-security games.

  the model If A has not stopped the simulation, it forwards B's output b .

Lemma 4. 4 .

 4 Consider game RK-CCA Φ,B BC with b fixed to 0 and define event E as follows: the adversary B makes two RKEnc queries (φ, M) and (φ , M), with φ = φ , both answered by the same C; or it makes two RKDec queries (φ, C), (φ , C), with φ = φ , both answered by the same M; or it makes two queries RKEnc(φ, M), answered by C and RKDec(φ , C), answered by M, with φ = φ .

  local list ML and since E(K * , •) is a permutation, each C uniquely determines the corresponding M, thus B's simulation is perfect. We thus have Adv kc-cca BC (Ξ e , Ξ d , A) = Adv kdm-cca BC (Ψ, B).

Figure 5 . 1 -

 51 Figure 5.1 -Game defining (Ξ e , Ξ d )-KC-CCA security of the ideal cipher with key length k and block length n.

Bad

  xkcd under KCEnc by a reduction to the multi-shot xkcd property by collecting all queries ξ e made to KCEnc and all query-answer pairs (ξ d , M) made to and received form KCDec in two lists and outputting them lists in the multi-shot xkcd game. The probability of setting of Bad xkcd under KCDec is analyzed analogously.

3.

  compute iD(K, C) to get M; 4. compute iE(K, M) to get C ; 5. return b := 1 if C = C and b := 0 otherwise.

Figure 6

 6 Figure 6.1 -KC-AE-security game for a symmetric encryption scheme SE.

  Figure 6.2 and Figure 6.3. The three games in Figure 6.2 run according to the KC-AE game with the HwN transform applied, and with b = 1. When b = 1, all oracle queries to KCEnc return encryptions of keyderived inputs under related keys. Queries to KCDec return the plaintext, or the error symbol ⊥ if the ciphertext is deemed illegitimate. The three games in Figure 6.3 run according to the KC-AE game with the HwN transform applied, and with b = 0. In this scenario, all oracle queries to KCEnc return random ciphertexts, and KCDec always returns the error symbol ⊥. All games, adversaries, and transitions are outlined below.

Figure 7

 7 Figure 7.1 -Illustration of balanced and correct partitions of strings with low Hamming weight.

  Figure 7.2 -Deriving the attack's random tape from a verifiable source in a deterministic way, as well as the keys.

Figure 7

 7 Figure 7.3 -The key generation procedure Gen(pp) for Mersenne-based encryption.

  Recovering F and G from H

8.3. 3

 3 Aggarwal-Joux-Prakash-Santha with Error Correction (AJPS-ECC) To thwart the effect of the above attacks, Aggarwal et al. proposed a new version of their cryptosystem.

8. 4

 4 the projected-mersenne cryptosystem 8.4.1 The Projected-Mersenne assumption We introduce the following problem: Projected-Mersenne Low Hamming Ratio Search Problem. Let p = 2 n -1 be a Mersenne prime. Given n, w, d ∈ N, M = 2 d -1, and h∈ Z p , find f , g ∈ Z p such that 1. g = w 2. f ∧ M = 13. f /g = h mod p under the promise that such a couple exists.

  Figure 8.2 -An illustration of the structure in D, as used in our Dec algorithm.

  and 8.2: n ≤ a + 2d and a + bn < c < b Assuming an ECC is given with block length d, we can choose the following parameters, which correspond to maximising a: a = n -2d and b {0, . . . , n} and c = bd mod p.

  8.5.1.1 Semantic Security of the Key Encapsulation Mechanism Theorem 8.1. [Semantic Security] Our KEM is semantically secure (Definition 8.5) under the a-Projected-Mersenne Assumption (Definition 8.4.1), with a as defined in Figure 8.1.

Theorem 8. 7 .

 7 [Semantic Security under Chosen Ciphertext Attack] Our KEM is semantically secure under chosen ciphertext attack (Definition 8.5) under the a-Projected-Mersenne Assumption (Definition 8.4.1), with a as defined in Figure 8.1.

Figure 9 . 1 -

 91 Figure 9.1 -The strong EUF-CMA experiment for digital signature schemes.

  Figure 9.2 -The algorithms used in Theorem 9.2, as part of the proof of Theorem 9.1 (ReSchnorr signatures are EUF-CMA).

  Choose x with low Hamming weight as proposed by Agnew et al. [AMOV91]; -Choose x to be a random Frobenius expansion of low Hamming weight, as discussed by Galbraith [Gal12, Sec. 11.3]; -Choose x to be given by a random addition chain, as proposed by Schroeppel et al. [SOOS95]; -Choose x to be a product of low Hamming weight integers as suggested by Hoffstein and Silverman [HS03]-broken by Cheon and Kim [CK08]; -Choose x to be a small random element in GLV representationbroken by Aranha et al. [AFGKTZ14]; Finally, a third branch of research uses large amounts of pre-computation to generate random pairs (x, g x mod p). The first effort in this direction was Schnorr's [Sch90], quickly broken by de Rooij [de 97]. Other constructions are due to Brickell et al. [BGMW93], Lim and Lee [LL94], and de Rooij [de 95]. The first provably secure solution is due to Boyko et al. [BPV98], henceforth BPV, which was extended and made more precise by [NSS01; CMT01; NS99]. This refined algorithm is called E-BPV (extended BPV).

(

  E-)BPV.Preprocessing: k 1 , . . . , k n Z * p for j ∈ [n] L ← L ∪ {(k j , K j = g k j mod p)} return L E-BPV.GetRandomPair: pick S ⊆ [n] s.t. |S| = k (d i , D i ) D r ← 0 R ← 1 for j ∈ S

Figure 9

 9 Figure9.7 -The LL algorithm for generating random pairs (x, g x mod p).

2

  [60]e0e8[56]18058164[53]1479d1e16e8[51]aa09581f139be[48]3 a9dc2e99b080dd[47]dfe705c4e9b3a45678[43]25a378c4e6b62835f4 01[42]471d330fbde56ef2c80281e[39]5c5388621a308a5425f007648 [37]4e506ba1a5b68dc5faca1155e64[35]270051399124b193e6716e0 8b4408[34]8a07b85ed815e7eac1135861bd67e3

  They say you can tell a lot about a person by the company they keep. You know me now, and you know that I am not the most 'company' type of person. Yet, you (probably singlehandedly) have made me grow to love the industry. Literally every single time we speak you are full of excitement and encouragement even on the most stressful days. It's quite amazing, and you're a force to be reckoned with. You have helped me achieve more than I ever thought possible, for which I'm super appreciative. Here's to the future, and to realising all those projects we've dreamed about :) To Marc. I don't know what to say to Marc that I haven't already said

	If I had to estimate,
	I'd say I've talk more
	to Marc, than
	everyone else
	combined, during
	my time in Paris.

Thanks for being there always. xiv To Michel Léger.

  . I can't give you thanks. I can't give you an acknowledgement. I can't give you so many things. The best I can do, in this chaotic world and point in time, is to hold your hand, and give you hope. An

	xx	contents	contents	xxi
	4.4 Key-Correlated Attacks 8.5.2 Attacks on the Underlying Assumption 104 42 Figure 7.1 Illustration of balanced and correct partitions
	4.4.1 A generic separation result 8.5.3 Conclusion 105 of strings with low Hamming weight.	42 86
	Alors, pa'lante, Pooya jan. 21 2.6.3 Authenticated Encryption with Associated Data C O N T E N T S List of Figures xxii List of Tables xxiii I prologue 1 introduction 3 1.1 The Birth of Modern Cryptography 3 1.2 Contributions of this Thesis 5 1.2.1 Try Again 5 1.2.2 Fail Again 6 1.2.3 Fail Better 6 2 preliminaries 9 2.1 Provable Security 9 2.2 Hard Problems 10 2.2.1 One-way Functions 11 2.2.2 Integer Factorisation 11 2.2.3 Discrete Logarithms 12 2.2.4 Lattice Based Problems 12 2.3 Idealised Models of Computation 13 2.4 Notation 14 2.5 Symmetric Cryptography 15 2.5.1 Blockciphers 16 2.5.2 Symmetric Encryption 17 2.6 Security Notions for Encryption 18 2.6.1 Authenticated Encryption 19 2.6.2 Nonce-Based Authenticated Encryption 22 2.7 Public-Key Cryptography 23 2.7.1 Key Exchange 23 2.7.2 Public Key Encryption 24 2.7.3 Key Encapsulation Mechanisms 25 2.8 Digital Signatures 26 2.8.1 Concrete Signature Schemes 27 II try again 3 key correlated security 33 3.1 Motivation 33 3.2 Related Work 34 3.3 Contributions 35 4 the model 39 4.1 Concept and Definitions 39 4.2 Examples 39 4.3 Relation with RKA and KDM 40 4.4.2 Attack on 2-round Even-Mansour 43 4.5 Relation between KCA, RKA, and KDM 43 4.5.1 KC(RK-only) ⇔ RK 44 4.5.2 KC(KDM-only) ⇔ KDM 49 5 kca-secure blockciphers 53 5.1 KCA security of the ideal cipher 53 5.2 KCA Security of 3-Round Even-Mansour 63 6 kca-secure symmetric encryption 69 6.1 KC-AE security 69 6.2 The Hash-with-Nonce Transform 70 6.3 KCA security of HwN 71 6.4 The reductions 74 6.5 Multi-User to Single-User Reduction for AE 76 III fail again 7 on the hardness of the mersenne low hamming ratio assumption 83 7.1 Introduction 83 7.2 Outline of the Analysis 84 7.2.1 Using LLL to Spread Information 84 7.2.2 Partition and Try 84 7.3 Putting it Together 87 7.3.1 Recovering F and G from H 89 7.3.2 Predicting the Total Execution Time 90 7.4 Conclusion 91 8 public-key cryptosystems based on a new com-plexity assumption 93 8.1 Introduction 93 8.2 Preliminaries 93 8.3.4 Ferradi-Naccache (AJPS-FN-BT) 97 8.4.2 Projected-Mersenne Encryption 98 8.4.4 Semantic Security 100 8.5.1 Security Analysis 101 77 on a multi-user AE adversary A. 8.5 Key Encapsiation Mechanism 100 77 Figure 6.7 Adversary B in the single-user AE game based an encryption under K i otherwise. 8.4.3 Correctness 99 Figure 6.6 which returns random values when i ≤ j and Game j (with 0 ≤ j ≤ n) showing MUAE game 8.4.1 The Projected-Mersenne assumption 97 76 SE. 8.4 The Projected-Mersenne Cryptosystem 97 Figure 6.5 Game MUAE A security of a authenticated encryption scheme AE defining the multi-user AE-rection (AJPS-ECC) 96 75 reduction. 8.3.3 Aggarwal-Joux-Prakash-Santha with Error Cor-Figure 6.4 Code of the adversaries in the KC-AE to MUAE tem (AJPS-1) 94 Figure 6.3 73 KC-AE to SE reduction with b = 0. 8.3.2 The Aggarwal-Joux-Prakash-Santha Cryptosys-Figure 6.2 72 KC-AE to SE reduction with b = 1. tion 94 70 tion scheme SE. 8.3.1 The Mersenne Low Hamming Ratio Assump-Figure 6.1 KC-AE-security game for a symmetric encryp-8.3 Prior Work 94 IV fail better 9 reusing nonces in schnorr signatures 111 9.1 Introduction 111 9.2 Schnorr Signatures 112 9.3 ReSchnorr Signatures 113 9.3.1 Generic Security of the Partial Discrete Loga-rithm Problem 119 9.4 Provably Secure Pre-Computations 121 9.4.1 Brief overview 122 9.4.2 The E-BPV Pre-Computation Scheme 122 9.4.3 Lim and Lee Pre-Computation Scheme 124 9.5 Implementation Results 124 9.5.1 Heuristic Security 125 9.5.2 Reduction-Friendly Moduli 127 9.6 Conclusion 127 V epilogue 10 conclusion 131 10.1 The Teenage Years of Modern Cryptography 131 10.2 Open Problems 131 10.2.1 Key-Correlated Security 131 10.2.2 New Assumptions and PKE Schemes 132 10.2.3 Efficient Signature Schemes 133 10.3 Beyond the Technicalities 134 Figure 7.2 Deriving the attack's random tape from a veri-fiable source in a deterministic way, as well as bibliography L I S T O F F I G U R E S Figure 2.1 88 the keys. Illustration of the shortest-vector problem in a Figure 7.3 The key generation procedure Gen(pp) for Mersenne-two-dimensional lattice. 12 Figure 2.2 88 based encryption. CPA and CCA experiments for a symmetric Figure 8.1 An illustration of the structure in F, as used in encryption scheme. 19 Figure 2.3 99 our Gen algorithm. Left-or-right, and real-or-random indistinguisha-Figure 8.2 An illustration of the structure in D, as used in bility games for a symmetric encryption scheme 99 our Dec algorithm. SE in the CCA-security model. 20 Figure 2.4 Figure 9.1 The strong EUF-CMA experiment for digital sig-Real-or-random indistinguishability games for nature schemes. 113 an adversary playing against AE, nonce-based Figure 9.2 The algorithms used in Theorem 9.2, as part of AEAD, and MRAE. 23 Figure 2.5 the proof of Theorem 9.1 (ReSchnorr signatures The EUF-CMA experiment for a digital signa-are EUF-CMA). 116 ture scheme. 27 Figure 4.1 Figure 9.3 An efficient EUF-CMA adversary A against ReSchnorr, with random oracle H and a signing oracle O. 118 Game defining the (Ξ 59 Figure 9.4
		xviii xxii	xix

e , Ξ d )-KC-CCA security of a blockcipher BC = (E, D) with key space K and message space M. We require that ξ e ∈ Ξ e and ξ d ∈ Ξ d for all queries. 40 Figure 4.2 Blockcipher (E , D ) that is both KDM-secure and RKA-secure secure but not KCA-secure. 42 Figure 4.3 The r-round iterated Even-Mansour cipher. 43 Figure 4.4 RKA-, and KDM-security games. 44 Figure 5.1 Game defining (Ξ e , Ξ d )-KC-CCA security of the ideal cipher with key length k and block length n. 54 Figure 5.2 Game 0 , Game 1 , and Game 2 used to prove the KCA-security of the ideal cipher. 58 Figure 5.3 Game 3 , Game 4 , and Game 5 used to prove the KCA-security of the ideal cipher. efficient solver R for the PDLP, using a polynomial number of queries to A. 118 Figure 9.5 An efficient solver for the PDLP, constructed from an efficient EUF-CMA adversary against ReSchnorr. 119 Figure 9.6

Table 8

 8

	.1	Synoptic comparison of NTRU and AJPS-1.	95
	Table 9.1	Precomputation/online computation trade-offs
		for ReSchnorr. 125
	Table 9.2	Timing results for Schnorr and ReSchnorr, at
		128-bit security (P = 3072, Q = 256). 126
	Table 9.3	Timing results for Schnorr and ReSchnorr, at
		192-bit security (P = 7680, Q = 384). 126

xxiii Part I

  You need a key. Deciding to keep it simple, you press 'A', a rotor turns, you take some paper and write 'K'.

	Press 'B', write 'Q'. Press 'C', write 'G'. Again, press 'A', then 'B',
	then 'C'. Write 'R, N, J'. Next, you can begin communication, press
	'W', write 'D' and continue; press E, T, T, E, R, B, E, R, I, C, H, T,

write OAJKXTQHETTI. You have your message. Move to your radio and transmit KQGRNJDOAJKXTQHETTI. . . and you've sent your first encrypted text. Does the thought ever arise in your mind as to whether or not it is dishonest to scramble your message? You do this for the sake of national security, for strategy in time of war, for your nation. You need ask no questions; this is your duty.

We jump to 1970. The height of the post-war, Golden Age of Capitalism. Electronic fund transfers (EFTs) are rampant and the number of issued credit cards surpasses 1 million in the United States. The world's economy is booming. Life is sweet.

It's 1977. Recovering from the 73-75 recession you are more skeptical about EFTs. Data protection laws surrounding the collection of payment information are passed. You need more secure systems and welcome the development of DES

[START_REF]Federal Information Processing Standards[END_REF]

. But to use it is not straightforward. What was once an instrument solely used for military advantage, encryption is now commercially required due to post-recession insecurities and the growth of electronic and computing industries, and is permissioned only via the licensing of your IP.

Let's move to 1991. You possess your own Personal Computer.

  the inequality uses Pr[E 0 ] ≤ by Lemma 4.4; and the second to last equality follows from B's behavior in case of E happening, thus Pr[RK 0 |E 0 ] = 0 and Pr[RK 1 |E 1 ] = 1. This concludes this direction of the proof.4.5.2 KC(KDM-only) ⇔ KDM Proposition 4.5. Let BC be a blockcipher. Let Ξ e and Ξ d be two KDM-only CDF sets with Ξ e = {id} × Ψ and Ξ d = {id} × Γ. Then for every adversary A there exists an adversary B such that

Table 8 .

 8 1 -Synoptic comparison of NTRU and AJPS-1.

	NTRU [HPS98]	AJPS-1 [AJPS17a]

  Figure 8.1 -An illustration of the structure in F, as used in our Gen algorithm.

		n bits n -a bits		A central region of size n -a contains
	F =	random	random	only a single set bit. Note that this
		b bits	c bits	figure and the following are not to scale, we give
				concrete
				parameters later.
			mod p

  Figure 9.3 -An efficient EUF-CMA adversary A against ReSchnorr, with random oracle H and a signing oracle O.Figure 9.4 -An efficient solver R for the PDLP, using a polynomial number of queries to A.

			O sign
	R implements the random oracle as R.H and the signing oracle as R.Sign. The rewinded adversary and	pp, pk g x , g, p, q 1 , . . . , q	A H R.Sign R.H i R.Init R.H i R.Sign	A R.Fin m R A	x i , i
	oracles are
	indicated with a
	prime symbol.

* , r * , s * , ρ * , i Theorem 9.8 (Security under Chosen Message Attack). An efficient attacker against Sign 2 can be turned into an efficient PDLP solver in the ROM.

Proof. Let A be an attacker that wins the EUF-CMA game for ReSchnorr, illustrated in Figure

9

.3. We construct in ?? an algorithm R that uses A to solve the PDLP. A is equivalent to A (with the same random tape which we omit in the notation), the difference being that it interacts with different oracles. Abusing notation we denote by R.H i the composition of the hash function and the conversion function. If L is a list of pairs, we denote by L -1 [e] the index of the element e in the list, and by L[i] the i-th element of the list. If they cannot (i.e. if e is not in the list, or the list does not have an i-th element) they abort.

Table 9 .

 9 1 -Precomputation/online computation trade-offs for ReSchnorr.

	Algorithm	Storage	Multiplications		Security
	Square-and-multiply	0	1.5 log P		Always
	BPV [BPV98] E-BPV [NSS01] Lim and Lee [LL94]	nP nP 2 h × v × P	k -1 2k + h -3 log P h (1 + 1 v ) -3	m	m P ( n k ) < 2 -λ P ( n k )(h-1) k < 2 -λ Always

Table 9 .

 9 2 -Timing results for Schnorr and ReSchnorr, at 128-bit security (P = 3072, Q = 256). Computation was performed on an ArchLinux single-core 32-bit virtual machine with 128 MB RAM. Averaged over 256 runs.

	Scheme	Storage	Time (/sig.)
	Schnorr	-	35.2 ms
	Schnorr + [LL94]	715 kB	508 ns
	Schnorr + [NSS01] + [BGMW93]	750 kB	2.08 ms
	Schnorr + [NSS01] + [BGMW93]	1.87 MB	1.62 ms
	Schnorr + [LL94]	1.87 MB	476 ns
	ReSchnorr	-	33.0 ms
	ReSchnorr + [LL94]	715 kB	486 ns
	ReSchnorr + [LL94]	1.87 MB	467 ns
	ReSchnorr + [NSS01] + [BGMW93]	1.87 MB	263 ns

Table 9 .

 9 3 -Timing results for Schnorr and ReSchnorr, at 192-bit security (P = 7680, Q = 384). Computation was performed on an ArchLinux single-core 32-bit virtual machine with 128 MB RAM. Averaged over 256 runs.

  looked at methods based on Grover's algorithm, but leave open the question of whether less generic approaches would work better. other schemes. Given a new hardness assumption, what other primitives can be build from it? As we saw with the DL and RSA problems, can we build signature schemes to provide integrity with such an assumption? 10.2.3 Efficient Signature Schemes

Claw-freeness can be modified to key-claw-freeness across encryption and decryption so that cross-key-claw-freeness is automatic. But in this case the reach of our feasibility results do not extend to the KDM setting since under KDM keys always collide.

Consistently, the attack in[START_REF] Bellare | Authenticated and Misuse-Resistant Encryption of Key-Dependent Data[END_REF] exploits claws in the key-dependent headers.

KCA security does not imply security against fault attacks in general.

Single-shot adversary B runs any given multi-shot A to obtain two lists, picks one entry at random from each list and outputs the pair. Then the success probability of B is at least 1/( 1 2 ) times that of A.

Please do not confuse this notion with the (popular :) web-comic xkcd.com.

The above cases take care of collisions between wires (1/2, 3), (1/2, 4) in the picture above.

Bernstein et al.[START_REF] Daniel | NTRU Prime[END_REF] argue against the use of such rings for NTRU.

If ECC is a linear code, then w 2 ≤ dk + 1, or in other terms, k ≤ dw 2 + 1. Therefore, η = d.

In fact, the noise considered here is additive, and may result in more than w 2 bits being affected due to the carry. We may choose a stronger error correction capacity to account for such unlikely events.

We omit the the carry's influence to simplify analysis: we only need a bound.

In contrast to the weak version, the adversary is allowed to forge for a message that they have queried before, provided that their forgery is not an oracle response.

This conversion function can read the string as a binary number and reduce it modq i for example.

BPV is a special case of E-BPV where h = 2. As such they share the same precomputing step.

A iE,iD,KCEnc,KCDec return (b = 1)

and Game 2 used to prove the KCA-security of the ideal cipher. unpredictability game. Moreover, and similarly to the RKA case, the set Ξ is claw-free iff Ψ is. Once again, this is because KDM-only CDFs do not modify the key component and hence any claw must be on the message part. For the xckd property, given ((id, ψ 1 ), C, (id, C 2 ), M, i), algorithm Det needs to check (1) if id(K) = id(K), which always holds; and (2) if C 2 = C when i = 1 or if ψ 1 (K) = M when i = 2. The first of these is trivially checkable. For the second, two cases could occur: either ψ 1 (K) is a constant function mapping to M 1 , in which case Det can easily check if M 1 = M; or ψ 1 is non-constant. However, since Ψ contains all constant functions, ψ 1 and M can be used to break claw-freeness. Hence in this case Det rejects. So similarly to the RKA setting, claw-freeness implies xckd. KCA security. We now show that the reach of the above feasibility result for the ideal cipher extends beyond RKA and KDM security. Suppose k = n and recall the set

This set captures related keys that are computed as offsets, keyindependent messages when α = 0, and key-dependent messages which are offsets of the key when α = 1. We identify functions in this set with tuples (∆ 1 , ∆ 2 , α).

This set is key-unpredictable with single-shot advantage at most 1/2 n , since xor-ing with ∆ 1 acts as a permutation and K remains information-theoretically hidden. It is also claw-free with single-shot advantage at most 1/2 n : If the offsets ∆ 1 and ∆ 1 for two functions ξ, ξ are different, there are no claws. If they are the same, and α = α , then a claw also implies ∆ 2 = ∆ 2 , making the two functions identical. So α = α is necessary for claws, in which case the functions collide on a random key with probability 1/2 n .

The set is also xkcd with single-shot advantage 2/2 n with respect to the following detector (recall that Det(ξ e , C,

If Det ⊕ returns "Yes", then both the key components and the ciphertext components collide; the answer is thus correct. Suppose it returns "No". If ∆ e 1 = ∆ d 1 , the key components do not collide and the answer is correct. Suppose

Again, since K * is information-theoretically hidden, this can only happen with probability 1/2 n . In case (b) outputs of $ + collide with probability 1/2 n for each pair of queries.

on the same point. This event is analyzed analogously to case ($ + , $ + ) above.

($ + , P- 3 ) Calls ξ e = (∆ e 1 , ∆ e 2 , α e ) to KCEnc and

3 on an input matching an output of $ + ; or in (b) querying P-3 on an input whose output matches an input of $ + . Let C be the reply to query ξ e . Then the value chosen by

Thus case (a) would happen if

If

1 , which leads to guessing K * and happens with probability at most 1/2 n . On the other hand, if α d = 0, we would have that

But for such queries either P-3 is sampled to be consistent with $ + (or it is not called at all when Det ⊕ returns "Yes"). Let us now look at case (b), which would happen if

was directly queried to P - 3 , an inconsistency of type ($ + , P ±

3 ) arises, which we dealt with above. On the other hand, it could be that this value was never queried to

P -

3 . If the KCEnc query comes before KCDec and the inputs are distinct-colliding inputs was case (a) above-P-3 chooses a random value, which collides with the input to $ + with probability at most 1/(2 nq). Suppose now that the KCEnc query comes after KCDec. Suppose the input to KCEnc is ξ e = (∆ e 1 , ∆ e 2 , α e ). The value computed as input to $ + is independent of the output of P-3 unless P + 1 is kept consistent with $ -(since otherwise P 1 and P 2 are independent of P-3 ). If independent, collisions happen with probability at most 1/(2 nq). Otherwise, dependency implies that M ⊕ ∆ d 1 = ∆ e 1 ⊕ ∆ e 2 where M is the output of KCDec. This

Game 0 shows the KC-AE game with respect to SE and challenge bit 1.

Game 1 separates the lists for H and H . There are no functional changes.

Game 2 then fully decouples H and H .

in Game 0 and event Bad prepares us to fully decouple H and H later:

Game 2 is identical to Game 1 up to the point that Bad is set. If this event occurs within H , records are no longer returned. By the fundamental lemma of game playing [START_REF] Bellare | The Security of Triple Encryption and a Framework for Code-Based Game-Playing Proofs[END_REF], we bound the difference between Game 2 and Game 1 as

Event Bad corresponds to a non-empty intersection between the two lists L and L . Below, we will bound Pr[Bad] in Game 1 by showing that (1) this probability is close to the probability of setting Bad in Game 2 down to the MUAE security of SE; and

(2) the probability of setting Bad in Game 2 is small down to the key unpredictability of Ξ e and Ξ d . Game 3 switches the challenge bit to b = 0. We show below that any adversarial advantage in distinguishing Game 2 and Game 3 can be converted, via an adversary B 1 , against the MUAE game:

Game 4 reverses the change in Game 2 and merges random oracles H and H . We have that Pr

where we choose Game 3 to analyze the probability of Bad. Below we construct adversaries to show that this probability is bounded above by the key-unpredictability advantages against Ξ e and Ξ d .

Game 5 is identical to Game 4 except for a reversal of the conceptual change seen between Game 0 and Game 1 . The random oracles are completely re-coupled, and all queries by A, KCEnc and KCDec are written to a single list L. There are no procedural changes in this game:

runs A similarly to algorithm B 1 . It however keeps track of the queried functions to KCEnc and KCDec as well as H. It uses its knowledge of K * to verify if Bad has occurred. When the MUAE challenge bit of B 2 is 1, algorithm B 2 runs A in an environment identical to that of Game 2 ; hence the probability of B 2 outputting 0 is exactly that of Bad in Game 2 . Similarly, the probability of B 2 outputting 1 is exactly that of Bad occurring in Game 3 . Hence

The theorem follows by putting the bounds established above together, and noting that

In the theorem statement, we choose B to be B 1 or B 2 having the bigger advantage.

Adversary B Init,Enc,Dec Remark. The above theorem can be extended to a misuse-resilient and key-correlated setting, whereby nonces may be repeated at encryption for a construction similar to HwN that also hashes the header

AE defining the multi-user AE-security of a authenticated encryption scheme SE. information. A similar proof strategy can be used to analyse its KC-MRAE security at the expense of introducing three extra conditions:

(1) the base scheme is MRAE secure; (2) the sets Ξ e and Ξ d are clawfree; and (3) (Ξ e , Ξ d ) is xkcd so that illegal decryption queries can be detected.

multi-user to single-user reduction for ae

This may not seem very important, and you may wonder why it is included, but this is the first reduction I ever wrote, and for that reason, it's super important to me :)

For convenience, the KC-AE to AE proof was shown in the multiuser setting. Here we show how to further reduce from multi-user to single user AE.

Multi-user security. We define the MUAE-security of an authenticated encryption scheme SE = (Gen, Enc, Dec) by considering the game described in Figure 6.5. The MUAE advantage of an adversary A against an MUAE game is defined by

Note that nonces may not be repeated for each user in Enc.

Theorem 6.2. Let SE be an authenticated encryption scheme. Then for any adversary A attacking the MUAE-security of SE while making at most n queries to Init, there exist AE adversaries B 1 , . . . , B n such that

Proof. The proof proceeds via a standard hybrid argument. We start by defining a sequence of games Game j (for 0 ≤ j < n) as shown in Figure 6.6. Game j runs similarly to the MUAE game except that if i (the index of the key) is less than or equal to j, then ciphertext C is randomly generated. For i > j, the encryption algorithm is used under key K i . Thus Game 0 is identical to the MUAE game with b = 1 and Game n is identical to the MUAE game with b = 0.

showing MUAE game which returns random values when i ≤ j and an encryption under K i otherwise.

Let A be any adversary in the MUAE game. To bound the advantage of A, note that

Thus, for j = 0, . . . , n -1 it remains to bound

To this end, we will rely on the underlying security of SE.

Claim 6.3. For any j, and for any adversary A, there exists a B j such that

The key observation is that in Game j , for the first j keys queried, j uniform strings are returned as the ciphertext and for the remaining keys, nj encryptions are returned. In Game j+1 , j + 1 uniform strings and nj -1 encryptions are returned. Leveraging this difference of one real encryption at the j + 1 position, we can construct an AE adversary B j to emulate the environment of an MUAE adversary A to break the single user AE security. Adversary B j works as follows. In the AE game that B j is playing, if the challenge bit b = 1, adversary A's view of the environment is identical to Game j . If B j 's challenge bit b = 0, A's view is identical to Game j+1 . When A outputs R.Init(y = g x , g, p, q 1 , . . . , q ):

(r, e 1 , . . . , e , s 1 , . . . , s , ρ 1 , . . . , ρ ) δ if ∃h s.t. ((M, r mod q 1 , ρ 1 ), h) ∈ L abort

((M, r mod q j , ρ j ), h) ∈ L abort L ← L ∪ {(M, r mod q j , ρ j ), e j } j ← j + 1 mod return (s j , r, ρ j , j) Σ ← Σ ∪ {(s j , r, ρ j , j)} If R does not abort, then g s * y e * p-1 q i * = (r * )

p-1 q i * = g s * y ẽ * p-1 q i * mod p. Then s * + e * x = s * + ẽ * mod q i * . It follows that the value returned by R is equal to x mod q i * . R succeeds with non negligible probability, as explained earlier. The probability of forking is polynomial in the number of queries to the random oracle, the number of queries to the signature oracle, and . Note that the reduction is times looser than [START_REF] Pointcheval | Security Arguments for Digital Signatures and Blind Signatures[END_REF]. This concludes the proof of Theorem 9.8. of Theorem 9.1. Using Theorem 9.2, we can use Sign 0 instead of Sign 2 as a target for the attacker in Theorem 9.8.

Generic Security of the Partial Discrete Logarithm Problem

In this section, we prove that the partial discrete logarithm problem introduced in Section 9.3 is intractable in the generic group model. This model was introduced by Shoup [Sho97] for measuring the exact difficulty of solving classical discrete logarithm problems. Algorithms in generic groups do not exploit any properties of the encodings of group elements. They can access group elements only via a random encoding algorithm that encodes group elements as random bit-strings.

RÉSUMÉ

Cette thèse présente des résultats nouveaux portant sur trois domaines fondamentaux de la cryptographie : les propriétés de sécurité, les hypothèses cryptographiques, et l'efficacité algorithmique. La première partie s'intéresse à la sécurité des primitives symétriques. Nous introduisons une nouvelle propriété de sécurité correspondant à la plus forte sécurité pour les primitives symétriques prouvées sûres dans le modèle de l'oracle aléatoire. Les attaques par clé corrélées capturent les scénarios dans lesquels toutes les entrées (clés, messages, et éventuellement nonces et en-têtes) sont corrélées avec avec la clé secrète. Sous des hypothèses relativement faibles nous prouvons la sécurité contre les attaques par clé corrélées pour les algorithmes de chiffrement par bloc, et montrons que trois tours d'Even-Mansour sont nécessaires pour cela. Nous étendons ensuite les attaques par clés corrélées au chiffrement authentifié basé sur les nonces, et fournissons une transformation en boîte noire qui, partant d'un chiffrement authentifié à utilisateurs multiples, donne un chiffrement authentifié démontré résistant aux attaques par clés corrélés dans le modèle de l'oracle aléatoire. Nous établissons les relations et séparations avec les notions déjà existantes (sécurité contre les attaques par clés apparentées et par message dépendant de la clé) pour montrer que la sécurité contre les attaques par clé corrélés est strictement plus forte, et implique les autres. La partie suivante porte sur la cryptographie à clé publique, et analyse les hypothèses sous-jacentes au nouveau cryptosystème introduit dans AJPS17. La cryptanalyse de cette hypothèse, reposant sur l'arithmétique modulo un premier de Mersenne, nous permet de reconstruire la clé secrète à partir de la clé publique uniquement. Nous proposons alors une variante de ce sytème à clé publique, fondée sur une modification de l'hypothèse précédente, résistant aux attaques connues (classiques et quantiques). La dernière partie aborde l'efficacité algorithmique du schéma de signature de Schnorr. En mettant à profit la structure de groupe nous pouvons tirer parti du nonce pour produire un lot de signatures. Combinant ceci avec des méthodes de précalcul nous permet de rendre plus efficace l'algorithme de signature de Schnorr . La sécurité est préservée sous une hypothèse nouvelle, dont on montre qu'elle est vraie dans le modèle du groupe générique.

MOTS CLÉS

Cryptographie Symétrique, Cryptographie Asymétrique, Signatures Numériques, Preuve de sécurité, Cryptanalyse.

ABSTRACT

This thesis presents new results addressing three fundamental areas of cryptography: security notions, assumptions, and efficiency. The first part encompasses the security of symmetric primitives. We give a new security notion that provides the strongest security for symmetric primitives proven in the random oracle model (ROM). Key-correlated attacks (KCA) model the scenario where all inputs (keys, messages, and possibly nonces and headers) are correlated with the secret key. Under mild assumptions, we prove KCA security of blockciphers, and show that 3-rounds of Even-Mansour are necessary to achieve this. Then, we define a KCA-security notion for nonce-based authenticated encryption (AE), and provide a black-box transformation that turns a multiuser-secure AE into an AE scheme that is provably KCA secure in the ROM. We show relations and separations with older notions (related-key and key-dependent message security) to show that security under KCA is strictly stronger, and implies the others. The next part turns to public-key cryptography, and analyses the assumptions underlying the new public-key cryptosystem of AJPS17. Cryptanalysis of their assumption, based on arithmetic modulo a Mersenne prime, allowed us to reconstruct the secret key, given only the public key. Based on a modified version of the assumption, we propose a variant post-quantum secure public-key cryptosystem. The last part turns to efficiency, and studies the Schnorr Signature scheme. Exploiting the group structure we can generate multiple nonces (instead of just one) with which we can then generate a batch of signatures. This, together with some preprocessing tricks, allow us to increase efficiency of Schnorr signature generation. Security is maintained under a new assumption shown intractable in the Generic Group Model.

KEYWORDS

Symmetric Cryptography, Public-key Cryptography, Digital Signatures, Provable Security, Cryptanalysis.