Benoît Libert

San Ling

Fabrice Mouhartem

Khoa Nguyen

Huaxiong Wang

Adaptive Oblivious Transfer with Access Control from Lattice Assumptions

Keywords: Lattice assumptions, standard assumptions, zero-knowledge arguments, adaptive oblivious transfer

Adaptive oblivious transfer (OT) is a protocol where a sender initially commits to a database {Mi} N i=1 . Then, a receiver can query the sender up to k times with private indexes ρ1, . . . , ρ k so as to obtain Mρ 1 , . . . , Mρ k and nothing else. Moreover, for each i ∈ [k], the receiver's choice ρi may depend on previously obtained messages {Mρ j }j<i. Oblivious transfer with access control (OT-AC) is a flavor of adaptive OT where database records are protected by distinct access control policies that specify which credentials a receiver should obtain in order to access each Mi. So far, all known OT-AC protocols only support access policies made of conjunctions or rely on ad hoc assumptions in pairing-friendly groups (or both). In this paper, we provide an OT-AC protocol where access policies may consist of any branching program of polynomial length, which is sufficient to realize any access policy in NC1. The security of our protocol is proved under the Learning-with-Errors (LWE) and Short-Integer-Solution (SIS) assumptions. As a result of independent interest, we provide protocols for proving the correct evaluation of a committed branching program on a committed input.

Introduction

Oblivious transfer (OT) is a central cryptographic primitive coined by Rabin [START_REF] Rabin | How to exchange secrets by oblivious transfer[END_REF] and extended by Even et al. [START_REF] Even | A randomized protocol for signing contracts[END_REF]. It involves a sender S with a database of messages M 1 , . . . , M N and a receiver R with an index ρ ∈ {1, . . . , N }. The protocol allows R to retrieve the ρ-th entry M ρ from S without letting S infer anything on R's choice ρ. Moreover, R only obtains M ρ learns nothing about {M i } i =ρ .

In its adaptive flavor [START_REF] Naor | Oblivious transfer with adaptive queries[END_REF], OT allows the receiver to interact k times with S to retrieve M ρ1 , . . . , M ρ k in such a way that, for each i ∈ {2, . . . , k}, the i-th index ρ i may depend on the messages M ρ1 , . . . , M ρi-1 previously obtained by R.

OT is known to be a complete building block for cryptography (see, e.g., [START_REF] Goldreich | How to play any mental game or a completeness theorem for protocols with honest majority[END_REF]) in that, if it can be realized, then any secure multiparty computation can be. In its adaptive variant, OT is motivated by applications in privacy-preserving access to sensitive databases (e.g., medical records or financial data) stored in encrypted form on remote servers, oblivious searches or location-based services.

As far as efficiency goes, adaptive OT protocols should be designed in such a way that, after an inevitable initialization phase with linear communication complexity in N and the security parameter λ, the complexity of each transfer is at most poly-logarithmic in N . At the same time, this asymptotic efficiency should not come at the expense of sacrificing ideal security properties. The most efficient adaptive OT protocols that satisfy the latter criterion stem from the work of Camenisch, Neven and shelat [START_REF] Camenisch | Simulatable adaptive oblivious transfer[END_REF] and its follow-ups [START_REF] Green | Blind identity-based encryption and simulatable oblivious transfer[END_REF][START_REF] Green | Universally composable adaptive oblivious transfer[END_REF][START_REF] Green | Practical adaptive oblivious transfer from simple assumptions[END_REF].

In its basic form, (adaptive) OT does not restrict in any way the population of users who can obtain specific records. In many sensitive databases (e.g., DNA databases or patients' medical history), however, not all users should be able to download all records: it is vital access to certain entries be conditioned on the receiver holding suitable credentials delivered by authorities. At the same time, privacy protection mandates that authorized users be able to query database records while leaking as little as possible about their interests or activities. In medical datasets, for example, the specific entries retrieved by a given doctor could reveal which disease his patients are suffering from. In financial or patent datasets, the access pattern of a company could betray its investment strategy or the invention it is developing. In order to combine user-privacy and fine-grained database security, it is thus desirable to enrich adaptive OT protocols with refined access control mechanisms in many of their natural use cases.

This motivated Camenisch, Dubovitskaya and Neven [START_REF] Camenisch | Oblivious transfer with access control[END_REF] to introduce a variant named oblivious transfer with access control (OT-AC), where each database record is protected by a different access control policy P : {0, 1} * → {0, 1}. Based on their attributes, users can obtain credentials generated by pre-determined authorities, which entitle them to anonymously retrieve database records of which the access policy accepts their certified attributes: in other words, the user can only download the records for which he has a valid credential Cred x for an attribute string x ∈ {0, 1} * such that P (x) = 1. During the transfer phase, the user demonstrates possession of a pair (Cred x , x) and simultaneously convinces the sender that he is querying some record M ρ associated with a policy P such that P (x) = 1. The only information that the database holder eventually learns is that some user retrieved some record which he was authorized to obtain.

Camenisch et al. formalized the OT-AC primitive and provided a construction in groups with a bilinear map [START_REF] Camenisch | Oblivious transfer with access control[END_REF]. While efficient, their solution "only" supports access policies consisting of conjunctions: each policy P is specified by a list of attributes that a given user should obtain a credential for in order to complete the transfer. Several subsequent works [START_REF] Zhang | Oblivious transfer with access control: Realizing disjunction without duplication[END_REF][START_REF] Camenisch | Oblivious transfer with hidden access control policies[END_REF][START_REF] Camenisch | Oblivious transfer with hidden access control from attribute-based encryption[END_REF] considered more expressive access policies while even hiding the access policies in some cases [START_REF] Camenisch | Oblivious transfer with hidden access control policies[END_REF][START_REF] Camenisch | Oblivious transfer with hidden access control from attribute-based encryption[END_REF]. Unfortunately, all of them rely on non-standard assumptions (known as "q-type assumptions") in groups with a bilinear maps. For the sake of not putting all one's eggs in the same basket, a primitive as powerful as OT-AC ought to have alternative realizations based on firmer foundations.

In this paper, we propose a solution based on lattice assumptions where ac-cess policies consist of any branching program of width 5, which is known [START_REF] Barrington | Bounded-width polynomial-size branching programs recognize exactly those languages in nc1[END_REF] to suffice for the realization of any access policy in NC1. As a result of independent interest, we provide protocols for proving the correct evaluation of a committed branching program. More precisely, we give zero-knowledge arguments for demonstrating possession of a secret input x ∈ {0, 1} κ and a secret (and possibly certified) branching program BP such that BP(x) = 1.

Related Work. Oblivious transfer with adaptive queries dates back to the work of Naor and Pinkas [START_REF] Naor | Oblivious transfer with adaptive queries[END_REF], which requires O(log N ) interaction rounds per transfer. Naor and Pinkas [START_REF] Naor | Computationally secure oblivious transfer[END_REF] also gave generic constructions of (adaptive) k-out-of-N OT from private information retrieval (PIR) [START_REF] Chor | Private information retrieval[END_REF]. The constructions of [START_REF] Naor | Oblivious transfer with adaptive queries[END_REF][START_REF] Naor | Computationally secure oblivious transfer[END_REF], however, are only secure in the half-simulation model, where simulation-based security is only considered for one of the two parties (receiver security being formalized in terms of a game-based definition). Moreover, the constructions of Adaptive OT from PIR [START_REF] Naor | Computationally secure oblivious transfer[END_REF] require a complexity O(N 1/2 ) at each transfer where Adaptive OT allows for O(log N ) cost. Before 2007, many OT protocols (e.g., [START_REF] Naor | Efficient oblivious transfer protocols[END_REF][START_REF] Aiello | Priced oblivious transfer: How to sell digital goods[END_REF][START_REF] Tauman-Kalai | Smooth projective hashing and two-message oblivious transfer[END_REF]) were analyzed in terms of half-simulation. While several efficient fully simulatable protocols appeared the last 15 years (e.g., [START_REF] Damgård | Universally composable efficient multiparty computation from threshold homomorphic encryption[END_REF][START_REF] Lindell | Efficient fully-simulatable oblivious transfer[END_REF][START_REF] Peikert | A framework for efficient and composable oblivious transfer[END_REF] and references therein), full simulatability remained elusive in the adaptive k-out-of-N setting [START_REF] Naor | Oblivious transfer with adaptive queries[END_REF] until the work [START_REF] Camenisch | Simulatable adaptive oblivious transfer[END_REF] of Camenisch, Neven and shelat, who introduced the "assisted decryption" paradigm. The latter consists in having the sender obliviously decrypt a re-randomized version of one of the original ciphertexts contained in the database. This technique served as a blueprint for many subsequent protocols [START_REF] Green | Blind identity-based encryption and simulatable oblivious transfer[END_REF][START_REF] Green | Universally composable adaptive oblivious transfer[END_REF][START_REF] Green | Practical adaptive oblivious transfer from simple assumptions[END_REF][START_REF] Jarecki | Efficient oblivious pseudorandom function with applications to adaptive OT and secure computation of set intersection[END_REF], including those with access control [START_REF] Camenisch | Oblivious transfer with access control[END_REF][START_REF] Camenisch | Oblivious transfer with hidden access control policies[END_REF][START_REF] Camenisch | Oblivious transfer with hidden access control from attribute-based encryption[END_REF][START_REF] Abe | Universally composable adaptive oblivious transfer (with access control) from standard assumptions[END_REF] and those presented in this paper. In the adaptive k-out-of-N setting (which we denote as OT N k×1 ), the difficulty is to achieve full simulatability without having to transmit a O(N ) bits at each transfer. To our knowledge, except the oblivious-PRF-based approach of Jarecki and Liu [START_REF] Jarecki | Efficient oblivious pseudorandom function with applications to adaptive OT and secure computation of set intersection[END_REF], all known fully simulatable OT N k×1 protocols rely on bilinear maps 4 . A recent work of Döttling et al. [START_REF] Döttling | Two-message, oblivious evaluation of cryptographic functionalities[END_REF] uses non-black-box techniques to realize LWE-based 2-round oblivious PRF (OPRF) protocols [START_REF] Freedman | Keyword search and oblivious pseudorandom functions[END_REF]. However, while fully simulatable OPRFs imply [START_REF] Jarecki | Efficient oblivious pseudorandom function with applications to adaptive OT and secure computation of set intersection[END_REF] fully simulatable adaptive OT, the OPRF construction of [START_REF] Döttling | Two-message, oblivious evaluation of cryptographic functionalities[END_REF] does not satisfy the standard notion of full simulation-based security against malicious adversaries (which is impossible to achieve in two rounds). It also relies on the full power of homomorphic encryption, which we do not require.

A number of works introduced various forms of access control in OT. Priced OT [START_REF] Aiello | Priced oblivious transfer: How to sell digital goods[END_REF] assigns variable prices to all database records. In conditional OT [START_REF] Di Crescenzo | Conditional oblivious transfer and timed-release encryption[END_REF], access to a record is made contingent on the user's secret satisfying some predicate.

Restricted OT [START_REF] Herranz | Restricted adaptive oblivious transfer[END_REF] explicitly protects each record with an independent access policy. Still, none of these OT flavors aims at protecting the anonymity of users. The model of Coull, Green and Hohenberger [START_REF] Coull | Controlling access to an oblivious database using stateful anonymous credentials[END_REF] does consider user anonymity via stateful credentials. For the applications of OT-AC, it would nevertheless require re-issuing user credentials at each transfer.

While efficient, the initial OT-AC protocol of Camenisch et al. [START_REF] Camenisch | Oblivious transfer with access control[END_REF] relies on non-standard assumptions in groups with a bilinear map and only realizes access policies made of conjunctions. Abe et al. [START_REF] Abe | Universally composable adaptive oblivious transfer (with access control) from standard assumptions[END_REF] gave a different protocol which they proved secure under more standard assumptions in the universal composability framework [START_REF] Canetti | Universally composable security: A new paradigm for cryptographic protocols[END_REF]. Their policies, however, remain limited to conjunctions. It was mentioned in [START_REF] Camenisch | Oblivious transfer with access control[END_REF][START_REF] Abe | Universally composable adaptive oblivious transfer (with access control) from standard assumptions[END_REF] that disjunctions and DNF formulas can be handled by duplicating database entries. Unfortunately, this approach rapidly becomes prohibitively expensive in the case of (t, n)-threshold policies with t ≈ n/2. Moreover, securing the protocol against malicious senders requires them to prove that all duplicates encrypt the same message. More expressive policies were considered by Zhang et al. [START_REF] Zhang | Oblivious transfer with access control: Realizing disjunction without duplication[END_REF] who gave a construction based on attribute-based encryption [START_REF] Sahai | Fuzzy identity-based encryption[END_REF] that extends to access policies expressed by any Boolean formulas (and thus NC1 circuits). Camenisch, Dubovitskaya, Neven and Zaverucha [START_REF] Camenisch | Oblivious transfer with hidden access control policies[END_REF] generalized the OT-AC functionality so as to hide the access policies. In [START_REF] Camenisch | Oblivious transfer with hidden access control from attribute-based encryption[END_REF], Camenisch et al. gave a more efficient construction with hidden policies based on the attributebased encryption scheme of [START_REF] Nishide | Attribute-based encryption with partially hidden encryptor-specified access structures[END_REF]. At the expense of a proof in the generic group model, [START_REF] Camenisch | Oblivious transfer with hidden access control from attribute-based encryption[END_REF] improves upon the expressiveness of [START_REF] Camenisch | Oblivious transfer with hidden access control policies[END_REF] in that its policies extend into CNF formulas. While the solutions of [START_REF] Camenisch | Oblivious transfer with hidden access control policies[END_REF][START_REF] Camenisch | Oblivious transfer with hidden access control from attribute-based encryption[END_REF] both hide the access policies to users (and the successful termination of transfers to the database), their policies can only live in a proper subset of NC1. As of now, threshold policies can only be efficiently handled by the ABE-based construction of Zhang et al. [START_REF] Zhang | Oblivious transfer with access control: Realizing disjunction without duplication[END_REF], which requires ad hoc assumptions in groups with a bilinear map.

Our Results and Techniques. We describe the first OT-AC protocol based on lattice assumptions. Our construction supports access policies consisting of any branching program of width 5 and polynomial length -which suffices to realize any NC1 circuit -and prove it secure under the SIS and LWE assumptions. We thus achieve the same level of expressiveness as [START_REF] Zhang | Oblivious transfer with access control: Realizing disjunction without duplication[END_REF] with the benefit of relying on well-studied assumptions. In its initial version, our protocol requires the database holder to communicate Θ(N ) bits to each receiver so as to prove that the database is properly encrypted. In the random oracle model, we can eliminate this burden via the Fiat-Shamir heuristic and make the initialization cost linear in the database size N , regardless of the number of users.

As a first step, we build an ordinary OT N k×1 protocol (i.e., without access control) via the "assisted decryption" approach of [START_REF] Camenisch | Simulatable adaptive oblivious transfer[END_REF]. In short, the sender encrypts all database entries using a semantically secure cryptosystem. At each transfer, the receiver gets the sender to obliviously decrypt one of the initial ciphertexts without learning which one. Security against malicious adversaries is achieved by adding zero-knowledge (ZK) or witness indistinguishable (WI) arguments that the protocol is being followed. The desired ZK or WI arguments are obtained using the techniques of [START_REF] Libert | Signature schemes with efficient protocols and dynamic group signatures from lattice assumptions[END_REF] and we prove that this basic protocol satisfies the full simulatability definitions of [START_REF] Camenisch | Simulatable adaptive oblivious transfer[END_REF] under the SIS and LWE assumptions. To our knowledge, this protocol is also the first OT N k×1 realization to achieve the standard simulation-based security requirements under lattice assumptions.

So far, all known "beyond-conjunctions" OT-AC protocols [START_REF] Zhang | Oblivious transfer with access control: Realizing disjunction without duplication[END_REF][START_REF] Camenisch | Oblivious transfer with hidden access control from attribute-based encryption[END_REF] rely on ciphertext-policy attribute-based encryption (CP-ABE) and proceed by attach-ing each database record to a CP-ABE ciphertext. Our construction departs from the latter approach for two reasons. First, the only known LWE-based CP-ABE schemes are obtained by applying a universal circuit to a key-policy system, making them very inefficient. Second, the ABE-based approach requires a fully secure ABE (i.e., selective security and semi-adaptive security are insufficient) since the access policies are dictated by the environment after the generation of the issuer's public key, which contains the public parameters of the underlying ABE in [START_REF] Zhang | Oblivious transfer with access control: Realizing disjunction without duplication[END_REF][START_REF] Camenisch | Oblivious transfer with hidden access control from attribute-based encryption[END_REF]. Even with the best known LWE-based ABE candidates [START_REF] Gorbunov | Riding on asymmetry: Efficient abe for branching programs[END_REF], a direct adaptation of the techniques in [START_REF] Zhang | Oblivious transfer with access control: Realizing disjunction without duplication[END_REF][START_REF] Camenisch | Oblivious transfer with hidden access control from attribute-based encryption[END_REF] would incur to rely on a complexity leveraging argument [START_REF] Boneh | Efficient selective-ID secure Identity-Based Encryption without random oracles[END_REF] and a universal circuit. Instead, we take a different approach and directly prove in a zero-knowledge manner the correct evaluation of a committed branching program for a hidden input.

At a high level, our OT-AC protocol works as follows. For each i ∈ [N ], the database entry M i ∈ {0, 1} t is associated with branching program BP i . In the initialization step, the database holder generates a Regev ciphertext (a i , b i ) of M i , and issues a certificate for the pair (a i , b i ), BP i , using the signature scheme from [START_REF] Libert | Signature schemes with efficient protocols and dynamic group signatures from lattice assumptions[END_REF]. At each transfer, the user U who wishes to get a record ρ ∈ [N ] must obtain a credential Cred x for an attribute string x ∈ {0, 1} κ such that BP ρ (x) = 1. Then, U modifies (a ρ , b ρ ) into an encryption of M ρ ⊕ µ ∈ {0, 1} t , for some random string µ ∈ {0, 1} t , and re-randomizes the resulting ciphertext into a fresh encryption (c 0 , c 1 ) of M ρ ⊕ µ. At this point, U proves that (c 0 , c 1 ) was obtained by transforming one of the original ciphertexts {(a i , b i )} N i=1 by arguing possession of a valid certificate for (a ρ , b ρ ), BP ρ and knowledge of all randomness used in the transformation that yields (c 0 , c 1 ). At the same time, U proves possession of Cred x for a string x which is accepted by the committed BP ρ . To demonstrate these statements in zero-knowledge, we develop recent techniques [START_REF] Ling | Group signatures from lattices: Simpler, tighter, shorter, ring-based[END_REF][START_REF] Libert | Zero-knowledge arguments for latticebased accumulators: Logarithmic-size ring signatures and group signatures without trapdoors[END_REF][START_REF] Libert | Signature schemes with efficient protocols and dynamic group signatures from lattice assumptions[END_REF] for lattice-based analogues [START_REF] Kawachi | Concurrently secure identification schemes based on the worst-case hardness of lattice problems[END_REF][START_REF] Ling | Improved zero-knowledge proofs of knowledge for the isis problem, and applications[END_REF] of Stern's protocol [START_REF] Stern | A new paradigm for public key identification[END_REF].

As a crucial component of our OT-AC protocol, we need to prove knowledge of an input x = (x 0 , . . . , x κ-1 ) ∈ {0, 1} κ satisfying a hidden BP of length L, where L and κ are polynomials in the security parameter. For each θ ∈ [L], we need to prove that the computation of the θ-th state

η θ = π θ,0 (η θ-1 ) • (1 -x var(θ) ) + π θ,1 (η θ-1 ) • x var(θ) , (1)
is done correctly, for permutations π θ,0 , π θ,1 : [0, 4] → [0, 4] and for integer var(θ) ∈ [0, κ -1] specified by BP. To date, equations of the form (1) have not been addressed in the context of zero-knowledge proofs for lattice-based cryptography. In this work, we are not only able to handle L such equations, but also manage to do so with a reasonable asymptotic cost. Below, we will explain the latter aspect.

In order to compute η θ as in (1), we have to fetch the value x var(θ) in the input (x 0 , . . . , x κ-1 ) and provide evidence that the searching process is conducted honestly. If we perform a naive left-to-right search in the array x 0 , . . . , x κ-1 , the expected complexity is O(κ) for each step, and the total complexity amounts to O(L • κ). If we instead perform a dichotomic search over x 0 , . . . , x κ-1 , we can decrease the complexity at each step down to O(log κ). However, in this case, we need to prove in zero-knowledge a statement "I obtained x var(θ) by conducting a correct dichotomic search in my secret array."

We solve this problem as follows. For each i ∈ [0, κ-1], we employ a SIS-based commitment scheme [START_REF] Kawachi | Concurrently secure identification schemes based on the worst-case hardness of lattice problems[END_REF] to commit to x i as com i , and prove that the committed bits are consistent with the ones involved in the credential Cred x mentioned above. Then we build a SIS-based Merkle hash tree [START_REF] Libert | Zero-knowledge arguments for latticebased accumulators: Logarithmic-size ring signatures and group signatures without trapdoors[END_REF] of depth δ κ = log κ on top of the commitments com 0 , . . . , com κ-1 . Now, for each θ ∈ [L], we consider the binary representation d θ,1 , . . . , d θ,δκ of var(θ). We then prove knowledge of a bit y θ such that these conditions hold: "If one starts at the root of the tree and follows the path determined by the bits d θ,1 , . . . , d θ,δκ , then one will reach the leaf associated with the commitment opened to y θ ." The idea is that, if the Merkle tree and the commitment scheme are both secure, then it should be true that y θ = x var(θ) . In other words, this enables us to provably perform a "binary search" for x var(θ) = y θ . Furthermore, this process can be done in zeroknowledge, by adapting the recent techniques from [START_REF] Libert | Zero-knowledge arguments for latticebased accumulators: Logarithmic-size ring signatures and group signatures without trapdoors[END_REF]. As a result, we obtain a protocol with communication cost just O(L • log κ + κ).

We believe that our idea of bringing Merkle trees into the context of privacypreserving protocols for branching programs to decrease the asymptotic complexity will be of independent interest. For instance, it may find applications in the private computation of branching programs [START_REF] Lipmaa | Private branching programs: On communication-efficient cryptocomputing[END_REF][START_REF] Ishai | Evaluating branching programs on encrypted data[END_REF].

Background and Definitions

Vectors are denoted in bold lower-case letters and bold upper-case letters will denote matrices. The Euclidean and infinity norm of any vector b ∈ R n will be denoted by b and b ∞ , respectively. The Euclidean norm of matrix B ∈ R m×n with columns (b i ) i≤n is B = max i≤n b i . When B has full columnrank, we let B denote its Gram-Schmidt orthogonalization.

When S is a finite set, we denote by U (S) the uniform distribution over S, and by x ← U (S) the action of sampling x according to this distribution. Finally for any integers A, B, N , we let [N ] and [A, B] denote the sets {1, . . . , N } and {A, A + 1, . . . , B}, respectively.

Lattices

A lattice L is the set of integer linear combinations of linearly independent basis vectors (b i ) i≤n living in R m . We work with q-ary lattices, for some prime q. It is well known that one can efficiently sample from a Gaussian distribution with lattice support given a sufficiently short basis of the lattice.

Definition 1. Let m ≥ n ≥ 1, a prime q ≥ 2 and A ∈ Z n×m q and u ∈ Z n q , define Λ q (A) := {e ∈ Z m | ∃s ∈ Z n q s.t. A T • s = e mod q} as well as Λ ⊥ q (A) := {e ∈ Z m | A • e = 0 n mod q}, Λ u q (A) := {e ∈ Z m | A • e = u mod q}.
Lemma 1 [START_REF] Brakerski | On the classical hardness of learning with errors[END_REF]Le. 2.3]). There exists a PPT algorithm GPVSample that takes as inputs a basis B of a lattice L ⊆ Z n and a rational σ ≥ B • Ω( √ log n), and outputs vectors b ∈ L with distribution D L,σ .

We also rely on the trapdoor generation algorithm of Alwen and Peikert [START_REF] Alwen | Generating shorter bases for hard random lattices[END_REF], which refines the technique of Gentry et al. [START_REF] Gentry | Trapdoors for hard lattices and new cryptographic constructions[END_REF].

Lemma 2 ([4, Th. 3.2]

). There is a PPT algorithm TrapGen that takes as inputs 1 n , 1 m and an integer q ≥ 2 with m ≥ Ω(n log q), and outputs a matrix A ∈ Z n×m q and a basis T A of Λ ⊥ q (A) such that A is within statistical distance 2 -Ω(n) to U (Z n×m q ), and

T A ≤ O( √ n log q).
We use the basis delegation algorithm [START_REF] Cash | Bonsai trees, or how to delegate a lattice basis[END_REF] that inputs a trapdoor for A ∈ Z n×m q and produces a trapdoor for any B ∈ Z n×m q containing A as a submatrix. A technique from Agrawal et al. [START_REF] Agrawal | Efficient lattice (H)IBE in the standard model[END_REF] is sometimes used in our proofs.

Lemma 3 ([18, Le. 3.2]

). There is a PPT algorithm ExtBasis that inputs B ∈ Z n×m q whose first m columns span Z n q , and a basis T A of Λ ⊥ q (A) where A ∈ Z n×m q is a submatrix of B, and outputs a basis

T B of Λ ⊥ q (B) with T B ≤ T A . Lemma 4 ([2, Th. 19]). There is a PPT algorithm SampleRight that inputs A, C ∈ Z n×m q , a small-norm R ∈ Z m×m , a short basis T C ∈ Z m×m of Λ ⊥ q (C), a vector u ∈ Z n
q and a rational σ such that σ ≥ T C • Ω( √ log n), and outputs b ∈

Z 2m such that A A • R + C • b = u mod q and with distribution statistically close to D L,σ where L = {x ∈ Z 2m : A A • R + C • x = u mod q}.

Hardness Assumptions

Definition 2. Let n, m, q, β be functions of λ ∈ N. The Short Integer Solution problem SIS n,m,q,β is, given

A ← U (Z n×m q ), find x ∈ Λ ⊥ q (A) with 0 < x ≤ β.
If q ≥ √ nβ and m, β ≤ poly(n), then standard worst-case lattice problems with approximation factors γ = O(β √ n) reduce to SIS n,m,q,β (see, e.g., [START_REF] Gentry | Trapdoors for hard lattices and new cryptographic constructions[END_REF]Se. 9]).

Definition 3. Let n, m ≥ 1, q ≥ 2, and let χ be a probability distribution on Z. For s ∈ Z n q , let A s,χ be the distribution obtained by sampling a ← U (Z n q ) and e ← χ, and outputting (a, a T • s + e) ∈ Z n q × Z q . The Learning With Errors problem LWE n,q,χ asks to distinguish m samples chosen according to A s,χ (for s ← U (Z n q )) and m samples chosen according to U (Z n q × Z q ).

If q is a prime power, B ≥ √ nω(log n), γ = O(nq/B), then there exists an efficient sampleable B-bounded distribution χ (i.e., χ outputs samples with norm at most B with overwhelming probability) such that LWE n,q,χ is as least as hard as SIVP γ (see, e.g., [START_REF] Regev | On lattices, learning with errors, random linear codes, and cryptography[END_REF][START_REF] Brakerski | On the classical hardness of learning with errors[END_REF]).

Adaptive Oblivious Transfer

In the syntax of [START_REF] Camenisch | Simulatable adaptive oblivious transfer[END_REF], an adaptive k-out-of-N OT scheme OT N k is a tuple of stateful PPT algorithms (S I , R I , S T , R T ). The sender S = (S I , S T ) consists of two interactive algorithms S I and S T and the receiver has a similar representation as algorithms R I and R T . In the initialization phase, the sender and the receiver run interactive algorithms S I and R I , respectively, where S I takes as input messages M 1 , . . . , M N while R I has no input. This phase ends with the two algorithms S I and R I outputting their state information S 0 and R 0 respectively.

During the i-th transfer, 1 ≤ i ≤ k, both parties run an interactive protocol via the R T and S T algorithms. The sender starts runs S T (S i-1 ) to obtain its updated state information S i while the receiver runs R T (R i-1 , ρ i ) on input of its previous state R i-1 and the index ρ i ∈ {1, . . . , N } of the message it wishes to retrieve. At the end, R T outputs an updated state R i and a message M ρi .

Correctness mandates that, for all M 1 , . . . , M N , for all ρ 1 , . . . , ρ k ∈ [N ] and all coin tosses of the (honestly run) algorithms, we have M ρi = M ρi for all i. We consider protocols that are secure (against static corruptions) in the sense of simulation-based definitions. The security properties against a cheating sender and a cheating receiver are formalized via the "real-world/ideal-world" paradigm. The security definitions of [START_REF] Camenisch | Simulatable adaptive oblivious transfer[END_REF] are recalled in Appendix B.1.

Adaptive Oblivious Transfer with Access Control

Camenisch et al. [START_REF] Camenisch | Oblivious transfer with access control[END_REF] define oblivious transfer with access control (OT-AC) as a tuple of PPT algorithms/protocols (ISetup, Issue, DBSetup, Transfer) such that:

ISetup: takes as inputs public parameters pp specifying a set P of access policies and generates a key pair (P K I , SK I ) for the issuer. Issue: is an interactive protocol between the issuer I and a stateful user U under common input (pp, x), where x is an attribute string. The issuer I takes as inputs its key pair (P K I , SK I ) and a user pseudonym P U . The user takes as inputs its state information st U . The user U outputs either an error symbol ⊥ or a credential Cred U , and an updated state st U . DBSetup: is an algorithm that takes as input the issuer's public key P K I , a database DB = (M i , AP i ) N i=1 containing records M i whose access is restricted by an access policy AP i and outputs a database public key P K DB , an encryption of the records (ER i ) N i=1 and a database secret key SK DB . Transfer: is a protocol between the database DB and a user U with common inputs (P K I , P K DB ). DB inputs SK DB and U inputs (ρ, st U , ER ρ , AP ρ ), where ρ ∈ [N ] is a record index to which U is requesting access. The interaction ends with U outputting ⊥ or a string M ρ and an updated state st U .

We assume private communication links, so that communications between a user and the issuer are authenticated, and those between a user and the database are anonymized: otherwise, anonymizing the Transfer protocol is impossible.

The security definitions formalize two properties called user anonymity and database security. The former captures that the database should be unable to tell which honest user is making a query and neither can tell which records are being accessed. This should remain true even if the database colludes with corrupted users and the issuer. As for database security, the intuition is that a cheating user cannot access a record for which it does not have the required credentials, even when colluding with other dishonest users. In case the issuer is colluding with these cheating users, they cannot obtain more records from the database than they retrieve. Precise security definitions [START_REF] Camenisch | Oblivious transfer with access control[END_REF] are recalled in Appendix B.2.

Vector Decompositions

We will employ the decomposition technique from [START_REF] Ling | Improved zero-knowledge proofs of knowledge for the isis problem, and applications[END_REF][START_REF] Libert | Signature schemes with efficient protocols and dynamic group signatures from lattice assumptions[END_REF], which allows transforming vectors with infinity norm larger than 1 into vectors with infinity norm 1.

For any B ∈ Z + , define the number δ B := log 2 B + 1 = log 2 (B + 1) and the sequence B 1 , . . . , B δ B , where

B j = B+2 j-1 2 j , ∀j ∈ [1, δ B ]. This se- quence satisfies δ B j=1 B j = B and any integer v ∈ [0, B] can be decomposed to idec B (v) = (v (1) , . . . , v (δ B ) ) ∈ {0, 1} δ B such that δ B j=1 B j • v j = v.
We describe this decomposition procedure in a deterministic manner as follows:

1. Set v := v; For j = 1 to δ B do: If v ≥ B j then v (j) := 1, else v (j) := 0; v := v -B j • v (j) . 2. Output idec B (v) = (v (1) , . . . , v (δ B ) ) .
For any positive integers m, B, we define H m,B :=

I m ⊗ [B 1 | . . . |B δ B ] ∈ Z m×mδ B
and the following injective functions:

(i) vdec m,B : [0, B] m → {0, 1} mδ B that maps vector v = (v 1 , . . . , v m ) to vector idec B (v 1 ) . . . idec B (v m ) . Note that H m,B • vdec m,B (v) = v.
(ii) vdec m,B : [-B, B] m → {-1, 0, 1} mδ B that maps vector w = (w 1 , . . . , w m ) to

vector σ(w 1 ) • idec B (|w 1 |) . . . σ(w m ) • idec B (|w m |)
, where for each i = 1, . . . , m: σ(w i ) = 0 if

w i = 0; σ(w i ) = -1 if w i < 0; σ(w i ) = 1 if w i > 0. Note that H m,B • vdec m,B (w) = w.

Building Blocks

We will use two distinct signature schemes because one of them only needs to be secure in the sense of a weaker security notion and can be more efficient. This weaker notion is sufficient to sign the database entries and allows a better efficiency in the scheme of Section 4. In particular, by making it stateful (which also suffices since all database entries are signed at once), we can reduce the public key size to log N matrices if N is the number of database entries. The second scheme must be stateful and secure in the standard EUF-CMA sense since the issuer uses it to certify users' attributes. The signature scheme of Section 3.1 is only used in the OT-AC protocol of Section 4 while the scheme of Section 3.2 is used in the adaptive OT protocol of Section 5 as well.

Signatures Supporting Efficient Zero-Knowledge Proofs

We use a signature scheme proposed by Libert et al. [START_REF] Libert | Signature schemes with efficient protocols and dynamic group signatures from lattice assumptions[END_REF] who extended the Böhl et al. signature [START_REF] Böhl | Confined guessing: New signatures from standard assumptions[END_REF] in order to sign messages comprised of multiple blocks while keeping the scheme compatible with zero-knowledge proofs.

Keygen(1 λ , 1 N b ): Given a security parameter λ > 0 and the number of blocks N b = poly(λ), choose n = O(λ), a prime modulus q = O(N • n 4 ), a dimension m = 2n log q ; an integer = poly(n) and Gaussian parameters σ = Ω( √ n log q log n). Define the message space as M = ({0, 1} m I ) N b .

1. Run TrapGen(1 n , 1 m , q) to get A ∈ Z n×m q and a short basis T A of Λ ⊥ q (A). This basis allows computing short vectors in Λ ⊥ q (A) with a Gaussian parameter σ. Next, choose + 1 random A 0 , A 1 , . . . , A ← U (Z n×m q ).

Choose random matrices

D ← U (Z n×m/2 q ), D 0 ← U (Z n×m q ), D j ← U (Z n×m I q
) for j = 1, . . . , N b , as well as a random vector u ← U (Z n q ). The private signing key consists of SK := T A while the public key is com-

prised of P K := A, {A j } j=0 , D, {D k } N b k=0 , u . Sign SK, Msg : To sign an N b -block Msg = (m 1 , . . . , m N b ) ∈ ({0, 1} m I ) N b , 1. Choose τ ← U ({0, 1} ). Using SK := T A , compute a short basis T τ ∈ Z 2m×2m for Λ ⊥ q (A τ ), where A τ = [A | A 0 + j=1 τ [j]A j ] ∈ Z n×2m q . 2. Sample r ← D Z m ,σ . Compute the vector c M ∈ Z n q as a chameleon hash of (m 1 , . . . , m N b ). Namely, compute c M = D 0 • r + N b k=1 D k • m k ∈ Z n q , which is used to define u M = u + D • vdec n,q-1 (c M ) ∈ Z n q . Using the delegated basis T τ ∈ Z 2m×2m , sample a vector v ∈ Z 2m in D Λ u M q (Aτ ),σ . Output the signature sig = (τ, v, r) ∈ {0, 1} × Z 2m × Z m . Verify P K, Msg, sig : Given Msg = (m 1 , . . . , m N b ) ∈ ({0, 1} m I ) N b and sig = (τ, v, r) ∈ {0, 1} × Z 2m × Z m , return 1 if v < σ √ 2m, r < σ √ m and
A τ • v = u + D • vdec n,q-1 (D 0 • r + N b k=1 D k • m k ) mod q.
(2)

A Simpler Variant with Bounded-Message Security and Security Against Non-Adaptive Chosen-Message Attacks

We consider a stateful variant of the scheme in Section 3.1 where a bound Q ∈ poly(n) on the number of signed messages is fixed at key generation time. In the context of OT N k×1 , this is sufficient and leads to efficiency improvements. In the modified scheme hereunder, the string τ ∈ {0, 1} is an -bit counter maintained by the signer to keep track of the number of previously signed messages. This simplified variant resembles the SIS-based signature scheme of Böhl et al. [START_REF] Böhl | Confined guessing: New signatures from standard assumptions[END_REF].

In this version, the message space is {0, 1} n log q so that vectors of Z n q can be signed by first decomposing them using vdec n,q-1 (.).

Keygen(1 λ , 1 Q ): Given λ > 0 and the maximal number Q ∈ poly(λ) of signatures, choose n = O(λ), a prime q = O(Q • n 4 ), m = 2n log q , an integer = log Q and Gaussian parameters σ = Ω( √ n log q log n). The message space is {0, 1} m d , for some m d ∈ poly(λ) with m d ≥ m.

1. Run TrapGen(1 n , 1 m , q) to get A ∈ Z n×m q and a short basis T A of Λ ⊥ q (A), which allows sampling short vectors in Λ ⊥ q (A) with a Gaussian parameter σ.

Next, choose + 1 random A 0 , A 1 , . . . , A ← U (Z n×m q ). 2. Choose D ← U (Z n×m d q
) as well as a random vector u ← U (Z n q ). The counter τ is initialized to τ = 0. The private key consists of SK := T A and the public key is P K := A, {A j } j=0 , D, u . Sign SK, τ, m : To sign a message m ∈ {0, 1} m d , 1. Increment the counter by setting τ := τ + 1 and interpret it as a string τ ∈ {0, 1} . Then, using SK := T A , compute a short delegated basis T τ ∈ Z 2m×2m for the matrix

A τ = [A | A 0 + j=1 τ [j]A j ] ∈ Z n×2m q . 2. Compute the vector u M = u + D • m ∈ Z n q .
Then, using the delegated basis

T τ ∈ Z 2m×2m , sample a short vector v ∈ Z 2m in D Λ u M q (Aτ ),σ . Output the signature sig = (τ, v) ∈ {0, 1} × Z 2m . Verify P K, m, sig : Given P K, m ∈ {0, 1} m d and a signature sig = (τ, v) ∈ {0, 1} × Z 2m , return 1 if v < σ √ 2m and A τ • v = u + D • m mod q.
For our purposes, the scheme only needs to satisfy a notion of boundedmessage security under non-adaptive chosen-message attack. In this relaxed model, the adversary only obtains a bounded number of signatures for messages that are chosen non-adaptively (i.e., all at once and before seeing the public key) by the adversary. This security notion is sufficient for signing the N database entries. Note that the queries are non-adaptive but the adversary can adaptively choose its forgery message. Theorem 1. The scheme is bounded message secure under non-adaptive chosenmessage attacks if the SIS assumption holds. (The proof is in Appendix C.1.)

A Fully Simulatable Adaptive OT Protocol

Our basic OT N k×1 protocol builds on the "assisted decryption" technique [START_REF] Camenisch | Simulatable adaptive oblivious transfer[END_REF]. The databases holder encrypts all entries using a multi-bit variant [START_REF] Peikert | A framework for efficient and composable oblivious transfer[END_REF] of Regev's cryptosystem [START_REF] Regev | On lattices, learning with errors, random linear codes, and cryptography[END_REF] and proves the well-formedness of its public key and all ciphertexts. In addition, all ciphertexts are signed using a signature scheme. At each transfer, the receiver statistically re-randomizes a blinded version of the desired ciphertext, where the blinding is done via the additive homomorphism of Regev. Then, the receiver provides a witness indistinguishable (WI) argument that the modified ciphertext (which is submitted for oblivious decryption) is a transformation of one of the original ciphertexts by arguing knowledge of a signature on this hidden ciphertext. In response, the sender obliviously decrypts the modified ciphertext and argues in zero-knowledge that the response is correct.

Adapting the technique of [START_REF] Camenisch | Simulatable adaptive oblivious transfer[END_REF] to the lattice setting requires the following building blocks: (i) A signature scheme allowing to sign ciphertexts while remaining compatible with ZK proofs; (ii) A ZK protocol allowing to prove knowledge of a signature on some hidden ciphertext which belongs to a public set and was transformed into a given ciphertext; (iii) A protocol for proving the correct decryption of a ciphertext; (iv) A method of statistically re-randomizing an LWE-encrypted ciphertext in a way that enables oblivious decryption. The first three ingredients can be obtained from [START_REF] Libert | Signature schemes with efficient protocols and dynamic group signatures from lattice assumptions[END_REF]. Since component (i) only needs to be secure against random-message attacks as long as the adversary obtains at most N signatures, we use the simplified SIS-based signature scheme of Section 3.2. The statistical re-randomization of Regev ciphertexts is handled via the noise flooding technique [START_REF] Asharov | Multiparty computation with low communication, computation and interaction via threshold FHE[END_REF], which consists in drowning the initial noise with a superpolynomially larger noise. While recent results [START_REF] Ducas | Sanitization of FHE ciphertexts[END_REF][START_REF] Bourse | FHE circuit privacy almost for free[END_REF] provide potentially more efficient alternatives, we chose the flooding technique for simplicity because it does not require the use of FHE (and also because the known multi-bit version [START_REF] Hiromasa | Packing messages and optimizing bootstrapping in GSW-FHE[END_REF] of the GSW FHE [START_REF] Gentry | Homomorphic encryption from learning with errors: Conceptually-simpler, asymptotically-faster, attribute-based[END_REF] incurs an ad hoc circular security assumption).

Description

Our scheme works with security parameter λ, modulus q, lattice dimensions n = O(λ) and m = 2n log q . Let B χ = O( √ n), and let χ be a B χ -bounded distribution. We also define an integer B as a randomization parameter such that B = n ω (1) • (m + 1)B χ and B + (m + 1)B χ ≤ q/5 (to ensure decryption correctness). Our basic OT N k×1 protocol goes as follows.

Initialization S I (1 λ , DB), R I (1 λ ) : In this protocol, the sender S I has a database DB = (M 1 , . . . , M N ) of N messages, where M i ∈ {0, 1} t for each i ∈ [N ], for some t ∈ poly(λ). It interacts with the receiver R I as follows.

1. Generate a key pair for the signature scheme of Section 3.2 in order to sign Q = N messages of length m d = (n + t) • log q each. This key pair consists of SK sig = T A ∈ Z m×m and P K sig := A, {A j } j=0 , D, u , where = log N and A, A 0 , . . . ,

A ∈ U (Z n×m q ), D ∈ U (Z n×m d q
). The counter is initialized to τ = 0. 2. Choose S ← χ n×t that will serve as a secret key for an LWE-based encryption scheme. Then, sample F ← U (Z n×m q

), E ← χ m×t and compute

P = [p 1 | . . . |p t ] = F • S + E ∈ Z m×t q , (3)
so that (F, P) ∈ Z n×m q × Z m×t q forms a public key for a t-bit variant of Regev's encryption scheme [START_REF] Regev | On lattices, learning with errors, random linear codes, and cryptography[END_REF].

Sample vectors

a 1 , . . . , a N ← U (Z n q ) and x 1 , . . . , x N ← χ t to compute (a i , b i ) = a i , S • a i + x i + M i • q/2 ∈ Z n q × Z t q ∀i ∈ [N ]. (4) 4. For each i ∈ [N ], generate a signature (τ i , v i ) ← Sign(SK sig , τ, m i ) on the decomposition m i = vdec n+t,q-1 (a i |b i ) ∈ {0, 1} m d . 5. S I sends R 0 = P K sig , (F, P), {(a i , b i ), (τ i , v i )} N i=1 to R I and interact- ively proves knowledge of small-norm S ∈ Z n×t , E ∈ Z m×t , short vectors {x i } N i=1 and t-bit messages {M i } N i=1
, for which (3) and ( 4) hold. To this end, S I plays the role of the prover in the ZK argument system described in Section 6.3. If the argument of knowledge does not verify or if there exists i ∈ [N ] such that (τ i , v i ) is an invalid signature on the message m i = vdec n+t,q-1 (a i |b i ) w.r.t. P K sig , then R I aborts. 6. Finally S I defines S 0 = (S, E), (F, P), P K sig , which it keeps to itself.

Transfer S T (S i-1 ), R T (R i-1 , ρ i ) : At the i-th transfer, the receiver R T has state R i-1 and an index ρ i ∈ [1, N ].
It interacts as follows with the sender S T that has state S i-1 in order to obtain M ρi from DB.

1. R T samples vectors e ← U ({-1, 0, 1} m ), µ ← U ({0, 1} t ) and a random ν ← U ([-B, B] t ) to compute (c 0 , c 1 ) = a ρi + F • e, b ρi + P • e + µ • q/2 + ν ∈ Z n q × Z t q , (5)
which is a re-randomization of (a ρi , b ρi +µ• q/2 ). The ciphertext (c 0 , c 1 ) is sent to S T . In addition, R T provides an interactive WI argument that (c 0 , c 1 ) is indeed a transformation of (a ρi , b ρi ) for some ρ i ∈ [N ], and R T knows a signature on m = vdec n+1,q-1 (a ρi |b ρi ) ∈ {0, 1} m d . To this end, R T runs the prover in the ZK argument system in Section 6.5.

If the argument of step 1 verifies, S

T uses S to decrypt (c 0 , c 1 ) ∈ Z n q × Z t q and obtain M = (c 1 -S • c 0 )/(q/2) ∈ {0, 1} t , which is sent back to R T .
In addition, S T provides a zero-knowledge argument of knowledge of vector y = c 1 -S • c 0 -M • q/2 ∈ Z t of norm y ∞ ≤ q/5 and small-norm matrices E ∈ Z m×t , S ∈ Z n×t satisfying (modulo q)

P = F • S + E , c 0 • S + y = c 1 -M • q/2 . ( 6
)
To this end, S T runs the prover in the ZK argument system in Section 6.4. 3. If the ZK argument produced by S T does not properly verify at step 2, R T halts and outputs ⊥. Otherwise, R T recalls the random string µ ∈ {0, 1} t that was chosen at step 1 and computes M ρi = M ⊕ µ. The transfer ends with S T and R T outputting S i = S i-1 and R i = R i-1 , respectively.

In the initialization phase, the sender has to repeat step 5 with each receiver to prove that {(a i , b i )} N i=1 are well-formed. Using the Fiat-Shamir heuristic [START_REF] Fiat | How to prove yourself: Practical solutions to identification and signature problems[END_REF], we can decrease this initialization cost from O(N • U ) to O(N ) (regardless of the number of users U ) by making the proof non-interactive. This modification also reduces each transfer to 5 communication rounds since, even in the transfer phase, the sender's ZK arguments can be non-interactive and the receiver's arguments only need to be WI, which is preserved when the basic ZK protocol (which has a ternary challenge space) is repeated ω(log n) times in parallel. To keep the security proof simple, we derive the matrix F ∈ Z n×m q from a second random oracle. Knowing a short basis of Λ ⊥ q (F), the simulator can extract the columns of S from the public key P ∈ Z n×m q . Details are given in Appendix D.

Security

The security of the above OT N k×1 protocol against static corruptions is stated by the following theorems.

OT with Access Control for Branching Programs

In this section, we extend our protocol of Section 4 into a protocol where database entries can be protected by access control policies consisting of branching programs. In a nutshell, the construction goes as follows.

When the database is set up, the sender signs (a binary representation of) each database entry (a i , b i ) together with a hash value h BP,i ∈ Z n q of the corresponding branching program. For each possessed attribute x ∈ {0, 1} κ , the user U obtains a credential Cred U,x from the issuer.

If U has a credential Cred U,x for an attribute x satisfying the ρ-th branching program, U can re-randomize (a ρ , b ρ ) into (c 0 , c 1 ), which is given to the sender, while proving that: (i) He knows a signature (τ, v) on some message (a ρ , b ρ , h BP,ρ ) such that (c 0 , c 1 ) is a re-randomization of (a ρ , b ρ ); (ii) The corresponding h BP,ρ is the hash value of (the binary representation of) a branching program BP ρ that accepts an attribute x ∈ {0, 1} κ for which he has a valid credential Cred U,x (i.e., BP ρ (x) = 1).

While statement (i) can be proved as in Section 4, handling (ii) requires a method of proving the possession of a (committed) branching program BP and a (committed) input x ∈ {0, 1} κ such that BP(x) = 1 while demonstrating possession of a credential for x.

Recall that a branching program BP of length L, input space {0, 1} κ and width 5 is specified by L tuples of the form (var(θ), π θ,0 , π θ,1 ) where

-var : [L] → [0, κ -1] is a function that associates the θ-th tuple with the coordinate x var(θ) ∈ {0, 1} of the input x = (x 0 , . . . , x κ-1 ) . -π θ,0 , π θ,1 : {0, 1, 2, 3, 4} → {0, 1, 2,
3, 4} are permutations that determine the θ-th step of the evaluation.

On input x = (x 0 , . . . , x κ-1 ) , BP computes its output as follows. For each bit b ∈ {0, 1}, let b denote the bit 1 -b. Let η θ denote the state of computation at step θ. The initial state is η 0 = 0 and, for θ ∈ [1, L], the state η θ is computed as

η θ = π θ,x var(θ) (η θ-1 ) = π θ,0 (η θ-1 ) • xvar(θ) + π θ,1 (η θ-1 ) • x var(θ) .
Finally, the output of evaluation is

BP(x) = 1 if η L = 0, otherwise BP(x) = 0.
We now let δ κ = log 2 κ and note that each integer in [0, κ -1] can be determined by δ κ bits. In particular, for each θ ∈ [L], let d θ,1 , . . . , d θ,δκ be the bits representing var(θ). Then, we consider the following representation of BP:

z BP = d 1,1 , . . . , d 1,δκ , . . . , d L,1 , . . . , d L,δκ , π 1,0 (0), . . . , π 1,0 (4), π 1,1 (0), . . . , π 1,1 (4), . . . , π L,0 (0), . . . , π L,0 (4), π L,1 (0), . . . , π L,1 (4) ∈ [0, 4] ζ , (7)
where ζ = L(δ κ + 10).

The OT-AC Protocol

We assume public parameters pp consisting of a modulus q, integers n, m such that m = 2n log q , a public matrix Ā ∈ Z n×m q , the maximal length L ∈ poly(n) of branching programs and their desired input length κ ∈ poly(n).

ISetup pp : Given public parameters pp = {q, n, m, Ā, L, κ}, generate a key pair (P K I , SK I ) ← Keygen(pp, 1) for the signature scheme in Section 3.1 in order to sign single-block messages (i.e., N b = 1) of length m I = n• log q +κ. Letting I = O(n), this key pair contains SK I = T A I ∈ Z m×m and

P K I := A I , {A I,j } I j=0 , D I , {D I,0 , D I,1 }, u I .
Issue I(pp, SK I , P K I , P U , x) ↔ U(pp, x, st U ) : On common input x ∈ {0, 1} κ , the issuer I and the user U interact in the following way:

1. If st U = ∅, U creates a pseudonym P U = Ā • e U ∈ Z n q , for a randomly chosen e U ← U ({0, 1} m ), which is sent to I. It sets st U = (e U , P U , 0, ∅, ∅). Otherwise, U parses its state st U as (e U , P U , f DB , C U , Cred U ).

The issuer I defines the message m

U,x = (vdec n,q-1 (P U ) |x ) ∈ {0, 1} m I .
Then, it runs the signing algorithm of Section 3.1 to obtain and return

cert U,x = τ U , v U , r U ← Sign(SK I , m U,x ) ∈ {0, 1} I × Z 2m × Z m , which binds U's pseudonym P U to the attribute string x ∈ {0, 1} κ . 3. U checks that cert U,x satisfies (2) and that v U ≤ σ √ 2m, r U ≤ σ √ m. If so, U sets C U := C U ∪ {x}, Cred U := Cred U ∪ {cert U,x } and updates its state st U = (e U , P U , f DB , C U , Cred U ). If cert U,x
does not properly verify, U aborts the interaction and leaves st U unchanged.

DBSetup P K I , DB = {(M i , BP i )} N i=1 : The sender DB has DB = {(M i , BP i )} N i=1
which is a database of N pairs made of a message M i ∈ {0, 1} t and a policy realized by a length-L branching program

BP i = {var i (θ), π i,θ,0 , π i,θ,1 } L θ=1 . 1. Choose a random matrix A HBP ← U Z n×ζ q
which will be used to hash the description of branching programs. 2. Generate a key pair for the signature scheme of Section 3.2 in order to sign Q = N messages of length m d = (2n + t) • log q each. This key pair consists of SK sig = T A ∈ Z m×m and P K sig := A, {A j } j=0 , D, u , where = log N and A, A 0 , . . . ,

A ∈ U (Z n×m q ), D ∈ U (Z n×m d q
) with m = 2n log q , m d = (2n + t) log q . The counter is initialized to τ = 0.

3. Sample S ← χ n×t which will serve as a secret key for an LWE-based encryption scheme. Then, sample F ← U (Z n×m q

), E ← χ m×t to compute

P = [p 1 | . . . |p t ] = F • S + E ∈ Z m×t q (8)
so that (F, P) forms a public key for a t-bit variant of Regev's system. 4. Sample vectors a 1 , . . . , a N ← U (Z n q ) and x 1 , . . . , x N ← χ t to compute

(a i , b i ) = a i , a i • S + x i + M i • q/2 ∈ Z n q × Z t q ∀i ∈ [N ] (9) 5. For each i = 1 to N , (a i , b i ) is bound to BP i as follows. a. Let z BP,i ∈ [0, 4] ζ be the binary representation of the branching program. Compute its digest h BP,i = A HBP • z BP,i ∈ Z n q . b. Using SK sig , generate a signature (τ i , v i ) ← Sign(SK sig , τ, m i ) on the message m i = vdec 2n+t,q-1 (a i |b i |h BP,i ) ∈ {0, 1} m d obtained by decomposing (a i |b i |h BP,i ) ∈ Z 2n+t q .
6. The database's public key is defined as P K DB = P K sig , (F, P), A HBP while the encrypted database is

{ER i = a i , b i , (τ i , v i ) , BP i } N i=1 . The sender DB outputs P K DB , {ER i , BP i } N i=1 and keeps SK DB = SK sig , S . Transfer DB(SK DB , P K DB , P K I ), U(ρ, st U , P K I , P K DB , ER ρ , BP ρ ) : Given an index ρ ∈ [N ], a record ER ρ = a ρ , b ρ , (τ ρ , v ρ
) and a policy BP ρ , the user U parses st U as (e U , P U , f DB , C U , Cred U ). If C U does not contain any x ∈ {0, 1} κ s.t. BP ρ (x) = 1 and Cred U contains the corresponding cert U,x , U outputs ⊥.

Otherwise, he selects such a pair (x, cert U,x ) and interacts with DB:

1. If f DB = 0, U interacts with DB for the first time and requires DB to prove knowledge of small-norm S ∈ Z n×t , E ∈ Z m×t , {x i } N i=1 and t-bit messages {M i } N i=1 satisfying (8)- [START_REF] Bourse | FHE circuit privacy almost for free[END_REF]. To do this, DB uses the ZK argument in Section 6.3. If there exists i ∈ [N ] such that (τ i , v i ) is an invalid signature on vdec 2n+t,q-1 (a i |b i |h BP,i ) or if the ZK argument does not verify, U aborts. Otherwise, U updates st U and sets f DB = 1.

U re-randomizes the pair (a

ρ , b ρ ) contained in ER ρ . It samples vectors e ← U ({-1, 0, 1} m ), µ ← U ({0, 1} t ) and ν ← U ([-B, B] t ) to compute (c 0 , c 1 ) = a ρ + F • e, b ρ + P • e + µ • q/2 + ν ∈ Z n q × Z t q , (10)
which is sent to DB as a re-randomization of (a ρ , b ρ + µ • q/2 ). Then, U provides an interactive WI argument that (c 0 , c 1 ) is a re-randomization of some (a ρ , b ρ ) associated with a policy BP ρ for which U has a credential cert U,x for some x ∈ {0, 1} κ such that BP ρ (x) = 1. In addition, U demonstrates possession of:

(i) a preimage z BP,ρ ∈ [0, 4] ζ of h BP,ρ = A HBP • z BP,ρ ∈ Z n q ;
(ii) a credential Cred U,x for the corresponding x ∈ {0, 1} κ and the private key e U ∈ {0, 1} m for the pseudonym P U to which x is bound; (iii) the coins leading to the randomization of some (a ρ , b ρ ). Then entire step is conducted by arguing knowledge of

                       e U ∈ {0, 1} m , m U,x ∈ {0, 1} m I , x ∈ {0, 1} κ , m U,x ∈ {0, 1} m/2 τ U ∈ {0, 1} I , v U = (v U,1 |v U,2 ) ∈ [-β, β] 2m , r U ∈ [-β, β] m // signature on m U,x = (vdecn,q-1(P U ) |x ) z BP,ρ ∈ [0, 4] ζ // representation of BPρ m ∈ {0, 1} m d , τ ∈ {0, 1} , v = (v 1 |v 2 ) ∈ Z 2m // signature on m = vdec2n+t,q-1(a i |b i |h BP,ρ ) e ∈ {-1, 0, 1} t , µ ∈ {0, 1} t , ν ∈ [-B, B] t ,
// coins allowing the re-randomization of (aρ, bρ) satisfying the relations (modulo q)

                                           H 2n+t,q-1 • m +    F P I t • q/2 I t -A HBP    •      e µ ν z BP,ρ      =    c 0 c 1 0 n    // (recall that (a ρ |b ρ |h BP,ρ ) = H2n+t,q-1 • m) A • v 1 + A 0 • v 2 + j=1 A j • (τ [j] • v 2 ) -D • m = u A I • v U,1 + A I,0 • v U,2 + I j=1 A I,j • (τ U [j] • v U,2 ) -D I • m U,x = u I D I,0 • r U + D I,1 • m U,x -H n,q-1 • m U,x = 0 H n,q-1 0 0 I κ • m U,x + - Ā 0 • e U + 0 -I κ • x = 0 (11)
and such that z BP,ρ ∈ [0, 4] ζ encodes BP ρ such that BP ρ (x) = 1. This is done by running the argument system described in Section 6.6. 3. If the ZK argument of step 2 verifies, DB decrypts (c 0 , c 1 )

∈ Z n q × Z t q to obtain M = (c 1 -S • c 0 )/(q/2) ∈ {0, 1} t , which is returned to U. Then, DB argues knowledge of y = c 1 -S • c 0 -M • q/2 ∈ Z t of norm y ∞ ≤ q/5 and small-norm E ∈ Z m×t , S ∈ Z n×t satisfying (modulo q) P = F • S + E , c 0 • S + y = c 1 -M • q/2 .
To this end, DB uses the ZK argument system of Section 6.4. 4. If the ZK argument produced by DB does not verify, U outputs ⊥. Otherwise, U recalls the string µ ∈ {0, 1} t and outputs M ρi = M ⊕ µ.

Like our construction of Section 4, the above protocol requires the DB to repeat a ZK proof of communication complexity Ω(N ) with each user U during the initialization phase. By applying the Fiat-Shamir heuristic as in Appendix D, the cost of the initialization phase can be made independent of the number of users: the sender can publicize P K DB , {ER i , BP i } N i=1 along with a with a universally verifiable non-interactive proof of well-formedness.

The security of the above protocol against static corruptions is proved in Appendix F, under the SIS and LWE assumptions.

Our Zero-Knowledge Arguments of Knowledge

This section provides all the zero-knowledge arguments of knowledge (ZKAoK) used as building blocks in our two adaptive OT schemes. Our argument systems operate in the framework of Stern's protocol [START_REF] Stern | A new paradigm for public key identification[END_REF], which was originally introduced in the context of code-based cryptography but has been developed [START_REF] Ling | Improved zero-knowledge proofs of knowledge for the isis problem, and applications[END_REF][START_REF] Ling | Group signatures from lattices: Simpler, tighter, shorter, ring-based[END_REF][START_REF] Libert | Zero-knowledge arguments for latticebased accumulators: Logarithmic-size ring signatures and group signatures without trapdoors[END_REF][START_REF] Libert | Signature schemes with efficient protocols and dynamic group signatures from lattice assumptions[END_REF][START_REF] Libert | Zero-knowledge arguments for matrix-vector relations and lattice-based group encryption[END_REF] into a useful tool for lattice-based cryptography.

In Section 6.1, we first recall Stern's protocol in a generalized, abstract manner suggested in [START_REF] Libert | Signature schemes with efficient protocols and dynamic group signatures from lattice assumptions[END_REF]. Then, using various transformations, we will demonstrate that all the required ZKAoKs can be obtained from this abstract protocol. Our basic strategy and techniques are summarized in Section 6.2, while the details of the protocols are given in the next subsections. In particular, our treatment of hidden branching programs in Section 6.6 is rather sophisticated as it requires to handle a number of secret objects nested together via branching programs, commitments, encryptions, signatures and Merkle trees. This protocol introduces new techniques and insights of which we provide the intuition hereafter.

Abstracting Stern's Protocol

Let K, D, q be positive integers with D ≥ K and q ≥ 2, and let VALID be a subset of Z D . Suppose that S is a finite set such that every φ ∈ S can be associated with a permutation Γ φ of D elements satisfying the following conditions:

w ∈ VALID ⇐⇒ Γ φ (w) ∈ VALID, If w ∈ VALID and φ is uniform in S, then Γ φ (w) is uniform in VALID. ( 12
)
We aim to construct a statistical ZKAoK for the following abstract relation:

R abstract = (M, v), w ∈ Z K×D q × Z D q × VALID : M • w = v mod q.
Note that, Stern's original protocol corresponds to the special case when VALID = {w ∈ {0, 1} D : wt(w) = k}, where wt(•) denotes the Hamming weight and k < D is a given integer, S = S D is the set of all permutations of D elements and Γ φ (w) = φ(w).

The conditions in (12) play a crucial role in proving in ZK that w ∈ VALID. To this end, the prover samples a random φ ← U (S) and lets the verifier check that Γ φ (w) ∈ VALID without learning any additional information about w due to the randomness of φ. Furthermore, to prove in a zero-knowledge manner that the linear equation is satisfied, the prover samples a masking vector r w ← U (Z D q ), and convinces the verifier instead that M

• (w + r w ) = M • r w + v mod q.
The interaction between prover P and verifier V is described in Figure 1. The protocol uses a statistically hiding and computationally binding string commitment scheme COM (e.g., the SIS-based scheme from [START_REF] Kawachi | Concurrently secure identification schemes based on the worst-case hardness of lattice problems[END_REF]).

Theorem 4. The protocol in Figure 1 is a statistical ZKAoK with perfect completeness, soundness error 2/3, and communication cost O(D log q). Namely:

1. Commitment: Prover samples rw ← U (Z D q ), φ ← U (S) and randomness ρ1, ρ2, ρ3 for COM. Then he sends CMT = C1, C2, C3 to the verifier, where C1 = COM(φ, M • rw mod q; ρ1), C2 = COM(Γ φ (rw); ρ2), C3 = COM(Γ φ (w + rw mod q); ρ3).

Challenge:

The verifier sends a challenge Ch ← U ({1, 2, 3}) to the prover. 3. Response: Depending on Ch, the prover sends RSP computed as follows:

-Ch = 1: Let tw = Γ φ (w), tr = Γ φ (rw), and RSP = (tw, tr, ρ2, ρ3).

-Ch = 2: Let φ2 = φ, w2 = w + rw mod q, and RSP = (φ2, w2, ρ1, ρ3).

-Ch = 3: Let φ3 = φ, w3 = rw, and RSP = (φ3, w3, ρ1, ρ2).

Verification: Receiving RSP, the verifier proceeds as follows:

-Ch = 1: Check that tw ∈ VALID, C2 = COM(tr; ρ2), C3 = COM(tw +tr mod q; ρ3).

-Ch = 2: Check that C1 = COM(φ2, M•w2 -v mod q; ρ1), C3 = COM(Γ φ 2 (w2); ρ3). -Ch = 3: Check that C1 = COM(φ3, M • w3; ρ1), C2 = COM(Γ φ 3 (w3); ρ2).
In each case, the verifier outputs 1 if and only if all the conditions hold. -There exists a polynomial-time simulator that, on input (M, v), outputs an accepted transcript statistically close to that produced by the real prover. -There exists a polynomial-time knowledge extractor that, on input a commitment CMT and 3 valid responses (RSP 1 , RSP 2 , RSP 3 ) to all 3 possible values of the challenge Ch, outputs w ∈ VALID such that M • w = v mod q.

The proof of the theorem relies on standard simulation and extraction techniques for Stern-like protocols [START_REF] Kawachi | Concurrently secure identification schemes based on the worst-case hardness of lattice problems[END_REF][START_REF] Ling | Improved zero-knowledge proofs of knowledge for the isis problem, and applications[END_REF][START_REF] Libert | Signature schemes with efficient protocols and dynamic group signatures from lattice assumptions[END_REF]. It is given in Appendix G.

Our Strategy and Basic Techniques, In a Nutshell

Before going into the details of our protocols, we first summarize our governing strategy and the techniques that will be used in the next subsections.

In each protocol, we prove knowledge of (possibly one-dimensional) integer vectors {w i } i that have various constraints (e.g., smallness, special arrangements of coordinates, or correlation with one another) and satisfy a system

i M i,j • w i = v j j , (13)
where {M i,j } i,j , {v j } j are public matrices (which are possibly zero or identity matrices) and vectors. Our strategy consists in transforming this entire system into one equivalent equation M•w = v, where matrix M and vector v are public, while the constraints of the secret vector w capture those of witnesses {w i } i and they are provable in zero-knowledge via random permutations. For this purpose, the Stern-like protocol from Section 6.1 comes in handy.

A typical transformation step is of the form w i → wi , where there exists public matrix P i,j such that P i,j • wi = w i . This subsumes the decomposition and extension mechanisms which first appeared in [START_REF] Ling | Improved zero-knowledge proofs of knowledge for the isis problem, and applications[END_REF].

-Decomposition: Used when w i has infinity norm bound larger than 1 and we want to work more conveniently with wi whose norm bound is exactly 1. In this case, P i,j is a decomposition matrix (see Section 2.5). -Extension: Used when we insert "dummy" coordinates to w i to obtain wi whose coordinates are somewhat balanced. In this case, P i,j is a {0, 1}matrix with zero-columns corresponding to positions of insertions.

Such a step transforms the term M i,j • w i into M i,j • wi , where M i,j = M i,j • P i,j is a public matrix. Also, using the commutativity property of addition, we often group together secret vectors having the same constraints. After a number of transformations, we will reach a system equivalent to (13):

       M 1,1 • w 1 + M 1,2 • w 2 + • • • + M 1,k • w k = v 1 , . . . M t,1 • w 1 + M t,2 • w 2 + • • • + M t,k • w k = v t , (14)
where integers t, k and matrices M i,j are public. Defining

M =     M 1,1 M 1,2 • • • M 1,k . . . . . . . . . . . . M t,1 M t,2 • • • M t,k     ; w =     w 1 . . . w k     ; v =     v 1 . . . v t     ,
we obtain the unified equation M • w = v mod q. At this stage, we will use a properly defined composition of random permutations to prove the constraints of w. We remark that the crucial aspect of the above process is in fact the manipulation of witness vectors, while the transformations of public matrices/vectors just follow accordingly. To ease the presentation of the next subsections, we will thus only focus on the secret vectors.

In the process, we will employ various extending and permuting techniques which require introducing some notations. The most frequently used ones are given in Table 1. Some of these techniques appeared (in slightly different forms) in previous works [START_REF] Ling | Improved zero-knowledge proofs of knowledge for the isis problem, and applications[END_REF][START_REF] Ling | Group signatures from lattices: Simpler, tighter, shorter, ring-based[END_REF][START_REF] Libert | Zero-knowledge arguments for latticebased accumulators: Logarithmic-size ring signatures and group signatures without trapdoors[END_REF][START_REF] Libert | Signature schemes with efficient protocols and dynamic group signatures from lattice assumptions[END_REF][START_REF] Libert | Zero-knowledge arguments for matrix-vector relations and lattice-based group encryption[END_REF]. The last three parts of the table summarizes newly-introduced techniques that will enable the treatment of secret-andcorrelated objects involved in the evaluation of hidden branching programs.

In particular, the intriguing technique of the last row will be used for proving knowledge of secret integer z of the form z = x • y for some (x, y) ∈ [0, 4] × {0, 1} satisfying other relations. The following example illustrates how it works.

-∀φ ∈ S2m, x ∈ Z 2m : x ∈ B 2 m ⇔ φ(x ) ∈ B 2 m . -To prove x ∈ {0, 1} m : Extend x to x ∈ B 2 m , then permute x . B 3 m
-The set of vectors in {-1, 0, 1} 3m that have exactly m coordinates equal to j, for every j ∈ {-1, 0, 1}.

-∀φ ∈ S3m, x ∈ Z 3m : x ∈ B 3 m ⇔ φ(x ) ∈ B 3 m . -To prove x ∈ {-1, 0, 1} m : Extend x to x ∈ B 3 m , then permute x . ext2(•)
and

T2[•](•) -For c ∈ {0, 1} : ext2(c) = (c, c) ∈ {0, 1} 2 .
-For b ∈ {0, 1} and

x = (x0, x1) ∈ Z 2 : T2[b](x) = (x b , xb) .
-

Property: x = ext2(c) ⇔ T2[b](x) = ext2(c ⊕ b).
-To prove c ∈ {0, 1} simultaneously satisfies many relations: Extend it to x = ext2(c), then permute and use the same b at all appearances.

expand(•,•)

and

Texp[•,•](•) -For c ∈ {0, 1} and x ∈ Z m : expand(c, x) = (c • x | c • x ) ∈ Z 2m . -For b ∈ {0, 1}, φ ∈ Sm, v = v0 v1 ∈ Z 2m : Texp[b, φ](v) = φ(v b ) φ(vb) .
-

Property: v = expand(c, x) ⇔ Texp[b, φ](v) = expand(c ⊕ b, φ(x)). [•]5 For k ∈ Z: [k]5 denotes the integer t ∈ {0, 1, 2, 3, 4}, s.t. t = k mod 5.

ext5(•)

and

T5[•](•) -For x ∈ [0, 4] : ext5(x) = ([x+4]5, [x+3]5, [x+2]5, [x+1]5, x) ∈ [0, 4] 5 .
-For c ∈ [0, 4] and v = (v0, v1, v2, v3, v4) ∈ Z 5 :

T5[c](v) = v [-c] 5 , v [-c+1] 5 , v [-c+2] 5 , v [-c+3] 5 , v [-c+4] 5 .
-

Property: v = ext5(x) ⇔ T5[c](v) = ext5(x + c mod 5).
-To prove x ∈ [0, 4] simultaneously satisfies many relations: Extend it to v = ext5(x), then permute and use the same c at all appearances.

unitx -∀x ∈ [0, 4]: unitx is the 5-dim unit vector (v0, . . . , v4) with vx = 1.

-

For c ∈ [0, 4], v ∈ Z 5 : v = unitx ⇔ T5[c](v) = unit x+c mod 5 .
→ Allow proving v = unitx for some x ∈ [0, 4] satisfying other relations.

ext5×2(•,•) and T5×2[•,•](•) -For x ∈ [0, 4] and y ∈ {0, 1}: ext5×2(x, y) = ([x + 4]5 • ȳ, [x + 4]5 • y, [x + 3]5 • ȳ, [x + 3]5 • y, [x + 2]5 • ȳ, [x + 2]5 • y, [x + 1]5 • ȳ, [x + 1]5 • y, x • ȳ, x • y) ∈ [0, 4] 10 -For (c, b) ∈ [0, 4] × {0, 1} and v = (v0,0, v0,1, . . . , v4,0, v4,1) ∈ Z 10 : T5×2[c, b](v) = v [-c] 5 ,b , v [-c] 5 ,b , v [-c+1] 5 ,b , v [-c+1] 5 ,b , v [-c+2] 5 ,b , v [-c+2] 5 ,b , v [-c+3] 5 ,b , v [-c+3] 5 ,b , v [-c+4] 5 ,b , v [-c+4] 5 ,b . -Property: v = ext5×2(x, y) ⇔ T5×2[c, b](v) = ext5×2(x+c mod 5, y⊕b).
→ Allow proving z = x • y for some (x, y) ∈ [0, 4] × {0, 1} satisfying other relations: Extend z to v = ext5×2(x, y), then permute and use the same c, b at all appearances of x, y, respectively.

Table 1. Basic notations and extending/permuting techniques used in our protocols.

Protocol 1

Let n, m, q, N, t, B χ be the parameters defined in Section 4. The protocol allows the prover to prove knowledge of LWE secrets and the well-formedness of ciphertexts. It is summarized as follows.

Common input:

F ∈ Z n×m q , P ∈ Z m×t q ; {a i ∈ Z n q , b i ∈ Z t q } N i=1 . Prover's goal is to prove knowledge of S ∈ [-B χ , B χ ] n×t , E ∈ [-B χ , B χ ] m×t , {x i ∈ [-B χ , B χ ] t , M i ∈ {0, 1} t } N i=1
such that the following equations hold:

F • S + E = P mod q ∀i ∈ [N ] : S • a i + x i + q/2 • M i = b i mod q. ( 15
)
For each j ∈ [t], let p j , s j , e j be the j-th column of matrices P, S, E, respectively. For each (i, j)

∈ [N ] × [t], let b i [j], x i [j], M i [j]
denote the j-th coordinate of vectors b i , x i , M i , respectively. Then, observe that (15) can be rewritten as:

∀j ∈ [t] : F • s j + I m • e j = p j mod q ∀(i, j) ∈ [N ] × [t] : a i • s j + 1 • x i [j] + q/2 • M i [j] = b i [j] mod q. ( 16
)
Then, we form the following vectors:

w 1 = s 1 | . . . | s t | e 1 | . . . | e t | (x 1 [1], . . . , x N [t]) ∈ [-B χ , B χ ] (n+m+N )t ; w 2 = (M 1 [1], . . . , M N [t]) ∈ {0, 1} N t .
Next, we run vdec (n+m+N )t,Bχ to decompose w 1 into w1 and then extend w1 to w * 1 ∈ B 3 (n+m+N )tδ Bχ . We also extend w 2 into w * 2 ∈ B 2 N t and we then form w = ((w * 1 ) | (w * 2 ) ) ∈ {-1, 0, 1} D , where D = 3(n + m + N )tδ Bχ + 2N t. Observe that relations [START_REF] Camenisch | Simulatable adaptive oblivious transfer[END_REF] can be transformed into one equivalent equation of the form M • w = v mod q, where M and v are built from the common input.

Having performed the above unification, we now define VALID as the set of all vectors t = (t 1 | t 2 ) ∈ {-1, 0, 1} D , where t 1 ∈ B 3 (n+m+N )tδ Bχ and t 2 ∈ B 2 N t . Clearly, our vector w belongs to the set VALID.

Next, we specify the set S and permutations of D elements {Γ φ : φ ∈ S}, for which the conditions in [START_REF] Brickell | Design validations for discrete logarithm based signature schemes[END_REF] hold.

-

S := S 3(n+m+N )tδ Bχ × S 2N t . -For φ = (φ 1 , φ 2 ) ∈ S and for t = (t 1 | t 2 ) ∈ Z D , where t 1 ∈ Z 3(n+m+N )tδ Bχ and t 2 ∈ Z 2N t , we define Γ φ (t) = (φ 1 (t 1 ) | φ 2 (t 2 ) ) .
By inspection, it can be seen that the desired properties in [START_REF] Brickell | Design validations for discrete logarithm based signature schemes[END_REF] are satisfied.

As a result, we can obtain the required ZKAoK by running the protocol from Section 6.1 with common input (M, v) and prover's input w. The protocol has communication cost

O(D log q) = O(λ) • O(N t) bits.
While this protocol has linear complexity in N , it is only used in the initialization phase, where Ω(N ) bits inevitably have to be transmitted anyway.

Protocol 2

Let n, m, q, N, t, B be system parameters. The protocol allows the prover to prove knowledge of LWE secrets and the correctness of decryption.

Common input: F ∈ Z n×m q , P ∈ Z m×t q ; c 0 ∈ Z n q , c 1 ∈ Z t q , M ∈ {0, 1} t . Prover's goal is to prove knowledge of S ∈ [-B χ , B χ ] n×t , E ∈ [-B χ , B χ ] m×t
and y ∈ [-q/5, q/5] t such that the following equations hold:

F • S + E = P mod q; c 0 • S + y = c 1 -M • q/2 mod q. ( 17
)
For each j ∈ [t], let p j , s j , e j be the j-th column of matrices P, S, E, respectively; and let y[j], c 1 [j], M [j] be the j-th entry of vectors y, c 1 , M , respectively. Then, observe that ( 17) can be re-written as:

∀j ∈ [t] : F • s j + I m • e j = p j mod q c 0 • s j + 1 • y[j] = c 1 [j] -M [j] • q/2 mod q. ( 18
)
Next, we form vector

w 1 = (s 1 | . . . | s t | e 1 | . . . | e t ) ∈ [-B χ , B χ ] (n+m)t ,
then decompose it to w1 ∈ {-1, 0, 1} (n+m)tδ Bχ , and extend w1 to w * 1 ∈ B 3 (n+m)tδ Bχ . At the same time, we decompose vector y = (y[1], . . . , y[t]) ∈ [-q/5, q/5] t to ȳ ∈ {-1, 0, 1} tδ q/5 , and then extend ȳ to y * ∈ B 3 tδ q/5 . Defining the ternary vector w = ((w * 1 ) | (y * ) ) ∈ {-1, 0, 1} D of dimension D = 3(n + m)tδ Bχ + 3tδ q/5 , we finally obtain the equation M • w = v mod q, for public matrix M and public vector v. Using similar arguments as in Section 6.3, we can obtain the desired zero-knowledge argument system. The protocol has communication cost O(D log q) = O(λ) • O(t) bits.

Protocol 3

Let n, m, m d , q, t, , B be the parameters defined in Section 4. The protocol allows the prover to argue that a given ciphertext is a correct randomization of some hidden ciphertext and that he knows a valid signature on that ciphertext. Let β be the infinity norm bound of these valid signatures.

Common input: It consists of matrices F ∈ Z n×m q , P ∈ Z m×t q , A, A 0 , A 1 , . . . , A ∈ Z n×m q , D ∈ Z n×m d q and vectors c 0 ∈ Z n q , c 1 ∈ Z t q , u ∈ Z n q . Prover's goal is to prove knowledge of m ∈ {0, 1} m d , µ ∈ {0, 1} t , e ∈ {-1, 0, 1} t , ν ∈ [-B, B] t , τ = (τ [1], . . . , τ [ ]) ∈ {0, 1} , v 1 , v 2 ∈ [-β, β] m such that the following equations hold:      A • v 1 + A 0 • v 2 + j=1 A j • (τ [j] • v 2 ) -D • m = u mod q; H n+t,q-1 •m + F P •e + 0 n×t q 2 •I t •µ + 0 n×t I t •ν = c 0 c 1 mod q. ( 19
)
For this purpose, we perform the following transformations on the witnesses.

Decompositions. Decompose vectors v 1 , v 2 , ν to vectors v1 ∈ {-1, 0, 1} mδ β , v2 ∈ {-1, 0, 1} mδ β , ν ∈ {-1, 0, 1} tδ B , respectively. Extensions/Combinations. -Let w 1 = (m | µ ) ∈ {0, 1} m d +t and extend it into w * 1 ∈ B 2 m d +t . -Let w 2 = (v 1 | ν | e ) ∈ {-1, 0, 1}
= w * 1 | w * 2 | s 0 | s 1 | . . . | s ∈ {-1, 0, 1} D , where D = (2 + 2)3mδ β + 3tδ B + 3t + 2(m d + t).
At this point, we observe that the equations in [START_REF] Chor | Private information retrieval[END_REF] can be equivalently transformed into M • w = v mod q, where the matrix M and the vector v are built from the public input.

Having performed the above transformations, we now define VALID as the set of all vectors t = (t

1 | t 2 | t 3,0 | t 3,1 | . . . | t 3, ) ∈ {-1, 0, 1} D for which there exists τ = (τ [1], . . . , τ [ ]) ∈ {0, 1} such that: t 1 ∈ B 2 m d +t ; t 2 ∈ B 3 mδ β +tδ B +t ; t 3,0 ∈ B 3 mδ β ; ∀j ∈ [ ] : t 3,j = expand(τ [j], t 3,0 ).
It can be seen that w belongs to this tailored set. Now, let us specify the set S and permutations of D elements {Γ φ : φ ∈ S} satisfying the conditions in [START_REF] Brickell | Design validations for discrete logarithm based signature schemes[END_REF].

-

S := S 2(m d +t) × S 3(mδ β +tδ B +t) × S 3mδ β × {0, 1} . -For φ = φ 1 , φ 2 , φ 3 , (b[1], . . . , b[ ]) ∈ S, we define the permutation Γ φ that transforms vector t = (t 1 | t 2 | t 3,0 | t T 3,1 | . . . | t 3, ) ∈ Z D as follows: Γ φ (t) = φ 1 (t 1 ) | φ 2 (t 2 ) | φ 3 (t 3,0 ) | T exp [b[1], φ 3 ](t 3,1 ) | . . . | T exp [b[ ], φ 3 ](t 3, )
.

By inspection, it can be seen that the properties in [START_REF] Brickell | Design validations for discrete logarithm based signature schemes[END_REF] are indeed satisfied.

As a result, we can obtain the required argument of knowledge by running the protocol from Section 6.1 with common input (M, v) and prover's input w. The protocol has communication cost O(D log q) = O(λ) • O(log N + t) bits.

Protocol 4: A Treatment of Hidden Branching Programs

We now present the proof system run by the user in the OT-AC system of Section 5. It allows arguing knowledge of an input x = (x 0 , . . . , x κ-1 ) ∈ {0, 1} κ satisfying a hidden branching program BP = {(var(θ), π θ,0 , π θ,1 )} L θ=1 of length for L ∈ poly(λ). The prover should additionally demonstrate that: (i) He has a valid credential for x; (ii) The hashed encoding of BP is associated with some hidden ciphertext of the database (and he knows a signature guaranteeing this link); (iii) A given ciphertext is a re-randomization of that hidden ciphertext.

Recall that, at each step θ ∈ [L] of the evaluation of BP(x), we have to look up the value x var(θ) in x = (x 0 , . . . , x κ-1 ) to compute the θ-th state η θ as per

η θ = π θ,x var(θ) (η θ-1 ) = π θ,0 (η θ-1 ) • xvar(θ) + π θ,1 (η θ-1 ) • x var(θ) . (20)
To prove that each step is done correctly, it is necessary to provide evidence that the corresponding search is honestly carried out without revealing x var(θ) , var(θ) nor {π θ,b } 1 b=0 . To this end, a first idea is to perform a simple left-toright search on (x 0 , . . . , x κ-1 ): namely, (20) is expressed in terms of a matrixvector relation where η θ is encoded as a unit vector of dimension 5; {π θ,b } 1 b=0 are represented as permutation matrices; and x var(θ) = M var(θ) • x is computed using a matrix M var(θ) ∈ {0, 1} κ×κ containing exactly one 1 per row. While this approach can be handled using proofs for matrix-vector relations using the techniques of [START_REF] Libert | Zero-knowledge arguments for matrix-vector relations and lattice-based group encryption[END_REF], the expected complexity is O(κ) for each step, so that the total complexity becomes O(Lκ). Fortunately, a better complexity can be achieved.

If we instead perform a dichotomic search on x = (x 0 , . . . , x κ-1 ) , we can reduce the complexity of each step to O(log κ). To this end, we need to prove a statement "I performed a correct dichotomic search on my secret array x".

In order to solve this problem, we will employ two existing lattice-based tools (which we recall in Section H.1 of Appendix, for the sake of completeness):

(i) A variant of the SIS-based computationally binding and statistically hiding commitment scheme from [START_REF] Kawachi | Concurrently secure identification schemes based on the worst-case hardness of lattice problems[END_REF], which allows to commit to one-bit messages; (ii) The SIS-based Merkle hash tree proposed in [START_REF] Libert | Zero-knowledge arguments for latticebased accumulators: Logarithmic-size ring signatures and group signatures without trapdoors[END_REF].

Let Ā ← U (Z n×m q
) and a com ← U (Z n q ). For each i ∈ [0, κ -1], we let the receiver commit to x i ∈ {0, 1} as com i = a com • x i + Ā • r com,i , with r com,i ← U ({0, 1} m ), and reveal com 1 , . . . , com κ-1 to the sender. We build a Merkle tree of depth δ κ = log κ on top of the leaves com 0 , . . . , com κ-1 using the SIS-based hash function h Ā : {0, 1} n log q × {0, 1} n log q → {0, 1} n log q of [START_REF] Libert | Zero-knowledge arguments for latticebased accumulators: Logarithmic-size ring signatures and group signatures without trapdoors[END_REF]. Our use of Merkle trees is reminiscent of [START_REF] Libert | Zero-knowledge arguments for latticebased accumulators: Logarithmic-size ring signatures and group signatures without trapdoors[END_REF] in that the content of the leaves is public. The Merkle tree will actually serve as a "bridge" ensuring that: (i) The same string x is used in all steps while enabling dichotomic searches; (ii) At each step, the prover indeed uses some coordinate of x (without revealing which one), the choice of which is dictated by a path in the tree determined by var(θ).

Since {com i } κ-1 i=0 are public, both parties can deterministically compute the root u tree of the Merkle tree. For each θ ∈ [L], we consider the binary representation d θ,1 , . . . , d θ,δκ of var(θ), which is part of the encoding of BP defined in [START_REF] Böhl | Confined guessing: New signatures from standard assumptions[END_REF]. We then prove knowledge of a bit y θ satisfying the statement "From the root u tree ∈ {0, 1} n log q of the tree, the path determined by the bits d θ,1 , . . . , d θ,δκ leads to the leaf associated with the commitment opened to y θ ." If the Merkle tree and the commitment scheme are both secure, it should hold that y θ = x var(θ) . Said otherwise, we can provably perform a "dichotomic search" for x var(θ) = y θ . Moreover, the techniques from [START_REF] Libert | Zero-knowledge arguments for latticebased accumulators: Logarithmic-size ring signatures and group signatures without trapdoors[END_REF] can be adapted to do this in zero-knowledge manner, i.e., without revealing the path nor the reached leaf. Now, our task can be divided into 3 steps: (i) Proving that the searches on Merkle tree yield y 1 , . . . , y L ; (ii) Proving that the branching program evaluates to BP(x) = 1 if y 1 , . . . , y L are used in the evaluation; (iii) Proving all the other relations mentioned above, as well as the consistency of {com i } κ-1 i=0 and the fact that they open to a certified x ∈ {0, 1} κ .

Thanks to dichotomic searches, the communication cost drops to O(Lδ κ +κ). These steps can be treated as explained below.

The Merkle Tree Step. At each step θ ∈ [L], the prover demonstrates knowledge of a path consisting of δ κ nodes g θ,1 , . . . , g θ,δκ ∈ {0, 1} n log q determined by d θ,1 , . . . , d θ,δκ , as well as their sibling nodes t θ,1 , . . . , t θ,δκ ∈ {0, 1} n log q . Also, the prover argues knowledge of an opening (y θ , r θ ) ∈ {0, 1} × {0, 1} m for the commitment of which g θ,δκ is a binary decomposition. As shown in [START_REF] Libert | Zero-knowledge arguments for latticebased accumulators: Logarithmic-size ring signatures and group signatures without trapdoors[END_REF] (and recalled in Appendix H.1), it suffices to prove the following relations (mod q):

∀θ ∈ [L]                              Ā • expand(d θ,1 , g θ,1 ) + Ā • expand( dθ,1 , t θ,1 ) = H n,q-1 •u tree , Ā • expand(d θ,2 , g θ,2 ) + Ā • expand( dθ,2 , t θ,2 ) -H n,q-1 • g θ,1 = 0, . . . Ā • expand(d θ,δκ , g θ,δκ ) + Ā • expand( dθ,κ , t θ,κ ) -H n,q-1 • g θ,δκ-1 = 0, a com • y θ + Ā • r θ -H n,q-1 • g θ,δκ = 0, (21)
where expand(•, •) is defined in Table 1.

Extending.

-For each (θ, i)

∈ [L] × [δ κ ]: Extend g θ,i , t θ,i ∈ {0, 1} m/2 to g θ,i , t θ,i ∈ B 2
m/2 , respectively. Then, let g θ,i = expand(d θ,i , g θ,i ) and t θ,i = expand( dθ,i , t θ,i ).

-For each θ ∈ [L], extend the bit y θ into the vector y θ = ext 2 (y θ ) ∈ {0, 1} 2 .

-Let r = (r 1 | . . . | r L ) ∈ {0, 1} mL , then extend it into the vector r ∈ B 2 mL .

Combining. Next, we let D tree = 5mLδ κ + 2L + 2mL and define

w tree = g 1,1 | g 1,1 | t 1,1 | . . . | g 1,δκ | g 1,δκ | t 1,δκ | . . . | g L,1 | g L,1 | t L,1 | . . . | g L,δκ | g L,δκ | t L,δκ | y 1 | . . . | y L | r ∈ {0, 1} Dtree . ( 22
)
Then, observe that, the above L(δ κ + 1) equations can be combined into one:

M tree • w tree = v tree mod q, (23)
where matrix M tree and vector v tree are built from the public input.

The Branching Program Step. The last three parts of Table 1 describe the vector transformations that will be used to handle the secret vectors appearing in the evaluation of BP. The following equations emulate the evaluation process. In particular, for each θ ∈ [2, L], we introduce an extra vector e θ = (c θ,0 , . . . , c θ,4 ) ∈ {0, 1} 5 to enable the extraction of the values π θ,0 (η θ-1 ), and π θ,1 (η θ-1 ).

                                           π 1,0 (0) • ȳ1 + π 1,1 (0) • y 1 -η 1 = 0,
// computing η1 with η0 = 0 e 2 -4 i=0 unit i • c 2,i = (0, 0, 0, 0, 0) , // we will also prove e2 = unitη 1 f 2,0 -

4 i=0 π 2,0 (i) • c 2,i = 0, // meaning: f2,0 = π2,0(η1) f 2,1 - 4 i=0 π 2,1 (i) • c 2,i = 0, // meaning: f2,1 = π2,1(η1) f 2,0 • ȳ2 + f 2,1 • y 2 -η 2 = 0, // computing η2 . . . e L - 4 i=0 unit i • c L,i = (0, 0, 0, 0, 0) , // we will also prove e L = unitη L-1 f L,0 - 4 i=0 π L,0 (i) • c L,i = 0, // meaning: f L,0 = π L,0 (η L-1 ) f L,1 - 4 i=0 π L,1 (i) • c L,i = 0, // meaning: f L,1 = π L,1 (η L-1 ) f L,0 • ȳL + f L,1 • y L = 0. // final state η L = 0 (24)
Extending.

-

For each θ ∈ [L -1], extend η θ ∈ [0, 4] to 5-dimensional vector s θ = ext 5 (η θ ). -For each (θ, j) ∈ [2, L] × {0, 1}, extend f θ,j ∈ [0, 4] to f θ,j = ext 5 (f θ,j ). -For each (θ, i) ∈ [2, L] × [0, 4], extend c θ,i ∈ {0, 1} to c θ,i = ext 2 (c θ,i ).
-Extend the products π 1,0 (0) • ȳ1 and π 1,1 (0) • y 1 into 10-dimensional vectors h 1,0 = ext 5×2 (π 1,0 (0), ȳ1 ) and h 1,1 = ext 5×2 (π 1,1 (0), y 1 ), respectively.

-For each θ ∈ [2, L], extend the products f θ,0 • ȳθ and f θ,1 • y θ into 10dimensional vectors h θ,0 = ext 5×2 (f θ,0 , ȳθ ) and h θ,1 = ext 5×2 (f θ,1 , y θ ).

-For (θ, i) ∈ [2, L]×[0, 4], extend the products π θ,0 (i)•c θ,i and π θ,1 (i)•c θ,i into z θ,0,i = ext 5×2 (π θ,0 (i), c θ,i ) and z θ,1,i = ext 5×2 (π θ,1 (i), c θ,i ), respectively.

Combining. Let D BP = 150L -130, and form w BP ∈ [0, 4] D BP of the form:

s 1 | . . . | s L-1 | e 2 | . . . | e L | c 2,0 | . . . | c L,4 | z 2,0,0 | . . . | z L,1,4 | f 2,0 | . . . | f L,1 | h 1,0 | h 1,1 | h 2,0 | h 2,1 | . . . | h L,0 | h L,1 . (25)
Then, observe that the vector w BP of (25) satisfies one equation of the form:

M BP • w BP = v BP , (26)
where matrix M BP and vector v BP are obtained from the common input. Note that we work with integers in [0, 4], which are much smaller than q. As a result,

M BP • w BP = v BP mod q. ( 27
)
Conversely, if we can prove that (27) holds for a well-formed vector w BP , then that vector should also satisfy [START_REF] Fiat | How to prove yourself: Practical solutions to identification and signature problems[END_REF].

The Third

Step. In the third layer, we have to prove knowledge of:

             d 1,1 , . . . , d L,δκ ∈ {0, 1}, π 1,0 (0), . . . , π L,1 (4) ∈ [0, 4], m ∈ {0, 1} m d , x = (x 0 , . . . , x κ-1 ) ∈ {0, 1} κ , m U,x ∈ {0, 1} m 2 +κ , m U,x ∈ {0, 1} m 2 , e U ∈ {0, 1} m , r com,0 , . . . , r com,κ-1 ∈ {0, 1} m , µ ∈ {0, 1} t , τ ∈ {0, 1} , τ U ∈ {0, 1} I ,v 1 ,v 2 ,v U,1 ,v U,2 ,r U ∈ [-β, β] m ,e ∈ {-1, 0, 1} t ,ν ∈ [-B, B] t , (28)
which satisfy the equations of (11) for z BP,ρ = (d 1,1 , . . . , d L,δκ , π 1,0 (0), . . . , π L,1 (4)) and, ∀i ∈ [0, κ -1], the bit x i is committed in com i with randomness r com,i :

   a com . . . a com    • x +    Ā . . . Ā    •    r com,0 . . . r com,κ-1    =    com 0 . . . com κ-1    mod q.
Decomposing. We use

vdec m,β (•) to decompose v 1 , v 2 , v U,1 , v U,2 , r U ∈ [-β, β] m into v1 , v2 , vU,1 , vU,2 , rU ∈ {-1, 0, 1} mδ β , respectively. Similarly, we decompose vector ν ∈ [-B, B] t into vector ν = vdec t,B (ν) ∈ {-1, 0, 1} tδ B .
Extending and Combining. Next, we perform the following steps: Given the above transformations, let D 3 = 2L(δ κ + 25) + 2D 3,1 + 3D 3,2 + 3mδ β (2 + 1) + 3mδ β (2 I + 1) and construct vector w 3 ∈ [-1, 4] D3 of the form:

-For each (θ, i) ∈ [L] × [δ κ ], extend d θ,i to d θ,i = ext 2 (d θ,i ). -For each (θ, j, i) ∈ [L] × {0, 1} × [0, 4], extend π θ,j (i) to Π θ,j,i = ext 5 (π θ,j (i)). -Let w 3,1 = x |r com,0 | . . . |r com,κ-1 |m U,x | m U,x |m | e U |µ ∈ {0, 1} D3,1 , where D 3,1 = κ(m + 2) + 2m + m d + t.
d 1,1 | . . . | d L,δκ | Π 1,0,0 | . . . | Π L,1,4 | w 3,1 | w 3,2 | s 0 | s 1 | . . . | s | s U,0 | s U,1 | . . . | s U, I | . (29)
Observe that the given five equations can be combined into one of the form:

M 3 • w 3 = v 3 mod q, ( 30
)
where matrix M 3 and vector v 3 can be built from the public input.

Putting Pieces Altogether. At the final stage of the process, we connect the three aforementioned steps. Indeed, all the equations involved in our process are captured by ( 23), [START_REF] Freedman | Keyword search and oblivious pseudorandom functions[END_REF], and (30) -which in turn can be combined into:

M • w = v mod q, ( 31
)
where w = (w tree | w BP | w 3 ) ∈ [-1, 4] D , for

D = D tree + D BP + D 3 = O(λ) • (L • log κ + κ) + O(λ) • (log N + λ) + O(1) • t.
The components of w all have constraints listed in Table 1. By construction, these blocks either belong to the special sets B 2 m , B 3 m or they have the special forms expand(•, •), ext 2 (•), ext 5 (•), ext 5×2 (•, •), which are invariant under the permutations defined in Table 1. As a result, we can specify suitable sets VALID, S and permutations of D elements {Γ φ : φ ∈ S}, for which the conditions of ( 12) are satisfied. The description of VALID, S and Γ φ is detailed in Appendix H.2.

Our desired argument system then works as follows. At the beginning of the interaction, the prover computes commitments com 0 , . . . , com κ-1 ∈ Z n q and send them once to the verifier. Both parties construct matrix M and vector v based on the public input as well as com 0 , . . . , com κ-1 , while the prover prepares vector w, as described. Finally, they run the protocol of Section 6.1, which has communication cost O(D log q) = O(L • log κ + κ).

A Comparisons Among Adaptive OT and OT-AC Protocols

Protocol Initialization Cost Transfer Cost Assumptions Security Folklore • O(λN ) general Full Sim NP [52] • O(λ • log(N )) DDH + OT 2 1
Half Sim KPN [START_REF] Kurosawa | Efficiency-improved fully simulatable adaptive OT under the DDH assumption[END_REF] O(λ

(N • U )) O(λ) DDH Full Sim CNS [16] O(λ(N + U )) O(λ) q-type Full Sim GH08 [34] O(λ(N + U )) O(λ) DLIN + q-type UC JL [40] O(λ(N + U )) O(λ) Comp. Dec. Residuosity + q-type Full Sim GH11 [35] O(λ(N + U )) O(λ) Decision 3-Party DH Full Sim GH11 [35] O(λN ) O(λ) 3-Party DDH + DLIN Full Sim Ours, §2.3 O(λ(N • U )) O(λ • log N ) LWE + SIS Full Sim Ours, App D O(λN ) O(λ • log N ) LWE + SIS Full Sim (ROM)
Table 2. This table gives an overview of adaptive OT protocols (without access control). In this table, λ stands for the security parameter; N denotes the size of the database and U is the number of receivers. The horizontal lines classify the schemes into categories based on their communication complexities. We note that, like the protocols of [START_REF] Kurosawa | Generic fully simulatable adaptive oblivious transfer[END_REF], the one of [START_REF] Kurosawa | Efficiency-improved fully simulatable adaptive OT under the DDH assumption[END_REF] is secure in a strictly weaker model than ours. In particular, the sender detects if the same record is obtained twice, as pointed out in [START_REF] Green | Practical adaptive oblivious transfer from simple assumptions[END_REF].

In this section, Table 2 and Table 3 give comparisons between existing adaptive oblivious transfer protocols and ours. These results are to be taken carefully, as earlier constructions are mostly designed in the pairing-based cryptography setting. The communication complexities thus take into account the number of underlying mathematical objects exchanged during each interactive protocols, which are group elements in the previous constructions, and vectors in our case.

Table 3 considers protocols that provide access control. They manage access policies in the fashion of Camenisch et al. [START_REF] Camenisch | Oblivious transfer with access control[END_REF] in that they model access policies as access categories bound to users (like their role, or their permission), which are certified by the issuer. In [START_REF] Camenisch | Oblivious transfer with access control[END_REF], a given message in the database is accessible to receivers holding a credential for a conjunction of access categories: namely, to access a specific file, a user has to be in all the categories the file is associated with. To handle disjunctions, [START_REF] Camenisch | Oblivious transfer with access control[END_REF] suggests to simply duplicate the file. However, this requires the database to provide evidence that encryptions of a duplicated file are consistent and indeed encrypt the same message. Moreover, this approach does not efficiently extend to, e.g., threshold policies.

By handling access control via branching programs, we directly enable access control for policies in NC1.

O(λ • N ) O(λ) • Poly (λ) q-type Conj. Full Sim CDNZ [15] O(λ • N ) O(λ) • Poly (λ) q-type + XDDH Conj. Full Sim ACDN [1] O(λ • N ) O(λ) • Poly (λ) DLIN + SXDH Conj. UC ZAW+ [62] O(λ • N ) O(λ) CP-ABE + q-type NC1 Full-Sim CDEN [13] O(λ • N ) O(λ log N ) + Poly (λ) CP-ABE + GGM CNF - Full-Sim Ours, §5 O(λ • N ) O(λ log N ) + Poly (λ) LWE + SIS NC1 Full Sim

B Security Definitions for Adaptive OT and OT-AC

B.1 Security Definitions for Adaptive k-out-of-N Oblivious Transfer

Security is defined via the "real-world/ideal-world" paradigm which was first introduced in the Universal Composability (UC) framework [START_REF] Canetti | Universally composable security: A new paradigm for cryptographic protocols[END_REF]. Like [START_REF] Camenisch | Simulatable adaptive oblivious transfer[END_REF][START_REF] Camenisch | Oblivious transfer with access control[END_REF], however, we do not incorporate all the formalities of the UC framework. We define two experiments: the Real experiment, where the two parties run the actual protocol, and the Ideal experiment wherein a trusted third party assumes the role of the functionality. The model of [START_REF] Camenisch | Simulatable adaptive oblivious transfer[END_REF] formalizes two security notions called sender security and receiver security. The former considers the security of honest senders against cheating senders whereas the latter considers the security of honest receivers interacting with malicious senders.

For an adaptive OT protocol OT N k comprised of algorithms (S I , S T , R I , R T ), we denote define the honest sender S as the algorithm that runs S I (M 1 , . . . , M N ) during the initialization phase, runs S T at each transfer and eventually returns S k = as its final output. Similarly, the honest receiver R is the algorithm that runs R I in the initialization phase, runs R T (R i-1 , ρ i ) during the i-th transfer and eventually returns R k = (M ρ1 , . . . , M ρ k ) as its final output.

Real Experiment. Here, a sender S and a receiver R which proceed as follows for experiment Real S, R (N, k, M 1 , . . . , M N , ρ 1 , . . . , ρ k ). The sender S is given messages M 1 , . . . , M N and interacts with R which does not have any input in the initialization phase. At end of the latter, S and R output their initial states S 0 and R 0 respectively. Then, S and R start k sequential interactions: for i ∈ [k], in the i-th transfer, the sender S and the receiver R run S i ← S(S i-1 ) and (R i , M ρi ) ← R(R i-1 , ρ i ), where ρ i ∈ [N ] is a message index and (S i , R i ) denote updated states for S and R, respectively. Note that M ρi may be different from M ρi if one of the participant deviates from the protocol. At the end of the k-th interaction, S and R output strings S k and R k respectively. The output of Real S, R is the pair (S k , R k ).

The honest sender S is the algorithm that runs S(M 1 , . . . , M N ) as in the initialization phase, runs S T in all subsequent interactions and always outputs S k = ε. The honest receiver R is the algorithm that runs R I in the initialization phase, runs R T (R i-1 , ρ i ) at the i-th transfer and returns the list of received messages R k = (M ρ1 , . . . , M ρ k ) as its final output.

Ideal Experiment. The experiment Ideal S , R (N, k, M 1 , . . . , M N , ρ 1 , . . . , ρ k ) is defined as follows. The (possibly malicious) algorithm S (M 1 , . . . , M N ) generates messages M 1 , . . . , M N which are given to the trusted party T. In each of the k transfers, T obtains a bit b i from the sender S and an index ρ i from the (possibly malicious) receiver R (ρ i ). If b i = 1, and ρ i ∈ [N ], then T reveals M ρi to the receiver R . Otherwise, R receives ⊥ from T. At the end of the k-th transfer, S and R output a string S k and R k and the output of the experiment is the pair (S k , R k ).

The ideal sender S (M 1 , . . . , M N ) is defined the be the sender that sends (M 1 , . . . , M N ) which sends the messages (M 1 , . . . , M N ) to T in the initialization phase, sends b i = 1 in each transfer and outputs the final state S k = ε. The honest ideal receiver R is defined to be the algorithm that sends T the real selection index ρ i at each transfer and eventually outputs the list of all received messages R k = (M ρ1 , . . . , M ρ k ) as its final state.

The bit b i sent by S at each transfer models its capability of making the transfer fail. By forcing S to choose b i without seeing ρ i , the definition prevents the cheating sender S from deciding to cause a failure of the transfer for specific values of ρ i .

Definition 4 (Sender Security

). An OT N k protocol is sender-secure if, for any PPT real-world cheating receiver R, there exists a PPT ideal-world receiver R such that, for any polynomial N m (λ), any N ∈ [N m (λ)], any k ∈ [N ], any messages M 1 , . . . , M N , and any indices ρ 1 , . . . , ρ k ∈ [N ], no PPT distinguisher can separate the two following distributions with noticeable advantage:

Real S, R (N, k, M 1 , . . . , M N , ρ 1 , . . . , ρ k ) and Ideal S , R (N, k, M 1 , . . . , M N , ρ 1 , . . . , ρ k ).
Definition 5 (Receiver Security). An OT N k protocol is receiver-secure if, for any PPT real-world cheating sender S, there exists a PPT ideal-world sender S such that, for any polynomial N m (λ), any N ∈ [N m (λ)], any k ∈ [N ], any messages M 1 , . . . , M N , and any indices ρ 1 , . . . , ρ k ∈ [N ], no PPT distinguisher can tell apart the two following distributions with non-negligible advantage:

Real S,R (N, k, M 1 , . . . , M N , ρ 1 , . . . , ρ k ) and
Ideal S ,R (N, k, M 1 , . . . , M N , ρ 1 , . . . , ρ k ).

B.2 Security Definition for Adaptive Oblivious Transfer with Access Control

Similarly to the OT N k×1 case, security is defined by requiring that any PPT real-world adversary A and any environment E, there exists a PPT adversary A which controls the same parties and such that no environment E can tell if it is running in the real world interacting with the real A or in the idealworld interacting with A . The distribution of outputs of the environment in the different settings is denoted by Real E,A (λ) and Ideal E,A (λ) for real-world adversary A and ideal-world adversary A , respectively. Definition 6. An OT-AC protocol is said to securely implement the functionality if for any real-world adversary A and any real world environment E, there exists an ideal-world simulator A controlling the same parties in the ideal-world as A does in the real-world, such that

|Real E,A (λ) -Ideal E,A (λ)| = negl(λ).
Real World. We describe the way that real-world algorithms interact when all participants (i.e., the real-world users U 1 , . . . , U U , the database DB and the issuer I) are honest. The issuer starts by generating a key pair (P K I , SK I ) ← ISetup(pp), and sends P K I to all users {U i } U i=1 and the database DB. When E sends a message initdb, DB = (M i , AP i ) N i=1 to the database DB, the latter encrypts the database DB by running DBSetup and sends the encrypted records to all users.

When E sends a message (issue, x) to user U i , this user starts an Issue protocol with the issuer on common input x, at the end of which it returns 1 to the environment if the protocol succeeded or 0 otherwise.

When E sends a message (transfer, ρ) to user U i , this user first checks if its credentials Cred U are sufficient to access the record M ρ . If it is the case, it engages in a Transfer protocol with the database DB, at the end of which it receives either the message M ρ , or an error symbol ⊥. If it failed at any steps, the user returns 0 to E, or 1 if it succeeded.

Notice that in this setting, neither the database nor the issuer return any outputs to the environment.

Ideal World. In the ideal world, participants only communicate via the trusted party T which implements the functionality of the protocol. We describe how T proceeds when receiving inputs from the ideal-world users {U i } U i=1 , issuer I and database DB . T maintains an initially empty set C i for each user U i and sets DB ← ⊥. It handles the queries of the different parties as follows: In other words, the ideal-world users, database and issuer relay inputs and outputs between the environment E and the trusted party T.

• When receiving a message (initdb, DB = (M i , AP i ) N i=1 ) from DB , T sets DB = (M i , AP i ) N i=1 . • When receiving (issue, x) from U i , T sends (issue, U i ,
Note that, like [START_REF] Camenisch | Oblivious transfer with access control[END_REF], the ideal functionality allows the database to learn whether a given user interacts with the database for the first time or not. The reason is that, like the protocol of [START_REF] Camenisch | Oblivious transfer with access control[END_REF], our basic OT-AC scheme requires the database to provide a particular interactive zero-knowledge proof at the very first time each user queries the database. In protocols where the database generates such an interactive proof, it is inevitable for U to reveal his state bit f DB to DB. In constructions where the zero-knowledge proof is made non-interactive and made publicly available at the same time as the database itself, this can be avoided and we can prevent DB from learning the state bit f DB . In this case, T does not send f U ,DB to DB in the ideal-world experiment.

The ideal world thus implies the following security properties.

User Anonymity. The database cannot tell which user a given query comes from and neither can it tell which record is being accessed. It only learns whether the user previously queried the database or not. Otherwise, two transfers involving the same users are unlinkable. Database Security. A single cheating user cannot access a record for which he does not have a certified authorized attribute string. Colluding users cannot pool their credentials to gain access to a record which none of them can individually access. Moreover, if the issuer colludes with some users, the protocol still provides the equivalent of sender security in the OT N k×1 functionality.

C Deferred Proofs for the Modified Signature Scheme

C.1 Proof of Theorem 1

Proof. We show that the scheme presented in Section 3.2 is secure against non-adaptive chosen-message attacks (na-CMA) under the SIS assumption. The shape of the proof is similar to the security proof of the signature scheme of [START_REF] Libert | Signature schemes with efficient protocols and dynamic group signatures from lattice assumptions[END_REF]. Namely, to prove the security, we distinguish two kinds of attacks:

We can notice that

A τ (i) = A A 0 + j=1 τ (i) [j]A j = Ā Ā • Q 0 + j=1 τ (i) [j] • Q j + t † j=1 τ [j] + (-1) τ [j] • τ (i) [j] • C = Ā Ā • Q 0 + j=1 τ (i) [j] • Q j + h τ (i) • C ,
where h τ (i) denotes the hamming distance between τ

(i)
|t † and τ † . With probability 1/(Q • ), and as > q, it holds that h τ (i) = 0 mod q whenever τ (i)

|t † = τ |t † .
The reduction then picks a random short matrix R ← Z m×m d which has its m d columns independently sampled from D Z m ,σ , and B computes

D = Ā • R ∈ Z n×m d q .
To finish, B samples a short vector e u ∈ D Z m ,σ and computes the vector u = Ā • e u . The following public key is finally given to A:

P K := (A, {A j } j=0 , D, u).
Signing queries. To handle signature queries, the reduction B uses the trapdoor T C ∈ Z m×m to generate a signature. To this end, B starts by computing the vector u M = u + D • m (i) . Then B can use T C with the algorithm SampleRight from Lemma 4 to compute a short vector v (i) in D u M Λ ⊥ (A τ (i) ),σ , distributed like a valid signature and satisfying the verification equation [START_REF] Agrawal | Efficient lattice (H)IBE in the standard model[END_REF].

Output. At some point, the attacker A halts and outputs a valid signature sig = (τ , v ) for a message m / ∈ {m (1) , . . . , m (Q) }. Since the signature is valid,

it satisfies v ≤ σ √ 2m. Parsing v as [v 1 | v 2 ] with v 1 , v 2 ∈ Z m and injecting it in (2) give: Ā Ā • Q 0 + j=1 τ [j] • Q j • v 1 v 2 = u + D • m mod q = Ā • e u + R • m mod q
Thus, the vector

v = v 1 + Q 0 + j=1 τ [j] • Q j • v 2 -e u -R • m is in Λ ⊥ ( Ā)
, and v is non-zero with overwhelming probabilities, since in A's view, the distribution of e u is D Λ u q (A),σ , which guarantees that e u is statistically hidden by the syndrome u = Ā • e u . Finally, the norm of v is upper bounded by β = σ 2 m 3/2 ( + 2) + 2σm 1/2 .

-If the query is not the i † -th, we have: [START_REF] Gordon | A group signature scheme from lattice assumptions[END_REF]. Thus, using the same technique as in the previous proof from [START_REF] Micciancio | Trapdoors for lattices: Simpler, tighter, faster[END_REF], the challenger B can use the trapdoor T C along with SampleRight algorithm to sample a short vector in Λ u M q (A τ (i) ) satisfying (2). -At the i † -th query, thanks to the second constraint of (32), we have:

A τ (i) = A A 0 + j=0 τ (i) [j] • A j = Ā • S Ā • (S 0 + j=0 τ (i) [j] • S j ) + h τ (i) • C , with h τ (i) = h 0 + τ (i) [j] • h j = 0 due to the first constraint of
A τ (i † ) = A A 0 + j=0 τ (i † ) [j] • A j = Ā • S Ā • (S 0 + j=0 τ (i † ) [j] • S j ) .
To answer this specific query, the challenger B returns sig [START_REF] Green | Blind identity-based encryption and simulatable oblivious transfer[END_REF], which furthermore implies that sig (i † ) verifies (2).

(i † ) = (τ (i † ) , v (i † ) ) where v (i † ) = (v †T 1 | v †T 2 ) verifying
Thus we claim that B can solve the SIS problem using the Type II forgery provided by A. At the end of the game, the adversary outputs a valid signature sig = (τ (i ) , v ) on a message m with v ≤ σ √ 2m. In the event that τ (i ) = τ i † , the reduction aborts. The latter event happens with probability 1 -

1/Q. If we parse v as (v ,T 1 | v T 2 ) ∈ Z 2m , with v 1 , v 2 ∈ Z m , it holds that: A τ (i † ) • v 1 v 2 = u + Ā • m mod q. (34)
According to the way u was defined at the beginning of the game, we also have

a vector v † = (v †T 1 | v †T 2 ) such that A τ (i † ) • v † 1 v † 2 = u + Ā • m † mod q. ( 35
)
As sig is a valid forgery for the dn-CMA game, it follows that m † = m . And we get by subtracting ( 34) and ( 35)

A τ (i † ) • v 1 -v † 1 v 2 -v † 2 = Ā • m -m † mod q, Ā • S Ā • (S 0 + j=0 τ (i † ) [j] • S j ) • v 1 -v † 1 v 2 -v † 2 = Ā • m -m † mod q.
Leading us to the fact that

v = S • (v 1 -v † 2 ) +   S 0 + j=1 τ (i † ) [j] • S j   • (v 2 -v † 2 ) (a) + m † -m -(b) (36)
is an integer vector of Λ ⊥ q ( Ā), with norm bounded by v ≤ √ 2( + 2)σm 3/2 + m 1/2 = β . Furthermore, if v was zero, it implies that (a) = (b) in Equation [START_REF] Herranz | Restricted adaptive oblivious transfer[END_REF]. And as sig = sig † , we have that either

v 1 = v † 1 or v 2 = v † 2 .
As a consequence, (a) is information theoretically unpredictable for A since the columns of S, S 0 , . . . S are statistically hidden from A, as shown in [START_REF] Micciancio | Trapdoors for lattices: Simpler, tighter, faster[END_REF] for instance: conditionally on the public key, each column of S and {S j } j=0 has at least n bits of min-entropy.

D Reducing the Communication Complexity in the Random Oracle Model

One limitation of our basic adaptive OT protocol is that it requires the sender to repeat the zero-knowledge proofs of the initialization phase for each user. In total, the communication cost of the initialization phase thus amounts to Ω(λN U ), which is even more expensive than the O(λ(N + U )) complexities of [START_REF] Camenisch | Simulatable adaptive oblivious transfer[END_REF][START_REF] Green | Blind identity-based encryption and simulatable oblivious transfer[END_REF][START_REF] Camenisch | Oblivious transfer with access control[END_REF][START_REF] Jarecki | Efficient oblivious pseudorandom function with applications to adaptive OT and secure computation of set intersection[END_REF]. As pointed out by Green and Hohenberger [START_REF] Green | Practical adaptive oblivious transfer from simple assumptions[END_REF], decreasing the cost of the initialization phase to be independent of the number of users is highly desirable: ideally, one would certainly prefer a non-interactive initialization phase where the Sender can publicize a O(λN )-size commitment to the database, which can subsequently be used by arbitrarily many receivers.

In the random oracle model, we show that our protocols can both be modified to obtain this optimized communication complexity. This can be achieve by the simple expedient of making the sender's zero-knowledge proofs non-interactive via the Fiat-Shamir heuristic.

By removing interaction from all the sender's proof (i.e., even those of the transfer phase), we also minimize the number of communication rounds since we only need the verifier's arguments to be witness indistinguishable and we can thus safely repeat them in parallel. Relying on the random oracle model thus allows the sender to publicize the entire database and proofs on a public repository so as to avoid repeating these proofs for each receiver.

D.1 Description

The description hereunder relies on the same parameters as in sections 4 and 5. Namely, we use m = 2n log q , a modulus q for which the noise distribution χ is αq-bounded, for some 0 < α < 1, and also define an integer B as a randomization parameter such that (m + 1)αq/B is negligible and choosing α such that (m + 1)α ≤ 1/5 ensures decryption correctness. and generate a signature of knowledge of

s j ∈ χ n , e j ∈ χ m , xj ∈ χ N , Mj ∈ {0, 1} N , for j ∈ [t], such that F I m A DB I N q/2 • I N •     s j e j xj Mj     = p j bj (40)
Let the NIZK proof be

π K = ({Comm K,j } ς j=1 , Chall K , {Resp K,j } ς j=1 ), where Chall K = H FS (F, P, A DB , B DB ), {Comm K,j } ς j=1 ∈ {1, 2, 3} ς . c.
If the proof of knowledge π K does not verify or if there exists i ∈ [N ] such that (τ i , v i ) is an invalid signature on vdec n+t,q-1 (a i |b i ) , then R I aborts. 6. Finally S I defines S 0 = (S, E), (F, P), P K sig , which it keeps to itself.

Transfer S T (S i-1 ), R T (R i-1 , ρ i ) : At the i-th transfer, the receiver R T has state R i-1 and an index ρ i ∈ [1, N ]. It interacts as follows with the sender S T that has state S i-1 in order to obtain M ρi from DB.

1. R T samples vectors e ← U ({-1, 0, 1} m ), µ ← U ({0, 1} t ) and a random ν ← U ([-B, B] t ) to compute (c 0 , c 1 ) = a ρi + F • e, b ρi + P • e + µ • q/2 + ν ∈ Z n q × Z t q , (41)
which is a re-randomization of (a ρi , b ρi +µ• q/2 ). The resulting ciphertext (c 0 , c 1 ) is sent to S T . In addition, R T provides an interactive WI argument that (c 0 , c 1 ) is indeed a re-randomization of (a ρi , b ρi ) for some index ρ i ∈ [N ]. To this end, R T argues knowledge of short vectors m = vdec n+1,q-1 (a

i |b i ) ∈ {0, 1} m d , e ∈ {-1, 0, 1} t , µ ∈ {0, 1} t , ν ∈ [-B, B] t , τ ∈ {0, 1} and v = (v 1 |v 2 ) ∈ Z 2m such that H n,q-1 F H t,q-1 P I t • q/2 I t •     m e µ ν     = c 0 c 1 (42)
and

A A 0 • • • A •         v 1 v 2 τ [1] • v 2 . . . τ [ ] • v 2         = u + D • m mod q (43)
2. If the WI argument of step 1 verifies, S T uses S ∈ χ n×t to decrypt (c 0 , c 1 ) ∈ Z n q × Z t q and obtain

M = (c 1 -S • c 0 )/(q/2) ∈ {0, 1} t ,
which is sent back to R T . In addition, S T provides a NIZK argument π T of knowledge of y = c 1 -S • c 0 -M • q/2 ∈ Z t of norm y ∞ ≤ q/5 and E = [e 1 | . . . |e t ] ∈ χ m×t satisfying (modulo q)

P = F • S + E , c 0 • S + y = c 1 -M • q/2 . ( 44
)
Given y = (y [START_REF] Abe | Universally composable adaptive oblivious transfer (with access control) from standard assumptions[END_REF]

F I m c 0 1 •   s j e j y[j]   = p j c 1 [j] -M [j] • q/2 ∀j ∈ [t], (45)
where

c 1 = (c 1 [1], . . . , c 1 [t]) and M = (M [1], . . . , M [t]
) . Let the NIZK argument be π T = ({Comm T,j } ς j=1 , Chall T , {Resp T,j } ς j=1 ), where Chall T = H FS (F, P, c 0 , c 1 ), {Comm T,j } ς j=1 ∈ {1, 2, 3} ς . 3. If th argument π T produced by S T does not properly verify, R T halts and outputs ⊥. Otherwise, R T recalls the random string µ ∈ {0, 1} t that was chosen at step 1 and computes M ρi = M ⊕ µ. The transfer ends with S T and R T outputting S i = S i-1 and R i = R i-1 , respectively.

D.2 Security

For simplicity, our proofs are given in the single-receiver setting but they readily carry over to the multi-receiver setting, as defined in [START_REF] Green | Practical adaptive oblivious transfer from simple assumptions[END_REF]Appendix B].

Theorem 5. The above OT N k×1 protocol provides receiver security under the SIS assumption in the random oracle model.

Proof. We show how to map any real-world cheating sender Ŝ to an idealworld cheating sender Ŝ such that, under the SIS assumption, the distributions Real Ŝ,R (N, k, M 1 , . . . , M N , ρ 1 , . . . , ρ k ) and Ideal Ŝ ,R (N, k, M 1 , . . . , M N , ρ 1 , . . . , ρ k ) are computationally indistinguishable.

We consider a sequence of hybrid experiments with binary outputs. In each experiment Exp i , a distinguisher D inputs the states (S k , R k ) produced by Ŝ and R at the end of Exp i and outputs a bit. We define W i to be the event that the output of Exp i is 1. The first experiment outputs whatever the distinguisher D outputs and corresponds to the real interaction between the cheating sender Ŝ and the receiver R.

Exp 0 : This experiment involves a real execution of Ŝ in interaction with a honest receiver R which queries the index ρ i ∈ [N ] at the i-th transfer for each i ∈ [k]. The output of Exp 0 is exactly the output of the distinguisher D on input of X = (S k , R k ) ← Real S, R, so that we have

Pr[W 0 ] = Pr[D(X) = 1 | X ← Real Ŝ,R ].
Exp 1 : This experiment is like Exp 0 except that R programs the random oracle H F : {0, 1} * → Z n×m q in the following way. It runs the trapdoor generation algorithm (F, T F ) ← TrapGen(1 n , 1 m , q) of [4] so as to obtain a statistically uniform matrix F ∈ Z n×m q and a small-norm T F ∈ Z m×m basis of Λ ⊥ q (F). It then programs the random oracle so as to have

H F (ε) = F ∈ Z n×m q .
Clearly, this change leaves the adversary's view statistically unchanged: we have

| Pr[W 1 ] -Pr[W 0 ]| ∈ negl(λ).
Exp 2 : is as Exp 1 but, at step 5 of the initialization phase, R uses the short basis T F ∈ Z m×m of Λ ⊥ q (F) (which satisfies F • T F = 0 n mod q) to extract witnesses s j ∈ χ n , e j ∈ χ m from the columns p j = F • s j + e j ∈ Z m of the matrix

P = [p 1 | . . . | p t ] ∈ Z m×t q each j ∈ [t].
Note that this can be done by inverting the LWE function (see, e.g., [START_REF] Gordon | A group signature scheme from lattice assumptions[END_REF]Section 2.3]). At this point, R aborts the interaction in the event that one of the following conditions holds: E.1: The LWE-inversion algorithm fails to compute small-norm vectors s j ∈ χ n , e j ∈ χ m such that p j = F • s j + e j ∈ Z m q for some j ∈ [t]. E.2: The columns of S = [s 1 | . . . | s t ] ∈ χ n×t are successfully extracted but there exists i ∈ [N ] such that one of the coordinates of b i -S •a i mod q is neither close to 0 nor q/2 (i.e., the inequalities |b i -S •a i mod q| > αq and |(b i -S • a i mod q) -q/2 | > αq are both satisfied). In either of the above situations, R infers that Ŝ managed to create a convincing argument for a false statement and aborts the interaction. In such a situation, however, R can be turned into an algorithm that breaks the binding property of the commitment scheme used in the ZK argument (which contradicts the SIS assumption if the statistically hiding commitment of [START_REF] Kawachi | Concurrently secure identification schemes based on the worst-case hardness of lattice problems[END_REF] is used) by replaying the adversary with the same random tape but a different random oracle H FS . According to the General Forking Lemma of [START_REF] Brickell | Design validations for discrete logarithm based signature schemes[END_REF], replaying Ŝ up to 32•Q H /( -3 -t ) times (where Q H is the number of queries to H FS is sufficient to extract a breach in the binding property of the commitment). Otherwise (i.e., if R does not fail), the matrix S ∈ χ n×t allows R to decode the messages M 1 , . . . , M N ∈ {0, 1} t from the encrypted database {(a i , b i )} N i=1 . Under the SIS assumption, it follows that Exp 1 returns 1 with about the same probability as Exp 0 . In the random oracle model, the SIS assumption thus implies that | Pr[W 2 ] -Pr[W 1 ]| ∈ negl(λ). Exp 3 : is identical to Exp 2 except that the receiver R makes use of the matrix S ∈ χ n×t , which was extracted at step 5 of the initialization phase. At step 2 of each transfer, R uses S to determine if the NIZK argument π T really proves a true statement or if Ŝ managed to break its soundness. Namely, upon receiving Ŝ's response M ∈ {0, 1} t at step 2, R uses the previously extracted S ∈ χ n×t to determine if there exists y ∈ Z t of norm y ∞ ≤ q/5 such that

c 0 • S + y = c 1 -M • q/2 . ( 46
)
If such vector y turns out not to exist, R deduces R that Ŝ was able to fake a convincing argument for a false statement and aborts the interaction.

However, R can then be turned into a PPT adversary against the binding property of the commitment scheme used in the ZK argument (and thus the SIS assumption if the commitment of [START_REF] Kawachi | Concurrently secure identification schemes based on the worst-case hardness of lattice problems[END_REF] is used) by replaying the adversary according to the General Forking technique [START_REF] Brickell | Design validations for discrete logarithm based signature schemes[END_REF]. The result of [START_REF] Brickell | Design validations for discrete logarithm based signature schemes[END_REF] tells us that replaying Ŝ up to 32

(c 0 , c 1 ) = a 1 + F • e, b 1 + P • e + µ • q/2 + ν ∈ Z n q × Z t q ,
which is a re-randomization of (a 1 , b 1 +µ• q/2 ). Moreover, R T uses the witness ρ i = 1 to faithfully generate an interactive WI argument that (c 0 , c 1 ) is a re-randomization of (a ρi , b ρi ). It thus generates a WI argument of knowledge of vectors m = vdec n+t,q-1 (a [START_REF] Chor | Private information retrieval[END_REF]. By the statistically WI of the interactive argument system, this modification has no noticeable impact on the output distribution of a cheating sender Ŝ whatsoever. We have

1 |b 1 ) ∈ {0, 1} m d , e ∈ {-1, 0, 1} t , µ ∈ {0, 1} t , ν ∈ [-B, B] t , τ ∈ {0, 1} and (v 1 |v 2 ) ∈ Z 2m satisfying relations
| Pr[W 4 ] -Pr[W 3 ]| ∈ negl(λ).
In Exp 4 , we define the ideal-world cheating sender Ŝ in the following way. It programs the random oracle H F : {0, 1} * → Z n×m q in such a way that H F (ε) = F ∈ Z n×m q for some statistically random matrix produced as (F, T F ) ← TrapGen(1 n , 1 m , q). At the initialization phase, Ŝ uses the small-norm basis T F of Λ ⊥ q (F) to extract the small-norm matrices S = [s 1 | . . . |s t ] ∈ χ n×t and E = [e 1 | . . . |e t ] ∈ χ m×t satisfying (37) and decrypt {(a i , b i )} N i=1 into messages M 1 , . . . , M N ∈ {0, 1} N . If the extraction fails because one of the events E.1 and E.2 (as defined in Exp 2 ) comes about, Ŝ aborts. Otherwise, it then submits M 1 , . . . , M N ∈ {0, 1} N to the trusted party T. As in Exp 2 , during each transfer phase, Ŝ computes (c 0 , c 1 ) as a re-randomization of (a 1 , b 1 ) ∈ Z n q ×Z t q and faithfully generates the receiver's argument of knowledge using the witness ρ i = 1 at step 1. At step 2 of each transfer, Ŝ aborts if it realizes that Ŝ created a convincing NIZK argument π T for a false statement. If π T correctly verifies and indeed relates to a true statement (which Ŝ can detect by applying the test [START_REF] Libert | Zero-knowledge arguments for latticebased accumulators: Logarithmic-size ring signatures and group signatures without trapdoors[END_REF] using the matrix S ∈ χ n×t extracted in the initialization phase), Ŝ sends 1 to the trusted party T so as to authorize the transfer in the ideal world. Otherwise, Ŝ sends 0 to T. At the end of the k-th transfer phase, Ŝ outputs whatever Ŝ outputs as its final state S k .

In Exp 4 , it is easy to see that

Pr[W 4 ] = Pr[D(X) = 1 | X ← Ideal Ŝ ,R ].
Exp 1 : This experiment is like Exp 0 except that, at step 5 of the initialization phase, the knowledge extractor of the argument system is used to extract the witnesses s j ∈ χ n , e j ∈ χ m , xj ∈ χ N , Mj ∈ {0, 1} N , for each j ∈ [t], from the sender's argument. In the event that the knowledge extractor fails to extract valid witnesses, the experiment aborts and outputs ⊥. We know that the zero-knowledge argument system is computationally sound as long as the underlying commitment is computationally binding. If the perfectly hiding commitment of [START_REF] Kawachi | Concurrently secure identification schemes based on the worst-case hardness of lattice problems[END_REF] is used, the binding property is in turn implied by the SIS assumption. Under the SIS assumption, it follows that Exp 1 returns 1 with about the same probability as Exp 0 . Specifically, there exists a SIS solver B such that

| Pr[W 1 ] -Pr[W 0 ]| ≤ Adv SIS B (λ). Exp 2 :
This experiment is identical to Exp 1 except that the receiver R makes use of the matrix S ∈ χ n×t , which underlies P ∈ Z m×t q in (3) and was extracted at step 5 of the initialization phase. Namely, at step 2 of each transfer, R uses S to determine if the ZK argument sent by Ŝ is really an argument for a true statement or if Ŝ somehow managed to break the soundness of the argument system. Namely, upon receiving the response M ∈ {0, 1} t of Ŝ at step 2, R uses the previously extracted S ∈ χ n×t to determine whether there exists a vector y ∈ Z t of norm y ∞ ≤ q/5 such that

c 0 • S + y = c 1 -M • q/2 . (47)
If no such vector y exists, R infers that Ŝ broke the soundness of the argument system. In this case, Ŝ can be rewound so as to break the binding property of the statistically hiding commitment scheme used by the ZK argument system, which in turn contradicts the SIS assumption. We thus have

| Pr[W 2 ] -Pr[W 1 ]| ≤ Adv SIS B (
λ) for some efficient algorithm B which is given rewinding access to Ŝ. Exp 3 : This experiment is like Exp 2 with the difference that, at each transfer, the receiver R chooses the index ρ i = 1 and thus always requests the first message of the encrypted database. In more details, at each transfer, R samples vectors e ← U ({-1, 0, 1} m ), µ ← U ({0, 1} t ) and ν ← U ([-B, B] t ) to compute and send

(c 0 , c 1 ) = a 1 + F • e, b 1 + P • e + µ • q/2 + ν ∈ Z n q × Z t q
, which is a re-randomization of (a 1 , b 1 +µ• q/2 ). Moreover, R T uses the witness ρ i = 1 to faithfully generate an interactive WI argument that (c 0 , c 1 ) is a re-randomization of (a ρi , b ρi ). It thus generates a WI argument of knowledge of vectors m = vdec n+t,q-1 (a [START_REF] Chor | Private information retrieval[END_REF]. By the statistically WI of the interactive argument system, this modification has no noticeable impact on the output distribution of a cheating sender Ŝ. Indeed, since we chose B as a randomization parameter such that (m+1)αq/B is negligible, the result of [24, Section 4.1] implies that always re-randomizing (a 1 , b 1 + µ • q/2 ) leaves the view of Ŝ statistically unchanged. We have

1 |b 1 ) ∈ {0, 1} m d , e ∈ {-1, 0, 1} t , µ ∈ {0, 1} t , ν ∈ [-B, B] t , τ ∈ {0, 1} and (v 1 |v 2 ) ∈ Z 2m satisfying relations
| Pr[W 2 ] -Pr[W 1 ]| ≤ negl(λ).
In Exp 3 , we can define the ideal-world cheating sender Ŝ which emulates the honest receiver R interacting with Ŝ. At the initialization phase, Ŝ appeals to the knowledge extractor of the argument system so as to extract the small-norm matrices S = [s 1 | . . . |s t ] ∈ χ n×t and E = [e 1 | . . . |e t ] ∈ χ m×t satisfying (3). Armed with the decryption key E ∈ χ m×t of the cryptosystem, Ŝ can decrypt {(a i , b i )} N i=1 and obtain the messages M 1 , . . . , M N ∈ {0, 1} N that were encrypted in (4) by Ŝ. It then submits M 1 , . . . , M N ∈ {0, 1} N to the trusted party T. As in Exp 2 , during each transfer phase, Ŝ computes (c 0 , c 1 ) as a re-randomization of (a 1 , b 1 ) ∈ Z n q × Z t q and faithfully generates the receiver's argument of knowledge using the witness ρ i = 1 at step 1. At step 2 of each transfer, Ŝ plays the role of the verifier on behalf of R in the interactive zero-knowledge argument generated by Ŝ. If Ŝ detects that Ŝ creates a verifying argument for a false statement (which Ŝ can detect using the extracted matrix S ∈ Z n×t , by applying the test ( 47)), it aborts the interaction as in Exp 3 . If the ZK argument involves a true statement, Ŝ sends 1 to the trusted party T so as to authorize the transfer in the ideal world. Otherwise, Ŝ sends 0 to T. At the end of the k-th transfer phase, Ŝ outputs whatever Ŝ outputs as its final state S k .

In Exp 3 , it is easy to see that

Pr[W 3 ] = Pr[D(X) = 1 | X ← Ideal Ŝ ,R ].
When putting the above altogether, we find that there exists a PPT SIS solver B such that

| Pr[D(X) = 1 | X ← Real Ŝ,R ] -Pr[D(X) = 1 | X ← Ideal Ŝ ,R ]| ≤ 2 • Adv SIS B (λ) + negl(λ),
which proves the result.

E.2 Proof of Theorem 3

Let us restate Theorem 3.

Theorem 8. The OT N k×1 protocol provides sender security under the SIS and LWE assumptions.

Proof. Given a real malicious receiver R, we construct a cheating receiver R in the ideal world such that, under the SIS and LWE assumption, no PPT distinguisher D can tell apart the distributions Real S, R(N, k, M 1 , . . . , M N , ρ 1 , . . . , ρ k ) and Ideal S , R (N, k, M 1 , . . . , M N , ρ 1 , . . . , ρ k ).

To do this, we proceed again via a sequence of hybrid experiments with binary outputs. For each i, we consider the probability that a distinguisher D outputs 1 on input of the states (S k , R k ) that constitute the outcome of experiment Exp i . We also define W i to be the event that experiment Exp i outputs 1.

Exp 0 : This experiment corresponds to a real execution of R in interaction with a honest sender S(M 1 , . . . , M N ). The output of the experiment is identical to that of the distinguisher D on input of X = (S k , R k ) ← Real S, R. We have

Pr[W 0 ] = Pr[D(X) = 1 | X ← Real S, R].
Exp 1 : This experiment departs from Exp 0 in that, when the dishonest receiver RT sends the ciphertext (c 0 , c 1 ) ∈ Z n q × Z t q at step 1 of each transfer, the knowledge extractor of the argument system is used to extract the witnesses [START_REF] Chor | Private information retrieval[END_REF]. If the knowledge extractor fails to produce valid witnesses at some transfer, the experiment aborts and outputs ⊥. Recall that the zero-knowledge argument system is computationally sound if the underlying commitment is binding, which is equivalent to the SIS assumption if the perfectly hiding commitment of [START_REF] Kawachi | Concurrently secure identification schemes based on the worst-case hardness of lattice problems[END_REF] is used. Under the SIS assumption, experiment Exp 1 returns 1 with about the same probability as Exp 0 . There thus exists a SIS solver B such that

m ∈ {0, 1} m d , e ∈ {-1, 0, 1} t , µ ∈ {0, 1} t , ν ∈ [-B, B] t , τ ∈ {0, 1} and v = (v 1 |v 2 ) ∈ Z 2m which satisfy
| Pr[W 1 ] -Pr[W 0 ]| ≤ k • Adv SIS B (λ),
where k is the number of transfers. Exp 2 : This experiment is identical to Exp 1 except that, at step 1 of each transfer, the experiment aborts if the extracted witnesses

m ∈ {0, 1} m d , e ∈ {-1, 0, 1} t , µ ∈ {0, 1} t , ν ∈ [-B, B] t , τ ∈ {0, 1} and v = (v 1 |v 2 ) ∈ Z 2m are such that the product a m b m = H n,q-1 H t,q-1 • m ∈ Z n+t q does not match any ciphertext {(a i , b i )} N i=1 appearing in R 0 (namely, we have (a m , b m ) = (a i , b i ) for each i ∈ [N ]
). We claim that such an event implies a breach in the bounded message security of the signature scheme: Lemma 7. Under the SIS assumption, experiments Exp 2 and Exp 1 are computationally indistinguishable: there exists a PPT algorithm B such that

| Pr[W 2 ] -Pr[W 1 ]| ≤ N • Adv SIS B (λ).
Exp 3 : This experiment is like Exp 2 except that, at step 5 of the initialization phase, the zero-knowledge argument of knowledge of

s j ∈ χ n , e j ∈ χ m , xj ∈ χ N , Mj ∈ {0, 1} N such that F I m A DB I N q/2 • I N •     s j e j xj Mj     = p j bj ∀j ∈ [t]
is replaced by a simulated interactive argument and so is the ZK argument of knowledge of {(s j , e j , y[j])} t j=1 satisfying (17) at step 2 of each transfer protocol. From this experiment on, we notice that the small-norm matrices of hybrid experiments Exp i where, for each i, a simulator Sim i interacts with A on behalf of U. For each i, we define by W i the event that the environment E outputs 1 in Exp i .

Exp 0 : This experiment involves a real execution of the adversary controlling DB and I in interaction with a honest user U which obtains credentials from I and queries database entries ρ i ∈ [N ] as dictated by the environment E. The output of Exp 0 is the output of the environment E, so that we have

Pr[W 0 ] = Pr[E(X) = 1 | X ← Real E,A (λ)].
Exp 1 : This experiment is identical to Exp 0 with the difference that, at the first transfer dictated by E (when its state bit is f DB = 0), the simulator Sim 1 appeals to the knowledge extractor of the argument system is used to extract the witnesses s j ∈ χ n , e j ∈ χ m , xj ∈ χ N , Mj ∈ {0, 1} N , for each j ∈ [t], at step 1 of the Transfer protocol. Should the knowledge extractor fail to extract valid witnesses, Sim 1 aborts and outputs ⊥. However, we know that the argument system is computationally sound whenever the underlying commitment is computationally binding, which boils down to the SIS assumption if the underlying commitment is the Kawachi et al. commitment [START_REF] Kawachi | Concurrently secure identification schemes based on the worst-case hardness of lattice problems[END_REF]. Under the SIS assumption, E returns 1 with essentially the same probability as Exp 0 as there exists a SIS solver B such that

| Pr[W 1 ] -Pr[W 0 ]| ≤ Adv SIS B (λ). Exp 2 :
This experiment is like Exp 1 with the difference that the receiver Sim 2 makes use of the matrix S ∈ χ n×t , which was extracted at the first transfer ordered by E. Specifically, at step 3 of each transfer, Sim 2 uses S to decide if the ZK argument sent by DB is an argument for a true statement or if the dishonest DB was able to break the soundness of the argument system. Upon receiving the response M ∈ {0, 1} t of DB at step 3, Sim 2 uses S ∈ χ n×t to test whether there exists a vector y ∈ Z t of norm y ∞ ≤ q/5 such that

c 0 • S + y = c 1 -M • q/2 . (48)
If no such vector y exists, Sim 2 concludes that A broke the soundness of the argument and aborts its interaction with A. In this case, however, Sim 2 can be turned into an algorithm B that breaks the binding property of the statistically hiding commitment used by the ZK argument system using rewinding access to A. This contradicts the SIS assumption and we have

| Pr[W 2 ] -Pr[W 1 ]| ≤ Adv SIS B (λ).
, 1} m ), µ ← U ({0, 1} t ) and ν ← U ([-B, B] t ) to compute (c 0 , c 1 ) = a ρ + F • e, b ρ + P • e + µ • q/2 + ν ∈ Z n q × Z t q ,
The changes introduced in Exp 2 and Exp 3 rule out the event that the dishonest user manages to cheat by breaking the binding property of the Merkle tree in an attempt to use an attribute string x ∈ {0, 1} κ that is accepted by BP ρ , but for which he has no credential. We now turn to the case where the adversary rather uses the strategy of breaking the signature scheme used by the issuer.

Exp 4 : This experiment is like Exp 3 with the difference that, at each transfer, Sim 4 aborts and outputs ⊥ in the event that the extracted pair (m U,x , cert U,x ) is such that was never m U,x certified by the honest issuer in any execution of Issue. This event clearly implies that A was able to forge a valid credential cert U,x for a message m U,x = m P ||x ∈ {0, 1} m I . Note that this covers the following cases: (i) A given user with pseudonym P U = H n,q-1 •m P ∈ Z n q who pools his legally obtained credentials for distinct attribute strings x 1 , . . . x Q to create one for a new x ∈ {x 1 , . . . x Q }; (ii) Distinct users with different pseudonyms P U,1 , . . . , P U,Q ∈ Z n q who pool their credentials to create one for P U ∈ {P U,1 , . . . , P U,Q }. The security of the signature scheme in Section 3.1 ensures that this event only occurs with negligible probability under the SIS assumption. Specifically, the result of [START_REF] Libert | Signature schemes with efficient protocols and dynamic group signatures from lattice assumptions[END_REF]Theorem 1] by uniformly random vectors p i ← U (Z m q ). Meaning that the matrix P is now distributed uniformly in Z m×t q . Sim 5 also replaces the Regev ciphertexts b i = S • a i + x i + M i q 2 by uniformly random vectors b i ← U (Z t q ). Hence, the sender's zero-knowledge arguments are now simulated arguments for false statements at steps 1 and 3 of Transfer. Still, under the LWE assumption over t • (m + N ) samples, this modified distribution of (P, {b i } N i=1 ) is not noticeable to A and has no significant impact on E's output distribution: we have | Pr[W 7 ] -Pr[W 6 ]| ≤ Adv LWE B (λ).

The ideal-world adversary A is designed as follows. It plays the role of DB and I in interaction with the real-world receivers U in Exp 7 . In the DBSetup phase, (F, P) are chosen as truly random matrices (F, P) ← U (Z n×m q × Z m×t q ) and while each pair (a i , b i ) ← U (Z n q × Z t q ) is sampled at random for all i ∈ [N ]. The tuples {(a i , b i , h BP,i )} N i=1 are faithfully signed using SK sig = T A at step 5.b of DBSetup. At the first Transfer message sent by T, A runs the simulator of the ZK argument. When A sends (c 0 , c 1 ) and argues knowledge of (m, e, µ, ν, τ, v 1 , v 2 ) at step 2 of the transfer phase, A uses the knowledge extractor of the argument system to extract (m, e, µ, ν, τ, v 1 , v 2 ) ∈ {0, 1} m d × {-1, 0, 1} t × {0, 1} t × [-B, B] t × {0, 1} and determine the index

ρ i ∈ [N ] such that   a ρi b ρi h BP,i   = H 2n+t,q-1 • m ∈ Z 2n+t q .
Note that, due to the change introduced in Exp 4 , such an index must exist unless A can forge a signature for the key P K sig . Having decoded the queried index ρ i ∈ [N ], A queries the trusted party T to obtain credentials for an x ∈ {0, 1} κ such that BP ρi (x) = 1, which subsequently allows A to query T so as to obtain M ρi ∈ {0, 1} t . The latter is used together with the extracted witness µ ∈ {0, 1} t to reverse-engineer the correct response M = M ρi ⊕ µ ∈ {0, 1} t that A should m ∈ {0, 1} m d , τ ∈ {0, 1} and v = (v 1 |v 2 ) ∈ Z 2m satisfy the equality by truly random vectors p i ← U (Z m q ). Which results in matrix P being uniform in Z m×t q . Simultaneously, Sim 4 trades the vectors b i = S • a i + x i + M i q 2 ∈ Z t q for uniformly random vectors in Z t q . At this point, the sender's zero-knowledge arguments become simulated arguments for false statements at steps 1 and 3 of Transfer. However, under the LWE assumption, these changes are not noticeable to A and should leave E's output distribution essentially unchanged: we have

A A 0 . . . A •        v 1 v 2 τ [1] • v 2 . . . τ [ ] • v 2        = u + D • m,
| Pr[W 4 ] -Pr[W 3 ]| ≤ Adv LWE B (λ).
From the real-world A, we build an ideal-world A that controls the issuer I and the users. In its interaction with the real-world A (which controls I and U Proof. It can be checked that the protocol has perfect completeness: If an honest prover follows the protocol, then he always gets accepted by the verifier. It is also easy to see that the communication cost is bounded by O(D log q).

We now prove that the protocol is a statistical zero-knowledge argument of knowledge.

Zero-Knowledge Property. We construct a PPT simulator SIM interacting with a (possibly dishonest) verifier V, such that, given only the public input, SIM outputs with probability negligibly close to 2/3 a simulated transcript that is statistically close to the one produced by the honest prover in the real interaction.

The simulator first chooses a random Ch ∈ {1, 2, 3} as a prediction of the challenge value that V will not choose. Case Ch = 1: Using basic linear algebra over Z q , SIM computes a vector w ∈ Z D q such that M • w = v mod q. Next, it samples r w ← U (Z D q ), φ ← U (S), and randomness ρ 1 , ρ 2 , ρ 3 for COM. Then, it sends the commitment CMT = C 1 , C 2 , C 3 to V, where Receiving a challenge Ch from V, the simulator responds as follows:

-If Ch = 1: Send RSP = Γ φ (w ), Γ φ (r w ), ρ 2 , ρ 3 .

-If Ch = 2: Output ⊥ and abort.

-If Ch = 3: Send RSP = φ, r w , ρ 1 , ρ 2 .

Case Ch = 3: SIM samples w ← U (VALID), r w ← U (Z D q ), φ ← U (S), and randomness ρ 1 , ρ 2 , ρ 3 for COM. Then it sends the commitment CMT = C 1 , C 2 , C 3 to V, where C 2 = COM(Γ φ (r w ); ρ 2 ), C 3 = COM(Γ φ (w + r w ); ρ 3 ) as in the previous two cases, while C 1 = COM(φ, M • (w + r w ) -v; ρ 1 ).

Receiving a challenge Ch from V, it responds as follows:

-If Ch = 1: Send RSP computed as in the case (Ch = 2, Ch = 1).

-If Ch = 2: Send RSP computed as in the case (Ch = 1, Ch = 2).

-If Ch = 3: Output ⊥ and abort.

We observe that, in every case we have considered above, since COM is statistically hiding, the distribution of the commitment CMT and the distribution of the challenge Ch from V are statistically close to those in the real interaction. Hence, the probability that the simulator outputs ⊥ is negligibly close to 1/3. Moreover, one can check that whenever the simulator does not halt, it will provide an accepted transcript, the distribution of which is statistically close to that of the prover in the real interaction. In other words, we have constructed a simulator that can successfully impersonate the honest prover with probability negligibly close to 2/3. Argument of Knowledge. Suppose that RSP 1 = (t w , t r , ρ 2 , ρ 3 ), RSP 2 = (φ 2 , w 2 , ρ 1 , ρ 3 ), RSP 3 = (φ 3 , w 3 , ρ 1 , ρ 2 ) are 3 valid responses to the same commitment CMT = (C 1 , C 2 , C 3 ), with respect to all 3 possible values of the challenge. The validity of these responses implies that:

         t w ∈ VALID; C 1 = COM(φ 2 , M • w 2 -v
mod q; ρ 1 ) = COM(φ 3 , M • w 3 ; ρ 1 ); C 2 = COM(t r ; ρ 2 ) = COM(Γ φ3 (w 3 ); ρ 2 ); C 3 = COM(t w + t r mod q; ρ 3 ) = COM(Γ φ2 (w 2 ); ρ 3 ).

Since COM is computationally binding, we can deduce that t w ∈ VALID; φ 2 = φ 3 ; t r = Γ φ3 (w 3 ); t w + t r = Γ φ2 (w 2 ) mod q; M • w 2 -v = M • w 3 mod q.

(51) Since t w ∈ VALID, if we let w = [Γ φ2 ] -1 (t w ), then w ∈ VALID. Furthermore, we have Γ φ2 (w ) + Γ φ2 (w 3 ) = Γ φ2 (w 2 ) mod q, which implies that w +w 3 = w 2 mod q, and that M•w +M•w 3 = M•w 2 mod q.

As a result, we have M • w = v mod q. This concludes the proof.

H More Details of Protocol 4

H.1 The Underlying Commitment and Merkle Hash Tree

Here, we recall the bit commitment and the Merkle hash tree used in Protocol 4 (Section 6.6). Both schemes work with security parameter λ, lattice parameter n = O(λ), modulus q and dimension m = 2n log q .

Commitment. The bit commitment we use is a variant of the scheme proposed by Kawachi et al. [START_REF] Kawachi | Concurrently secure identification schemes based on the worst-case hardness of lattice problems[END_REF]. It is statistically hiding (based on the left-over hash lemma [START_REF] Regev | On lattices, learning with errors, random linear codes, and cryptography[END_REF]) and computationally binding (based on the SIS assumption).

For a lattice

  L, let ρ σ,c (x) = exp(-π xc 2 /σ 2 ) for a vector c ∈ R m and a real σ > 0. The discrete Gaussian of support L, center c and parameter σ is D L,σ,c (y) = ρ σ,c (y)/ρ σ,c (L) for any y ∈ L, where ρ σ,c (L) = x∈L ρ σ,c (x). The distribution centered in c = 0 is denoted by D L,σ (y).

Theorem 2 .

 2 The OT N k×1 protocol provides receiver security under the SIS assumption. (The proof is available in Appendix E.1.) Theorem 3. The OT N k×1 protocol provides sender security under the SIS and LWE assumptions. (The proof is available in Appendix E.2.)

Figure 1 :

 1 Figure 1: Stern-like ZKAoK for the relation R abstract .

Example 1 . 2 T 2 m-

 122 Let (x, y) = (2, 1) and (c, b) = (4, 1). Then we have: ext 5×2 (2, 1) = 0, 1, 0, 0, 0, 4, 0, 3, 0, 5×2[START_REF] Alwen | Generating shorter bases for hard random lattices[END_REF][START_REF] Abe | Universally composable adaptive oblivious transfer (with access control) from standard assumptions[END_REF] ext 5×2 (2, 1) = 0, 0, 4, 0, 3, 0, 2, 0, 1, 0 Note that:T 5×2 [4, 1] ext 5×2 (2, 1) = ext 5×2 (1, 0) = ext 5×2 (2 + 4 mod 5, 1 ⊕ 1).Notation Meaning/Property/Usage/Technique B The set of vectors in {0, 1} 2m with Hamming weight m.

  Then extend w 3,1 to w 3,1 ∈ B 2 D3,1 . -Define the vector w 3,2 = (v 1 |v U,1 |r U |ν |e ) ∈ {-1, 0, 1} D3,2 of dimension D 3,2 = 3mδ β + t(δ B + 1) and extend it into w 3,2 ∈ B 3 D3,2 . -Extend v2 to s 0 ∈ B 3 mδ β . Then for j ∈ [ ], form vector s j = expand τ [j], s 0 . -Extend vU,2 to s U,0 ∈ B 3 mδ β . Then for j ∈ [ I ], form s U,j = expand τ U [j], s U,0 .

  x) to I which replies with a bit b. If b = 1, then T adds x to C i . In any cases, T sends b to U i . • When receiving (transfer, ρ) from U i , the trusted party T acts as follows. If U i previously sent a message of the form (transfer, .), T defines f U ,DB = 1. Otherwise, it sets f U ,DB = 0. If DB = ⊥, it sends (transfer, f U ,DB ) to DB , who sends a bit b. If b = 1 and if st i contains a vector x such that AP i (x) = 1, then it sends the record to U i . In any other cases, it sends ⊥ to U i .

Exp 3 :

 3 This experiment is like Exp 2 except that, instead of faithfully querying the database entry ρ i dictated by E at each transfer, Sim 3 chooses a random index ρ ∈ [N ] among those for which, on behalf of U, it obtained a valid credential for an attribute string x satisfying BP ρ (x) = 1. That is, at each transfer, Sim 3 samples vectors e ← U ({-1, 0

Exp 5 := 6 :

 56 implies the existence of a SIS algorithm such that | Pr[W 4 ] -Pr[W 3 ]| ≤ Q I • Adv SIS B (λ), where Q I is the number of queries made by A to the honest issuer controlled by Sim 4 . This experiment is the same as Exp 4 with the difference that, after each knowledge extraction incurred by step 2 of Transfer, Exp 5 aborts if the extracted witnesses m ∈ {0, 1} m d , τ ∈ {0, 1} and v = (v 1 |v 2 ) ∈ Z 2m satisfy the equalityA A 0 . . . A • u + D • m, whereas the left-hand-side member of 2n+t,q-1 • m ∈ Z 2n+t q (50) does not coincide with any triple {(a i , b i , h BP,i )} Ni=1 appearing in DB. This event clearly implies a breach in the bounded message security of the signature scheme in Section 3.2. Under the SIS assumption, experiments Exp 5 and Exp 4 are thus computationally indistinguishable as there exists a PPT algorithm B such that | Pr[W 5 ] -Pr[W 4 ]| ≤ Q • Adv SIS B (λ). Exp This experiment is the same as Exp 5 but that, at the first Transfer query dictated by the environment E, the zero-knowledge argument of knowledge 57 of s j ∈ χ n , e j ∈ χ m , xj ∈ χ N , Mj ∈ {0, 1} N such that generated at step 1 of Transfer) is replaced by a simulated interactive argument (which the ZK simulator generates without knowing the witnesses) and so is the ZK argument of knowledge of {(s j , e j , y[j])} t j=1 satisfying (17) at step 3 of Transfer. Henceforth, the small-norm matrices S = [s 1 | . . . |s t ] ∈ Z n×t , E = [e 1 | . . . |e t ] ∈ χ m×t satisfying (8) are no longer used by Sim 4 . The statistical ZK property of the argument system guarantees that | Pr[W 6 ] -Pr[W 5 ]| ≤ negl(λ). Exp 7 : This experiment is like Exp 6 with the difference that, at step 3 of DBSetup, Sim 7 replaces the columns of the matrix P = [p 1 | . . . | p t ] = F • S + E ∈ Z m×t q

3 :

 3 2n+t,q-1 • m ∈ Z 2n+t q differs from all tuples {(a i , b i , h BP,i )} N i=1 in DB. This contradicts the bounded message security of the signature scheme in Section 3.2. Under the SIS assumption, Exp 2 and Exp 1 are thus computationally indistinguishable as there is a PPT algorithmB such that | Pr[W 2 ] -Pr[W 1 ]| ≤ Q • Adv SIS B (λ). Exp This experiment is the same as Exp 2 but that, at the first Transfer query dictated by the environment E, the zero-knowledge argument of knowledge of s j ∈ χ n , e j ∈ χ m , xj ∈ χ N , Mj ∈ {0, 1} N such that at step 1 of Transfer) is simulated (i.e., the ZK simulator generates it without knowing the witnesses) and so is the ZK argument of knowledge of {(s j , e j , y[j])} t j=1 satisfying (17) at step 3 of Transfer. The small-norm matrices S = [s 1 | . . . |s t ] ∈ Z n×t , E = [e 1 | . . . |e t ] ∈ χ m×t satisfying (8) are not used any longer by Sim 3 . The statistical ZK property of the argument system guarantees that | Pr[W 3 ] -Pr[W 2 ]| ≤ negl(λ). Exp 4 : Here, at step 3 of DBSetup, Sim 4 replaces the columns p i of the matrix P = [p 1 | . . . | p t ] = F •S+E ∈ Z m×t q

C 1 =

 1 COM(φ, M • r w ; ρ 1 ),C 2 = COM(Γ φ (r w ); ρ 2 ), C 3 = COM(Γ φ (w + r w ); ρ 3 ).Receiving a challenge Ch from V, the simulator responds as follows:-If Ch = 1: Output ⊥ and abort. -If Ch = 2: Send RSP = φ, w + r w , ρ 1 , ρ 3 . -If Ch = 3: Send RSP = φ, r w , ρ 1 , ρ 2 .Case Ch = 2: SIM samples w ← U (VALID), r w ← U (Z D q ), φ ← U (S), and randomness ρ 1 , ρ 2 , ρ 3 for COM. Then it sends the commitment CMT = C 1 , C 2 , C 3 to V, whereC 1 = COM(φ, M • r w ; ρ 1 ), C 2 = COM(Γ φ (r w ); ρ 2 ), C 3 = COM(Γ φ (w + r w ); ρ 3 ).

  mδ β +tδ B +t and extend it into the vector w * 2 ∈ B 3 mδ β +tδ B +t . -Extend v2 into s 0 ∈ B 3 mδ β . Then, for each j ∈ [ ], define s j = expand(τ [j], s 0 ). (We refer to Table 1 for details about expand(•, •).)

	Now, we form vector w

Table 3 .

 3 Overview of the different adaptive OT-AC protocols secure in the standard model. Here N denotes the size of the database. The polynomial Poly (λ) in transfer costs captures the complexity incurred by the treatment of access policies. In[START_REF] Camenisch | Oblivious transfer with hidden access control from attribute-based encryption[END_REF], GGM stands for "generic group model" while CNF -refers to restricted CNF formulas: each clause is restricted to have its literals from the same category (e.g., if categories are Job Title = {Professor, Post-Doc, Ph.D. Student} and Gender = {Male, Female}, a policy can be "(Professor ∨ Post-doc) ∧ (Male ∨ Female)", but cannot contain a clause of the form (Professor ∨ Female) or two clauses containing litterals from the Job Title category). Finally, "Conj." means "Conjunctions", meaning that the user has to possess all the credentials for a given message, and disjunctions can be achieved by duplicating database entries.

  , . . . , y[t]) ∈ Z t and S = [s 1 | . . . |s t ], this amounts to proving, for each j ∈ [t], knowledge of s j ∈ χ n , y[j] ∈ Z such that |y[j]| < q/4 and e j ∈ χ m , such that

  • Q H /( -3 -t ) times (where Q H is the number of queries to H FS ) suffices to break the binding property of the commitment. Under the SIS assumption, we have| Pr[W 3 ] -Pr[W 2 ]| ∈ negl(λ).Exp 4 : This experiment is like Exp 3 with the difference that, at each transfer, the receiver R chooses the index ρ i = 1 and thus always requests the first message of the encrypted database. In more details, at each transfer, R samples vectors e ← U ({-1, 0, 1} m ), µ ← U ({0, 1} t ) and ν ← U ([-B, B] t ) to compute and send

Several pairing-free candidates were suggested in[START_REF] Kurosawa | Efficiency-improved fully simulatable adaptive OT under the DDH assumption[END_REF][START_REF] Kurosawa | Generic fully simulatable adaptive oblivious transfer[END_REF] but, as pointed out in[START_REF] Green | Practical adaptive oblivious transfer from simple assumptions[END_REF], they do not achieve full simulatability in the sense of[START_REF] Camenisch | Simulatable adaptive oblivious transfer[END_REF]. In particular, the sender can detect if the receiver fetches the same record in two distinct transfers.

Acknowledgements

Part of this research was funded by Singapore Ministry of Education under Research Grant MOE2016-T2-2-014(S) and by the French ANR ALAMBIC project (ANR-16-CE39-0006). Another part was funded by BPI-France in the context of the national project RISQ (P141580).

Type I attacks, where in the adversary's forgery sig = (τ , v ), τ did not appear in any outputs of the signing oracle.

Type II attacks, where in the adversary's forgery sig = (τ , v ), τ has been recycled from an output sig (i ) = τ (i ) , v (i ) of the signing oracle for some query i ∈ {1, . . . , Q}.

Lemma 5 states that the signature scheme is secure against Type I forgery using the same technique as is [START_REF] Agrawal | Efficient lattice (H)IBE in the standard model[END_REF][START_REF] Boyen | Lattice mixing and vanishing trapdoors: A framework for fully secure short signatures and more[END_REF][START_REF] Micciancio | Trapdoors for lattices: Simpler, tighter, faster[END_REF]. Lemma 6 claims that the signature scheme resists Type II attacks, with a proof that is very similar to the one of Lemma 5.

Both security proofs assume the computational hardness of the SIS problem.

Lemma 5. The signature scheme of Section 3.2 is secure against Type I attacks if the SIS n,m,q,β assumption holds, with β = σ 2 m 3/2 ( + 2) + σm 1/2 .

Proof. Let A be a PPT adversary against the na-CMA security of our scheme that mounts Type I attacks with non negligible success probability . We construct a PPT algorithm B using A to break the SIS n,m,q,β assumption. Our reduction B takes as input a target matrix Ā ∈ Z n×m q and computes v ∈ Λ ⊥ q ( Ā) satisfying 0 < v ≤ β .

At first, B calls A to obtain the messages to be queried: m (1) , . . . , m (Q) . For the sake of readability, let us define τ (i) = i, viewed as a bit-string, to be the tag corresponding to the i-th signature in our scheme.

Setup. As in [START_REF] Hohenberger | Short and stateless signatures from the RSA assumption[END_REF], the reduction guesses the shortest prefix such that the string τ embedded in A's forgery differs from all prefixes to {τ (1) , . . . , τ (Q) }. To achieve this, B chooses at random i † ← U ({1, . . . , Q}) and t † ← U ({1, . . . , }). Then, with probability 1/(Q • ), the longest common prefix between τ and one of the tags {τ

: the first (t † -1)-th bits of τ . Let us define τ † = τ |t † , where s |i denotes the i-th prefix for a string s.

|t † , . . . , τ

|t † } with probability 1/(Q • ). Next, the reduction B runs TrapGen(1 n , 1 m , q) to obtain matrices C ∈ Z n×m q and a short basis T C ∈ Z m×m of Λ ⊥ q (C), which will be useful to answer the following opening oracle queries. The reduction B continues by picking + 1 matrices Q 0 , . . . , Q ∈ Z m×m where each matrix Q i has its column independently sampled from D Z m ,σ , and B defines the matrices A = Ā and {A j } j=0 as follows

. Lemma 6. The signature scheme of Section 3.2 is secure against Type II attacks if SIS n,m,q,β holds, with β = √ 2( + 2)σm 3/2 + m 1/2 .

Proof. We will prove this result using techniques analogous to the previous proof. We show that given an adversary A that comes out with a Type II signature in the na-CMA game with non negligible probability ε, we can construct a PPT B that breaks the SIS assumption with advantage ε/Q using A.

Firstly, the reduction B is given a matrix Ā ∈ Z n×m d q as input and has to output an integer vector v ∈ Z m d in Λ ⊥ q ( Ā) such that 0 < v ≤ β . Next, B receives from A the messages m (1) , . . . , m (Q) for which A will further ask signature queries.

To compute the public key, at the outset of the game, the reduction B starts by sampling i † ← U ({1, . . . , Q}) corresponding to the guess that A's forgery will recycle τ (i †) . This is independent of A's view, and the guess will be correct with probability 1/Q. Using this guess to compute P K, the reduction B picks h 0 , . . . , h ∈ Z q subject to the constraints

B then runs (C, T C ) ← TrapGen(1 n , 1 m , q). The resulting matrix C ∈ Z n×m q is statistically random, and the trapdoor T C ∈ Z m×m is a short basis of Λ ⊥ q (C). Next B re-randomize Ā using short matrices S, S 0 , S 1 , . . . , S ∈ Z m d ×m which are obtained by sampling their columns from the distribution D Z m d ,σ . The challenger B then uses these matrices to define:

Observe that matrices A, {A j } j=0 are all statistically uniform over

Finally, B sends to A the public key

which is distributed as the P K of the real scheme.

To answer signing queries, the challenger B do as follows.

We assume two random oracles H F : {0, 1} * → Z n×m q and H FS : {0, 1} * → {1, 2, 3} ς , for some ς ∈ ω(log n). The former will be used to derive the sender's public matrix F ∈ Z n×m q while the latter will provide the verifier's challenges when we apply the Fiat-Shamir heuristic.

Initialization S I (1 λ , DB), R I (1 λ ) : In this protocol, the sender S I has a database DB = (M 1 , . . . , M N ) of N messages, where M i ∈ {0, 1} t for each i ∈ [N ], for some t ∈ poly(λ). It interacts with the receiver R I as follows.

1. Generate a key pair for the signature scheme of Section 3.2 in order to sign Q = N messages of length m d = (n + t) • log q each. This key pair consists of SK sig = T A ∈ Z m×m and

) with m = 2n log q , m d = (n + t) log q . The counter is initialized to τ = 0. 2. Choose a matrix S ← χ n×t that will serve as a secret key for an LWEbased encryption scheme. Then, define the matrix F = H F (ε) ∈ Z n×m q and sample a matrix E ← χ m×t to compute

so that (F, P) ∈ Z n×m q × Z m×t q forms a public key for a t-bit variant of Regev's encryption scheme [START_REF] Regev | On lattices, learning with errors, random linear codes, and cryptography[END_REF] (or, equivalently, a set of m encryptions of the all-zeroes t-bit string). 3. Sample vectors a 1 , . . . , a N ← U (Z n q ) and x 1 , . . . , x N ← χ t to compute

which includes a NIZK argument of knowledge π K of small-norm matrices S ∈ Z n×t and E ∈ χ m×t and t-bit messages {M i } N i=1 that are consistent with (37)- [START_REF] Hohenberger | Short and stateless signatures from the RSA assumption[END_REF]. The argument π K is built by taking the following steps:

Putting the above altogether, we find that the SIS assumption implies such that

The proof of security against a dishonest receiver is almost identical to the proof of Theorem 3. The only difference is that, from experience Exp 3 onwards, the sender's ZK arguments are non-interactive and can be simulated by programming the random oracle H FS : {0, 1} * → {1, 2, 3} ς in the standard way. The detailed proof of the following theorem is thus omitted. Theorem 6. The above OT N k×1 protocol provides sender security under the SIS assumption in the random oracle model.

As mentioned in [START_REF] Green | Practical adaptive oblivious transfer from simple assumptions[END_REF], extending the simulation-based definitions to the multireceiver setting is rather straightforward (see [START_REF] Green | Practical adaptive oblivious transfer from simple assumptions[END_REF]Appendix B] for details).

Analogously to the Green-Hohenberger protocol [35, Section 4], our proof of sender security goes through in the multi-receiver setting as long as the receivers interact with the sender in a sequential manner. This restriction is important since the simulator has to rewind the receiver's zero-knowledge arguments at step 1 of each transfer, which would not be possible in concurrent sessions.

E Security Proofs for the OT N k×1 Protocol of Section 4

E.1 Proof of Theorem 2

Let us first recall Theorem 2:

Theorem 7. The OT N k×1 protocol provides receiver security under the SIS assumption.

Proof. We prove that any real-world cheating sender Ŝ implies an ideal-world cheating sender Ŝ such that, under the SIS assumption, the two distributions Real Ŝ,R (N, k, M 1 , . . . , M N , ρ 1 , . . . , ρ k ) and Ideal Ŝ ,R (N, k, M 1 , . . . , M N , ρ 1 , . . . , ρ k ) are indistinguishable to any PPT distinguisher D.

To this end, we consider a sequence of hybrid experiments with binary outputs. In each experiment Exp i , a distinguisher D takes as input the states (S k , R k ) produced by Ŝ and R at the end of the experiment and outputs a bit. We define W i as the event that the output of experiment Exp i is 1. The first experiment outputs whatever the distinguisher D outputs and corresponds to the real interaction between the cheating sender Ŝ and the receiver R.

Exp 0 : This experiment involves a real execution of Ŝ in interaction with a honest receiver R which queries the index ρ i ∈ [N ] at the i-th transfer for each i ∈ [k]. The output of Exp 0 is exactly the output of the distinguisher D on input of X = (S k , R k ) ← Real S, R, so that we have

is traded for a uniformly random vector p i ← U (Z m q ). At the same time, each

q is replaced by a truly uniform random vector in Z t q . Therefore, P is a uniformly distributed matrix in Z m×t q , and the (b i ) N i=1 are distributed as uniform vectors in (Z t q ) N . Now, at step 5 of the initialization phase and step 2 of each transfer, the sender's zero-knowledge arguments are simulated arguments for false statements. However, a straightforward reduction shows that, under the LWE assumption over t • (m + N ) samples, these changes should remain unnoticed to the malicious receiver R and have no impact on the distinguisher's output:

The ideal-world receiver R is defined as follows. It assumes the role of the sender S in interaction with the real-world receiver R in Exp 4 . This implies that, in the initialization phase, the matrices (F, P) are chosen as uniformly random matrices (F, P) ← U (Z n×m q × Z m×t q ) and while, at step 3, (a

are faithfully signed using SK sig = T A at step 4. In step 5 of the initialization phase, R appeals to the simulator of the ZK argument. At the i-th transfer, when R sends (c 0 , c 1 ) and argues knowledge of (m, e, µ, ν, τ, v 1 , v 2 ) at step 1, R uses the knowledge extractor of the argument system to extract the witnesses (m, e, µ, ν, τ,

Note that, by Lemma 7, such an index must exist unless R can forge a signature. Having determined the index ρ i ∈ [N ] of the queried database entry, R sends ρ i to the trusted party T which returns the message M ρi ∈ {0, 1} t . The latter is used together with the extracted witness µ ∈ {0, 1} t to define the response M = M ρi ⊕ µ ∈ {0, 1} t that R generates on behalf of the sender Ŝ at step 2 of the transfer. In addition, the ideal-world dishonest receiver R appeals to the simulator of the zero-knowledge argument system to simulate an argument of knowledge of {(s j , e j , y[j])} t j=1 for the statement [START_REF] Canetti | Universally composable security: A new paradigm for cryptographic protocols[END_REF]. It is easy to see that, when R interacts with the simulator R that emulates the real-world sender S , its view is identical to that of Exp 4 : we have

When combining the above, we conclude that there exist PPT algorithms B and B such that

This proves the sender security under the SIS and LWE assumptions.

Proof (of Lemma 7). Let us assume that, at some transfer, the knowledge extractor reveals witnesses that contain a m d -bit string m which is not the decomposition of any (a i |b i ) ∈ Z n+t q appearing in R 0 . We construct an algorithm B that breaks the random-message security of the stateful signature scheme in Section 3.2 after N non-adaptive signing queries. In turn, this will contradict the SIS assumption.

Algorithm B begins by faithfully running steps 2 and 3 of the real initialization algorithm. Having generated

i=1 to its own challenger for the bounded-message security of the signature scheme. The latter challenger replies by returning a public key P K sig and a set of signatures

Since B knows the messages {M i } N i=1 and (S, E) ∈ χ n×t × χ m×t for having generated the matrix P = F • S + E at step 2, it can faithfully generate the sender's argument of knowledge at step 5 of the initialization algorithm.

By hypothesis, we know that, in some transfer, the knowledge extractor will extract witnesses m ∈ {0,

a valid signature on m unless the failure event introduced in Exp 1 (i.e., a failure of the knowledge extractor) occurs. This means that B can break the non-adaptive chosen-message security of the stateful signature scheme by outputting m, (τ, v) . Proof. As in [START_REF] Camenisch | Oblivious transfer with access control[END_REF], we assume that there is only one honest user U since the adversary can simulate the remaining users on its own. We consider a sequence which is a re-randomization of (a ρ , b ρ + µ • q/2 ). Moreover, Sim 2 uses the witness ρ to faithfully generate an interactive WI argument that (c 0 , c 1 ) is a re-randomization of (a ρ , b ρ ). It thus generates a WI argument of knowledge of vectors z BP,ρ , m = vdec 2n+t,q-1 (a

F Security Proofs for the OT-AC Protocol

satisfying relations [START_REF] Chor | Private information retrieval[END_REF] as well as the verification equations of BP ρ . The statistical WI property of the argument system ensures that this modification leaves the output distribution of E statistically unchanged. Indeed, since the randomization parameter B was chosen to make (m + 1)αq/B negligible, the distribution of (c 0 , c 1 ) is not affected (by the result of [24, Section 4.1]) if Sim 3 trades the real index ρ i for a random one. We have

From the adversary A of Exp 3 , we construct an ideal-world adversary A which assumes the roles of the database and the dishonest issuer. This ideal-world adversary A relays all the messages between E and the real-world A. It runs A so as to obtain the issuer's public key P K I = (A I , {A I,j } I j=0 , D I , {D I,0 , D I,1 }, u I ) and the encrypted database

At each instruction (issue, U , x) received from T, it starts an execution of the Issue protocol on behalf of U interacting with the issuer-executing A. At the first instruction transfer received from T, A runs to the knowledge extractor of the argument system at step 1 of Transfer so as to extract the small-norm

i=1 and obtain the messages M 1 , . . . , M N ∈ {0, 1} N that were encrypted as per [START_REF] Bourse | FHE circuit privacy almost for free[END_REF]. It then sends the message (initdb, {(M i , BP i )} N i=1 ) to the trusted party T. Then, it simulates step 2 of Transfer on behalf of the real-world U and queries a random record ρ ∈ [N ] among those for which it has a credential for an input x ∈ {0, 1} κ such that BP ρ (x) = 1. At step 3 of the transfer, it aborts the interaction in the event that A provides a verifying ZK argument whereas condition [START_REF] Ling | Improved zero-knowledge proofs of knowledge for the isis problem, and applications[END_REF] is not satisfied. If the real-world transfer is successful (resp. fails), A s sends b = 1 (resp. b = 0) to the trusted party T. Subsequent transfer instructions from T are treated in the same way, but without the first step of running the knowledge extractor.

We observe that A provides the real-world database/issuer A with the same view as Sim 3 does in Exp 2 . We have

When combining the above altogether, we obtained the claimed statement as there exists a PPT SIS solver B such that

F.2 Security Against a Corrupted Database Lemma 9. For any environment E and any adversary A controlling only the database, there exists an ideal-world adversary A such that the distributions Real E,A (λ) and Ideal E,A (λ) are computationally indistinguishable under the SIS assumption.

Proof. Again, we assume that there is only one honest user U as the adversary can simulate the remaining users on its own. The proof is almost identical to the proof of Lemma 8: the sequence of experiments Exp i is the same and only the simulation changes. We thus only describe the simulation.

From the adversary A of Exp 2 , we construct an ideal-world adversary A which assumes the roles of the database and the dishonest issuer. This ideal-world adversary A relays all the messages between E and the real-world A. It runs A so as to obtain the issuer's public key P K I = (A I , {A I,j } I j=0 , D I , {D I,0 , D I,1 }, u I ) and the encrypted database

. At the first instruction transfer received from trusted party T, A runs to the knowledge extractor of the argument system at step 1 of Transfer so as to extract the small-norm

i=1 and obtain M 1 , . . . , M N ∈ {0, 1} N which were encrypted in [START_REF] Bourse | FHE circuit privacy almost for free[END_REF]. It then sends the message (initdb, {(M i , BP i )} N i=1 ) to T. Next, it simulates step 2 of Transfer on behalf of U and queries a random record ρ ∈ [N ] among those for which it has a credential for an x ∈ {0, 1} κ satisfying BP ρ (x) = 1. At step 3 of the transfer, it aborts the interaction with A if A provides a verifying ZK argument but condition [START_REF] Ling | Improved zero-knowledge proofs of knowledge for the isis problem, and applications[END_REF] does not hold. If the transfer succeeds (resp. fails), A s sends b = 1 (resp. b = 0) to the trusted party T. Subsequent transfer instructions from T are handled in the same way, but without running the knowledge extractor to extract S and E.

We remark that, when emulating the honest user U, the ideal-world adversary A provides the real-world database/issuer A with the same view as Sim 3 does in Exp 3 . We thus find that Pr

F.3 Security Against Corrupted Users

Lemma 10. For any environment E and any adversary A controlling only some of the users, there exists an ideal-world adversary A such that the distributions Real E,A (λ) and Ideal E,A (λ) are computationally indistinguishable under the SIS and LWE assumptions.

Proof. We consider again a sequence of hybrid experiments Exp i where, for each i, a simulator Sim i interacts with A on behalf of the database and the issuer. For each i, W i stands for the event that the environment E outputs 1 in Exp i .

Exp 0 : This experiment corresponds to a real execution of the adversary A in interaction with a honest sender and a honest issuer. The output of the experiment is identical to the output of the environment E. We have

Exp 1 : This experiment is like Exp 0 except that, when the user U sends the ciphertext (c 0 , c 1 ) ∈ Z n q × Z t q at step 2 of each transfer, Sim 1 appeals to the knowledge extractor of the argument system so as to extract the witnesses x ∈ {0, 1} κ , r com,0 , . . . , [START_REF] Brakerski | On the classical hardness of learning with errors[END_REF] and [START_REF] Chor | Private information retrieval[END_REF], as well as the relations ( 21)-( 28) of Section 6.6. If the knowledge extraction fails at some transfer, Sim 1 aborts and outputs ⊥. Since the zero-knowledge argument system is computationally sound as long as the underlying commitment is binding, which boils down to the SIS assumption if the commitment of [START_REF] Kawachi | Concurrently secure identification schemes based on the worst-case hardness of lattice problems[END_REF] is used. Under the SIS assumption, E returns 1 with nearly the same probability in Exp 1 as in Exp 0 : concretely, there exists a SIS-solver B such that

, where Q is the total number of transfers.

Exp 2 : This experiment is like Exp 1 with one modification. At each step θ ∈ [L] of each transfer, Sim 2 considers the extracted witnesses g 1,0 , . . . , g L,δκ ∈ {0, 1} n log q and var(θ

and aborts in the event that com var(θ) = com var(θ) . Owing to relations [START_REF] Damgård | Universally composable efficient multiparty computation from threshold homomorphic encryption[END_REF], the soundness of the argument system ensures that the knowledge extractor reveals a path connecting com var(θ) to the root u tree of the Merkle tree, which is deterministically computed by hashing {com i } κ-1 i=0 . Together with (49), the inequality com var(θ) = com var(θ) implies that Sim 2 obtains a collision on the hash chain from com var(θ) = com var(θ) to the root u tree . This contradicts the SIS assumption when the Merkle tree is instantiated with the same SIS-based hash function as in [START_REF] Libert | Zero-knowledge arguments for latticebased accumulators: Logarithmic-size ring signatures and group signatures without trapdoors[END_REF]. We thus have and checks if the witness x var(θ) ∈ {0, 1} (i.e., the var(θ)-th coordinate of the extracted witness x of relation ( 28)) disagrees with the extracted bit y θ ∈ {0, 1} for which relation [START_REF] Damgård | Universally composable efficient multiparty computation from threshold homomorphic encryption[END_REF] ensures that (y θ , r θ ) ∈ {0, 1} × {0, 1} m forms an opening of com var(θ) = H n,q-1 • g θ,δκ . In this case, the knowledge extractor outputs two distinct openings (x var(θ) , r com,var(θ) ) and (y θ , r θ ) of com var(θ) , which breaks the binding property of the commitment. Since the latter relies on the SIS assumption, we have

return on behalf of the sender DB at step 3 of the transfer. In addition, the idealworld A runs simulator of the argument system so as to simulate an argument of knowledge of {(s j , e j , y[j])} t j=1 for the statement [START_REF] Canetti | Universally composable security: A new paradigm for cryptographic protocols[END_REF]. We remark that, when A and E interact with the simulator A which emulates the real-world DB and I while playing the ideal-world receiver, their view is identical to that of Exp 6 : we have

We find that there exists a PPT algorithms B and B such that

which proves the lemma's statement.

F.4 Security of the Database Against Colluding Issuer and Users

Lemma 11. For any environment E and any adversary A controlling the issuer and some of the users, there is an ideal-world adversary A such that the distributions Real E,A (λ) and Ideal E,A (λ) are computationally indistinguishable under the SIS and LWE assumptions.

Proof. The proof is very similar to the proof of Lemma 10 except that, since the adversary controls the issuer, it can obtain any credential of its choice and we do not have to rule out credential forgeries any longer. Again, for each i, W i stands for the event that the environment E outputs 1 in Exp i .

Exp 0 : This corresponds to a real execution of the adversary A interacting with a honest sender and a honest issuer. The output of the experiment is the output of the environment E. We have Pr

This experiment is like Exp 0 except that, when the user U sends the ciphertext (c 0 , c 1 ) ∈ Z n q × Z t q at step 2 of each transfer, Sim 1 appeals to the knowledge extractor of the argument system to extract witnesses m ∈ {0, 19) at step 2 of Transfer. Should the knowledge extraction fail at some transfer, Sim 1 aborts and outputs ⊥. Given that the zero-knowledge argument system is computationally sound so long as the underlying commitment is binding. If the commitment scheme of [START_REF] Kawachi | Concurrently secure identification schemes based on the worst-case hardness of lattice problems[END_REF] is used for this purpose, the SIS assumption reduces to the binding property. Under the SIS assumption, E returns 1 with very close probabilities in Exp 1 as in Exp 0 : if Q denotes the total number of transfers, we have ) and while each pair

i=1 are faithfully signed using SK sig = T A at step 5.b of DBSetup. At the first Transfer message sent by T, A runs the simulator of the ZK argument. When A sends (c 0 , c 1 ) and argues knowledge of (m, e, µ, ν, τ, v 1 , v 2 ) at step 2 of the transfer phase, A uses the knowledge extractor of the argument system to extract (m, e, µ, ν, τ,

Note that, due to the change introduced in Exp 3 , such an index must exist. Having extracted the queried index ρ i ∈ [N ], A queries the trusted party T to obtain credentials for an x ∈ {0, 1} κ such that BP ρi (x) = 1. Since A controls the ideal-world I, it sends the bit 1 to T so as to deliver all the necessary credentials to the user. Then, A queries T to obtain M ρi ∈ {0, 1} t . The latter is used together with the extracted witness µ ∈ {0, 1} t to reverse-engineer the correct response M = M ρi ⊕ µ ∈ {0, 1} t that A should return on behalf of DB at step 3 of the transfer. In addition, the ideal-world A runs simulator of the argument system so as to simulate an argument of knowledge of {(s j , e j , y[j])} t j=1 for the statement 17.

When A and E interact with the simulator A emulating the real-world DB while playing the ideal-world U and I, their view is identical to that of Exp 4 : we have Pr

Putting the above altogether, we find that there exists a PPT algorithms B and B such that

G Analysis of the Abstract Protocol

We first restate Theorem 4.

Theorem 9. The protocol in Figure 1 is a statistical ZKAoK with perfect completeness, soundness error 2/3, and communication cost O(D log q). Namely:

-There exists a polynomial-time simulator that, on input (M, v), outputs an accepted transcript statistically close to that produced by the real prover. -There exists a polynomial-time knowledge extractor that, on input a commitment CMT and 3 valid responses (RSP 1 , RSP 2 , RSP 3 ) to all 3 possible values of the challenge Ch, outputs w ∈ VALID such that M • w = v mod q.

The commitment key consists of vector a com ← U (Z n q ) and matrix Ā ← U (Z n×m q ). To commit to a bit x ∈ {0, 1}, one samples r com ← U ({0, 1} m ), and outputs the commitment

For uniformly random Ā ∈ Z n×m q and uniformly random r com ∈ {0, 1} m , the distribution of vector Ā • r com ∈ Z n q is statistically close to the uniform distribution over Z n q (by the left-over hash lemma). Thus, the commitment com statistically hides the committed bit x.

Meanwhile, if one can find x , x ∈ {0, 1} and r , r ∈ {0, 1} m , such that x = x and

then the non-zero vector x -x rr ∈ {-1, 0, 1} m+1 yields a valid solution to the SIS n,m+1,q, √ m+1 problem associated with matrix

. In other words, an adversary breaking the computational binding property of the scheme leads to an adversary breaking the SIS assumption.

Merkle hash tree. We now recall SIS-based Merkle tree proposed by Libert et al. [START_REF] Libert | Signature schemes with efficient protocols and dynamic group signatures from lattice assumptions[END_REF]. The construction relies on the following collision-resistant hash function.

For matrix

, define the function h Ā as follows:

This hash function is collision-resistant under the SIS assumption. Indeed, if two pairs (u 0 , u 1 ) and (u 0 , u 1 ) cause a collision, then one has:

where z = u 0 -u 0 u 1 -u 1 ∈ {-1, 0, 1} m is a non-zero vector. Thus, z yields a valid solution to the SIS n,m,q, √ m problem associated with matrix Ā. Using the hash function described above, one can build Merkle hash trees to securely accumulate data. In particular, for any κ ∈ poly(λ), and for any data values com 0 , . . . , com κ-1 ∈ Z n q , one builds the tree of depth δ κ = log κ on top of these values, as follows. Leaf nodes: Since 2 δκ leaf nodes are needed to build a complete binary tree of depth δ κ , one appends 2 δκ -κ duplications of the value com κ-1 to the sequence com 0 , . . . , com κ-1 so that the appended sequence has length 2 δκ .

Applying the function vdec n,q-1 (•) to elements of the appended sequence, one gets 2 δκ values denoted as u 0,0,...,0 , . . . , u 1,1,...,1 ∈ {0, 1} n log q . These values are associated with the 2 δκ leaves of the tree.

Non-leaf nodes: Every non-leaf node of the tree is associated with the hash value of its two children. Specifically:

1. At depth i ∈ [δ κ ], the node u b1,...,bi ∈ {0, 1} n log q , for all (b 1 , . . . , b i ) ∈ {0, 1} i , is defined as h Ā(u b1,...,bi,0 , u b1,...,bi,1 ). 2. At depth 0: The root u tree ∈ {0, 1} n log q is defined as h Ā(u 0 , u 1 ).

Note that, the collision resistance of the hash function h Ā guarantees that it is infeasible to find a tree path starting from u tree and ending with two distinct leaf nodes. Now, for any integer var(θ) ∈ [0, κ -1], the witness for the fact that com var(θ) was properly accumulated into u tree consists of:

-The binary representation (d θ,1 , . . . , d θ,δκ ) of var(θ); -The nodes g θ,1 , . . . , g θ,δκ ∈ {0, 1} n log q on the tree path determined by (d θ,1 , . . . , d θ,δκ ), as well as their sibling nodes t θ,1 , . . . , t θ,δκ ∈ {0, 1} n log q . (Note that H n,q-1 • g θ,δκ = com var(θ) mod q.)

The witness satisfies the relations described below. At the root, if d θ,1 = 0 then one has

). In other words, one has:

where expand(•, •) is defined in Table 1. Similarly, going along the path, one has equations:

Additionally, if g θ,δκ is the binary representation of a commitment to a bit y θ with randomness r θ (where the underlying commitment scheme is the one discussed above), then one eventually has:

This explains the equations considered in the "Merkle Tree Step" of Protocol 4 (Section 6.6).

H.2 Deferred Description Details of Protocol 4: VALID, S and Γ φ Let VALID be the set of all vectors in [-1, 4] D having the form (w T tree w T BP w T 3 ) T , where w tree , w BP , w 3 have the form [START_REF] Di Crescenzo | Conditional oblivious transfer and timed-release encryption[END_REF], [START_REF] Even | A randomized protocol for signing contracts[END_REF], and [START_REF] Gentry | Homomorphic encryption from learning with errors: Conceptually-simpler, asymptotically-faster, attribute-based[END_REF], respectively, and the following conditions hold:

-For each (θ, i) ∈ [L] × [δ κ ]: There exists d θ,i ∈ {0, 1} and g θ,i , t θ,i ∈ B 2 m/2 such that d θ,i = ext 2 (d θ,i ) and g θ,i = expand(d θ,i , g θ,i ); t θ,i = expand( dθ,i , t θ,i ).

-There exist y 1 ∈ {0, 1} and π 1,0 (0), π 1,1 (0) ∈ [0, 4] such that

-For all (j, i) ∈ {0, 1} × [START_REF] Abe | Universally composable adaptive oblivious transfer (with access control) from standard assumptions[END_REF][START_REF] Alwen | Generating shorter bases for hard random lattices[END_REF]: Π 1,j,i = ext 5 (π 1,j (i)), for some π 1,j (i) ∈ [0, 4].

(Note that these π 1,j (i) do not participate in the evaluation of BP.)

-For θ ∈ [2, L]: There exist y θ ∈ {0, 1}, f θ,0 , f θ,1 ∈ [0, 4] such that y θ = ext 2 (y θ ) and

-For (θ, j, i) ∈ [2, L] × {0, 1} × [0, 4]: there exist π θ,j (i) ∈ [0, 4], c θ,i ∈ {0, 1} such that Π θ,j,i = ext 5 (π θ,j (i)); c θ,i = ext 2 (c θ,i ); z θ,j,i = ext 5×2 (π θ,j (i), c θ,i ).

-There exist η 1 , . . . , η L-1 ∈ [0, 4] such that the following hold.

1. For all θ = 1, . . . , L -1: s θ = ext 5 (η θ ).

2. For all θ = 2, . . . , L: e θ = unit η θ-1 .

-r ∈ B 2 mL ; w 3,1 ∈ B 2 D3,1 ; w 3,2 ∈ B 3 D3,2 ; -s 0 ∈ B 3 mδ β , and there exists τ = (τ [1], . . . , τ [ ]) T ∈ {0, 1} such that for all j ∈ [ ]: s j = expand τ [j], s 0 .

-s U,0 ∈ B 3 mδ β , and there exists

By construction, we have w ∈ VALID. Let us now specify the set S and permutations of D elements {Γ φ : φ ∈ S}, for which the conditions in [START_REF] Brickell | Design validations for discrete logarithm based signature schemes[END_REF] hold. Again, we refer to the notations and techniques from Table 1, which we will apply here. Let ) T , Σ tree = (σ g,1,1 , . . . , σ g,θ,δκ , σ t,1,1 , . . . , σ t,θ,δκ , σ r ),

let Γ φ be the permutation that, when applying to vector s having the form (w T tree w T BP w T 3 ) T ∈ Z D , where w tree , w BP , w 3 have the form ( 22), [START_REF] Even | A randomized protocol for signing contracts[END_REF], and ( 29), respectively, it transforms the block-vectors as follows:

-For each θ = 1, . . . , L -1:

-For each θ = 2, . . . , L:

Based on the equivalences observed in Table 1, it can be checked that the conditions of (12) hold, namely:

H.3 Notes on the Simulator and Knowledge Extractor of Protocol 4

We recall that Protocol 4 invokes the Stern-like protocol from Section 6.1. Here, we give some remarks on how the transcript simulator SIM and knowledge extractor KE of the former protocol work, based on those of the latter protocol (see Theorem 4) and the facts that the bit commitment scheme and the Merkle hash tree being used are secure. In a nutshell:

-SIM relies on the simulator SIM of the abstract protocol and the statistically hiding property of the bit commitment scheme. -KE works by invoking the extractor KE of the abstract protocol, the computationally binding property of the bit commitment scheme and the collision resistance of the Merkle hash tree.

Transcript Simulation. In the real protocol, at the beginning of the interaction, the prover sends commitments com 0 , . . . , com κ-1 ∈ Z n q to the verifier for once, then both parties construct matrix M and vector v, and they run the protocol from Section 6.1 on common input (M, v). As noted in Section H.1 of this Supplementary Material, for each i ∈ [0, κ -1] the distribution of com i is statistically close to U (Z n q ). The simulator SIM interacts with a (possibly dishonest) verifier V as follows.

-At the beginning of the interaction, it samples com 0 , . . . , com κ-1 ← U (Z n q ), and sends these vectors to V. The distribution of (com 0 , . . . , com κ-1 ) is thus statistically close to the distribution of (com 0 , . . . , com κ-1 ) in the real protocol. Both parties then construct the common input as in the real protocol.

-Next, SIM proceeds exactly as the simulator SIM of the abstract protocol (see Section G of this Supplementary Material). Note that the latter produces an accepted transcript statistically close to that produced by the real prover with success probability negligibly close to 2/3.

It can be seen from the above construction that SIM successfully simulates the honest prover of Protocol 4 with probability negligibly close to 2/3.

Knowledge Extraction. The knowledge extractor KE takes as input the following:

-Matrix M and vector v, which are built from F, P, A HBP , c 0 , c 1 , A, A 0 , A 1 , . . . , A , D, u, A I , A I,0 , A I,1 , . . . , A I, I , D I , u I , D I,0 , D I,1 , a com , Ā, com 0 , . . . , com κ-1 , as described in Section 6.6. -A commitment CMT and 3 valid responses (RSP 1 , RSP 2 , RSP 3 ) to all 3 possible values of the challenge Ch, with respect to the abstract protocol.

By invoking the knowledge extractor KE of the abstract protocol, KE obtains vector w ∈ VALID such that M • w = v mod q. Next, it parses w as

where w tree ∈ {0, 1} Dtree , w BP ∈ [0, 4] D BP and w 3 ∈ [-1, 4] D3 . Now, KE backtracks the transformations of Section 6.6, as follows.

Backtracking the third step. Write w 3 ∈ [-1, 4] D3 in the form of [START_REF] Gentry | Homomorphic encryption from learning with errors: Conceptually-simpler, asymptotically-faster, attribute-based[END_REF] and backtracks the transformations of the third steps, KE obtains

and ∀i ∈ [0, κ -1] :

Backtracking the Merkle tree step. Write w tree in the form of [START_REF] Di Crescenzo | Conditional oblivious transfer and timed-release encryption[END_REF] and backtracks the transformations done in the Merkle tree step, the extractor KE obtains {g θ,δκ ∈ {0, 1} n log q , (y θ , r θ ) ∈ {0, 1} × {0, 1} m } θ∈[L] such that, for each θ ∈ [L]:

1. The Merkle tree path determined by bits d θ,1 , . . . , d θ,δκ (which were obtained above) leads to leaf node g θ,δκ . 2. Equation a com • y θ + Ā • r θ = H n,q-1 • g θ,δκ mod q holds. On the other hand, since the Merkle hash tree was built on top of public values com 0 , . . . , com κ-1 , there must exist an integer var (θ) ∈ [0, κ -1], such that the path determined by the same bits d θ,1 , . . . , d θ,δκ leads to a leaf node denoted by c θ ∈ {0, 1} n log q such that H n,q-1 • c θ = com var (θ) mod q. Note that, if g θ,δκ = c θ , then this yields a collision for the hash function h Ā. Thus, under the SIS assumption, one can deduce that g θ,δκ = c θ . This further implies that: a com • y θ + Ā • r θ = H n,q-1 • g θ,δκ = H n,q-1 • c θ = com var (θ) mod q.

Meanwhile, from [START_REF] Naor | Efficient oblivious transfer protocols[END_REF], one also has a com • x var (θ) + Ā • r com,var (θ) = com var (θ) mod q.

In other words, the same commitment com var (θ) opens to bits y θ and x var (θ) . If these bits are distinct then the binding property of the commitment scheme is broken. Thus, under the SIS assumption, one can deduce that y θ = x var (θ) , for all θ ∈ [L].

Backtracking the branching program step. Write w BP in the form of [START_REF] Even | A randomized protocol for signing contracts[END_REF] and backtracks the transformations done in the branching program step, the knowledge extractor KE obtains η 1 , . . . , η L-1 ∈ [0, 4], f 2,0 , f 2,1 , . . . , f L,0 , f L,1 ∈ [0, 4], c 2,0 , . . . , c L,4 ∈ {0, 1}, satisfying the relations In other words, one has BP (x ) = 1, where BP is the branching program determined by var (1), . . . , var (θ), π 1,0 (0), . . . , π L,1 (4).

To summarize, under the SIS assumption, the knowledge extractor KE can extract witnesses satisfying the statement considered by Protocol 4.