We consider the problem of secure histogram es-timation, where n users hold private items x i from a size-d domain and a server aims to estimate the histogram of the user items. Previous results utilizing orthogonal communication schemes have shown that this problem can be solved securely with a total communication cost of O(n 2 log(d)) bits by hiding each item x i with a mask. In this paper, we offer a different approach to achieving secure aggregation. Instead of masking the data, our scheme protects individuals by aggregating their messages via a multiple-access channel. A naive communication scheme over the multiple-access channel requires d channel uses, which is generally worse than the O(n 2 1og(d)) bits communication cost of the prior art in the most relevant regime d » n . Instead, we propose a new scheme that we call Over-the-Air Group Testing (AirG T) which uses group testing codes to solve the histogram estimation problem in O(n log(d)) channel uses. AirGT reconstructs the histogram exactly with a vanishing probability of error P error = O(d -T ) that drops exponentially in the number of channel uses T.