zbMATH — the first resource for mathematics

Secure outsourcing of cryptographic circuits. (English) Zbl 1421.94082
Baek, Joonsang (ed.) et al., Provable security. 12th international conference, ProvSec 2018, Jeju, South Korea, October 25–28, 2018. Proceedings. Cham: Springer. Lect. Notes Comput. Sci. 11192, 94-108 (2018).
Summary: Learning Parity with Noise (LPN) represents a notoriously hard problem in learning theory and it is also closely related to the “Decoding Random Linear Codes” problem in coding theory. Recently LPN has found many cryptographic applications such as authentication protocols, pseudorandom generators/functions and even advanced tasks including public-key encryption (PKE) schemes and oblivious transfer (OT) protocols. Crypto-systems based on LPN are computationally efficient and parallelizable in concept, thanks to the simple algebraic structure of LPN, but they (especially the public-key ones) are typically inefficient in terms of public-key/ciphertext sizes and/or communication complexity. To mitigate the issue, Heyse et al. (FSE 2012) introduced the ring variant of LPN (Ring-LPN) that enjoys a compact structure and gives rise to significantly more efficient cryptographic schemes. However, unlike its large-modulus analogue Ring-LWE (to which a reduction from ideal lattice problems can be established), no formal asymptotic studies are known for the security of Ring-LPN or its connections to other hardness assumptions.
Informally, we show that for \(\mu=1/n^{0.5-\epsilon}\) and \(\delta=\mu\mu 'n=o(1)\): assume that the decisional LPN problem of noise rate \(\mu\) is hard even when its matrix is generated by a random Ring-LPN instance of noise rate \(\mu '\) (whose matrix is also kept secret in addition to secret and noise), then either Ring-LPN of noise rate \(\delta \) is hard or public-key cryptography is implied. We remark that the heuristic-based approach to public randomness generation (as used in the assumption) is widely adopted in practice, and the latter statement is less likely because noise rate \(\mu=1/n^{0.5-\epsilon}\) is believed to reside in the minicrypt-only regime for LPN. Therefore, our results constitute non-trivial evidence that Ring-LPN might be as hard as LPN.
For the entire collection see [Zbl 1398.94007].
94A60 Cryptography
94A62 Authentication, digital signatures and secret sharing
Full Text: DOI