Updated: 10 hours 57 min ago
Abstract. A fuzzy extractor (Dodis et al., Eurocrypt 2004) is a pair of procedures that turns a noisy secret into a uniformly distributed key R. To eliminate noise, the generation procedure takes as input an enrollment value w and outputs R and a helper string P that enables further reproduction of R from some close reading w'.
Boyen immediately highlighted the need for reusable fuzzy extractors (CCS 2004) that remain secure even when numerous calls to the generation procedure are made on a users noisy secret. Boyen proved that any information-theoretically secure reusable fuzzy extractor is subject to strong limitations. In subsequent
work, Simoens et al. (IEEE S&P, 2009) showed that reusability was indeed a practical vulnerability.
More recently, Canetti et al. (Eurocrypt 2016) proposed moving to computational security and constructed a computationally secure reusable fuzzy extractor for the Hamming metric that corrects a
sublinear fraction of errors.
We propose a generic approach to building reusable fuzzy extractors where the main idea is to separate the reusability property from the key recovery. To do so, we define a new primitive called a reusable pseudoentropic isometry that projects an input metric space in a distance-and-entropy-preserving manner
even if applied multiple times. Generation of multiple randomized secrets $\Omega$s via such a tool does not reveal information about the original fuzzy secret w and can be used to decorrelate noisy versions of w.
We show that building a reusable fuzzy extractor from a reusable pseudoentropic isometry is straightforward by 1) randomizing the noisy secret w into $\Omega$ and 2) applying a traditional fuzzy extractor to derive a secret key from $\Omega$.
To show the promise of our framework, we propose instantiations that handle the set difference and Hamming metrics. The first one is an original construction based on composable digital lockers (Canetti and Dakdouk, Eurocrypt 2008) yielding the first reusable fuzzy extractor that corrects a linear fraction of errors. For the second one, we show that Construction 2 proposed by Canetti et al. in Eurocrypt 2016 (Section 5.1) can be seen as an instantiation of our framework. In both cases, the pseudoentropic isometrys
reusability requires noisy secrets distributions to have entropy in each symbol of the alphabet.
At last, we describe two practical solutions that reap benefits of our results while dealing with the aforementioned limitation.
In recent years, performance counters have been used as a side channel source for the branch mispredictions which has been used to attack ciphers with user privileges. However, existing research considers blinding techniques, like scalar blinding, scalar splitting as a mechanism of thwarting such attacks. In this endeavour, we reverse engineer the undisclosed model of Intels Broadwell and Sandybridge branch predictor and further utilize the largely unexplored perf ioctl calls in sampling mode to granularly monitor the branch prediction events asynchronously when a victim cipher is executing. With these artifacts in place, we target scalar blinding and splitting countermeasures to develop a key retrieval process using what is called as Deduce & Remove. The Deduce step uses template based on the number of branch misses as expected from the
3-bit model of the BPU to infer the matched candidate values. In the
Remove step, we correct any erroneous conclusions that are made, by
using the properties of the blinding technique under attack. It may be emphasized that as in iterated attacks the cost of a mistaken deduction could be significant, the blinding techniques actually aids in removing wrong guesses and in a way auto-corrects the key retrieval process. Finally, detailed experimental results have been provided to illustrate all the above steps for point blinding, scalar blinding, and scalar splitting to show that the secret scalar can be correctly recovered with high confidence. The paper concludes with recommendation on some suitable countermeasure at the algorithm level to thwart such attacks.
In anonymous identity-based encryption (IBE), ciphertexts not only hide their corresponding messages, but also their target identity. We construct an anonymous IBE scheme based on the Computational Diffie-Hellman (CDH) assumption in general groups (and thus, as a special case, based on the hardness of factoring Blum integers).
Our approach extends and refines the recent tree-based approach of Cho et al. (CRYPTO '17) and Döttling and Garg (CRYPTO '17). Whereas the tools underlying their approach do not seem to provide any form of anonymity, we introduce two new building blocks which we utilize for achieving anonymity: blind garbled circuits (which we construct based on any one-way function), and blind batch encryption (which we construct based on CDH).
We then further demonstrate the applicability of our newly-developed tools by showing that batch encryption implies a public-key encryption scheme that is both resilient to leakage of a $(1-o(1))$-fraction of its secret key, and KDM secure (or circular secure) with respect to all linear functions of its secret key (which, in turn, is known to imply KDM security for bounded-size circuits). These yield the first high-rate leakage-resilient encryption scheme and the first KDM-secure encryption scheme based on the CDH or Factoring assumptions.
Finally, relying on our techniques we also construct a batch encryption scheme based on the hardness of the Learning Parity with Noise (LPN) problem, albeit with very small noise rate $\Omega(\log^2(n)/n)$. Although this batch encryption scheme is not blind, we show that it still implies standard (i.e., non-anonymous) IBE, leakage resilience and KDM security. IBE and high-rate leakage resilience were not previously known from LPN, even with extremely low noise.
We introduce Multi Tree XMSS (XMSS^MT), a hash-based signature scheme that can be used to sign a virtually unlimited number of messages. It is provably forward and hence EU-CMA secure in the standard model and improves key and signature generation times compared to previous schemes. XMSS^MT has --- like all practical hash-based signature schemes --- a lot of parameters that control different trade-offs between security, runtimes and sizes. Using linear optimization, we show how to select provably optimal parameter sets for different use cases.
We present WOTS+, a Winternitz type one-time signature scheme (WOTS). We prove that WOTS+ is strongly unforgeable under chosen message attacks in the standard model. Our proof is exact and tight. The first property allows us to compute the security of the scheme for given parameters. The second property allows for shorter signatures than previous proposals without lowering the security. This improvement in signature size directly carries over to all recent hash-based signature schemes. I.e. we can reduce the signature size by more than 50% for XMSS+ at a security level of 80 bits. As the main drawback of hash-based signature schemes is assumed to be the signature size, this is a further step in making hash-based signatures practical.