ploc-article.bib

@InProceedings{AC:AmjKamMoa23,
  author =       "Ghous Amjad and Seny Kamara and Tarik Moataz",
  title =        "Injection-Secure Structured and Searchable Symmetric
                  Encryption",
  pages =        "232--262",
  editor =       asiacrypt23ed,
  booktitle =    asiacrypt23name6,
  volume =       asiacrypt23vol6,
  address =      asiacrypt23addr,
  month =        asiacrypt23month,
  publisher =    asiacrypt23pub,
  series =       mylncs,
  year =         2023,
  doi =          "10.1007/978-981-99-8736-8_8",
}

@InProceedings{AC:AgaKamMoa24,
  author =       "Archita Agarwal and Seny Kamara and Tarik Moataz",
  title =        "Concurrent Encrypted Multimaps",
  pages =        "169--201",
  editor =       asiacrypt24ed,
  booktitle =    asiacrypt24name4,
  volume =       asiacrypt24vol4,
  address =      asiacrypt24addr,
  month =        asiacrypt24month,
  publisher =    asiacrypt24pub,
  series =       mylncs,
  year =         2024,
  doi =          "10.1007/978-981-96-0894-2_6",
}

@Article{PoPETS:APPYY23,
  author =       "Ghous Amjad and Sarvar Patel and Giuseppe Persiano and Kevin
                  Yeo and Moti Yung",
  title =        "Dynamic Volume-Hiding Encrypted Multi-Maps with Applications
                  to Searchable Encryption",
  pages =        "417--436",
  volume =       2023,
  month =        jan,
  publisher =    sciendo,
  year =         2023,
  journal =      popets,
  number =       1,
  doi =          "10.56553/popets-2023-0025",
}

@book{10.5555/1618542,
  author =       {Dybvig, R. Kent},
  title =        {The Scheme Programming Language, 4th Edition},
  year =         2009,
  isbn =         {026251298X},
  publisher =    {The MIT Press},
  edition =      {4th},
  abstract =     {Scheme is a general-purpose programming language, descended
                  from Algol and Lisp, widely used in computing education and
                  research and a broad range of industrial applications. This
                  thoroughly updated edition of The Scheme Programming Language
                  provides an introduction to Scheme and a definitive reference
                  for standard Scheme, presented in a clear and concise
                  manner. Written for professionals and students with some prior
                  programming experience, it begins by leading the programmer
                  gently through the basics of Scheme and continues with an
                  introduction to some of the more advanced features of the
                  language. The fourth edition has been substantially revised
                  and expanded to bring the content up to date with the current
                  Scheme standard, the Revised6 Report on Scheme. All parts of
                  the book were updated and three new chapters were added,
                  covering the language's new library, exception handling, and
                  record-definition features. The book offers three chapters of
                  introductory material with numerous examples, eight chapters
                  of reference material, and one chapter of extended examples
                  and additional exercises. All of the examples can be entered
                  directly from the keyboard into an interactive Scheme
                  session. Answers to many of the exercises, a complete formal
                  syntax of Scheme, and a summary of forms and procedures are
                  provided in appendixes. The Scheme Programming Language is the
                  only book available that serves both as an introductory text
                  in a variety of courses and as an essential reference for
                  Scheme programmers.}
}

@Misc{EPRINT:BreHeb24,
  author =       "Théophile Brézot and Chloé Hébant",
  title =        "Findex: {A} Concurrent and Database-Independent Searchable
                  Encryption Scheme",
  year =         2024,
  howpublished = "Cryptology ePrint Archive, Report 2024/1541",
  url =          "https://eprint.iacr.org/2024/1541",
}

@inproceedings{Hoeffding1963probabilityif,
  title =        {Probability inequalities for sum of bounded random variables},
  author =       {Wassily Hoeffding},
  year =         1963,
  url =          {https://api.semanticscholar.org/CorpusID:121341745}
}

@article{chernoff_1952,
  title =        {A Measure of Asymptotic Efficiency for Tests of a Hypothesis
                  Based on the sum of Observations},
  volume =       23,
  DOI =          {10.1214/aoms/1177729330},
  publisher =    {Institute of Mathematical Statistics},
  author =       {Chernoff},
  year =         1952
}

@inproceedings{chase2010structured,
  author =       {Chase, Melissa and Kamara, Seny},
  title =        {Structured Encryption and Controlled Disclosure},
  series =       {Lecture Notes in Computer Science},
  booktitle =    {Advances in Cryptology - ASIACRYPT 2010},
  year =         {2010},
  month =        {December},
  publisher =    {Springer Verlag},
  pages =        {577-594},
  volume =       {6477},
  edition =      {Advances in Cryptology - ASIACRYPT 2010},
}

@inproceedings{10.1145/1180405.1180417,
  author =       {Curtmola, Reza and Garay, Juan and Kamara, Seny and Ostrovsky,
                  Rafail},
  title =        {Searchable symmetric encryption: improved definitions and
                  efficient constructions},
  year =         {2006},
  isbn =         {1595935185},
  publisher =    {Association for Computing Machinery},
  address =      {New York, NY, USA},
  doi =          {10.1145/1180405.1180417},
  booktitle =    {Proceedings of the 13th ACM Conference on Computer and
                  Communications Security},
  pages =        {79–88},
  numpages =     {10},
  keywords =     {multi-user, searchable encryption, searchable symmetric
                  encryption, security definitions},
  location =     {Alexandria, Virginia, USA},
  series =       {CCS '06}
}

@inproceedings{10.1145/2976749.2978303,
  author =       {Bost, Raphael},
  title =        {∑oφoς: Forward Secure Searchable Encryption},
  year =         {2016},
  isbn =         {9781450341394},
  publisher =    {Association for Computing Machinery},
  address =      {New York, NY, USA},
  url =          {https://doi.org/10.1145/2976749.2978303},
  doi =          {10.1145/2976749.2978303},
  abstract =     {Searchable Symmetric Encryption aims at making possible
                  searching over an encrypted database stored on an untrusted
                  server while keeping privacy of both the queries and the data,
                  by allowing some small controlled leakage to the
                  server. Recent work shows that dynamic schemes -- in which the
                  data is efficiently updatable -- leaking some information on
                  updated keywords are subject to devastating adaptative attacks
                  breaking the privacy of the queries. The only way to thwart
                  this attack is to design forward private schemes whose update
                  procedure does not leak if a newly inserted element matches
                  previous search queries.This work proposes Sophos as a forward
                  private SSE scheme with performance similar to existing less
                  secure schemes, and that is conceptually simpler (and also
                  more efficient) than previous forward private
                  constructions. In particular, it only relies on trapdoor
                  permutations and does not use an ORAM-like construction. We
                  also explain why Sophos is an optimal point of the
                  security/performance tradeoff for SSE.Finally, an
                  implementation and evaluation results demonstrate its
                  practical efficiency.},
  booktitle =    {Proceedings of the 2016 ACM SIGSAC Conference on Computer and
                  Communications Security},
  pages =        {1143–1154},
  numpages =     {12},
  keywords =     {searchable symmetric encryption, provable security,
                  implementation, forward privacy},
  location =     {Vienna, Austria},
  series =       {CCS '16}
}

@inproceedings{10.1145/3319535.3354213,
  author =       {Patel, Sarvar and Persiano, Giuseppe and Yeo, Kevin and Yung,
                  Moti},
  title =        {Mitigating Leakage in Secure Cloud-Hosted Data Structures:
                  Volume-Hiding for Multi-Maps via Hashing},
  year =         {2019},
  isbn =         {9781450367479},
  publisher =    {Association for Computing Machinery},
  address =      {New York, NY, USA},
  url =          {https://doi.org/10.1145/3319535.3354213},
  doi =          {10.1145/3319535.3354213},
  abstract =     {Volume leakage has recently been identified as a major threat
                  to the security of cryptographic cloud-based data structures
                  by Kellaris em et al. [CCS'16] (see also the attacks in Grubbs
                  em et al. [CCS'18] and Lacharit\'{e} em et al. [S&P'18]). In
                  this work, we focus on volume-hiding implementations of em
                  encrypted multi-maps as first considered by Kamara and Moataz
                  [Eurocrypt'19]. Encrypted multi-maps consist of outsourcing
                  the storage of a multi-map to an untrusted server, such as a
                  cloud storage system, while maintaining the ability to perform
                  private queries. Volume-hiding encrypted multi-maps ensure
                  that the number of responses (volume) for any query remains
                  hidden from the adversarial server. As a result, volume-hiding
                  schemes can prevent leakage attacks that leverage the
                  adversary's knowledge of the number of query responses to
                  compromise privacy. We present both conceptual and algorithmic
                  contributions towards volume-hiding encrypted multi-maps. We
                  introduce the first formal definition of volume-hiding leakage
                  functions. In terms of design, we present the first
                  volume-hiding encrypted multi-map dprfMM whose storage and
                  query complexity are both asymptotically optimal. Furthermore,
                  we experimentally show that our construction is practically
                  efficient. Our server storage is smaller than the best
                  previous construction while we improve query complexity by a
                  factor of 10-16x. In addition, we introduce the notion of
                  differentially private volume-hiding leakage functions which
                  strikes a better, tunable balance between privacy and
                  efficiency. To accompany our new notion, we present a
                  differentially private volume-hiding encrypted multi-map dpMM
                  whose query complexity is the volume of the queried key plus
                  an additional logarithmic factor. This is a significant
                  improvement compared to all previous volume-hiding schemes
                  whose query overhead was the maximum volume of any key. In
                  natural settings, our construction improves the average query
                  overhead by a factor of 150-240x over the previous best
                  volume-hiding construction even when considering small privacy
                  budget of ε=0.2.},
  booktitle =    {Proceedings of the 2019 ACM SIGSAC Conference on Computer and
                  Communications Security},
  pages =        {79–93},
  numpages =     {15},
  keywords =     {volume-hiding, privacy, encrypted search, cloud storage},
  location =     {London, United Kingdom},
  series =       {CCS '19}
}

@inproceedings{10.1145/3133956.3133980,
  author =       {Bost, Rapha\"{e}l and Minaud, Brice and Ohrimenko, Olga},
  title =        {Forward and Backward Private Searchable Encryption from
                  Constrained Cryptographic Primitives},
  year =         {2017},
  isbn =         {9781450349468},
  publisher =    {Association for Computing Machinery},
  address =      {New York, NY, USA},
  url =          {https://doi.org/10.1145/3133956.3133980},
  doi =          {10.1145/3133956.3133980},
  abstract =     {Using dynamic Searchable Symmetric Encryption, a user with
                  limited storage resources can securely outsource a database to
                  an untrusted server, in such a way that the database can still
                  be searched and updated efficiently. For these schemes, it
                  would be desirable that updates do not reveal any information
                  a priori about the modifications they carry out, and that
                  deleted results remain inaccessible to the server a
                  posteriori. If the first property, called forward privacy, has
                  been the main motivation of recent works, the second one,
                  backward privacy, has been overlooked.In this paper, we study
                  for the first time the notion of backward privacy for
                  searchable encryption. After giving formal definitions for
                  different flavors of backward privacy, we present several
                  schemes achieving both forward and backward privacy, with
                  various efficiency trade-offs.Our constructions crucially rely
                  on primitives such as constrained pseudo-random functions and
                  puncturable encryption schemes. Using these advanced
                  cryptographic primitives allows for a fine-grained control of
                  the power of the adversary, preventing her from evaluating
                  functions on selected inputs, or decrypting specific
                  ciphertexts. In turn, this high degree of control allows our
                  SSE constructions to achieve the stronger forms of privacy
                  outlined above. As an example, we present a framework to
                  construct forward-private schemes from range-constrained
                  pseudo-random functions.Finally, we provide experimental
                  results for implementations of our schemes, and study their
                  practical efficiency.},
  booktitle =    {Proceedings of the 2017 ACM SIGSAC Conference on Computer and
                  Communications Security},
  pages =        {1465–1482},
  numpages =     {18},
  keywords =     {backward privacy, constrained prf, forward privacy,
                  puncturable encryption, searchable encryption},
  location =     {Dallas, Texas, USA},
  series =       {CCS '17}
}

@Article{PoPETS:BosFou19,
  author =       "Raphael Bost and
                  Pierre-Alain Fouque",
  title =        "Security-Efficiency Tradeoffs in Searchable Encryption",
  pages =        "132--151",
  volume =       2019,
  month =        oct,
  publisher =    degruyter,
  year =         2019,
  journal =      popets,
  number =       4,
  doi =          "10.2478/popets-2019-0062",
}

@inproceedings{10.1145/3548606.3560593,
  author =       {Kornaropoulos, Evgenios M. and Moyer, Nathaniel and
                  Papamanthou, Charalampos and Psomas, Alexandros},
  title =        {Leakage Inversion: Towards Quantifying Privacy in Searchable
                  Encryption},
  year =         {2022},
  isbn =         {9781450394505},
  publisher =    {Association for Computing Machinery},
  address =      {New York, NY, USA},
  url =          {https://doi.org/10.1145/3548606.3560593},
  doi =          {10.1145/3548606.3560593},
  abstract =     {Searchable encryption (SE) provides cryptographic guarantees
                  that a user can efficiently search over encrypted data while
                  only disclosing patterns about the data, also known as
                  leakage. Recently, the community has developed leakage-abuse
                  attacks that shed light on what an attacker can infer about
                  the underlying sensitive information using the aforementioned
                  leakage. A glaring missing piece in this effort is the absence
                  of a systematic and rigorous method that quantifies the
                  privacy guarantees of SE.In this work, we put forth the notion
                  of leakage inversion that quantifies privacy in SE. Our
                  insight is that the leakage is a function and, thus, one can
                  define its inverse which corresponds to the collection of
                  databases that reveal structurally equivalent patterns to the
                  original plaintext database. We call this collection of
                  databases the reconstruction space and we rigorously study its
                  properties that impact the privacy of an SE scheme such as the
                  entropy of the reconstruction space and the distance of its
                  members from the original plaintext database. Leakage
                  inversion allows for a foundational algorithmic analysis of
                  the privacy offered by SE and we demonstrate this by defining
                  closed-form expressions and lower/upper bounds on the
                  properties of the reconstruction space for both keyword-based
                  and range-based databases. We use leakage inversion in three
                  scenarios: (i) we quantify the impact that auxiliary
                  information, a typical cryptanalytic assumption, has to the
                  overall privacy, (ii) we quantify how privacy is affected in
                  case of restricting range schemes to respond to a limited
                  number of queries, and (iii) we study the efficiency
                  vs. privacy trade-off offered by proposed padding defenses. We
                  use real-world databases in all three scenarios and we draw
                  theoretically-grounded new insights about the interplay
                  between leakage, attacks, defenses, and efficiency.},
  booktitle =    {Proceedings of the 2022 ACM SIGSAC Conference on Computer and
                  Communications Security},
  pages =        {1829–1842},
  numpages =     {14},
  keywords =     {searchable encryption, quantifying metric, privacy, encrypted
                  databases},
  location =     {Los Angeles, CA, USA},
  series =       {CCS '22}
}

@article{10.1145/3177872,
  author =       {Stefanov, Emil and Dijk, Marten Van and Shi, Elaine and Chan,
                  T.-H. Hubert and Fletcher, Christopher and Ren, Ling and Yu,
                  Xiangyao and Devadas, Srinivas},
  title =        {Path ORAM: An Extremely Simple Oblivious RAM Protocol},
  year =         {2018},
  issue_date =   {August 2018},
  publisher =    {Association for Computing Machinery},
  address =      {New York, NY, USA},
  volume =       {65},
  number =       {4},
  issn =         {0004-5411},
  url =          {https://doi.org/10.1145/3177872},
  doi =          {10.1145/3177872},
  abstract =     {We present Path ORAM, an extremely simple Oblivious RAM
                  protocol with a small amount of client storage. Partly due to
                  its simplicity, Path ORAM is the most practical ORAM scheme
                  known to date with small client storage. We formally prove
                  that Path ORAM has a O(log N) bandwidth cost for blocks of
                  size B = Ω (log2 N) bits. For such block sizes, Path ORAM is
                  asymptotically better than the best-known ORAM schemes with
                  small client storage. Due to its practicality, Path ORAM has
                  been adopted in the design of secure processors since its
                  proposal.},
  journal =      {J. ACM},
  month =        apr,
  articleno =    {18},
  numpages =     {26},
  keywords =     {access pattern, Path ORAM, Oblivious RAM, ORAM}
}

@InProceedings{NDSS:DCPP20,
  author =       "Ioannis Demertzis and Javad Ghareh Chamani and Dimitrios
                  Papadopoulos and Charalampos Papamanthou",
  title =        "Dynamic Searchable Encryption with Small Client Storage",
  booktitle =    ndss20name,
  address =      ndss20addr,
  month =        ndss20month,
  publisher =    ndsspub_v2,
  year =         2020,
  doi =          "10.14722/ndss.2020.24423",
}

@InProceedings{10.1007/3-540-49543-6_13,
  author =       "Raab, Martin and Steger, Angelika",
  editor =       "Luby, Michael and Rolim, Jos{\'e} D. P.  and Serna, Maria",
  title =        "``Balls into Bins'' --- A Simple and Tight Analysis",
  booktitle =    "Randomization and Approximation Techniques in Computer
                  Science",
  year =         "1998",
  publisher =    "Springer Berlin Heidelberg",
  address =      "Berlin, Heidelberg",
  pages =        "159--170",
  abstract =     "Suppose we sequentially throw m balls into n bins. It is a
                  natural question to ask for the maximum number of balls in any
                  bin. In this paper we shall derive sharp upper and lower
                  bounds which are reached with high probability. We prove
                  bounds for all values of m(n) ≧ n/polylog(n) by using the
                  simple and well-known method of the first and second moment.",
  isbn =         "978-3-540-49543-7"
}