2026-07-22T21:35:20Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:22667 2026-04-17T05:32:03Z ddc:004 open_access

Data Reconstruction: When You See It and When You Don't Cohen, Edith Kaplan, Haim Mansour, Yishay Moran, Shay Nissim, Kobbi Stemmer, Uri Tsfadia, Eliad differential privacy reconstruction We revisit the fundamental question of formally defining what constitutes a reconstruction attack. While often clear from the context, our exploration reveals that a precise definition is much more nuanced than it appears, to the extent that a single all-encompassing definition may not exist. Thus, we employ a different strategy and aim to "sandwich" the concept of reconstruction attacks by addressing two complementing questions: (i) What conditions guarantee that a given system is protected against such attacks? (ii) Under what circumstances does a given attack clearly indicate that a system is not protected? More specifically, - We introduce a new definitional paradigm - Narcissus Resiliency - to formulate a security definition for protection against reconstruction attacks. This paradigm has a self-referential nature that enables it to circumvent shortcomings of previously studied notions of security. Furthermore, as a side-effect, we demonstrate that Narcissus resiliency captures as special cases multiple well-studied concepts including differential privacy and other security notions of one-way functions and encryption schemes. - We formulate a link between reconstruction attacks and Kolmogorov complexity. This allows us to put forward a criterion for evaluating when such attacks are convincingly successful. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Edith Cohen and Haim Kaplan and Yishay Mansour and Shay Moran and Kobbi Nissim and Uri Stemmer and Eliad Tsfadia 2025 Is Part Of LIPIcs, Volume 325, 16th Innovations in Theoretical Computer Science Conference (ITCS 2025) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ITCS.2025.39 urn:nbn:de:0030-drops-226674 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2025.39 eng https://creativecommons.org/licenses/by/4.0/legalcode