Score:2

Why is the helper data of a fuzzy extractor considered a good model for memory leakage?

ru flag

In "Memory Leakage-Resilient Encryption based on Physically Unclonable Functions" (ASIACRYPT2009), the authors use a construction based on a PUF and a Fuzzy Extractor and argue that this yields a Memory-leakage resilient encryption.

The definition of a Fuzzy Extractor is the following:

A $\left(m,n,\delta,\mu_{FE},\epsilon_{FE}\right)$-fuzzy extractor $\mathsf{E}$ is a pair of randomized procedures, "generate" $\mathsf{Gen}:\{0,1\}^m\to\{0,1\}^n\times\{0,1\}^{*}$ and "reproduce" $\mathsf{Rep}:\{0,1\}^m\to\{0,1\}^*\times\{0,1\}^{n}$.

The correctness property guarantees that for $(z,\omega)\leftarrow\mathsf{Gen}(y)$ and $y'\in\{0,1\}^m$ with $\mathsf{dist}\left(y,y'\right)\leqslant\delta$, then $\mathsf{Rep}\left(y',\omega\right)=z$. If $\mathsf{dist}\left(y,y'\right)>\delta$, then no guarantee is provided about the output of $\mathsf{Rep}$.

The security property guarantees that for any distribution $\mathbb{D}$ on $\{0,1\}^m$ of min-entropy $\mu_{FE}$, the string $z$ is nearly uniform even for those who observe $\omega$: if $(z,\omega)\leftarrow\mathsf{Gen}(\mathbb{D})$, then it holds that $SD\left((z,\omega),\left(\mathbb{U}_n,\omega\right)\right)\leqslant\epsilon_{FE}$.

Where $\mathbb{U}_n$ is the uniform distribution on $[n]$. From my understanding, the authors then define an encryption scheme based on $\mathsf{Gen}\circ\Pi$, where $\Pi$ is a PUF. They model the resources the adversary get access to by the helper data, namely $\omega$.

However, I don't understand why is this model realistic. In a memory-leakage situation, the adversary should be able to learn information on the plaintext. Though they argue that this is the case when usign Fuzzy Extractors, I can't convince myself that this model isn't a tautology. Of course, if the adversary is only given some helper data that looks random anyway because of the security guarantee of the Fuzzy Extractor, surely the model is secure.

Hence my question: why do we consider the Fuzzy-Extractors to be a good model for memory leakage?

mangohost

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.