International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

Paper: Learning Parity with Physical Noise: Imperfections, Reductions and FPGA Prototype

Authors:
Davide Bellizia , UCLouvain, ICTEAM, Crypto Group, Louvain-la-Neuve, Belgium
Clément Hoffmann , UCLouvain, ICTEAM, Crypto Group, Louvain-la-Neuve, Belgium
Dina Kamel , UCLouvain, ICTEAM, Crypto Group, Louvain-la-Neuve, Belgium
Hanlin Liu , Shanghai Jiao Tong University, China
Pierrick Méaux , UCLouvain, ICTEAM, Crypto Group, Louvain-la-Neuve, Belgium
François-Xavier Standaert , UCLouvain, ICTEAM, Crypto Group, Louvain-la-Neuve, Belgium
Yu Yu , Shanghai Jiao Tong University, China
Download:
DOI: 10.46586/tches.v2021.i3.390-417
URL: https://tches.iacr.org/index.php/TCHES/article/view/8979
Search ePrint
Search Google
Abstract: Hard learning problems are important building blocks for the design of various cryptographic functionalities such as authentication protocols and post-quantum public key encryption. The standard implementations of such schemes add some controlled errors to simple (e.g., inner product) computations involving a public challenge and a secret key. Hard physical learning problems formalize the potential gains that could be obtained by leveraging inexact computing to directly generate erroneous samples. While they have good potential for improving the performances and physical security of more conventional samplers when implemented in specialized integrated circuits, it remains unknown whether physical defaults that inevitably occur in their instantiation can lead to security losses, nor whether their implementation can be viable on standard platforms such as FPGAs. We contribute to these questions in the context of the Learning Parity with Physical Noise (LPPN) problem by: (1) exhibiting new (output) data dependencies of the error probabilities that LPPN samples may suffer from; (2) formally showing that LPPN instances with such dependencies are as hard as the standard LPN problem; (3) analyzing an FPGA prototype of LPPN processor that satisfies basic security and performance requirements.
Video from TCHES 2021
BibTeX
@article{tches-2021-31289,
  title={Learning Parity with Physical Noise: Imperfections, Reductions and FPGA Prototype},
  journal={IACR Transactions on Cryptographic Hardware and Embedded Systems},
  publisher={Ruhr-Universität Bochum},
  volume={2021, Issue 3},
  pages={390-417},
  url={https://tches.iacr.org/index.php/TCHES/article/view/8979},
  doi={10.46586/tches.v2021.i3.390-417},
  author={Davide Bellizia and Clément Hoffmann and Dina Kamel and Hanlin Liu and Pierrick Méaux and François-Xavier Standaert and Yu Yu},
  year=2021
}