We introduce a new model of k-type anonymity, called k-concealment, as an alternative to the well-known model of k-anonymity. This new model achieves similar privacy goals as k-anonymity: While in k-anonymity one generalizes the table records so that each one of them becomes equal to at least k-1 other records, when projected on the subset of quasi-identifiers, k-concealment proposes to generalize the table records so that each one of them becomes computationally - indistinguishable from at least k-1 others. As the new model extends that of k-anonymity, it offers higher utility. To motivate the new model and to lay the ground for its introduction, we first present three other models, called (1, k)-, (k, 1)- and (k, k)-anonymity which also extend k-anonymity. We characterize the interrelation between the four models and propose algorithms for anonymizing data according to them. Since k-anonymity, on its own, is insecure, as it may allow adversaries to learn the sensitive information of some individuals, it must be enhanced by a security measure such as p-sensitivity or l-diversity. We show how also k-concealment can be enhanced by such measures. We demonstrate the usefulness of our models and algorithms through extensive experiments.