Welcome to the resource topic for 2013/864
Title:
Near-linear time, Leakage-resilient Key Evolution Schemes from Expander Graphs
Authors: Adam Smith, Ye Zhang
Abstract:We develop new schemes for deterministically updating a stored cryptographic key that provide security against an internal adversary who can control the update computation and leak bounded amounts of information to the outside world. Our schemes are much more efficient than the previous schemes for this model, due to Dziembowski, Kazana and Wichs (CRYPTO 2011). Specifically, our update operation runs in time quasilinear in the key length, rather than quadratic, while offering a similar level of leakage resilience. In order to design our scheme, we strengthen the connections between the model of Dziembowski et al. and pebbling games'', showing that random-oracle-based key evolution schemes are secure as long as the graph of the update function's calls to the oracle has appropriate combinatorial properties. This builds on a connection between pebbling and the random oracle model first established by Dwork, Naor and Wee (CRYPTO 2005). Our scheme's efficiency relies on the existence (which we show) of families of local’’ bipartite expander graphs of constant degree.
ePrint: https://eprint.iacr.org/2013/864
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .