tl;dr: Provide the existence of a code-based zero-knowledge PRF argument.
Paper: ISC 2019 or personal pdf.
Carlo Brunetta, Bei Liang, Aikaterini Mitrokotsa
Pseudo-random functions are a useful cryptographic primitive that, can be combined with zero-knowledge proof systems in order to achieve privacy-preserving identification. Libert et al. (ASIACRYPT 2017) has investigated the problem of proving the correct evaluation of lattice-based PRFs based on the Learning-With-Rounding (LWR) problem. In this paper, we go beyond lattice-based assumptions and investigate, whether we can solve the question of proving the correct evaluation of PRFs based on code-based assumptions such as the Syndrome Decoding problem. The answer is affirmative and we achieve it by firstly introducing a very efficient code-based PRG based on the Regular Syndrome Decoding problem and subsequently, we give a direct construction of a code-based PRF. Thirdly, we provide a zero-knowledge protocol for the correct evaluation of a code-based PRF, which allows a prover to convince a verifier that a given output $y$ is indeed computed from the code-based PRF with a secret key k on an input x, i.e., y=f(k,x). Finally, we analytically evaluate the protocol’s communication costs.