Cryptology ePrint Archive: Report 2016/573

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

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

Abstract: 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.

Category / Keywords: Masking, t-probing model, Re-Keying, LWR, LPN, Side-Channels

Original Publication (with minor differences): IACR-CRYPTO-2016

Date: received 3 Jun 2016

Contact author: gottfried herold at rub de

Available format(s): PDF | BibTeX Citation

Version: 20160603:182240 (All versions of this report)

Short URL:

Discussion forum: Show discussion | Start new discussion

[ Cryptology ePrint archive ]