Paper 2016/573

Towards Sound Fresh Re-Keying with Hard (Physical) Learning Problems

Stefan Dziembowski, Sebastian Faust, Gottfried Herold, Anthony Journault, Daniel Masny, and Francois-Xavier Standaert


Most leakage-resilient cryptographic constructions aim at limiting the information adversaries can obtain about secret keys. In the case of asymmetric algorithms, this is usually obtained by secret sharing (aka masking) the key, which is made easy by their algebraic properties. In the case of symmetric algorithms, it is rather key evolution that is exploited. While more efficient, the scope of this second solution is limited to stateful primitives that easily allow for key evolution such as stream ciphers. Unfortunately, it seems generally hard to avoid the need of (at least one) execution of a stateless primitive, both for encryption and authentication protocols. As a result, fresh re-keying has emerged as an alternative solution, in which a block cipher that is hard to protect against side-channel attacks is re-keyed with a stateless function that is easy to mask. While previous proposals in this direction were all based on heuristic arguments, we propose two new constructions that, for the first time, allow a more formal treatment of fresh re-keying. More precisely, we reduce the security of our re-keying schemes to two building blocks that can be of independent interest. The first one is an assumption of Learning Parity with Leakage, which leverages the noise that is available in side-channel measurements. The second one is based on the Learning With Rounding assumption, which can be seen as an alternative solution for low-noise implementations. Both constructions are efficient and easy to mask, since they are key homomorphic or almost key homomorphic.

Available format(s)
Publication info
A minor revision of an IACR publication in CRYPTO 2016
Maskingt-probing modelRe-KeyingLWRLPNSide-Channels
Contact author(s)
gottfried herold @ rub de
2016-06-03: received
Short URL
Creative Commons Attribution


      author = {Stefan Dziembowski and Sebastian Faust and Gottfried Herold and Anthony Journault and Daniel Masny and Francois-Xavier Standaert},
      title = {Towards Sound Fresh Re-Keying with Hard (Physical) Learning Problems},
      howpublished = {Cryptology ePrint Archive, Paper 2016/573},
      year = {2016},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.