Cancelable biometric schemes have been widely studied to protect templates in biometric authentication over networks. These schemes transform biometric features and perform pattern matching without restoring the original features. Although they strongly prevent the leakage of the original features, the response time can be very long in a large-scale biometric identification system. Most of the existing indexing schemes cannot be used to speed up the biometric identification system over networks since a biometric index leaks some information about the original feature. Secure and efficient indexing is a major challenge in large-scale biometric identification over networks. In this paper, we propose a novel indexing scheme that is promising with regard to both security and efficiency. The proposed indexing scheme transforms a permutation-based index, which is the state-of-the-art index in the field of similarity search, and performs a query search without recovering the original index. We also propose a method to artificially generate biometric features necessary to generate an index (which are called “pivots”) based on GANs (Generative Adversarial Networks). We prove that the transformed index leaks no information about the original index and the original biometric feature (i.e., perfect secrecy), and comprehensively show that the proposed indexing scheme has the irreversibility, unlinkability, and revocability. We then demonstrate that the proposed indexing scheme significantly outperforms the existing indexing schemes using three real datasets (face, fingerprint, and finger-vein datasets), and is very promising with respect to the accuracy and response time.