Elette Boyle
email: eboyle@alum.mit.edu

Geoffroy Couteau
email: cnrs.couteau@irif.fr

Pierre Meyer
email: pierre.meyer@irif.fr

Sublinear Secure Computation from New Assumptions

Keywords: Foundations, Private Information Retrieval, Secure Multiparty Computation

Secure computation enables mutually distrusting parties to jointly compute a function on their secret inputs, while revealing nothing beyond the function output. A long-running challenge is understanding the required communication complexity of such protocols-in particular, when communication can be sublinear in the circuit representation size of the desired function. For certain functions, such as Private Information Retrieval (PIR), this question extends to even sublinearity in the input size. We develop new techniques expanding the set of computational assumptions for sublinear communication in both settings:

-Circuit size. We present sublinear-communication protocols for secure evaluation of general layered circuits, given any 2-round rate-1 batch oblivious transfer (OT) protocol with a particular "decomposability" property. In particular, this condition can be shown to hold for the recent batch OT protocols of (Brakerski et al. Eurocrypt 2022), in turn yielding a new sublinear secure computation feasibility: from Quadratic Residuosity (QR) together with polynomialnoise-rate Learning Parity with Noise (LPN).

Our approach constitutes a departure from existing paths toward sublinear secure computation, all based on fully homomorphic encryption or homomorphic secret sharing. -Input size. We construct single-server PIR based on the Computational Diffie-Hellman (CDH) assumption, with polylogarithmic communication in the database input size n. Previous constructions from CDH required communication Ω(n). In hindsight, our construction comprises of a relatively simple combination of existing tools from the literature.

Introduction

Secure computation enables mutually distrusting parties to jointly compute a function on their secret inputs, while revealing nothing beyond the function output. We focus on the case of two-party computation with semi-honest (passive) security. Since the seminal feasibility results of the 1980s [Yao86, GMW87, BGW88,CCD88], a major challenge in the area of secure computation has been if and when it is possible to break the "circuit-size barrier." This barrier refers to the fact that all classical techniques for secure computation required a larger amount of communication than the size of a boolean circuit representing the function to be computed. In contrast, insecure computation only requires exchanging the inputs, which are usually considerably smaller than the entire circuit.

Early positive results with sublinear communication either required exponential computation [BFKR91, NN01], or (as discussed later) were limited to very simple functions such as point functions [CGKS95, KO97, CG97] or constantdepth circuits [BI05].

Beyond the circuit-size barrier. This situation changed with the breakthrough result of Gentry [Gen09] on fully homomorphic encryption (FHE). FHE is a powerful primitive supporting computation on encrypted data, which can be used to build optimal-communication protocols in the computational setting [DFH12, AJL + 12], by having parties perform the desired computation locally on encrypted inputs without additional communication. However, despite significant efforts, the set of assumptions under which we know how to build FHE is very narrow. Standard approaches are restricted to lattice-based assumptions, such as Learning With Errors (LWE), and in particular do not include any of the traditional assumptions which were used in the 20th century. Very recent developments in indistinguishability obfuscation imply results based on an alternative (relatively exotic) bundle of assumptions [CLTV15, JLS22]. 4The work of [BGI16] first showed that secure computation with communication sublinear in the circuit size could also be based on assumptions not known to imply FHE, via a new primitive of homomorphic secret sharing (HSS). HSS can be viewed as a relaxation of FHE, where homomorphic evaluation can be distributed among two parties who do not interact with each other. More concretely, from the Decisional Diffie-Hellman (DDH) assumption, [BGI16] constructed a form of HSS for branching programs (including N C 1 ), implying secure computation for the corresponding function class with asymptotically optimal communication. In turn, this was shown to yield secure computation for general layered circuits5 of size s with sublinear communication O(s/ log s), by evaluating in (log s)-depth blocks, and communicating only between blocks.

Since then, the HSS-based approach and variations have resulted in sublinearcommunication secure protocols from an additional assortment of assumptions. Following the [BGI16] blueprint, the works of [FGJI17,OSY21,RS21] were able to replace the DDH assumption with Decision Composite Residuosity (DCR). The framework was recently abstracted and extended to further algebraic structures, including a class of assumptions based on class groups of imaginary quadratic fields [ADOS22]. In addition, the work of [CM21] built HSS for log log-depth circuits (yielding O(s/ log log s) communication secure computation for layered circuits) based on a strong flavor of the Learning Parity with Noise (LPN) assumption: with a small number of samples, but assuming super-polynomial hardness, with inverse-superpolynomial noise rate.

To date, these two approaches-FHE and HSS-still comprise the only known paths to sublinear-communication secure computation for general circuit classes, without resorting to superpolynomial computation or setup assumptions such as correlated randomness [IKM + 13, DNNR17, Cou19]. It remains a motivated research agenda not only to continue expanding the set of distinct computational assumptions upon which sublinear secure computation can be built, but additionally of exploring new types of approaches toward this goal.

Private Information Retrieval. As mentioned, one exception to the above treatment is the special case of specific simple functionalities: most prominently, the task of Private Information Retrieval (PIR) [CGKS95,KO97]. A (single-server) PIR protocol roughly amounts to a secure computation protocol (with one-sided privacy) for the specific function f (x, i) = x i with x ∈ {0, 1} n and i ∈ [n]. Unlike the case of general computation (where the communication complexity of the underlying function may be Ω(n) even without security), PIR can admit secure protocols with communication sublinear (even polylogarithmic) in the input size.

For many years, protocols for PIR with polylogarithmic communication in n were known only from the Decisional Composite Residuosity (DCR), Learning with Errors (LWE), or Phi-hiding assumptions [CMS99, Cha04,Lip05,OS07]. More recently, such constructions were achieved from Quadratic Residuosity (QR), or Decisional Diffie-Hellman (DDH) [DGI + 19].

Our Results

We present new approaches and techniques for both of the above settings, ultimately extending the set of computational assumptions under which we can achieve sublinear-communication secure computation protocols.

Our results fall within two primary categories:

-We obtain (slightly) sublinear secure two-party computation for general layered circuits, through a new path of low-communication batch oblivious transfer. -We explore the specific goal of Private Information Retrieval (PIR), and provide a new construction with polylogarithmic communication based on Computational Diffie-Hellman (CDH).

We emphasize that our protocols execute in polynomial runtime, and do not rely on any correlated randomness assumptions.

Sublinear 2PC for layered circuits. We present a new approach toward secure two-party computation protocols for general layered circuits, with communication complexity that scales sublinearly in the circuit size. As opposed to building FHE or HSS, our approach begins with protocols for "batch Oblivious Transfer" with low communication.

Oblivious Transfer (OT) is an atomic functionality in which sender and receiver parties begin with inputs m 0 , m 1 ∈ {0, 1} and b ∈ {0, 1}, respectively; at the conclusion the receiver learns the selected message m b ; and neither party learns further information about one another's inputs. OT was shown to be a complete functionality for general secure computation [Kil00], where OT protocol execution(s) take place for each nonlinear gate of the corresponding circuit.

OT protocols are known from a number of standard assumptions, in just two rounds of communication (i.e., one message from receiver to sender, and one message in return); but, the communication complexity for all such solutions is (inherently) significantly larger than the input size. Very recently, it was shown by Brakerski et al. [BBDP22] how to achieve a batched version of OT, still in two rounds, and with rate-1 communication. That is, for a collection of message pairs ({m

(i) 0 , m (i) 1 }) i∈[k] and selection bits (b (i) ) i∈[k]
, a sender and receiver could perform k parallel batched executions of OT in communication roughly k.

We prove that any such protocol which satisfies an additional decomposability property suffices to imply secure computation protocols for general layered circuits with sublinear communication complexity. To define decomposability, consider the communication structure of any 2-round rate-1 batch OT protocol. In the first round, the receiver sends k + o(k) bits to the sender,6 somehow encoding its selection bits b (i) . In response, the sender performs some computation as a function of its message pairs {m

(i) 0 , m (i)
1 }, and returns k + o(k) bits in response, somehow encoding the k selected messages, m (i) b (i) . For the constructions of [BBDP22], the sender's message size is just k + polylog(k).

We say that the (2-round, rate-1) batch OT protocol is decomposable if for any agreed subset S ⊂ [k] of indices, the sender can choose a corresponding subset of |S| + polylog(k) of its return message bits, such that sending this partial sender response reveals exactly the corresponding subset of selected messages (m (i) b (i) ) i∈S to the receiver. Namely, given the partial response, these |S| messages can be recovered, and no information is revealed about m

(i) b (i) for i / ∈ S.
Theorem 1 (Sublinear 2PC from Decomposable Batch OT -informal).

Assume existence of 2-round rate-1 batch OT with the above "decomposability" property. Then for any k, we can securely compute layered (synchronous) circuits of depth d and size s using poly(2 2 k , s) computation and O(2

2 k • d • poly(λ) + s/k) communication.
In particular, for k = O(log log s), we obtain communication O(s/ log log s + d 1/3 •s 2(1+ε)/3 •poly(λ)), for an arbitrary small constant ε. The latter is sublinear in s whenever d = o(s 1-ε /poly(λ)), i.e., the circuit is not too "tall and skinny". This decomposability property is not simply hypothetical, but rather was inspired by the batch-OT protocols of Brakerski et al. [BBDP22], which we show to satisfy the requirement. At a high level, the sender's message in their protocols consists of an encryption of the selected message bits (computed homomorphically as a function of receiver-sent ciphertexts of its selection bits, together with the message pairs {m + 19] to rate 1. The resulting rate-1 ciphertexts have the structure of a polylog(k)-size "header" string, independent of the messages, together with a single bit of information for each encrypted message bit. Decomposability thus follows (pseudo)directly, by simply omitting those information bits corresponding to encrypted messages the sender wishes to drop (i.e., [k] \ S). 7In turn, we obtain the following corollary.

(i) 0 , m (i) 1 }), compressed à la [DGI
Corollary 2 (Sublinear 2PC from QR+LPN -informal). The conclusion of Theorem 1 holds based on Quadratic Residuosity (QR) and Learning Parity with Noise (LPN) for any inverse-polynomial noise rate.

Our result is summarized on Table 1, where we also recall the state of the art in sublinear secure computation. We remark that while sublinear O(s/ log log s)communication protocols were known from a variant of LPN from [CM21], their result must assume superpolynomial hardness of LPN with a small inversesuperpolynomial error rate. In contrast, our result requires only polynomial hardness of LPN, with any inverse-polynomial error rate (as inherited by the construction of [BBDP22]).

We finally mention that this result is also not implied by the constructions of pseudorandom correlation functions (PCF) [BCG + 20] from QR+LPN of [OSY21] (or in fact any of the line of work on pseudorandom correlation generators (PCG) [BCG + 19]). While PCG/PCFs enable the generation of large quantities of random instances of OT with sublinear communication, the best known approaches for utilizing these random correlations within an actual secure computation protocol require communication that scales linearly with the circuit size.

Private Information Retrieval. Motivated by the goal of building decomposable rate-1 batch OT from new assumptions, we then turn to a deeper exploration of one of the required underlying components from the [BBDP22] batch OT construction: (single-server) Private Information Retrieval (PIR).

We succeed in constructing PIR with polylogarithmic communication from the Computational Diffie-Hellman assumption. While this is only one sub-component required to obtain the necessary batch OT from LPN+CDH,8 this provides one step toward this direction. But, more importantly, it constitutes a new feasibility result of its own right. From CDH, previously no PIR protocol was known with communication o(n). Theorem 3 (PIR from CDH -informal). Based on the Computational Diffie-Hellman (CDH) assumption, there exists single-server PIR on n-bit databases with communication polylog(n) and O(log(n)) rounds.

In hindsight, our construction forms a surprisingly simple and clean combination of two existing tools from the literature. Along the way, we identify an improved procedure for converting between a weak form of "semi-PIR" as considered in [BIP18], which reveals the client's queried index with some probability, to full-blown secure PIR. We refer the reader to the Technical Overview for more details.

Technical Overview

We assume familiarity with standard cryptographic assumptions such as QR, LPN, CDH, and DDH, and refer the reader to the full version for a formal statement of these assumptions.

Sublinear 2PC for Layered Circuits from Decomposable Batch OT

We consider Boolean circuits over any base of gates with fan-in two. Toward our sublinear 2PC result for layered circuits, we begin by focusing on circuits of low depth k (e.g., think of k = log log log s), and devise a secure protocol with communication n + m + (2 2 k • poly(λ)), for input size n, output size m, circuit size s, and security parameter λ. Given such a tool, we can appropriately divide a larger layered circuit into depth-k blocks where the sum of all block input and output sizes is s/k, and then iteratively compute (secret shares of) each layer output via the sub-protocol. Combined, this yields a secure computation for the layered circuit with overall communication O(s/k + 2 2 k • d • poly(λ)), as desired.

Starting point: An SPIR viewpoint. Consider a circuit with input size n, output size m, and low depth k. Given fan-in 2, each output bit is computed as a function of at most 2 k input bits. We may thus view the circuit output as dictated by m separate truth tables, each of size 2 2 k , indexed by the values of the corresponding relevant 2 k input bits. More concretely, think of one party as holding the (partially collapsed) truth tables incorporating its known inputs, and the second party as holding its own input string, dictating the relevant position of each truth table. We will refer to the first party as "sender" and second as "receiver."

Given this perspective, protocols for (Symmetric) Private Information Retrieval (SPIR) immediately come to mind. An SPIR protocol is a strengthened version of PIR, where the client additionally learns nothing beyond its queried value of the database. Secure computation of our circuit precisely amounts to m instances of SPIR, where the receiver party learns exactly the desired indexed values of the m truth tables.

However, the situation is not so simple: Even the best known (S)PIR protocols have communication polylogarithmic in the database size. Applying m instances of SPIR for the m outputs would thus yield communication polylog(2 k ) • m ∈ Ω(km), killing sublinearity.

In order to obtain sublinear communication, we must somehow leverage that the m SPIR instances are not completely independent, but rather are made with correlated queries. That is, although there are m instances each with (2 k )bit index values, the m•2 k selection bits have several repeats, collectively coming from different subsets of only n < m • 2 k input bits.

Toward batch SPIR with correlated queries. Our task becomes precisely to construct such an object: m-instance batch SPIR, with significantly lower communication complexity given correlated queries.

For purposes of discussion, suppose there existed a 2-round rate-1 protocol for oblivious transfer, where each sender and receiver (magically) sends only a single bit. Given access to such a tool, then by leveraging ideas from the literature (e.g., achieving PIR from linearly homomorphic encryption [KO97]), we would be set. Indeed, the receiver would simply send 1 bit for each input bit, corresponding to the first OT message using this value as a selector bit. These first messages could then be reused by the sender in multiple, recursive executions.

More concretely, suppose the server holds a database of N bits and that the receiver wants to retrieve the element stored at index x = (x 1 , . . . , x log N ). If the receiver sends a message otr 1 generated as its first-round OT-receiver message for the first bit x 1 of the desired index, the server can take the database, pair up elements whose indices differ only on the first bit, then apply the OT-server computation with respect to otr 1 on each pair in order to retrieve a single-bit response for each, creating a new "database" of half the number of elements, each corresponding to a 1-bit sender answer message. If instead the receiver sends messages (otr 1 , . . . , otr log N ), one for each bit of the desired index, the server can now iteratively compress the database down to a single bit by building a "Merkle tree" where in each recursive iteration corresponding to input index bit x i , the new "database" is split into pairs of messages whose indices differ only in this index, and performing the OT-server computation on each pair produces a new list of 1-bit sender answer messages of again half the length. At the conclusion, the server will be left with a single message value remaining, which by construction precisely enables the receiver to recover the target value stored at index x. This approach extends directly for m distinct databases with the same total receiver message (otr 1 , . . . , otr log N ), since the corresponding OTreceiver messages can be used independently in any mix and match format across databases. In turn, the sender would need to send only m total bits response, one bit for each database query.

Of course, unfortunately, we do not have such a strong rate-1 OT. We thus turn to the next closest alternative which does exist: 2-round rate-1 batch OT, as recently achieved by Brakerski et al. [BBDP22]. Batch OT considers a collection of message pairs ({m

(i) 0 , m (i) 1 }) i∈[ ] and selection bits (b (i) ) i∈[ ] ,
and enables a sender and receiver to perform parallel batched executions of OT with communication roughly . Attempting to apply the above strategy with rate-1 batch OT, however, poses significant challenges.

-The batching structure restricts the "mix and match" abilities of the sender when using the receiver's OT message. The sender must respond to the entire batched vector of receiver's selection bits at any stage, without freely accessing subsets of selection bits. Instead, the above approach involves using each selection bit b (i) within a different number (N/2 i ) of message pairs. -Even worse, the sender's (batch) response in general is only defined given all pairs of messages to be selected by the bits b (1) , . . . , b ( ) . In contrast, the above approach crucially relies on the ability to choose the message pairs for selection bit b (i) dynamically as a function of the server's responses given the previous selection bits b (1) , . . . , b (i-1) .

-Finally, it is no longer the case that for each selected message the sender has a single corresponding response bit. In fact, rate 1 here does not even mean that for instances that exactly bits are sent in each direction, but rather just asymptotically +o( ). This means that in each recursive OT execution, the sender's messages (and thus "database entry" size) may grow, leading to large growth and ultimately large communication upon further recursions.

Decomposable batch OT. With this motivation, we introduce the notion of decomposable (2-round, rate-1) batch oblivious transfer, which can be seen as a strengthening of two-round batch OT with constant upload-rate (i.e. the size of the receiver message is linear in the batch size ) and download-rate asymptotically one (i.e. the size of the sender message is + o( )). The differences boil down to a notion of decomposability which we impose on the sender message. At a high level, what we want to capture is the fact that the receiver should be able to retrieve the i th selected message in the batch if and only it also has access to the i th bit of the sender message (using its own internal state saved from generating the receiver message). More generally, given only a subset of the bits of the sender message, the receiver should able to retrieve the corresponding subset of selected messages in the batch.

Slightly more formally, we say that the (2-round, rate-1) batch OT protocol is decomposable if for any agreed subset S ⊂ [ ] of indices, the sender can choose a corresponding subset of |S| + polylog( ) of its return message bits, such that sending this partial sender response reveals exactly the corresponding subset of selected messages (m (i) b (i) ) i∈S to the receiver. Namely, given the partial response, these |S| messages can be recovered, and no information is revealed about m (i) b (i) for i / ∈ S. For our purposes, it will suffice to consider a relaxation of the notion we just described, and allow the sender message to have some small overhead rather than having a one-to-one correspondence between the bits on the sender message and the selected messages. In this relaxed form, we require that the sender message be comprised of two parts: a "reusable" part (of size o( )), and a "decomposable" part (of size ). On its own, the reusable part should reveal nothing about the messages, but can be used to "decode" each bit of the decomposable part so as to retrieve (exactly) the corresponding selected message in the batch. Among other benefits of this relaxation, it allows us to consider constructions whose download-rate is only asymptotically one. This decomposability property is not only enough for our needs, but perhaps more importantly, is achievable, in fact achieved by the batch OT constructions of [BBDP22]. Roughly speaking, the sender message in their construction is composed of a rate-1 encryption of the vector of requested message bits, with structure consisting of a short "header" independent of the message bits, together with a single ciphertext bit encoding each message bit separately. Decomposability can then be achieved by sending only those ciphertext bits encoding the desired subset of messages.

Slightly more accurately, this describes the situation for all but an inversepolynomial fraction of message bits (corresponding to noisy coordinates of an LPN ciphertext sent by the receiver), which actually encode the incorrect messages. In order to separately address these values, they employ a "co-PIR" (or "punctured OT" [BGI17]) to efficiently mask out the undesired values from the receiver, and a separate PIR to learn the correct values for these positions. The separate PIR query responses appear as part of the short "header" information of the server's response, which may sound like an issue, as this portion should not reveal information directly about any message bits. However, this problem does not occur, because the extra PIR queries are set up to actually reveal the difference between the masked-out incorrect message (r i ⊕ m 1-b ) and the target message m b . Because of the mask, this difference value (revealed in the header) provides no information about any message in the absence of the corresponding value (r i ⊕ m 1-b ) from the payload portion of the ciphertext, as required by decomposability. We refer the reader to Section 3.2 for further details.

Sublinear 2PC from decomposable batch OT. This decomposability property directly allows us to address one of the above challenges of batch OT: we will not have issues with exponential growth of the database entry size in the recursive OT executions. Instead, the result of one iteration of the batch OT on n inputs will result in a short o(n)-size header together with n bits that each provide information about a distinct queried message. The header string we will put to the side (ultimately we will send the collection of all the headers, which is still sufficiently short). The remaining n bits induce the recursive sender-message database that, as desired, consists of exactly 1 bit per message.

In fact, if we temporarily suppose that the assignment graph structure of n input bits to m = n output bits can be decomposed as the disjoint union of 2 k matchings, then we have a solution. Each disjoint matching will correspond directly to a different instance of n-input batch OT, where each of the n inputs is simultaneously used to index a different database. Applying the recursive solution as above, the sender will ultimately compute a single bit for each output, as well as a collection of header strings from each of the batch OT executions.

The remaining challenge is that general circuits do not have such nice regular structure, instead with inputs appearing in different numbers of output computations, with inconvenient correlations, demanding a stronger form of "mix and match" of batched OT queries beyond a direct approach.

To address this issue, we modify the structure of batch OT receiver queries, effectively extending the batch size (say from n to 2n), and employing a careful choice of how to pack extra copies of more highly influential input bits into the queried vector, so that the overall total number of batch OT instances remains sufficiently small that the overhead of extra header strings does not negatively impact the final communication complexity. We refer the reader to the technical body for a detailed treatment of this procedure.

Polylogarithmic PIR from CDH

We now turn our attention to our second contribution: private information retrieval with polylogarithmic communication from the computational Diffie-Hellman assumption. A private information retrieval (PIR) is a two party protocol between a server S holding a string z (the database) and a client C holding an integer i. At the end of the interaction, the client should learn z i , without revealing i to the server. A polylogarithmic PIR is a PIR where the total communication is poly(λ, log |z|), where λ is the security parameter.

Below, we sketch our approach to building polylogarithmic PIR from CDH. In hindsight, our construction is in fact relatively straightforward, and follows from an elegant combination of two recent results. We outline the sequence of implications below.

CDH Laconic PSI Half-PIR Random-index PIR PIR =⇒ =⇒ =⇒ =⇒ [ABD + 21] Lemma 19 Lemma 22 [GHM + 21]
Laconic PSI. A private set intersection protocol is a two-party protocol allowing a receiver to securely compute the intersection of its input set S R with the set S S of a sender: at the end of the protocol, the receiver learns S R ∩ S S and nothing more. A laconic PSI protocol, introduced in [ABD + 21], additionally enforces that the protocol is two-round (receiver to sender, then sender to receiver), and both the total communication and the sender runtime are bounded by poly(λ, log |S R |, |S S |). The work of [ABD + 21] showed that laconic PSI can be constructed from anonymous hash encryption, a primitive that can be constructed (in particular) from the CDH assumption [DG17b, DG17a, BLSV18].

From Laconic PSI to Half-PIR. Given a laconic PSI protocol, we exhibit a construction of polylogarithmic-communication PIR, using in addition a pseudorandom function. However, our construction only achieves a very weak form of security: it only guarantees that the index i is kept hidden from the server with probability 1/2. This notion, which we call half-PIR, has been introduced in [BIP18] (under the name Rand 1 2 PIR). It was shown in [BIP18] that polylogarithmic half-PIR already suffices to construct slightly sublinear PIR (with communication O(|z|/ log |z|)); looking ahead, we will provide a stronger reduction and show that it actually implies polylogarithmic PIR.

Our construction of half-PIR proceeds as follows: the client and the server agree on a PRF key K. The server with input z builds the set S R = {F K (1||z 1 ), • • • , F K (|z|||z |z| )}, and the client with input i builds the set S S = {F K (i||b)}, where b is a uniformly random bit. The core properties that this achieves are:

-If b = z i , then |S R ∩ S S | = 1 (note that |S S | = 1), and -If b = z i , then |S R ∩ S S | = 0 with high probability.
To show the second property, we rely on the security of the PRF to argue that a collision between PRF evaluations on distinct inputs is highly unlikely (provided the PRF outputs are large enough). Note, therefore, that we rely on the PRF security to argue the correctness of the construction (while this is slightly unusual, this kind of arguments has been used a few times in the literature). Now, the server and the client execute a laconic PSI, which has total communication poly(λ, log |z|) (since |S S | = 1). At the end of the protocol, the server, who plays the role of the receiver, sends |S R ∩ S S | to the client. Note that |S R ∩ S S | = (1 -b) ⊕ z i , hence the client can decode z i from this information. Yet, whenever |S R ∩ S S | = 0, the security of the laconic PSI implies that the server actually learns nothing about i: this guarantees client security with probability 1/2. When |S R ∩ S S | = 1, however, the server learns the intersection S R ∩ S S = F K (i||z i ), and can in particular retrieve i easily.

From Half-PIR to PIR. We now turn to constructing a polylogarithmic PIR from a polylogarithmic half-PIR. Here, our construction is mostly a simple observation: half-PIR implies random-index PIR via a straightforward construction. A random-index PIR, introduced in [GHM + 21], is a PIR protocol where the client has no input, and receives (i, z i ) where the index i is picked uniformly at random between 1 and |z|. Given a half-PIR, building a random-index PIR is almost immediate: the client and the server execute λ parallel instances of a half-PIR protocol, where the client uses uniformly random independent indices in each instance. With overwhelming probability, at least one of these instances will be secure (in the sense that the server does not learn the index); the client simply outputs (i * , z i * ) where i * is the index used in the first such execution.

Eventually, random-index PIR was recently shown in [GHM + 21] to imply full-fledged PIR, with a log |z| blowup in communication and round complexity. The key observation underlying this reduction is that a single invocation of a random-index PIR, together with sending log |z| bits, allows to reduce the task of executing a PIR on a size-|z| database to that of executing a PIR on a size-|z|/2 database. The construction follows by recursively invoking this construction (we provide a more detailed description of this construction in Section 4.3). Combining all these building blocks together leads to a logarithmicround, polylogarithmic-communication PIR from the CDH assumption.

3 Sublinear Computation for log log-Depth Circuits

Decomposable Two-Round Batch Oblivious Transfer

We introduce the notion of decomposable two-round batch oblivious transfer (definition 4), which can be seen as a strengthening of two-round batch OT with constant upload-rate and download-rate asymptotically one. The differences boil down to a notion of decomposability which we impose on the sender message, which should be comprised of a (small) reusable part and a linear-size decomposable part: the receiver should be able to retrieve the i th selected message in the batch if and only it also has access to the i th bit of the decomposable part of the sender message (along with the reusable part).

Definition 4 (Decomposable Two-Round Batch Oblivious Transfer). Let k ∈ N and α(•) = o(n). A semi-honest two-round decomposable batch OT protocol with α(•)-overhead between a sender and a receiver is defined as a triple of PPT algorithms dec-OT = (dec-OTR, dec-OTS, dec-OTD) with the following syntax and properties:

-Syntax.

dec-OTR : On input the security parameter 1 λ and a vector of selection bits b = (b 1 , . . . , b k ) ∈ {0, 1} k , dec-OTR outputs a receiver message otr ∈ {0, 1} O(k) and an internal state st; without loss of generality we assume that st contains all the random coins used by dec-OTR as well as b. dec-OTS : On input the security parameter 1 λ , a receiver message otr, and a database ((m

(i) 0 , m (i) 1 )) i∈[k] ∈ {0, 1} 2k
comprised of k pairs of bits, dec-OTS outputs a sender message ots = (ots , ots dec ), which is comprised of a reusable part ots ∈ {0, 1} α(k) and a decomposable part ots dec ∈ {0, 1} k . dec-OTD : On input a batch subset K ⊆ [k], a partial sender message ots ∈ {0, 1} α(k)+|K| , and an internal state st, dec-OTD outputs a vector of messages ( m i ) i∈K ∈ {0, 1} |K| .

-Decomposable Correctness. For every λ ∈ N , K ⊆ [k], every b = (b 1 , . . . , b k ) ∈ {0, 1} k , and every m = ((m

(i) 0 , m (i) 1 )) i∈[k] ∈ {0, 1} 2k , Pr   ( m 1 , . . . , m |K| ) = (m (i) bi ) i∈K : (otr, st) $ ← dec-OTR(1 λ , b) (ots , ots DB ) $ ← dec-OTS(1 λ , otr, m) ( m 1 , . . . , m |K| ) $ ← dec-OTD(K, (ots , [ots dec ] K ), st)    = 1 .
-Receiver Security (against Semi-Honest Sender). There exists an expected polynomial time simulator Sim S such that for every λ ∈ N and every

b = (b 1 , . . . , b k ) ∈ {0, 1} k , otr : (otr, st) $ ← dec-OTR(1 λ , b) c ≈ Sim S (1 λ ) .
-Decomposable Sender Security (against Semi-Honest Receiver).

There exists an expected polynomial time simulator Sim R such that for every

λ ∈ N , every K ⊆ [k], every b = (b 1 , . . . , b k ) ∈ {0, 1} k
, and every m = ((m

(i) 0 , m (i) 1 )) i∈[k] ∈ {0, 1} 2k , (ots , [ots dec ] K , otr, st) : (otr, st) $ ← dec-OTR(1 λ , b) (ots , ots BD ) $ ← dec-OTS(1 λ , otr, m) c ≈ (sim , sim dec , otr, st) : (otr, st) $ ← dec-OTR(1 λ , b) (sim , sim dec ) $ ← Sim R (1 λ , K, (m (i) bi ) i∈K , b, otr, st) .

Instantiation under QR + LPN, Adapted from [BBDP22]

As noted previously, two-round decomposable batch oblivious transfer can be seen as a strengthening of two-round batch OT with constant upload-rate and download-rate asymptotically one. As a matter of fact, the construction of batch OT with optimal rate from [BBDP22] natively satisfies the extra requirements and can be cast as two-round decomposable batch OT with sublinear overhead.

Theorem 5 (Corollary of [BBDP22, Section 7]). Assume the QR assumption and the binary LPN assumption LPN(dim, num, ρ) with dimension dim = poly(λ), number of samples num = dim c (for any constant c > 1), and noise rate ρ = num ε-1 (for some constant ε < 1). Then for any = (λ), there exists a decomposable two-round batch oblivious transfer for batch size k = • num where -The receiver message otr has size The proof of theorem 5 is deferred to the full version of this paper. Note that the construction of batch OT in [BBDP22] from LPN plus DDH or LPN plus polynomial-modulus LWE can similarly be shown to be decomposable. However, two-party sublinear secure computation is already known under these assumptions, via HSS for NC 1 [BGI16, BKS19].

( 2 • dim + • num ε ) • poly(λ) + k -

Bounded Query Repetitions

At a high level the goal of this section is to show how a receiver message of dec-OT can be re-used, possibly with imbalances in how many times each selection bit in the batch is re-used, while asymptotically preserving upload-and download-rate.

Definition 6 (Decomposable Two-Round Batch Oblivious Transfer with Bounded Query Repetitions). Let k ∈ N and α = o(n). A semi-honest tworound decomposable batch OT protocol with α(•)-overhead and T -bounded query repetitions between a sender and a receiver can be defined as a triple of PPT algorithms rep-OT = (rep-OTR, rep-OTS, rep-OTD) with the following syntax and properties:

-Syntax.

• rep-OTR : On input the security parameter 1 λ and a vector of selection bits b = (b 1 , . . . , b k ) ∈ {0, 1} k , rep-OTR outputs a receiver message otr ∈ {0, 1} O(k) and an internal state st; without loss of generality we assume that st contains all the random coins used by rep-OTR as well as b. • rep-OTS : On input the security parameter 1 λ , a query otr, a database ((m

(i) 0 , m (i) 1 )) i∈[k ] ∈ {0, 1} 2k (where k ≤ k ≤ k • T ),
(i) 0 , m (i) 1 )) i∈[k ] ∈ {0, 1} 2k , Pr   ( m 1 , . . . , m |K| ) = (m (i) σi ) i∈K : (otr, st) $ ← rep-OTR(1 λ , b) ((ots , ots dec ), rep) $ ← rep-OTS(1 λ , otr, m, rep) ( m 1 , . . . , m |K| ) $ ← rep-OTD(K, (ots , [ots dec ] K ), rep, st)    = 1 ,
where σ i := b max{j : ( j <j rep j )≤i} .

-Receiver Security (against Semi-Honest Sender). There exists an expected polynomial time simulator Sim S such that for every λ ∈ N and every

b = (b 1 , . . . , b k ) ∈ {0, 1} k , otr : (otr, st) $ ← rep-OTR(1 λ , b) c ≈ Sim S (1 λ ) .
-Decomposable Sender Security (against Semi-Honest Receiver).

There exists an expected polynomial time simulator Sim R such that for every

λ ∈ N , every rep = (rep 1 , . . . , rep k ) ∈ [0, T ] k such that rep 1 = k , every K ⊆ [k ], every b = (b 1 , . . . , b k ) ∈ {0, 1} k
, and every m = ((m The proof of lemma 7 is deferred to the full version of this paper.

(i) 0 , m (i) 1 )) i∈[k ] ∈ {0, 1} 2k , (ots , [ots dec ] K , otr, st) : (otr, st) $ ← rep-OTR(1 λ , b) (ots , ots dec ) $ ← rep-OTS(1 λ , otr, m, rep) c ≈ (sim , sim dec , otr, st) : (otr, st) $ ← rep-OTR(1 λ , b) (sim , sim dec ) $ ← Sim R (1 λ , K, (m (i) σi ) i∈K ,
(j,i) 0 , m (j,i) 1 )) j∈[k],i∈[rep j ] . 2. For j ∈ [k] and i ∈ [rep j + 1, T ], set (m (j,i) 0 , m (j,i) 1 ) ← (0, 0). 3. For i ∈ [T ] set m i := ((m (j,i) 0 , m (j,i) 1 )) j∈[k] . 4. For j = 1 . . . T : Compute (ot
v i ← j∈Ki [ot dec S,i ] j . (c) Compute ( m i,j ) j∈Ki $ ← dec-OTD(K i , (ot S,i , v i ), st). 5. Output ( m 1,1 , . . . , m rep 1 ,1 , m 1,2 , . . . , m rep 2 ,2 , . . . , m rep k ,k ).

Two-Round Batch SPIR with Correlated Queries

We next introduce and achieve a notion of batch symmetric PIR with correlated queries. This corresponds to batch SPIR where the queries are not independent; rather, the total entropy w used to describe the queries is small, and the queried indices can be reconstructed via a public function that "mixes and matches" the individual bits of entropy α = (α 1 , . . . , α w ) in a public manner. This will allow us to compress k size-N databases each down to a single bit-achieving batch SPIR-using batch OT on the selection bit vector α, by building a "Merkle-like forest" (seeing each 1-out-of-2 OT in the batch as a roughly length-halving hash function): the correlation in the queries across different databases is what allows the nodes of the Merkle forest to be batched.

In more detail, if the w bits of entropy are α 1 , . . . , α w , "mixing and matching" means that each of the (n = log N )-bit queries to a single database can be obtained by concatenating n of the bits α i , possibly permuted. In the notation below, the j th query is given by vector (α sj,1 , . . . , α sj,n ). We will be interested in how many times a given α i appears within the k queries (counted by the occurrence function t i below), as well as how many times it appears in specific position j ∈ [n] within the k queries (denoted below by t i,j ). If all t i,j are bounded by T , then for each level j ∈ [n] in the "Merkle forest" we can achieve the desired length-halving compression by using at most T batch OT sender computations on the original batch OT selection vector α.

Definition 8 ("Mix and Match" Functions). A "mix and match" function

MixAndMatch : {0, 1} w → [N ] k is one parameterised by k ordered subsets of n := log N elements of [w], S j = (s j,1 , . . . , s j,n ) ∈ [w] n for j ∈ [k] such that: ∀ α = (α 1 , . . . , α w ) ∈ {0, 1} w , MixAndMatch(α 1 , . . . , α w ) := (x 1 , . . . , x k ), with x j := α sj,1 • • • α sj,n ∈ [N ].
Such a function is associated with an occurrence function, which counts the occurrences of each input position in the outputs:

t • : [w] → [k] i → t i = k j=1 1 i∈Sj Each t i (i ∈ [w]
) can be decomposed as

t i = t i,1 + • • • + t i,n
, where t i,j is equal to the number of values of j ∈ [k] such that s j,j = i.

-

MixAndMatch is said to be T -balanced if ∀i ∈ [w], ∀j ∈ [n], t i,j ≤ T .
-MixAndMatch is said to be T -balanceable if it can be expressed as the function MixAndMatch = (MixAndMatch • replicate), where MixAndMatch : {0, 1} w → [N ] k is a T -balanced mix-and-match function and replicate is defined as:

replicate : {0, 1} w → {0, 1} w (b 1 , . . . , b w ) → (b t1/T 1 . . . b tw/T w ) where w := i∈[w] t i /T .
Lemma 9. Let w, n ∈ N be a sufficiently large integers. For any family of unordered subsets S 1 , . . . , S k ∈ [w] n there exists an ordering of each subset S j such that the mix-and-match function induced by the resulting ( Sj ) j∈[k] is polylog(w)balanceable. Furthermore, such orderings can be found in expected constant time.

The proof of lemma 9 is deferred to the full version of this paper.

Definition 10 (Two-Round Batch Computational Batch SPIR with Correlated "Mix and Match" Queries). A semi-honest two-round batch SPIR protocol with correlated "mix and match" queries between a sender and a receiver can be defined as a triple of PPT algorithms corrSPIR = (corrSPIR R , corrSPIR S , corrSPIR D ) parameterised by a public T -balanceable "mix and match" function (definition 8) MixAndMatch : {0, 1} w → [N ] k with the following syntax and properties:

-Syntax.

• corrSPIR R : On input the security parameter 1 λ and a vector of selection bits w) and an internal state st; without loss of generality, we assume st contains all the coins used by corrSPIR R as well as b. • corrSPIR S : On input the security parameter 1 λ , a receiver message spir R , and k N -bit databases m 1 , . . . , m k ∈ {0, 1} N , corrSPIR S outputs a sender message spir S ∈ {0, 1} O(k) . • corrSPIR D : On input a sender message spir S and an internal state st, corrSPIR D outputs a vector of messages ( m 1 , . . . , m k ) ∈ {0, 1} k .

b = (b 1 , . . . , b w ) ∈ {0, 1} w , corrSPIR R outputs a receiver message spir R ∈ {0, 1} O(
-Correctness.

∀ b = (b 1 , . . . , b w ) ∈ {0, 1} w , ∀ M = ( m 1 , . . . , m k ) ∈ {0, 1} N •k , Pr   ( m 1 , . . . , m k ) = ( m 1 [x 1 ], . . . , m k [x k ]) : (spir R , st) $ ← corrSPIR R (1 λ , b) spir S $ ← corrSPIR S (1 λ , spir R , M ) ( m 1 , . . . , m k ) $ ← corrSPIR D (spir S , st)    = 1
where (x 1 , . . . , x k ) := MixAndMatch( b).

-Security. The following protocol securely realises F corrSPIR (fig. 2) in the presence of a semi-honest adversary: the receiver computes (spir R , st)

$ ← corrSPIR R (1 λ , b
) and sends spir R to the sender, who in turn computes spir S $ ← corrSPIR S (1 λ , spir R , M ) and returns spir S ; finally, the receiver computes and outputs ( m 1 , . . . , m k ) $ ← corrSPIR D (spir S , st).

Functionality F corrSPIR

The functionality F corrSPIR is parameterised by the number k of SPIRs in the batch, the size N of each database, and the number w of selection bits. Furthermore, it is parameterised by a public T -balanceable "mix and match" function (definition 8) MixAndMatch : {0, 1} w → [N ] k . F corrSPIR interacts with an ideal sender S and an ideal receiver R via the following queries.

1. On input (sender, M = ( m i ) i∈[k] ) from S, with m i = (m i,j ) j∈[N ] ∈ {0, 1} N store M . 2. On input (receiver, (b j ) j∈[w] ) from R, check if a tuple of in- puts M has already been recorded; if so, compute (x 1 , . . . , x k ) := MixAndMatch(b 1 , . . . , b w ) ∈ [N ] k , send (m i,xi ) i∈[k]
to R, and halt.

If the functionality receives an incorrectly formatted input, it aborts.

Fig. 2: Ideal Functionality F corrSPIR for Batch SPIR with Correlated "Mix and Match" Queries Batch SPIR with Correlated "Mix and Match" Queries

Parameters: k, N , n := log N , w, T , a T -balanceable MixAndMatch : {0, 1} w → [N ] k (parameterised by subsets S j = (s j,1 , . . . , s j,n ) ∈ [w] n for j ∈ [k]
) and an associated list of number of occurrences (t 1 , . . . , t w ) with corrSPIR S : On input the security parameter 1 λ , a receiver message spir R , and k databases m 1 , . . . , m k ∈ [N ]:

t i = t i,1 + • • • + t i,n , a two-round batch rep-OT protocol rep-OT = (rep-OTR, rep-OTS, rep-OTD).
1. Set (DB 1,1 , . . . , DB 1,k ) := ( m 1 , . . . , m k ). 2. For d = 1, . . . , n:
(a) For i = 1, . . . , w:

Set rep d,i ← T t i,d /T 0 ti/T -t i,d /T if T |t i,d T t i,d /T t i,d %T 0 ti/T -t i,d /T if T |t i,d (b) Set rep d ← rep d,1 . . . rep d,w . (c) Initialise X d ← ∅ . (d) For j = 1, . . . , k: For x = 0, . . . , N/2 d -1: X d .append(((DB d,j [2x], DB d,j [2x + 1]), s j,d , x, j))
. (e) Sort X d according to the lexicographic order which first sorts by increasing fourth element (the "j ∈ [k]") and then, in case of equality, by increasing third element (the "x

∈ [0, N/2 d -1]"). (f) Greedily partition X d as X = X d,1 • • • X d,(N/2 d ) such that for each ∈ [N/2 d ] and each i ∈ [w], X d, contains (up to) t i,d elements of the form ((•, •), i, •, •)
; "greedily" is here taken to mean that the first t i,d elements of the form

((•, •), i, •, •) are placed in X d,1 , the next t i,d in X d,2
, and so on. (g) For = 1, . . . , N/2 d :

-Sort X d, according to the second element in increasing order, breaking ties with the fourth, and then if necessary the third element of the 4-tuples.

-Set DB d, ← (S d, [0].first, . . . , S d, [( w i=1 t i,d ) -1].first) ∈ {0, 1} 2|S d, | . -Set (ots d, , ots dec d, ) $ ← rep-OTS(1 λ , spir R , DB d, , rep d ) . (h) If d < n:
-For j = 1, . . . , k: Initialise DB d+1,j ← 0 N/2 d . -For = 1, . . . , N/2 d : For = 0, . . . , ( (c) Sort X d according to the lexicographic order which first sorts by increasing fourth element (the "j ∈ [k]") and then, in case equality, by increasing third element (the "x -Set j,d to be the unique

w i=1 t i,d ) -1: Parse X d, [ ] as ((•, •), •, x, j), with x ∈ [N/2 d ] and j ∈ [k]. Set DB d+1,j [x] ← ots dec d, [ ] . (i) Set
∈ [0, N/2 d -1]"). (d) Greedily partition X d as X d = X d,1 • • • X d,N/2 d such
∈ [N/2 d ] such that (⊥, s j,d , (b sj,n . . . b s j,d ), j) ∈ X d, .
-Set ind j,d to be the index of (⊥, s j,d , (b sj,n . . . b s j,d ), j) in X d, .

-Update m j ← rep-OTD({ind j,d }, (ots d, j,d , m j ), rep, st) 5. Output ( m 1 , . . . , m k ) .

Sublinear Computation of log log-Depth Circuits from corrSPIR

In this section theorem 12 shows how to build sublinear secure computation for shallow (roughly log log-depth) circuits from corrSPIR, with an explicit protocol provided in fig. 4. Main theorem 1 combines all of the previous theorems and shows that sublinear secure computation for shallow circuits can be based on QR + LPN.

Protocol Π 2PC

Functionality:

-Parameters: C : {0, 1} n → {0, 1} m is a boolean circuit of depth k. For j ∈ [m], S j = {s j,1 , . . . , s j,2 k } is the subset a of the inputs on which depends the j th output of f , and for i ∈ [n] we denote t i the number of outputs of C on which the i th variable depends.

(π j ) j∈[m] ∈ (S 2 k ) m is a family of m permutations on [2 k ],
such that the following is a (T = polylog(n))-balanced "mix and match" function:

MixAndMatch C : {0, 1} w → [2 k ] m (x 1 , . . . , x w ) → (x s j,π j (1) . . . x s j,π j (2 k ) ) j∈[m]
-Inputs: Parties P 0 and P 1 hold additive shares ( x 0 , x 1 ) of an input

x ∈ {0, 1} n . -Outputs: The parties output C( x).

-Requires: corrSPIR = (corrSPIR R , corrSPIR S , corrSPIR D ) is a tworound batch SPIR protocol with correlated "mix and match" queries.

Protocol:

1. P 0 samples y 0 $ ← {0, 1} m and for j ∈ [m] sets DB j ∈ {0, 1} 2 2 k to be the truth table of the following function:

g j : {0, 1} 2 k → {0, 1} (X 1 , . . . , X 2 k ) → C j ((X πj (1) ⊕ x 0 [π j (1)] . . . X πj (2 k ) ⊕ x 0 [π j (2 k )])) ⊕ y 0 [j]
where C j is the j th output of C.

P

1 sets x 1 ← ( x 1 [1]) t 1 /T . . . b t w /T w . 3. P 1 samples (spir R , st) $ ← corrSPIR R (1 λ , x 1
) and sends spir R to P 0 . 4. P 0 samples spir S $ ← corrSPIR S (1 λ , spir R , (DB j ) j∈ [m] ) and sends (spir S , y 0 ) to P 1 . 5. P 1 recovers y 1 ← corrSPIR D (spir S , st). 6. P 1 sets y ← y 0 ⊕ y 1 , and sends y to P 0 . 7. Each party P σ outputs y.

a Because C has depth k and each of its gate has fan-in at most 2, each output value only depends on at most 2 k inputs. Without loss of generality we can assume each output depends on exactly 2 k (by allowing for trivial "dependencies"). The proof of theorem 12 is deferred to the full version of this paper.

Our first main theorem follows from the combination of theorem 5-which instantiates dec-OT from QR + LPN-, lemma 7-which provides a construction of rep-OT from dec-OT-, theorem 11-which provides a construction of corrSPIR from rep-OT, and theorem 12-which provides a secure computation protocol from corrSPIR.

Main Theorem 1 (Sublinear Secure Computation from QR + LPN). Assume the QR assumption and the binary LPN assumption LPN(dim, num, ρ) with dimension dim = poly(λ), number of samples num = (n + m) 1/3 • poly(λ), and noise rate ρ = num ε-1 (for some constant ε < 1). Then for any n-input moutput boolean circuit C of size s and depth k, there is a two-party protocol for securely computing C using only O

(n + m + 2 k+2 k • polylog(n) • poly(λ) • ((n + m) 2/3 + (n + m) (1+2ε)/3
)) bits of communication, and computation poly(λ, 2 2 k ).

The discussion on the parameters is deferred to the full version of this paper.

Corollary 13 (Sublinear Secure Computation of log log-Depth Circuits).

Assume the QR assumption and the binary LPN assumption LPN(dim, num, ρ) with dimension dim = poly(λ), number of samples num = (n+m) 1/3 •poly(λ), and noise rate ρ = num -1/2 . Then for any n-input m-output boolean circuit C of polynomial size s and depth log log s/4, there is a two-party protocol for securely computing C using only O(n + m + √ s • poly(λ) • (n + m) 2/3 ) bits of communication, and polynomial computation.

Extension to Layered Circuits

Layered circuits are boolean circuits whose gates can be arranged into layers such that any wire connects adjacent layers. It is well-known from previous works [BGI16, Cou19, CM21] that sublinear protocols for low-depth circuits translate to sublinear protocols for general layered circuits: the parties simply cut the layered circuit into low-depth "chunks", and securely evaluate it chunkby-chunk. We refer to the full version of this paper for the extension of our protocol to layered circuits.

Polylogarithmic PIR from CDH

A private information retrieval is a two-party protocol between a server S holding a string z (the database) and a client C holding an integer i, where only the client receives an output. The security parameter λ and the length n(λ) = poly(λ) = |z| of the server database are a common (public) input. We let View S (λ, z, i) denote the view of S during its interaction with C on respective inputs (z, i) with common input (λ, n = |z|), and by Out C (λ, z, i) the output of C after the interaction.

Definition 14 (Private Information Retrieval). A private information retrieval for database size n = n(λ) (n-PIR) is an interactive protocol between a PPT server S holding a string z ∈ {0, 1} n and a PPT client C holding an index i ≤ n which satisfies the following properties:

-Correctness: there exists a negligible function µ such that for every λ

∈ N, z ∈ {0, 1} n , i ∈ [n]: Pr[Out C (λ, z, i) = z i ] ≥ 1 -µ(λ).
-Security: there exists a negligible function µ such that for every PPT adversary A, large enough λ ∈ N, (i, j) ∈ [n] 2 , and z ∈ {0, 1} n :

| Pr[A(1 λ+n , View S (λ, z, i)) = 1]-Pr[A(1 λ+n , View S (λ, z, j)) = 1]| ≤ µ(λ, n).
-Efficiency: A PIR is polylogarithmic if its communication complexity c(λ, n), measured as the worst-case number of bits exchanged between S and C (over their inputs (z, i) and their random coins), satisfies c(λ, n) = poly(λ, log n).

Main Theorem 2. Assuming the hardness of the computational Diffie-Hellman assumption against poly(n)-time adversaries, there exists a polylogarithmic n-PIR protocol, with polylogarithmic client computation, and O(log n) rounds.

Laconic Private Set Intersection

Definition 15 (Laconic PSI [ABD + 21]). An PSI scheme LPSI = (Setup, R 1 , S, R 2 ) is defined as follows:

-Setup(1 λ ): Take as input a security parameter 1 λ and outputs a common reference string crs. -R 1 (crs, S R ): takes as input a crs and a receiver set S R . Outputs a first PSI message psi 1 and a state st. -S(crs, S S , psi 1 ): takes as input a crs, a sender set S S , and a first PSI message psi 1 . Outputs a second PSI message psi 2 . -R 2 (crs, st, psi 2 ): takes as input a crs, a state st, and a second PSI message psi 2 . Outputs a set X .

An PSI protocol satisfies the following properties:

-Correctness: for every sets (S R , S S ), given crs

$ ← Setup(1 λ ), (psi 1 , st) $ ← R 1 (crs, S R ), psi 2 $ ← S(crs, S S , psi 1 ), and X $ ← R 2 (crs, st, psi 2 ), it holds that X = S R ∩ S S with probability 1.
-Security: the two-round protocol defined by LPSI = (Setup, R 1 , S, R 2 ) implements the PSI functionality given on Figure 5 in the semi-honest model. -Efficiency: there exists a fixed polynomial poly such that both the length of psi 1 and the running time of S are bounded by poly(λ, log |S R |).

Functionality F psi

Parameters: The PSI functionality F psi is parameterised with a universe U.

Setup Phase: The functionality waits until it receives S R with S R ⊆ U from R. Ignores subsequent messages from R.

Send Phase: The functionality waits until it receives S S with S S ⊆ U from S. Sends S R ∩ S S to R. Ignores subsequent messages from R. ). Assuming the security of the computational Diffie-Hellman assumption against poly(n)-time adversaries, there exists an PSI protocol for receiver sets of size n with statistical receiver security and computational (semi-honest) sender security.

From Laconic PSI to Half-PIR

We define the notion of half-PIR, first introduced in [BIP18] (under the name Rand 1 2 PIR). Informally, a half-PIR behaves as a regular PIR with probability 1/2; otherwise, correctness and security might not hold. The receiver gets notified when the scheme successfully worked as intended.

Definition 17. A half-PIR protocol is defined as an n-PIR (Definition 14) where the correctness and security properties are modified as follows:

-Correctness: there exists a negligible function µ such that for every λ ∈ N, z ∈ {0, 1} n , i ∈ [n]:

Pr[Out C (λ, z, i) = (z i , success)] ≥ 1/2 -µ(λ).

-Security: there exists a negligible function µ such that for every PPT adversary A, large enough λ ∈ N, (i, j) ∈ Below, we recall the definition of pseudorandom functions (PRFs), first introduced in the seminal work of [GGM84]. For simplicity, we restrict our attention to PRFs with key length and output length equal to the security parameter λ.

Definition 18 (Pseudorandom function [GGM84, NR95]). A pseudorandom function with input size m is syntactically defined by a function family F = {F K : {0, 1} m(λ) → {0, 1} λ } λ∈N,K∈{0,1} λ , where the output F K (x) can be computed from (K, x) in polynomial time, and which satisfies the following security property: for every λ ∈ N and every oracle PPT attacker A, it holds that Pr

K [A(1 λ ) F K (•) = 1] -Pr R [A(1 λ ) R(•) = 1] ≤ negl(λ),
where K $ ← {0, 1} λ , and R : {0, 1} m → {0, 1} λ is a truly random function. Furthermore, we say that the PRF is T (λ)-secure if the above inequality still holds when A is additionally given 1 T as input.

For a high-level intuition of the protocol provided in fig. 6, we refer to the full version of this paper.

Half-PIR from Laconic PSI and PRF.

Parameters: The protocol is parameterised with a security parameter λ, and a database size n = n(λ) ≤ 2 λ • negl(λ). {F K } K∈{0,1} λ is a family of n(λ)-secure PRFs with input size m = log n + 1. The protocol operates in the F psi -hybrid model, where the universe U is defined as {0, 1} λ . The server holds an input string z ∈ {0, 1} n and a the client holds an index i ≤ n.

Protocol: The protocol operates in three steps. Assuming the hardness of the computational Diffie-Hellman assumption against poly(n)-time adversaries, there exists a (constant-round) polylogarithmic half-PIR protocol for databases of size n (where the client computation is also polylogarithmic).

From Polylogarithmic Half-PIR to Polylogarithmic PIR

We now describe a simple generic transformation from Half-PIR to PIR.

Random-index PIR. First, we recall the definition of random-index PIR from [GHM + 21]:

Definition 20 (Random-Index PIR). A random-index PIR for database of size n is a two-party protocol between a server and a client which implements the random-index PIR functionality given on Figure 7 in the semi-honest model. We refer to the full version of this paper for a high-level explanation, and to [GHM + 21] for a formal proof of Lemma 21.

From half-PIR to random-index PIR. By the above, constructing PIR from half-PIR is reduced to constructing random-index PIR from half-PIR. The latter, however, is straightforward: the client and the server can simply execute a half-PIR, where the client picks its input uniformly at random. At the end of the protocol, if the client receives fail, both parties simply restart the protocol. By the correctness of the half-PIR, a successful execution will happen after an expected O(1) number of restarts. Below, we describe a slight variant of this where the client runs λ half-PIRs in parallel, and outputs the lexicographically first successful output.

  The sender message ots = (ots , ots dec ) has size |ots | = (num + • num ε ) • poly(λ) and |ots dec | = k. In particular, for appropriate parameters (sufficiently large , and num sufficiently larger than ), |otr| = k + o(k), and |ots | = o(k).

  and a vector of repetitions rep = (rep 1 , . . . , rep k ) ∈ [0, T ] k such that k i=1 rep i = k , rep-OTS outputs a sender message ots = (ots , ots dec ), which is comprised of a reusable part ots ∈ {0, 1} α(k) and a decomposable part ots dec ∈ {0, 1} k , as well as rep. • rep-OTD : On input a batch subset K ⊆ [k ], a partial sender message ots ∈ {0, 1} α(k)+|K| , a vector of repetitions rep = (rep 1 , . . . , rep k ) ∈ [0, T ] k such that k i=1 rep i = k , and an internal state st, rep-OTD outputs a vector of messages ( m i ) i∈K ∈ {0, 1} |K| . -Decomposable Correctness. For every λ ∈ N , K ⊆ [k ], every b = (b 1 , . . . , b k ) ∈ {0, 1} k , and every m = ((m

  b, rep, otr, st) where σ i := b max{j : ( j <j rep j )≤i} . Decomposable Two-Round Batch Oblivious Transfer with Bounded Query Repetition Parameters: Batch number k, Repetition bound T . Requires: A two-round decomposable batch dec-OT protocol dec-OT = (dec-OTR, dec-OTS, dec-OTD) with α-overhead such that α(k) = o(k/T ). rep-OTR: On input the security parameter 1 λ and a vector of selection bits b = (b 1 , . . . , b k ) ∈ {0, 1} k : 1. Compute (otr, st) $ ← dec-OTR(1 λ , b). 2. Output (otr, st). rep-OTS: On input the security parameter 1 λ , a receiver message otr, a database m ∈ {0, 1} 2k , and a vector of repetitions rep = (rep 1 , . . . , rep k ) ∈ [0, T ] k such that ||rep|| 1 = k : 1. Parse m as ((m

4.

  For i = 1 . . . T : (a) Set K i := {j : j ∈ [k], rep j ≤ i}, ordered according to the natural order on N. (b) Set

Fig. 1 :

 1 Fig. 1: From dec-OT with α overhead to rep-OT with α • T overhead. Lemma 7 (From dec-OT to rep-OT). If dec-OT is a semi-honest two-round decomposable batch OT protocol with α overhead, then the construction rep-OT from fig. 1 is a semi-honest two-round decomposable batch OT protocol with α • T overhead and T -bounded repetitions.

  corrSPIR R : On input the security parameter 1 λ and a vector of selection bits b = (b 1 , . . . , b w ) ∈ {0, 1} w : (spir R , st) $ ← OTR(1 λ , b ), and output (spir R , st b).

  ots d ← (ots d,1 , . . . , ots d,N/2 d ) . 3. Set spir S := ((ots 1 , . . . , ots n ), ots dec n ), and output spir S . corrSPIR D : On input a sender message spir S and an internal state st: 1. Parse spir S as spir S = ((ots 1 , . . . , ots n ), ots dec n ), and parse st as st b . 2. Set (y 1 , . . . , y k ) ← MixAndMatch( b) (i.e. y j ← b sj,1 . . . b sj,n for j ∈ [n]). 3. Initialise ( m 1 , . . . , m k ) ← ots dec n . 4. For d = 1, . . . , n : (a) Initialise X d ← ∅ . (b) Initialise X d ← ((⊥, s j,d , x, j)) j∈[k],x∈[0,N/2 d -1]

Fig. 3 :

 3 Fig. 3: corrSPIR from rep-OT. Theorem 11. Assume that rep-OT is a semi-honest two-round decomposable batch OT protocol with α(•)-overhead and T -bounded query repetitions. Then construction (corrSPIR R , corrSPIR S , corrSPIR D ) from fig. 3 is a two-round batch SPIR protocol with correlated "mix and match" queries. Furthermore the size of the receiver message is linear in w + k • n/T and the size of the sender message is upper bounded by k + (log N ) • (N -1) • α(w + k • n/T ) (where k is the batch number and N is the size of each of the k databases).

Fig. 4 :

 4 Fig. 4: Secure Computation of Low-Depth Circuits from corrSPIR

Fig. 5 :

 5 Fig. 5: PSI functionality F psi Lemma 16 ( PSI from CDH [ABD + 21]). Assuming the security of the computational Diffie-Hellman assumption against poly(n)-time adversaries, there exists an PSI protocol for receiver sets of size n with statistical receiver security and computational (semi-honest) sender security.

  [n] 2 , and z ∈ {0, 1} n , it holds that |p i -p j | ≤ µ(n, λ), where for an integer k ∈[n], p k denotes the conditional probability Pr[A(1 λ+n , View S (λ, z, k)) = 1 | Out C (λ, z, k) 2 = success].

  1. The server picks a random PRF key K $ ← {0, 1} λ and sends it to the client. The client samples a uniformly random bit b $ ← {0, 1}, and sets y ← F K (i||b).2. The server constructs the setS R = {F K (1||z 1 ), • • • , F K (n||z n )},and queries (sid, S R ) to F psi , playing the role of the receiver. The client constructs the set S S = {y} and queries S S to F psi , playing the role of the sender. The server receives S R ∩ S S . 3. The server indicates whether S R ∩ S S is empty by sending a bit to the client. If S R ∩ S S is empty, the client outputs (1 -b, success); otherwise, the client outputs (b, fail).

Fig. 6 :

 6 Fig. 6: Half-PIR from Laconic PSI and PRF.

Functionality F rpir Parameters:

 rpir The functionality is parameterised with a database size n. Server Message: The functionality waits until it receives z ∈ {0, 1} n from the server. Output: If the client is honest, sample i $ ← [n] and output (i, z i ) to the client. Otherwise, output z to the client.

Fig. 7 :

 7 Fig. 7: Random-index PIR functionality F rpir .

Table 1 :

 1 Existing protocols for secure computation with sublinear communication under various assumptions, in the computational setting. We use n for input size, m for output size, s for circuit size, and d for circuit depth.2 [CM21] assumes the superpolynomial hardness of the LPN assumption with dimension N , O(N ) samples, and noise rate N o(1)-1 . 3 We assume the polynomial hardness of LPN with dimension N , poly(N ) samples, and inverse-polynomial noise rate.

		Assumptions	Circuit class	Sublinearity 1
	[Gen09]	LWE	P/poly	O(n + m)
	[BGI16]	DDH	Layered circuits	O(n + m + s/ log s)
	[OSY21, RS21]	DCR	Layered circuits	O(n + m + s/ log s)
	[CM21]	superpoly LPN 2 Layered circuits	O(n + m + s/ log log s)
	[ADOS22]	Class groups	Layered circuits	O(n + m + s/ log s)
	This work	LPN + QR 3	Layered circuits	O n + m + d 1/3 • s 2(1+ε)/3 • poly(λ) +	s log log s
	1

  On input a sender message ots, a vector of repetitions rep =(rep 1 , . . . , rep k ) ∈ [0, T ] k such that ||rep|| 1 = k ,and an internal state st: 1. Parse ots as (ot S , ot dec S ). 2. Parse ot S as ot S,1 . . . ot S,T . 3. Parse ot dec S as ([ot dec S,1 ] 1 . . . [ot dec S,rep 1 ] 1 ) . . . ([ot dec S,1 ] k . . . [ot dec S,rep k ] k ).

	5. Set	ots	←	ot S,1 . . . ot S,T	and	ot dec S	←
	([ot dec S,1 ]

S,j , ot dec S,j )

$ ← dec-OTS(1 λ , otr, m j ). 1 . . . [ot dec S,rep 1 ] 1 ) . . . ([ot dec S,1 ] k . . . [ot dec S,rep k ] k ). 6. Output (ot S , ot dec S ).

rep-OTD:

  that for each ∈ [N/2 d ] and each i ∈ [w], X d, contains exactly t i,d elements of the form (•, i, •, •); "greedily" is here taken to mean that the firstt i,d elements of the form (•, i, •, •) are placed in X d,1 , the next t i,d in X d,2, and so on. (e) For = 1, . . . , N/2 d : Sort X d, according to the second element in increasing order, breaking ties with the fourth, and then if necessary the third element of the 4-tuples. (f) Parse ots d as ots d = (ots d,1 , . . . , ots d,N/2 d ) (g) For j = 1, . . . , k:

Namely, subexponential security of the combination of: Learning Parity with Noise, plus polynomial-stretch pseudorandom generators in N C 0 , plus the Decision Linear assumption on symmetric bilinear groups of prime order [JLS22].

A depth-d circuit is layered if it can be divided into d layers such that any wire connects adjacent layers.

Our construction can actually handle arbitrary constant client-to-server upload rate, as long as the sender-to-receiver download rate is 1.

We are of course sweeping details under the rug here, and refer the reader to the main body for a more complete treatment.

Indeed, the approach of [BBDP22] requires also a form of homomorphic encryption compressible to rate 1.

Acknowledgments

Elette Boyle and Pierre Meyer were supported by AFOSR Award FA9550-21-1-0046, a Google Research Award, and ERC Project HSS (852952). Geoffroy Couteau was supported by the ANR SCENE.

Random-Index PIR from Half-PIR.

Parameters: The protocol is parameterised with a security parameter λ, and a database size n = n(λ) ≤ 2 λ • negl(λ). The server holds an input string z ∈ {0, 1} n ; the client has no input.

Protocol: The client samples λ uniformly random integers

The client and the server run in parallel λ instances of a half-PIR protocol with respective client inputs i j and server input z. The client receives outputs Out C (λ, z, i j ).

Output: The client sets j * to be the lexicographically first j such that Out C (λ, z, i j ) = (z j , success) for some bit z j . The client outputs (z j * , success). If there is no such j, the client outputs ⊥ instead.

The security analysis is deferred to the full version of this paper. Combining this protocol with Lemma 21, we get: Lemma 22. If there exists a half-PIR protocol for databases of size n with communication complexity c(λ, n) and round complexity r(λ, n), then there exists an n-PIR protocol with communication complexity O(λ • c(λ, n) • log n) and round complexity O(r(λ, n) • log n).

Putting together Lemmas 19 and 22 finishes the proof of Theorem 2.


Biplab Dutta

João Carlos

Aquino Carvalho

Guadalupe Garcia-Arellano

Isabelle Maurin

Daniel Bloch

Athanasios Laliotis

Measuring the Casimir-Polder interaction of Rydberg atoms by vapour cell spectroscopy

Section XXX ICSLS2022 Caserta, 19-24 June 2022 Abstract number: assigned after submission Poster

Measuring the Casimir-Polder interaction of Rydberg atoms by vapour cell spectroscopy Dutta B. 1 , De Aquino Carvalho J. C. 1 , Garcia Arellano G. 1 , Maurin I. 1 ,Bloch D. 1 , Laliotis A. †1 1 Laboratoire de Physique des Lasers, Universite Sorbonne Paris Nord, CNRS UMR7538, F-93430 Villetaneuse, France † laliotis@univ-paris13.fr

The modification of quantum fluctuations by a surface of finite reflectivity shifts the energy levels of atoms and changes their radiative properties (Casimir-Polder effect). At nanometric distances away from a surface (near field), the Casimir-Polder energy shift is given by -C3/z 3 (where C3 is the van der Waals coefficient and z is the atom-surface distance) corresponding to the interaction of the fluctuating atomic dipole with its surface induced image. Near field Rydberg-surface interactions are of fundamental interest because the atomic size, scaling as n * 2 (where n * is the principle quantum number corrected by the quantum defect), is no longer negligible compared to the atom-surface separation, z. In this case, the dipole approximation, (-C3/z 3 law of interaction), is no longer valid and higher-order terms, corresponding to the interaction of the fluctuation quadrupole with its own image, need to be taken into account. Quadrupole interaction terms in the atom-surface interaction manifest themselves with a novel distance dependence of z 5 that has not been experimentally investigated yet 1 . Casimir-Polder experiments were first performed with low-lying Rydberg states (n= 10-14), demonstrating the -C3/z 3 law of interaction 2 . Nevertheless, more recent experiments with high-lying rubidium Rydbergs (n=32-43) 3 were not in agreement with Casimir-Polder theory thus highlighting the need for further experimental studies. 16,17). Experimental data are represented with black lines and theoretical fits with coloured lines. The cesium pressure is 25mTorr. The two peaks correspond to the 6P 1/2 hyperfine manifold (both levels are populated due to collisions), separated by 1.1 GHz.

In the SAI group, we use the well-developed technique of selective reflection spectroscopy that probes atoms at a distance of about λ/2π (where λ is the excitation wavelength) and allows us to measure the Casimir-Polder interaction between Cs(nD 3/2 , nS 1/2 ) (where n=15-18) atoms and a sapphire surface. The experiments are performed in a vapour cell with sapphire windows using a set-up similar to the one reported in previous experiments 4 . The cesium atoms are excited by a strong pump laser to the first cesium resonance (6P 1/2 ) and subsequently selective reflection is performed on 6P 1/2 → nD 3/2 , nS 1/2 transition with a tunable laser at λ = 512nm -508nm (see Fig. 1a). In Fig. 1b we show selective reflection spectra for the 6P 1/2 → nD 3/2 transitions (colored lines), along with the best theoretical predictions (black lines) assuming an interaction energy of -C3/z 3 and considering motionless atoms (an assumption justified when the van der Waals shift is much larger than the Doppler shift). Our theoretical model describes well the experimental data but provides C3 coefficients larger than the theoretically predicted values. However, the experimentally extracted values of the van der Waals coefficients scale with the principle quantum number as n * 4 faithful to basic theoretical considerations.

We are currently working on improving our theoretical models to include the effects of atomic motion. This could lead to more accurate measurements of the C3 coefficient. In addition, we are also planning to conduct experiments on a thin cell 5 which allows us to probe atoms at distances from 50 nm up to 1µm form the surface and can prove to be an excellent way to test the limits of the dipole approximation and probe quadrupole interactions.

Figure 1 :

 1 Figure 1: (a) Relevant cesium energy levels. (b) Selective reflection spectra normalized by the off-resonant reflection for the 6P 1/2 → nD 3/2 transitions (where n=15,16,17). Experimental data are represented with black lines and theoretical fits with coloured lines. The cesium pressure is 25mTorr. The two peaks correspond to the 6P 1/2 hyperfine manifold (both levels are populated due to collisions), separated by 1.1 GHz.