The Security of Hardware-Based Omega(n^2) Cryptographic One-Way Functions: Beyond Satisfiability and P=NP
arXiv:1610.07190v1
Originality Incremental advance
AI Analysis
This addresses security for cryptography in scenarios where traditional computational hardness assumptions might fail, though it appears incremental as it builds on hardware-based approaches.
The paper tackles the problem of creating cryptographic one-way functions that remain secure even under strong computational assumptions like P=NP, by proposing hardware-based functions with omega(n^2) circuit size and runtime, achieving practical hardness against inversion.
We present a class of hardware-based cryptographic one-way functions that, in practice, would be hard to invert even if P=NP and linear-time satisfiability algorithms exist. Such functions use a hardware-based component with omega(n^2) size circuits, and omega(n^2) run time.