Data Reconstruction: When You See It and When You Don't
<|reference_start|>Data Reconstruction: When You See It and When You Don't: 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.<|reference_end|>
@article{cohen2024data,
    title={Data Reconstruction: When You See It and When You Don't},
    author={Edith Cohen, Haim Kaplan, Yishay Mansour, Shay Moran, Kobbi Nissim,
  Uri Stemmer, Eliad Tsfadia},
    journal={arXiv preprint arXiv:2405.15753},
    year={2024},
    archivePrefix={arXiv},
    eprint={2405.15753},
    primaryClass={cs.CR}
}