More Like this

1. Amortizing Rate-1 OT and Applications to PIR and PSI

   https://doi.org/10.1007/978-3-030-90456-2_5  

   Chase, M. ; Garg, S. ; Hajiabadi, M. ; Li, J. ; Miao, P. ( November 2022 , 19th Theory of Cryptography Conference (TCC))

   Nissim, K. ; Waters, B. (Ed.)

   Recent new constructions of rate-1 OT [Döttling, Garg, Ishai, Malavolta, Mour, and Ostrovsky, CRYPTO 2019] have brought this primitive under the spotlight and the techniques have led to new feasibility results for private-information retrieval, and homomorphic encryption for branching programs. The receiver communication of this construction consists of a quadratic (in the sender's input size) number of group elements for a single instance of rate-1 OT. Recently [Garg, Hajiabadi, Ostrovsky, TCC 2020] improved the receiver communication to a linear number of group elements for a single string-OT. However, most applications of rate-1 OT require executing it multiple times, resulting in large communication costs for the receiver. In this work, we introduce a new technique for amortizing the cost of multiple rate-1 OTs. Specifically, based on standard pairing assumptions, we obtain a two-message rate-1 OT protocol for which the amortized cost per string-OT is asymptotically reduced to only four group elements. Our results lead to significant communication improvements in PSI and PIR, special cases of SFE for branching programs. - PIR: We obtain a rate-1 PIR scheme with client communication cost of $O(\lambda\cdot\log N)$ group elements for security parameter $\lambda$ and database size $N$. Notably, after a one-time setup (or one PIR instance), any following PIR instance only requires communication cost $O(\log N)$ number of group elements. - PSI with unbalanced inputs: We apply our techniques to private set intersection with unbalanced set sizes (where the receiver has a smaller set) and achieve receiver communication of $O((m+\lambda) \log N)$ group elements where $m, N$ are the sizes of the receiver and sender sets, respectively. Similarly, after a one-time setup (or one PSI instance), any following PSI instance only requires communication cost $O(m \cdot \log N)$ number of group elements. All previous sublinear-communication non-FHE based PSI protocols for the above unbalanced setting were also based on rate-1 OT, but incurred at least $O(\lambda^2 m \log N)$ group elements. 

   more » « less
2. Time-sliced quantum circuit partitioning for modular architectures

   https://doi.org/10.1145/3387902.3392617  

   Baker, Jonathan M. ; Duckering, Casey ; Hoover, Alexander ; Chong, Frederic T. ( May 2020 , CF '20: Proceedings of the 17th ACM International Conference on Computing Frontiers)

   Current quantum computer designs will not scale. To scale beyond small prototypes, quantum architectures will likely adopt a modular approach with clusters of tightly connected quantum bits and sparser connections between clusters. We exploit this clustering and the statically-known control flow of quantum programs to create tractable partitioning heuristics which map quantum circuits to modular physical machines one time slice at a time. Specifically, we create optimized mappings for each time slice, accounting for the cost to move data from the previous time slice and using a tunable lookahead scheme to reduce the cost to move to future time slices. We compare our approach to a traditional statically-mapped, owner-computes model. Our results show strict improvement over the static mapping baseline. We reduce the non-local communication overhead by 89.8% in the best case and by 60.9% on average. Our techniques, unlike many exact solver methods, are computationally tractable. 

   more » « less
3. (Private) Kernelized Bandits with Distributed Biased Feedback

   https://doi.org/10.1145/3579318  

   Li, Fengjiao ; Zhou, Xingyu ; Ji, Bo ( February 2023 , Proceedings of the ACM on Measurement and Analysis of Computing Systems)

   In this paper, we study kernelized bandits with distributed biased feedback. This problem is motivated by several real-world applications (such as dynamic pricing, cellular network configuration, and policy making), where users from a large population contribute to the reward of the action chosen by a central entity, but it is difficult to collect feedback from all users. Instead, only biased feedback (due to user heterogeneity) from a subset of users may be available. In addition to such partial biased feedback, we are also faced with two practical challenges due to communication cost and computation complexity. To tackle these challenges, we carefully design a new distributed phase-then-batch-based elimination (DPBE) algorithm, which samples users in phases for collecting feedback to reduce the bias and employs maximum variance reduction to select actions in batches within each phase. By properly choosing the phase length, the batch size, and the confidence width used for eliminating suboptimal actions, we show that DPBE achieves a sublinear regret of ~O(T1-α/2 +√γT T), where α ∈ (0,1) is the user-sampling parameter one can tune. Moreover, DPBE can significantly reduce both communication cost and computation complexity in distributed kernelized bandits, compared to some variants of the state-of-the-art algorithms (originally developed for standard kernelized bandits). Furthermore, by incorporating various differential privacy models (including the central, local, and shuffle models), we generalize DPBE to provide privacy guarantees for users participating in the distributed learning process. Finally, we conduct extensive simulations to validate our theoretical results and evaluate the empirical performance. 

   more » « less
4. Computational screening of chemically active metal center in coordinated dipyridyl tetrazine network

   https://doi.org/10.1088/1361-648X/acb8f3  

   Din, Naseem Ud ; Le, Duy ; Rahman, Talat S. ( February 2023 , Journal of Physics: Condensed Matter)

   Creation, stabilization, characterization, and control of single transition metal (TM) atoms may lead to significant advancement of the next-generation catalyst. Metal organic network (MON) in which single TM atoms are coordinated and separated by organic ligands is a promising class of material that may serve as a single atom catalyst. Our density functional theory-based calculations of MONs in which dipyridyl tetrazine (DPTZ) ligands coordinate with a TM atom to form linear chains leads to two types of geometries of the chains. Those with V, Cr, Mo, Fe, Co, Pt, or Pd atoms at the coordination center are planar while those with Au, Ag, Cu, or Ni are non-planar. The formation energies of the chains are high (∼2.0–7.9 eV), suggesting that these MON can be stabilized. Moreover, the calculated adsorption energies of CO and O₂on the metal atom at center of the chains with the planar configuration lie in the range 1.0–3.0 eV for V, Cr, Mo, Fe, and Co at the coordination center, paving the way for future studies of CO oxidation on TM-DPTZ chains with the above five atoms at the coordination center.

    

   more » « less
5. A Differentially Private Incentive Design for Traffic Offload to Public Transportation

   https://doi.org/10.1145/3430847  

   Niu, Luyao ; Clark, Andrew ( January 2021 , ACM Transactions on Cyber-Physical Systems)

   Increasingly large trip demands have strained urban transportation capacity, which consequently leads to traffic congestion and rapid growth of greenhouse gas emissions. In this work, we focus on achieving sustainable transportation by incentivizing passengers to switch from private cars to public transport. We address the following challenges. First, the passengers incur inconvenience costs when changing their transit behaviors due to delay and discomfort, and thus need to be reimbursed. Second, the inconvenience cost, however, is unknown to the government when choosing the incentives. Furthermore, changing transit behaviors raises privacy concerns from passengers. An adversary could infer personal information (e.g., daily routine, region of interest, and wealth) by observing the decisions made by the government, which are known to the public. We adopt the concept of differential privacy and propose privacy-preserving incentive designs under two settings, denoted as two-way communication and one-way communication. Under two-way communication, passengers submit bids and then the government determines the incentives, whereas in one-way communication, the government simply sets a price without acquiring information from the passengers. We formulate the problem under two-way communication as a mixed integer linear program and propose a polynomial-time approximation algorithm. We show the proposed approach achieves truthfulness, individual rationality, social optimality, and differential privacy. Under one-way communication, we focus on how the government should design the incentives without revealing passengers’ inconvenience costs while still preserving differential privacy. We formulate the problem as a convex program and propose a differentially private and near-optimal solution algorithm. A numerical case study using the Caltrans Performance Measurement System (PeMS) data source is presented as evaluation. The results show that the proposed approaches achieve a win-win situation in which both the government and passengers obtain non-negative utilities. 

   more » « less