On Bringer-Chabanne EPIR Protocol for Polynomial Evaluation
This is an incremental finding that exposes a critical error in a cryptographic protocol, impacting researchers and practitioners in privacy-preserving computation.
The paper identifies a correctness flaw in the Bringer-Chabanne EPIR protocol for polynomial evaluation, showing it fails to return the expected result with high probability under specific coefficient conditions.
Extended private information retrieval (EPIR) was defined by \cite{BCPT07} at CANS'07 and generalized by \cite{BC09} at AFRICACRYPT'09. In the generalized setting, EPIR allows a user to evaluate a function on a database block such that the database can learn neither which function has been evaluated nor on which block the function has been evaluated and the user learns no more information on the database blocks except for the expected result. An EPIR protocol for evaluating polynomials over a finite field $L$ was proposed by Bringer and Chabanne in \cite{BC09}. We show that the protocol does not satisfy the correctness requirement as they have claimed. In particular, we show that it does not give the user the expected result with large probability if one of the coefficients of the polynomial to be evaluated is primitive in $L$ and the others belong to the prime subfield of $L$.