本发明公开了一种基于同态加密和匿名伪装的导航服务隐私保护方法及装置，方法包括：LBS服务商进行同态加密方案的初始化；用户利用匿名伪装算法分别生成出匿名伪装区域；用户根据匿名伪装区域的路网信息，随机选取出发点附近满足伪装距离L的出发地伪装点和目的地伪装点，同步规划出真实出发地到伪装出发地的路线；云服务商规划出一组候选路线，同时向LBS服务商请求实时路况信息；云服务商对候选路线组的开销进行进一步计算，利用全同态加密的比较运算，将密文比较结果传输给LBS服务商；从候选路线组中选取最佳路线并在本地将和伪装区域内的路线连接，生成最终的出行路线。本发明采用全同态加密和匿名伪装技术实现高质量的导航服务隐私保护。