This paper proposes PolyProtect, a method for protecting the sensitive face embeddings that are used to represent people's faces in neural-network-based face verification systems. PolyProtect transforms a face embedding to a more secure template, using a mapping based on multivariate polynomials parameterised by user-specific coefficients and exponents. In this work, PolyProtect is evaluated on two open-source face recognition systems in a cooperative-user mobile face verification context, under the toughest threat model that assumes a fully-informed attacker with complete knowledge of the system and all its parameters. Results indicate that PolyProtect can be tuned to achieve a satisfactory trade-off between the recognition accuracy of the PolyProtected face verification system and the irreversibility of the PolyProtected templates. Furthermore, PolyProtected templates are shown to be effectively unlinkable, especially if the user-specific parameters employed in the PolyProtect mapping are selected in a non-naive manner. The evaluation is conducted using practical methodologies with tangible results, to present realistic insight into the method's robustness as a face embedding protection scheme in practice. This work is fully reproducible using the publicly available code at: https://gitlab.idiap.ch/bob/bob.paper.polyprotect_2021.