More Like this

1. Minimum Membership Covering and Hitting

   https://doi.org/10.1016/j.tcs.2021.05.002  

   Mitchell, Joseph S.B. ; Pandit, Supantha ( July 2021 , Theoretical Computer Science)

   null (Ed.)
2. Credibility in Private Set Membership

   https://doi.org/10.1007/978-3-031-31371-4_6  

   Garg, Sanjam ; Hajibadi, Mohammad ; Jain, Abhishek ; Jin, Zhengzhong ; Pandey, Omkant ; Shiehian, Sina ( January 2023 , Public Key Cryptography -- PKC 2023)
3. Credibility in Private Set Membership

   https://doi.org/10.1007/978-3-031-31371-4_6  

   Garg, S. ; Hajiabadi, M. ; Jain, A. ; Jin, Z. ; Pandey, O. ; Shiehian, S. ( May 2023 , Public-Key Cryptography (PKC 2023))

   Boldyreva, A. ; Kolesnikov, V. (Ed.)

   A private set membership (PSM) protocol allows a “receiver” to learn whether its input x is contained in a large database 𝖣𝖡 held by a “sender”. In this work, we define and construct credible private set membership (C-PSM) protocols: in addition to the conventional notions of privacy, C-PSM provides a soundness guarantee that it is hard for a sender (that does not know x) to convince the receiver that 𝑥∈𝖣𝖡. Furthermore, the communication complexity must be logarithmic in the size of 𝖣𝖡. We provide 2-round (i.e., round-optimal) C-PSM constructions based on standard assumptions: We present a black-box construction in the plain model based on DDH or LWE. Next, we consider protocols that support predicates f beyond string equality, i.e., the receiver can learn if there exists 𝑤∈𝖣𝖡 such that 𝑓(𝑥,𝑤)=1. We present two results with transparent setups: (1) A black-box protocol, based on DDH or LWE, for the class of NC1 functions f which are efficiently searchable. (2) An LWE-based construction for all bounded-depth circuits. The only non-black-box use of cryptography in this construction is through the bootstrapping procedure in fully homomorphic encryption. As an application, our protocols can be used to build enhanced round-optimal leaked password notification services, where unlike existing solutions, a dubious sender cannot fool a receiver into changing its password. https://doi.org/10.1007/978-3-031-31371-4_6 

   more » « less
4. Revisiting Membership Inference Under Realistic Assumptions

   https://doi.org/10.2478/popets-2021-0031  

   Jayaraman, Bargav ; Wang, Lingxiao ; Knipmeyer, Katherine ; Gu, Quanquan ; Evans, David ( January 2021 , Proceedings on Privacy Enhancing Technologies)

   Abstract We study membership inference in settings where assumptions commonly used in previous research are relaxed. First, we consider cases where only a small fraction of the candidate pool targeted by the adversary are members and develop a PPV-based metric suitable for this setting. This skewed prior setting is more realistic than the balanced prior setting typically considered. Second, we consider adversaries that select inference thresholds according to their attack goals, such as identifying as many members as possible with a given false positive tolerance. We develop a threshold selection designed for achieving particular attack goals. Since previous inference attacks fail in imbalanced prior settings, we develop new inference attacks based on the intuition that inputs corresponding to training set members will be near a local minimum in the loss function. An attack that combines this with thresholds on the per-instance loss can achieve high PPV even in settings where other attacks are ineffective. 

   more » « less
5. Local Testing for Membership in Lattices

   https://doi.org/10.4230/LIPIcs.FSTTCS.2016.46  

   Chandrasekaran, K. ; Cheraghchi, M. ; Gandikota, V. ; Grigorescu, E. ( December 2016 , FSTTCS)

   Testing membership in lattices is of practical relevance, with applications to integer programming, error detection in lattice-based communication and cryptography. In this work, we initiate a systematic study of {\em local testing} for membership in lattices, complementing and building upon the extensive body of work on locally testable codes. In particular, we formally define the notion of local tests for lattices and present the following: \begin{enumerate} \item We show that in order to achieve low query complexity, it is sufficient to design one-sided non-adaptive {\em canonical} tests. This result is akin to, and based on an analogous result for error-correcting codes due to Ben-Sasson \etal\ (SIAM J. Computing 35(1) pp1--21). \item We demonstrate upper and lower bounds on the query complexity of local testing for membership in {\em code formula} lattices. We instantiate our results for code formula lattices constructed from Reed-Muller codes to obtain nearly-matching upper and lower bounds on the query complexity of testing such lattices. \item We contrast lattice testing from code testing by showing lower bounds on the query complexity of testing low-dimensional lattices. This illustrates large lower bounds on the query complexity of testing membership in {\em knapsack lattices}. On the other hand, we show that knapsack lattices with bounded coefficients have low-query testers if the inputs are promised to lie in the span of the lattice. \end{enumerate} 

   more » « less