publications

2022

1. EUROCRYPT

   Batch-OT with Optimal Rate

   Zvika Brakerski, Pedro Branco, Nico Döttling, and Sihang Pu

   In Advances in Cryptology - EUROCRYPT 2022 - 41st Annual International Conference on the Theory and Applications of Cryptographic Techniques, Trondheim, Norway, May 30 - June 3, 2022, Proceedings, Part II 2022

   Abs eprint

   We show that it is possible to perform n independent copies of 1-out-of-2 oblivious transfer in two messages, where the communication complexity of the receiver and sender (each) is n(1+o(1)) for sufficiently large n. Note that this matches the information-theoretic lower bound. Prior to this work, this was only achievable by using the heavy machinery of rate-1 fully homomorphic encryption (Rate-1 FHE, Brakerski et al., TCC 2019). To achieve rate-1 both on the receiver’s and sender’s end, we use the LPN assumption, with slightly sub-constant noise rate 1/m^εfor any ε>0 together with either the DDH, QR or LWE assumptions. In terms of efficiency, our protocols only rely on linear homomorphism, as opposed to the FHE-based solution which inherently requires an expensive “bootstrapping” operation. We believe that in terms of efficiency we compare favorably to existing batch-OT protocols, while achieving superior communication complexity. We show similar results for Oblivious Linear Evaluation (OLE). For our DDH-based solution we develop a new technique that may be of independent interest. We show that it is possible to “emulate” the binary group Z2 (or any other small-order group) inside a prime-order group Zp in a function-private manner. That is, Z2 operations are mapped to Zp operations such that the outcome of the latter do not reveal additional information beyond the Z2 outcome. Our encoding technique uses the discrete Gaussian distribution, which to our knowledge was not done before in the context of DDH.

2021

1. TCC

   Laconic Private Set Intersection and Applications

   Navid Alamati, Pedro Branco, Nico Döttling, Sanjam Garg, Mohammad Hajiabadi, and Sihang Pu

   In Theory of Cryptography - 19th International Conference, TCC 2021, Raleigh, NC, USA, November 8-11, 2021, Proceedings, Part III 2021

   Abs eprint

   Consider a server with a large set S of strings x1, x2,..., xN that would like to publish a small hash h of its set S such that any client with a string y can send the server a short message allowing it to learn y if y ∈ S and nothing otherwise. In this work, we study this problem of two-round private set intersection (PSI) with low (asymptotically optimal) communication cost, or what we call laconic private set intersection (\ell PSI) and its extensions. This problem is inspired by the recent general frameworks for laconic cryptography [Cho et al. CRYPTO 2017, Quach et al. FOCS’18]. We start by showing the first feasibility result for realizing ‘PSI based on the CDH assumption, or LWE with polynomial noise-to-modulus ratio. However, these feasibility results use expensive non-blackbox cryptographic techniques leading to significant inefficiency. Next, with the goal of avoiding these inefficient techniques, we give a construction of \ell PSI schemes making only black-box use of cryptographic functions. Our construction is secure against semi-honest receivers, malicious senders and reusable in the sense that the receiver’s message can be reused across any number of executions of the protocol. The scheme is secure under the φ-hiding, decisional composite residuosity and subgroup decision assumptions. Finally, we show natural applications of \ellPSI to realizing a semantically-secure encryption scheme that supports detection of encrypted messages belonging to a set of “illegal” messages (e.g., an illegal video) circulating online. Over the past few years, significant effort has gone into realizing laconic cryptographic protocols. Nonetheless, our work provides the first black-box constructions of such protocols for a natural application setting.

2. PKC

   Multiparty Cardinality Testing for Threshold Private Set Intersection

   Pedro Branco, Nico Döttling, and Sihang Pu

   In Public-Key Cryptography - PKC 2021 - 24th IACR International Conference on Practice and Theory of Public Key Cryptography, Virtual Event, May 10-13, 2021, Proceedings, Part II 2021

   Abs eprint

   Threshold Private Set Intersection (PSI) allows multiple parties to compute the intersection of their input sets if and only if the intersection is larger than n-t, where n is the size of each set and t is some threshold. The main appeal of this primitive is that, in contrast to standard PSI, known upper-bounds on the communication complexity only depend on the threshold t and not on the sizes of the input sets. Current threshold PSI protocols split themselves into two components: A Cardinality Testing phase, where parties decide if the intersection is larger than some threshold; and a PSI phase, where the intersection is computed. The main source of inefficiency of threshold PSI is the former part. In this work, we present a new Cardinality Testing protocol that allows N parties to check if the intersection of their input sets is larger than n-t. The protocol incurs in O(Nt^2) communication complexity. We thus obtain a Threshold PSI scheme for N parties with communication complexity O(Nt^2).

2020

1. ASIACRYPT

   A Combinatorial Approach to Quantum Random Functions

   Nico Döttling, Giulio Malavolta, and Sihang Pu

   In Advances in Cryptology - ASIACRYPT 2020 - 26th International Conference on the Theory and Application of Cryptology and Information Security, Daejeon, South Korea, December 7-11, 2020, Proceedings, Part II 2020

   Abs eprint

   Quantum pseudorandom functions (QPRFs) extend the classical security of a PRF by allowing the adversary to issue queries on input superpositions. Zhandry [Zhandry, FOCS 2012] showed a separation between the two notions and proved that common construction paradigms are also quantum secure, albeit with a new ad-hoc analysis. In this work we revisit the question of constructing QPRFs and propose a new method starting from small-domain (classical) PRFs: At the heart of our approach is a new domain-extension technique based on bipartite expanders. Interestingly, our analysis is almost entirely classical. As a corollary of our main theorem, we obtain the first (approximate) key-homomorphic quantum PRF based on the quantum intractability of the learning with errors problem.

2017

1. CARDIS

   Trace Augmentation: What Can Be Done Even Before Preprocessing in a Profiled SCA

   Sihang Pu, Yu Yu, Weijia Wang, Zheng Guo, Junrong Liu, Dawu Gu, Lingyun Wang, and Jie Gan

   In Smart Card Research and Advanced Applications - 16th International Conference, CARDIS 2017, Lugano, Switzerland, November 13-15, 2017, Revised Selected Papers 2017

   Abs

   Preprocessing is an important first step in side-channel attacks, especially for template attacks. Typical processing techniques, such as Principal Component Analysis (PCA) and Singular Spectrum Analysis (SSA), mainly aim to reduce noise and/or extract useful information from raw data, and they are barely robust to tolerate differences between profiling and target traces. In this paper, we propose an efficient and easy-to-implement approach to preprocessing by applying the data augmentation method from deep learning, whose appropriate parameters can be efficiently determined using a simple validation. Our trace augmentation method, when added prior to existing profiling methods, significantly enhances robustness and improves performance of the attacks. Simulation-based experiments show that our approach not only results in a more robust profiling (even show an enhancement to the known robust profilings), but also works well in the ideal scenario (no distortions between profiling and target traces). The results of FPGA-based and software experiments are consistent to the ones of simulation-based counterparts. Thus, we conclude that the proposed augmentation method is an efficient performance-boosting add-on to profiled side-channel attacks in real world

2016

1. CARDIS

   Inner Product Masking for Bitslice Ciphers and Security Order Amplification for Linear Leakages

   Weijia Wang, François-Xavier Standaert, Yu Yu,  Sihang Pu, Junrong Liu, Zheng Guo, and Dawu Gu

   In Smart Card Research and Advanced Applications - 15th International Conference, CARDIS 2016, Cannes, France, November 7-9, 2016, Revised Selected Papers 2016

   Abs PDF

   Designers of masking schemes are usually torn between the contradicting goals of maximizing the security gains while minimizing the performance overheads. Boolean masking is one extreme example of this tradeoff: its algebraic structure is as simple as can be (and so are its implementations), but it typically suffers more from implementation weaknesses. For example knowing one bit of each share is enough to know one bit of secret in this case. Inner product masking lies at the other side of this tradeoff: its algebraic structure is more involved, making it more expensive to implement (especially at higher orders), but it ensures stronger security guarantees. For example, knowing one bit of each share is not enough to know one bit of secret in this case. In this paper, we try to combine the best of these two worlds, and propose a new masking scheme mixing a single Boolean matrix product (to improve the algebraic complexity of the scheme) with standard additive Boolean masking (to allow efficient higher-order implementations). We show that such a masking is well suited for application to bitslice ciphers. We also conduct a comprehensive security analysis of the proposed scheme. For this purpose, we give a security proof in the probing model, and carry out an information leakage evaluation of an idealized implementation. For certain leakage functions, the latter exhibits surprising observations, namely information leakages in higher statistical moments than guaranteed by the proof in the probing model, which we can connect to the recent literature on low entropy masking schemes. We conclude the paper with a performance evaluation, which confirms that both for security and performance reasons, our new masking scheme (which can be viewed as a variation of inner product masking) compares favorably to state-of-the-art masking schemes for bitslice ciphers