Paper related to WP5 TREDISEC.
Cryptographic primitives for searching and computing over encrypted data have proven useful in many applications. In this paper, we revisit the application of symmetric searchable encryption (SSE) to biometric identification. Our main contribution is two SSE schemes well-suited to be applied to biometric identification over encrypted data. While existing solution uses SSE with single-keyword search and highly sequential design, we use threshold conjunctive queries and parallelizable constructions. As a result, we are able to perform biometric identification over a large amount of encrypted biometric data in reasonable time. Our two SSE schemes achieve a different trade-off between security and efficiency. The first scheme is more efficient, but is proved secure only against non-adaptive adversaries while the second is proved secure against adaptive adversaries.