Homomorphic encryption (HE) enables privacy-preserving machine learning by allowing computation directly over encrypted data, and HE-based inference algorithms are already practical even for relatively large Convolutional Neural Networks (CNNs). Encrypted training, on the other hand, is still a major challenge, with current solutions taking up to weeks of computation. In this paper, we introduce a framework for training and inference on Weightless Neural Network (WNN) models over encrypted data. Compared to CNNs, we show (HE-based) WNNs offer much better performance with a relatively small accuracy loss. Our solution is based on new building blocks we introduce for the TFHE scheme that can be of independent interest. We achieve 91.71