The use of human biometrics is becoming widespread and its major application is human recognition for controlling unauthorized access to both digital services and physical localities. However, the practical deployment of human biometrics for recognition poses a number of challenges, such as template storage capacity, computational requirements, and privacy of biometric information. These challenges are important considerations, in addition to performance accuracy, especially for authentication systems with limited resources. In this paper, we propose a wave atom transform (WAT)-based palm-vein recognition scheme. The scheme computes, maintains, and matches palm-vein templates with less computational complexity and less storage requirements under a secure and privacy-preserving environment. First, we extract palm-vein traits in the WAT domain, which offers sparser expansion and better capability to extract texture features. Then, the randomization and quantization are applied to the extracted features to generate a compact, privacy-preserving palm-vein template. We analyze the proposed scheme for its performance and privacy-preservation. The proposed scheme obtains equal error rates (EERs) of 1.98%, 0%, 3.05%, and 1.49% for PolyU, PUT, VERA and our palm-vein datasets, respectively. The extensive experimental results demonstrate comparable matching accuracy of the proposed scheme with a minimum template size and computational time of 280 bytes and 0.43 s, respectively.