Paper 2021/950

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

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


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.

Available format(s)
Publication info
A minor revision of an IACR publication in TCHES 2021
Side-Channel AttacksFresh Re-KeyingLow-Complexity wPRFsLearning With RoundingBoolean FunctionsMaskingKey-Homomorphism
Contact author(s)
sebastien duval @ uvsq fr
charles momin @ uclouvain be
pierrick meaux @ uclouvain be
francois-xavier standaert @ uclouvain be
2021-07-22: received
Short URL
Creative Commons Attribution


      author = {Sébastien Duval and Pierrick Méaux and Charles Momin and François-Xavier Standaert},
      title = {Exploring Crypto-Physical Dark Matter and Learning with Physical Rounding Towards Secure and Efficient Fresh Re-Keying},
      howpublished = {Cryptology ePrint Archive, Paper 2021/950},
      year = {2021},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.