A method for using a location-based service while preserving anonymity includes receiving a location associated with a mobile node, receiving an anonymity level associated with the mobile node, computing a region containing the location of the mobile node and a number of footprints based on the anonymity level, wherein each of the footprints from a different user, and providing the region to a location-based service to thereby preserve anonymity of the mobile node. A method also allow a mobile device or its user to specify the anonymity level by selecting a public region consistent with a user's feelings towards desired privacy.