Polynomial Interpolation of the Naor-Reingold Pseudo-Random Function

Thierry Mefenza (1, 2) , Damien Vergnaud (2, 1)

1 DI-ENS - Département d'informatique - ENS Paris
2 CASCADE - Construction and Analysis of Systems for Confidentiality and Authenticity of Data and Entities

We prove lower bounds on the degree of polynomials interpolating the Naor–Reingold pseudo-random function over a finite field and over the group of points on an elliptic curve over a finite field.

Mots clés: Naor–Reingold pseudo-random function; Polynomial interpolation; Finite fields; Elliptic curves

Domaines: Cryptographie et sécurité [cs.CR]

Thierry Mefenza, Damien Vergnaud. Polynomial Interpolation of the Naor-Reingold Pseudo-Random Function. Applicable Algebra in Engineering, Communication and Computing, 2017, 28 (3), pp.237-255. ⟨10.1007/s00200-016-0309-4⟩. ⟨hal-01550044⟩