We address the problem of personalizing ad delivery to a smart phone, without violating user privacy. We propose a flexible framework where users can decide how much information about their private context they are willing to share with the ad server. Based on this limited information the server selects a set of ads and sends them to the client. The client then picks the most relevant one based on all its private contextual information. The optimization of selecting the most relevant ads to display is done jointly by the user and the server under two constraints on (1) privacy, i.e., how much information is shared, and (2) communication complexity, i.e. how many ads are sent to the client. We formalize the optimization problem, show that it is NP-hard, and present efficient algorithms with tight approximation guarantees. We then propose the first differentially-private distributed protocol to compute various statistics required for our framework even in the presence of a dynamic and malicious set of participants. Our experiments on real click logs show that reasonable levels of privacy, efficiency, and ad relevance can be achieved simultaneously.