Neural Architecture Search (NAS) allows the user to design the most appropriate network architecture for specific assignments automatically. Outsourced NAS, as one of the applications in the Deep-Learning-as-a-Service paradigm, provides APIs for the resource-limited clients to delegate the architecture design task to a remote server. Despite its merits, the outsourced NAS poses significant concerns about the computation integrity and privacy. In this work, we propose \(\textsf{zkNAS}\) , a secure and efficient zero-knowledge NAS scheme for the outsourced NAS. Unlike prior works, \(\textsf{zkNAS}\)  enables the server to prove the integrity of the NAS computation while preserving the privacy of the NAS strategies and hyperparameters. \(\textsf{zkNAS}\)  is established on zero-knowledge proof (ZKP) protocols and a ZK-friendly NAS algorithm. The core idea is to utilize the information contained in the feature maps during forward propagation as zero-cost proxies, thus significantly reducing computation overhead. Specifically, we adopt three indicators based on feature maps and establish the ZKP-friendly NAS algorithm. Based on the system design, we design concrete ways to efficiently transform NAS computation into arithmetic circuits. We fully implement the design, which is significantly more efficient than the baselines on all evaluation metrics.