Search for: All records

If a web service is so secure that it does not even know---and does not want to know---the identity and contact info of its users, can it still offer account recovery if a user forgets their password? This paper is the culmination of the authors' work to design a cryptographic protocol for account recovery for use by a prominent secure matching system: a web-based service that allows survivors of sexual misconduct to become aware of other survivors harmed by the same perpetrator. In such a system, the list of account-holders must be safeguarded, even against the service provider itself. In this work, we design an account recovery system that, on the surface, appears to follow the typical workflow: the user types in their email address, receives an email containing a one-time link, and answers some security questions. Behind the scenes, the defining feature of our recovery system is that the service provider can perform email-based account validation without knowing, or being able to learn, a list of users' email addresses. Our construction uses standardized cryptography for most components, and it has been deployed in production at the secure matching system. As a building block toward our main construction, we design a new cryptographic primitive that may be of independent interest: an oblivious pseudorandom function that can either have a fully-private input or a partially-public input, and that reaches the same output either way. This primitive allows us to perform online rate limiting for account recovery attempts, without imposing a bound on the creation of new accounts. We provide an open-source implementation of this primitive and provide evaluation results showing that the end-to-end interaction time takes 8.4-60.4 ms in fully-private input mode and 3.1-41.2 ms in partially-public input mode. 

The celebrated model of auctions with interdependent valuations, introduced by Milgrom and Weber in 1982, has been studied almost exclusively under private signals $$s_1, \ldots, s_n$$ of the $$n$$ bidders and public valuation functions $$v_i(s_1, \ldots, s_n)$$. Recent work in TCS has shown that this setting admits a constant approximation to the optimal social welfare if the valuations satisfy a natural property called submodularity over signals (SOS). More recently, Eden et al. (2022) have extended the analysis of interdependent valuations to include settings with private signals and \emph{private valuations}, and established $$O(\log^2 n)$$-approximation for SOS valuations. In this paper we show that this setting admits a {\em constant} factor approximation, settling the open question raised by Eden et al. (2022). 

We study combinatorial auctions with interdependent valuations, where each agent i has a private signal s_ithat captures her private information and the valuation function of every agent depends on the entire signal profile, [Formula: see text]. The literature in economics shows that the interdependent model gives rise to strong impossibility results and identifies assumptions under which optimal solutions can be attained. The computer science literature provides approximation results for simple single-parameter settings (mostly single-item auctions or matroid feasibility constraints). Both bodies of literature focus largely on valuations satisfying a technical condition termed single crossing (or variants thereof). We consider the class of submodular over signals (SOS) valuations (without imposing any single crossing-type assumption) and provide the first welfare approximation guarantees for multidimensional combinatorial auctions achieved by universally ex post incentive-compatible, individually rational mechanisms. Our main results are (i) four approximation for any single-parameter downward-closed setting with single-dimensional signals and SOS valuations; (ii) four approximation for any combinatorial auction with multidimensional signals and separable-SOS valuations; and (iii) (k + 3) and (2 log(k) + 4) approximation for any combinatorial auction with single-dimensional signals, with k-sized signal space, for SOS and strong-SOS valuations, respectively. All of our results extend to a parameterized version of SOS, d-approximate SOS, while losing a factor that depends on d. Funding: A. Eden was partially supported by NSF Award IIS-2007887, the European Research Council (ERC) under the European Union's Seventh Framework Programme [FP7/2007-2013]/ERC Grant Agreement 337122, by the Israel Science Foundation [Grant 317/17], and by an Amazon research award. M. Feldman received funding from the European Research Council (ERC) under the European Union's Horizon 2020 research and innovation program [Grant Agreement 866132], by the Israel Science Foundation [Grant 317/17], by an Amazon research award, and by the NSF-BSF [Grant 2020788]. The work of K. Goldner was supported partially by NSF awards DMS-1903037 and CNS-2228610 and a Shibulal Family Career Development Professorship. A. R. Karlin was supported by the NSF-CCF [Grant 1813135].