Flexible Two-Source Extractors and their Applications

Prezentujemy nowe pojęcie elastycznego extraktora dwuźródłowego. W przeciwień- stwie do standardowych dwuźródłowych ekstraktorów, które wymagają by każde ze źródeł osobno miało pewną entropię, elastyczny ekstraktor wymaga by sumaryczna entropia źródeł przekraczała daną wartość. Wyróżniamy słabe i silne elastyczne ekstraktory i podobnie jak w przypadku słabych i silnych ekstraktorów dwuźró- dłowych dowodzimy, że każdy słaby ekstraktor jest też silny kosztem nieznacznego pogorszenia jego parametrów. Ponadto dowodzimy, że dwa z powszechnie znanych i używanych ekstraktorów są elastyczne co znacząco wzmacnia tezę Leftover Hash Lemma dla tych ekstraktorów. Pojęcia elastycznych ekstraktorów używamy we wspólnej pracy ze Stefanem Dziembowskim i Tomaszem Kazaną ”Non-Malleable Codes from Two-Source Extractors”, praca ta została wysłana na międzynaro- dową konferencję. Konstruujemy w niej wydajny, teorio-informacyjnie bezpieczny kod niekowalny w modelu z przepołowioną pamiecią dla wiadomości jednobito- wych. Pojęcie kodów niekowalnych zostało wprowadzone przez S.Dziembowskiego, K.Pietrzaka i D.Wichsa (ICS 2010), jako narzędzie do składowania danych na urządzeniu, które może być poddane działaniu przeciwnika modyfikującego dane. Nieformalnie ujmując, schemat (Enc : M → L × R, Dec : L × R → M) jest kodem niekowalnym w modelu z przepołowioną pamięcią jeśli wspomniany prze- ciwnik manipulujący niezależnie L i R (gdzie (L,R) koduje pewną wiadomość m) nie może otrzymac, kodu wiadomości m′, która byłaby różna od m ale z nią “skorelowana”(np. m′ = m + 1). Do teraz efektywna konstrukcja informacyjnie bezpiecznego kodu o takiej wlasności pozostawala nieznana nawet dla wiadomości ze zbioru {0,1}. Nasza konstrukcja rozwiązuje ten problem. Ponadto dowodzimy jej odporności na wycieki, w następującym sensie: przeciwnik zanim wybierze dwie funkcje manipulujące (jedną na L, drugą na R) może poznać dowolną, ustaloną wcześniej funkcję wycieku z (L,R). Formalnie, dla każdego ξ < 1/4 potrafimy podać efektywną konstrukcje kodu niekowalnego taką, że przeciwnik przed wybo- rem funkcji manipulacji pozna wartości wybranych przez siebie adaptywnie funkcji F1(L),F2(R),F3(L),F4(R)... byle tylko sumaryczna dlugość wyjścia tych funkcji nie przekraczała ξ · (|L| + |R|). Konstrukcja naszego kodu jest oparta na iloczynie skalarnym nad ciałami skończonymi, ale pokazujemy jak zbudowac kod z dowol- nego innego dwuźródłowego ekstraktora, który jest elastyczny (flexible). Poza tym pokazujemy, ze definicja kodów niekowalnych w przypadku wiadomości jednobi- towych ma równoważną, prostszą charakteryzację mianowicie: jeśli wybierzemy wiadomość m jednostajnie z {0, 1} wtedy prawdopodobieństwo, że przeciwnik be- dzie w stanie uzyskac (w sposób opisany powyżej) wiadomość przeciwną do m jest niewiększe niż 1/2 + ε.

We introduce a new notion flexible extractor. It is a generalization of the standard concept of a two-source-extractor which require each of a sources to have some entropy, flexible extractor requires the sum of sources entropy to exceed fixed value. We distinguish between a strong and a weak flexible extractors and (similarly to two-source-extractors case) prove that every weak flexible extractor is also a strong extractor just with a slightly worse parameters. Moreover we prove that two common two-source extractors are in fact flexible which can be viewed as a generalization of the Leftover Hash Lemma for those extractors. We use that notion in joint work with Stefan Dziembowski and Tomasz Kazana “Non-Malleable Codes from Two-Source Extractors” currently under submission. In that work we use the flexible extractors to construct an efficient information-theoretically non-mall- eable code in the split-state model for one-bit messages. Non-malleable codes were introduced recently by Dziembowski, Pietrzak and Wichs (ICS 2010), as a general tool for storing messages securely on hardware that can be subject to tampering attacks. Informally, a code (Enc : M → L × R, Dec : L × R → M) is non-malleable in the split-state model if any adversary, by manipulating independently L and R (where (L,R) is an encoding of some message M), cannot obtain an encoding of a message M ′ that is not equal to M but is “related” M in some way. Until now it was unknown how to construct an information-theoretically secure code with such a property, even for M = {0, 1}. Our construction solves this problem. Additionally, it is leakage-resilient, and the amount of leakage that we can tolerate can be an arbitrary fraction ξ < 1/4 of the length of the codeword. Our code is based on the inner-product two-source extractor, but in general it can be instantiated by any two-source extractor that has the property of being flexible. We also show that the non-malleable codes for one-bit messages have an equivalent, perhaps simpler characterization, namely such codes can be defined as follows: if M is chosen uniformly from {0,1} then the probability (in the experiment described above) that the output message M ′ is not equal to M can be at most 1/2 + ε.