Efficient Fuzzy Extraction of PUF Induced Secrets  Theory and Applications
Dank je, chairman. Allow me to introduce the names of the co-authors. Dat is Dawu Hu, Ingrid Verbouwede, Mathias Hiller en Mandeljou. So this work is about puff-based key generation or also physical extraction. And for this problem, there is a default solution or a default architecture available. So suppose we have an embedded device, this embedded device is an integrated circuit. And this IC will house a Puff. So the puff will produce a device-unique fingerprint similar to human biometrics. So for this purpose, the puff will produce thousands of bits, thousands of response bits. And these bits are noisy and non-uniform. And in the end, we want to have a secret key that is, for instance, a 128-bit key that is stable and uniform. So we need to solve two problems. One is a noisiness and two is non-uniformity. So to do that, we need some additional digital logic in between and that is referred to as a fuzzy extractor. So the fuzzy extractor consists of two steps. First, there is the error correction. So here we get rid of the noisiness problem. So the secure sketch is the building block to do that and it relies on an error correcting code. And it will also need some public helper data. So we have thousands of public helper bits that are available to the attacker. So the attacker has read access to these bits. And then finally we end up with a stable secret but it is still non-uniform. So the second step of the fuzzy extractor is a hash function. So here we basically downsize the secret so that we go from non-uniform to uniform. And now the question that we address is can we make this default architecture more efficient? So without making any changes to the design of this architecture, can we make it more efficient? And more efficient here means that we use less puff bits and also less helper data bits. And because we have left less puff bits and less helper data bits, it also means that the secure sketch has to process less data and also the hash has to process less data. So that is the main question that we address here. So now we go to the presentation outline. So first some preliminaries. First about the puff and then about the secure sketch.  So in this presentation we mainly cover the secure sketch. And in the paper there is an extensive tier apart, actually more than half of the paper, where we derive tight bounds on the secure sketch min entropy loss. And it are these bounds that are responsible for the savings in implementation overhead. We have to make an apology here because we only do a brief introduction of the theory. Because the theory is formula based and in order to explain it properly we would need more time than we have. So what we do instead here is we focus on the applications of the theory. And we hope that these applications may spark your interest to also take a look at the theory in a more convenient written form. So the first obvious application of the theory is to reduce the implementation overhead of the fusie extractor. So we use less puff bits and less helper data bits without chasing anything to the architecture. But there are other applications. In general, the theory is useful to analyze various error correction methods for puffs. So one application is that we can show that there is a flaw in the security proof of the reverse fusie extractor. The reverse fusie extractor does a special mode of operation over the fusie extractor. And third, we provide proper motivation for the biasing schemes because we think this was a bit missing in the original proposals. And for these two last applications, here we put two papers from the last chess edition in a somewhat different spotlight. So we have now the preliminaries. So this work applies to array-based puffs which can be informally referred to as the copy-based puffs. So what we do, we have an array of identical cells and each cell will produce exactly one bit. So to design a puff like that, you just design one cell and then you copy paste it in your layout. So we have thousands of cells that produce the device unique identifier and later this is post-processed better into a secret key. So examples of puff architecture that comply with this array-based structure are the memory-based puffs, for instance the SRAM puff, the DRAM puff, which is covered in the next presentation. Also the D-flip-flop puff applies to this context. There is also a ring-holiciter base design that match the criteria.  Also the coating puff, not included are arbiter puffs and variations. So we have two issues that need to be resolved to use the puff identifier as a secret key. One is the noisiness, so there is a bit error rate between 1% and 20% with respect to a reference response of the puff. A second, there are non-ineformities and for array-based puffs, there are two predominant non-ineformities. One is bias, so it can be the case that there are more ones and zeros or vice versa. And the other predominant imperfection are spatial correlations, implying that neighbouring cells influence each other. So in this example bit string, it is a case that the neighbouring bits tend to have the same value. So we are still at the preliminaries and now the secure sketch because this is the main focus of our theory. So the secure sketch relies on an error-acting code and most frequently this will be an NKT block code. So we have a message which is K-bit en this message is encoded into a code word having N-bit. An N is larger than K, so there is a certain redundancy building. And because of this redundancy, we can decode a corrupted code word again into the original message as long as the number of errors is not exceeding T. So various secure sketch constructions rely on an error-correcting code, on an NKT block code. However, these constructions will also publish helper data. Helper data, which is available to the attacker. So because the helper data is published, there is a loss in minentropy because the attacker gains some information. So on the left we have the entropy at the input, which is represented here with a thermometer scale. So the fraction in red is the minentropy at the input. And then on the right we have the minentropy at the output taking into account that the attacker observes the helper data. So there is a drop in minentropy. En when implementing a Pufbevski generator on an embedded device, system providers will always rely on the N minus K upper bound on the minentropy loss. So given the minentropy at the input, if we subtract N minus K, that is an upper bound on the loss. As visualized here, however, this upper bound is in many cases overly conservative.  So we have more minentropy left dan de bounds indicates. En dit is een inefficiëncie. Dus de goal van dit werk is om het meer efficiënt te maken. Dus om nieuwe bounds te drijven. Dus we drijven tieter, lower en upper bounds op de minentropy los. Dus dit is indiceerd in red hier. En met deze bounds kunnen we de Pufbevski generator meer efficiënt maken. Het is ook belangrijk te mention dat deze bounds te makkelijk zijn om te evalueren. Dus het is makkelijk om nummerale resultaten te krijgen. Het is gewoon een bedrijf van millisecondes tot een seconde op een konventioneel of standaard PC. Dus is er een related werk dat einds om op de N minus K gebouwd te proeven? Niet te veel eigenlijk. Het is een verkeerde nieuwe research direction. Dus tot de beste van de kennis, alleen twee papieren over deze. En voor deze twee papieren, het is niet zelf de hoofdtopiek, maar alleen een kleine sitecontributie. Maar de praktische applicabiliteit van het existere werk is limiter omdat het alleen opgevoerd is voor de repetitie codes. Dus de repetitie codes zijn heel makkelijk te analyseren omdat er alleen twee code woorden zijn. De al-0 code woorden en de al-1 code woorden. Het is makkelijk te analyseren. Maar als je op een Pufbevski generator wil implementeren, dan moet je verschillende codes hebben. Je moet meer volledige, lager, meer complex codes hebben. Dus dit is interessant voor de theorie, maar niet voor praktisch, nog steeds. En ook de distributie van de Pufbevski, de opgevoerd is heel limiter. Het is aangezien dat de Pufbevski-codes indipend en identiek distributief zijn. Dus de beste die we kunnen kopen hier is de bias-case. Dus hier is het representatie van de bit string. We hebben een distributie en het is aangezien dat de Pufbevski-codes indipend zijn en de probabiliteit dat een certain bit is 1 is een paramieter B. En B is zomaar tussen 0 en 1. Dus als B is 0,5, dit zou uniform zijn. Maar hier in het exemplen, B is groter dan 0,5, zoals 0,7 of iets. En dan heb je meer 1's en 0's opgeverd. Dus nu gaan we verantwoordelijk de scoop op twee fronten. Eerst kunnen we een grote complex code kopen zoals ze gebruiken in een praktisch pufbevski generator. Dus we kunnen kopen bijvoorbeeld BCH code, Riedmuller code, een concatenation of code.  En de tweede, we kunnen kopen de verschillende distributies. Dus we kunnen niet kopen, geen mogelijkse distributie, maar er zijn wat limitaties over wat we kunnen kopen. Maar zeker de variatie dat we kunnen kopen is groter dan vanaf. En hier in de manuscript zijn we veel focussed op een proef van een concept distributie waar we een speciaal correlatie hebben. Dus hier is een exemplen bitstring. En in het exemplen, we ontdekken dat de probabiliteit dat twee neighbouring bits zijn gelijk. Dat is een certain parameter C, met C tussen 0 en 1. Dus als C is bijvoorbeeld 0,7 of 0,8, dan betekent dat neighbouring bits tenden te hebben dezelfde waarde. Dus nu gaan we naar de applicaties. Er zijn drie applicaties. Hier is de eerste. Dus de bepaalde applicatie is om de implementatie voetprint van de Puffbase keygenerator te vervangen. En een keygenerator zal er wat specificaties hebben. Dus we gebruiken typische spekken. Zoals we willen gebruiken, of we willen genereren, een 128-bit key. We gebruiken een BCH-code dat is concatenateerd met een repetitiecode. De bit error rate van de Puff is on average 10%. En de vergelijking rate voor een reproductie van een key is kleiner dan 10-6. Dus deze zijn typische spekken. Dus er is niets speciaal hier. En nu gaan we oefenen van de ressources voor de keygenerator. We gebruiken de N-K-bound en de nieuw improve bound. Dus er zijn twee kolen. Dat is de N-K-bound. Blu is de nieuw bound. Dus we hebben een plot hier. En we illustreren het voor de bias distributie. Maar we kunnen ook voor andere distributies. Maar nu gaan we het gewoon doen en doen we het voor de IID bias distributie alleen. Dus in de horizontal axis hebben we de parameter B. Dus de magniteit van de bias. Dus de groter B, de meer 1's versus 0's. En op de vertical axis hebben we de nummer van de Puff bits die zijn nodig om dit 128-bit key te genereren. Dus als je de N-K-bound gebruikt, dan krijg je het al snel in de groter. Dus een kleine bias is voor je bepaald. Om te kunnen instantieën de keygenerator die alle contrainten ontvangt. Maar met de nieuw improve bound moet het makkelijker zijn. Dus voor dezelfde bias heb je minder Puff bits nodig. Dus je kan de bias op de 0.65 te onderhalen. Dus twee kolen hier.  We gebruiken minder Puff bits met een nieuw bound. We gebruiken minder helper bits, die hier niet bepaald zijn. En ook dit is voor de bias distributie. Maar we kunnen ook dit doen voor andere distributies zoals de spatial correlaties. De distributie van de vorige slide. En er is een simpel gap tussen de N-K-bound en de nieuw bound. Dus nu gaan we naar de tweede applicatie uit de drie applicaties. En dat is de security analysis van de reversie extractor. Dus dat is een speciale mode van operation van de conventional physics extractor. En dat is meenelijk een techniek om de implementatie, voedprint of Puff base protocol te reduzen. Dus er zijn er verschillende protocol-proposen die er relyen op deze techniek. Dus eerst zullen we kijken naar de conventional strategie. Dus dit is niet de reversie, dat is een picatier bij de conventional strategie. Dus als we een twee-partie protocol hebben, aan de linker hebben we een embedded device en aan de reis hebben we een server. Dus op de embedded device doen we Puff base key generation, dus we hebben de secure sketch, we hebben de hash function, dus we genereren een secret key en de server zal een kopie van deze key sturen. En als we een asymmetric key ontbouwen, kunnen we ook een cryptoprotocool doen dat we willen. Dus vooral authentische protocols. Nu, de reversie strategie is een beetje verschillend. Dus hier, met elke protocolroom, nieuw helperdata is geïnsprensverd van de embedded device naar de server. En dit geeft ons te implementeren, de error-correcting code, of alstublieft de meest hardware-intensieve decoder-part op de server, zonder de device. Dus dit is meer lichtwijd. En een klein site-effect eraf is dat de key niet stedig is in de morbidynamic, maar dat is alleen een voetnote. Dus je kunt nog steeds een asymmetric key protocol doen dat je wilt. Dus de meeste veiligheid van de reversie strategie is dat het een gemakkelijk veilig is als een conventional one. Een meer vormlijke staat dat het gevoel dat een helperdata-exposure gegeven is, dus niet resultaat in een extra minentropie los. En de proef is ontbouwd van een 2004 papier van Boyen. Maar er is een vrouw in deze transfer omdat Boyen een bepaalde kondition dat niet in de reversie extractor kase is geïnteresseerd.  En om te zijn specifiek, het is overal uitzienbaar dat de athakker kan, door de verhaalde helperdata-exposure, dat de athakker kan voor elke perfbit vertellen wat de exacte bit eroreert van die bit is. Dus we geven nu de intuïtie waarom de exposure van de bit eroreert leeft te meer minentropie los. En we doen dit voor de biast pufdistribution, de IID biaspuff. Dit is gewoon een voorbeeld, omdat er een similaar reden is voor spatieal correlatie. Maar laten we het simpel doen en doen biast alleen. Dus hier in dit geval, we hebben 70 procent is 1 ongeveer en 30 procent is 0. Nu als we kijken naar de puf erostatistiek voor de schitterde distributie, het is een geval dat de athakker een klein beetje eroreert dan de 0's. Dus gegeven nu dat een athakker voor elke bit, de exacte bit eroreert, dit zal helpen om te distinguen tussen 0 en 1. Dat is een klere minentropie los. In praktisch, however, de protocols die gelijven op de reversie extractor zijn niet dat veel effecteerd. Dat is omdat ze ook gelijven op de n-k-bound en de n-k-bound is overal conservatief. Dus de fact dat het overal conservatief geeft wat extra veiligheid dat is nu gebruikt door dit inanticipeerde los en dat is niet geïncloed. Nu hebben we de tweede en de laatste applicatie. Dus motivatie voor de biasing schemes. Dus er zijn er verschillende proposalen. Een is de IBS-scheme en de andere is de Von Neumann-scheme. En beide hebben gelijk overigend geïnproefd. Dus alle schermen zijn geconjectieerd dat een standaard loon-scherm niet bij ons kan veranderen. En dit is inderdaad correct als we de n-k-bound van de n-k-bound maken, zoals we hebben gezien. Dus de idee achter alle schermen of wat alle schermen hebben in het commond is dat ze een biost-i-i-d-puff serveen. En dan zal ze deze biostere distributie in een uniforme distributie veranderen. Dus ze zullen deze door selecten een subset van de responsie bits alleen veranderen. Dus er is extra helperdata om welke bits die selecten zijn en welke bits die veranderen zijn. En dit maakt de balans tussen de nummer van 0's en de nummer van 1's te veranderen. En dan, wat er naartoe komt, is gewoon de convention voor de extractoren. Dus we hebben de secure sketch en de hash, zoals het eerder was.  Dus nu, dit is dezelfde plot zoals we het eerder hebben gezien, maar we hebben gewoon twee andere curve. Dus de curve in light blue is de Von Neumann-scheme of de Von Neumann-debijing gevolgd door een secure sketch en dan in green we hebben de IBS-scheme ook gevolgd door een secure sketch. En op de horizontal access hebben we nog de bias en op de vertical access hebben we nog de nummer van puff bits die nodig is om een 128-bit key te genereren. Dus het kan worden gezien dat in de low bias region de nieuwe bound is competitief. In de high bias region, dan kan één zeggen dat er een need voor de biasing schemes omdat een stand-alone sketch zelf met een nieuw improve bound niet kunnen handelen. Of misschien beter een puff-free design omdat als je puff een bias heeft van 80 procent of 90 procent, dit is meestal in de negatie dat er een klere probleem is met je puff. Dus als je kijkt naar de transistere niveau van de puff, er zal waarschijnlijk een soort asymmetrie zijn die deze grote bias maakt. Dus misschien, in plaats van de IBS-scheme of de Von Neumann-scheme, het zou eigenlijk een beter idee zijn om een puff te bekijken en om de asymmetrie in je design te veranderen om een low-bias te hebben. Maar in ieder geval in de low-bias region de nieuwe bound is competitief. En er zijn wat extra elementen die in favoriete van een stand-alone sketch versus de biasing schemes zijn. Een is dat de biasing niet voor vreemde is. Dus we moeten dus selecten een subtelheid van de bits en dit zou require een circuitrie en ook, misschien meer belangrijk, een significant amount of helper data. En de tweede, de IBS en Von Neumann-de biasing schemes zijn voor de IID bias-puff in specifiek voor de stand-alone sketch en een nieuw improve bound. We kunnen meer distributie kopen zodat het een meer generische techniek is. Dus in het eind van de laatste slide, we hebben een t-repart waarbij we de tijdbounds onder de circuit-sketchminentrepilos voor area-based puffs, dus azzarm-like puffs. En dit is een heel nieuw resultaat, dus het is zeker open voor meer improvements en verder exploratie. En dan hebben we verschillende applicaties, dus we hebben de implementatie voedpunt van de fysie extractor in comparison met de n-bounds. 