Techniques are provided for ground distance calculations using sanitized location data. One method comprises a service provider obtaining: (i) a geographic zone identifier of multiple predefined geographic zones of a first location of a user, and (ii) a first distance between the first location of the user and multiple reference points that define boundaries of the predefined geographic zones; the service provider obtaining: (i) a geographic zone identifier of the multiple predefined geographic zones of a second location of the user, and (ii) a second distance between the first location of the user and the multiple reference points; and computing a ground distance between the first location and the second location by selecting a subset of the multiple reference points based at least in part on the relative geographic zones of the current and second locations. The user may: (i) estimate the first location and calculate the first distance; and/or (ii) compute the first and second distances.