Cryptology ePrint Archive: Report 2021/950

Exploring Crypto-Physical Dark Matter and Learning with Physical Rounding Towards Secure and Efficient Fresh Re-Keying

Sébastien Duval and Pierrick Méaux and Charles Momin and François-Xavier Standaert

Abstract: State-of-the-art re-keying schemes can be viewed as a tradeoff between efficient but heuristic solutions based on binary field multiplications, that are only secure if implemented with a sufficient amount of noise, and formal but more expensive solutions based on weak pseudorandom functions, that remain secure if the adversary accesses their output in full. Recent results on “crypto dark matter” (TCC 2018) suggest that low-complexity pseudorandom functions can be obtained by mixing linear functions over different small moduli. In this paper, we conjecture that by mixing some matrix multiplications in a prime field with a physical mapping similar to the leakage functions exploited in side-channel analysis, we can build efficient re-keying schemes based on “crypto-physical dark matter”, that remain secure against an adversary who can access noise-free measurements. We provide first analyzes of the security and implementation properties that such schemes provide. Precisely, we first show that they are more secure than the initial (heuristic) proposal by Medwed et al. (AFRICACRYPT 2010). For example, they can resist attacks put forward by Belaid et al. (ASIACRYPT 2014), satisfy some relevant cryptographic properties and can be connected to a “Learning with Physical Rounding” problem that shares some similarities with standard learning problems. We next show that they are significantly more efficient than the weak pseudorandom function proposed by Dziembowski et al. (CRYPTO 2016), by exhibiting hardware implementation results.

Category / Keywords: Side-Channel Attacks, Fresh Re-Keying, Low-Complexity wPRFs, Learning With Rounding, Boolean Functions, Masking, Key-Homomorphism

Original Publication (with minor differences): IACR-CHES-2021

Date: received 13 Jul 2021

Contact author: sebastien duval at uvsq fr, charles momin at uclouvain be, pierrick meaux at uclouvain be, francois-xavier standaert at uclouvain be

Available format(s): PDF | BibTeX Citation

Version: 20210722:090313 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]