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: ia.cr/2016/573
Discussion forum: Show discussion | Start new discussion
[ Cryptology ePrint archive ]