Leveled Fuzzy Identity-Based Fully Homomorphic Signatures

In fuzzy identity-based fully homomorphic signature (FIBFHS), the output of homomorphic computation, which is related to the identity id, can be verified by the receiver using the identity id^ as long as id and id^ are within a certain distance of each other. Gorbunov, Vaikuntanathan and Wichs (STOC 2015) introduced a new notion called homomorphic trapdoor functions (HTDFs) and constructed the first leveled fully homomorphic signature (FHS) scheme from HTDFs. In this paper, firstly, we extend the notion of HTDFs to fuzzy identity-based homomorphic trapdoor functions (FIBHTDFs). Next, we construct a FIBHTDF based on the small integer solution (SIS) problem by borrowing ideas from the secret-sharing techniques developed by Agrawal et al. (PKC 2012) and Boyen (TCC 2013) and prove that it is selective-identity secure in the standard model. Finally, we construct the first leveled FIBFHS scheme from FIBHTDFs and prove that it satisfies existential unforgeability under selective-identity and static chosen-message attacks in the standard model.