What Can Phase Retrieval Tell Us About Private Distributed Learning?
In this work, we examine the security of InstaHide, a scheme recently proposed by \cite{hsla20} for preserving the security of private datasets in the context of distributed learning. To generate a synthetic training example to be shared among the distributed learners, InstaHide takes a convex combination of private feature vectors and randomly flips the sign of each entry of the resulting vector with probability 1/2. A salient question is whether this scheme is secure in any provable sense, perhaps under a plausible complexity-theoretic assumption. The answer to this turns out to be quite subtle and closely related to the average-case complexity of a multi-task, missing-data version of the classic problem of phase retrieval that is interesting in its own right. Motivated by this connection, under the standard distributional assumption that the public/private feature vectors are isotropic Gaussian, we design an algorithm that can actually recover a private vector using only the public vectors and a sequence of synthetic vectors generated by InstaHide.
Code (0)
등록된 구현이 없습니다.
Tasks
RetrievalSimilar Papers 제목 키워드 기반
A New Design of Cache-aided Multiuser Private Information Retrieval with Uncoded Prefetching
In the problem of cache-aided multiuser private information retrieval (MuPIR), a set of $K_{\rm u}$ cache-equipped users wish to privately download a set of messages from $N$ distributed databases each holding a library …
Information RetrievalRetrievalEvent-Enriched Image Analysis Grand Challenge at ACM Multimedia 2025
The Event-Enriched Image Analysis (EVENTA) Grand Challenge, hosted at ACM Multimedia 2025, introduces the first large-scale benchmark for event-level multimodal understanding. Traditional captioning and retrieval tasks l…
Image RetrievalOn InstaHide, Phase Retrieval, and Sparse Matrix Factorization
In this work, we examine the security of InstaHide, a scheme recently proposed by [Huang, Song, Li and Arora, ICML'20] for preserving the security of private datasets in the context of distributed learning. To generate a…
RetrievalEgoPrivacy: What Your First-Person Camera Says About You?
While the rapid proliferation of wearable cameras has raised significant concerns about egocentric video privacy, prior work has largely overlooked the unique privacy threats posed to the camera wearer. This work investi…
RetrievalCache-Aided Multi-User Private Information Retrieval using PDAs
We consider the problem of cache-aided multi-user private information retrieval (MuPIR). In this problem, $N$ independent files are replicated across $S \geq 2$ non-colluding servers. There are $K$ users, each equipped w…
Information RetrievalRetrieval