Abstract: Storing and sharing databases in the cloud of computers raise serious concern of individual privacy. We consider two kinds of privacy risk: presence leakage, by which the attackers can explicitly identify individuals in (or not in) the database, and association leakage, by which the attackers can unambiguously associate individuals with sensitive information. However, the existing privacy-preserving data sharing techniques either fail to protect the presence privacy or incur considerable amounts of information loss. In this paper, we propose a novel technique, Ambiguity, to protect both presence privacy and association privacy with low information loss. We formally define the privacy model and quantify the privacy guarantee of Ambiguity against both presence leakage and association leakage. We prove both theoretically and empirically that the information loss of Ambiguity is always less than the classic generalization-based anonymization technique. We further propose an improved scheme, PriView, that can achieve better information loss than Ambiguity. We propose efficient algorithms to construct both Ambiguity and PriView schemes. Extensive experiments demonstrate the effectiveness and efficiency of both Ambiguity and PriView schemes.