Abstract
We show that it is possible to perform n independent copies of 1-out-of-2 oblivious transfer in two messages, where the communication complexity of the receiver and sender (each) is \(n(1+o(1))\) for sufficiently large n. Note that this matches the information-theoretic lower bound. Prior to this work, this was only achievable by using the heavy machinery of rate-1 fully homomorphic encryption (Rate-1 FHE, Brakerski et al., TCC 2019).
To achieve rate-1 both on the receiver’s and sender’s end, we use the LPN assumption, with slightly sub-constant noise rate \(1/m^{\epsilon }\) for any \(\epsilon >0\) together with either the DDH, QR or LWE assumptions. In terms of efficiency, our protocols only rely on linear homomorphism, as opposed to the FHE-based solution which inherently requires an expensive “bootstrapping” operation. We believe that in terms of efficiency we compare favorably to existing batch-OT protocols, while achieving superior communication complexity. We show similar results for Oblivious Linear Evaluation (OLE).
For our DDH-based solution we develop a new technique that may be of independent interest. We show that it is possible to “emulate” the binary group \(\mathbb {Z}_2\) (or any other small-order group) inside a prime-order group \(\mathbb {Z}_p\) in a function-private manner. That is, \(\mathbb {Z}_2\) operations are mapped to \(\mathbb {Z}_p\) operations such that the outcome of the latter do not reveal additional information beyond the \(\mathbb {Z}_2\) outcome. Our encoding technique uses the discrete Gaussian distribution, which to our knowledge was not done before in the context of DDH.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
Notes
- 1.
That is, a protocol in which the receiver obtains \(b, x_b\) and the sender obtains \(x_0,x_1\), where \(b, x_0, x_1\) are all (pseudo-)randomly sampled.
- 2.
In more detail, since 2-message OT implies a public-key encryption scheme, the messages must have length that relates to the security parameter of the underlying computation assumption. This is the case even for single-bit OT.
- 3.
Achieving optimal rate (or any rate above 1/2) seems to involve a “phase-transition” and should be viewed as more than a “constant factor” improvement. For example, OT beyond this threshold implies the existence of lossy trapdoor functions (see discussion in [19], Sect. 6.3). Therefore one could expect such a protocol to inherently be heavier on public-key operations.
- 4.
This is still a regime where LPN alone is not known to imply public-key encryption.
- 5.
i.e. every component of \(e_i\) of \(\mathbf {e}\) is independently 0 with probability \(1 - \rho \) and 1 with probability \(\rho \).
- 6.
- 7.
If there is only one index different from zero, \(\mathsf {Supp}(\mathbf {u})\) denotes this index.
- 8.
The matrix \(\mathbf {B}\) is called a basis of \(\varLambda (\mathbf {B})\).
- 9.
Please refer to Appendix D.1 and D.2 of the full version paper for the construction of LWE and QR.
- 10.
Note that \(\left\lceil \cdot \right\rfloor _\sigma \) is defined in Sect. 4.
- 11.
Recall that we use the notation \( \mathsf {Eval \& Shrink}\) to denote the composition of algorithms \(\mathsf {Eval}\) and \(\mathsf {Shrink}\).
References
Alamati, N., Branco, P., Döttling, N., Garg, S., Hajiabadi, M., Pu, S.: Laconic private set intersection and applications. In: Nissim, K., Waters, B. (eds.) TCC 2021. LNCS, vol. 13044, pp. 94–125. Springer, Cham (2021). https://doi.org/10.1007/978-3-030-90456-2_4
Banaszczyk, W.: New bounds in some transference theorems in the geometry of numbers. Math. Ann. 296(4), 625–636 (1993). http://eudml.org/doc/165105
Boneh, D., Halevi, S., Hamburg, M., Ostrovsky, R.: Circular-secure encryption from decision Diffie-Hellman. In: Wagner, D. (ed.) CRYPTO 2008. LNCS, vol. 5157, pp. 108–125. Springer, Heidelberg (2008). https://doi.org/10.1007/978-3-540-85174-5_7
Bourse, F., Del Pino, R., Minelli, M., Wee, H.: FHE circuit privacy almost for free. In: Robshaw, M., Katz, J. (eds.) CRYPTO 2016, Part II. LNCS, vol. 9815, pp. 62–89. Springer, Heidelberg (2016). https://doi.org/10.1007/978-3-662-53008-5_3
Boyle, E., et al.: Efficient two-round OT extension and silent non-interactive secure computation. In: Cavallaro, L., Kinder, J., Wang, X., Katz, J. (eds.) ACM CCS 2019: 26th Conference on Computer and Communications Security, pp. 291–308. ACM Press, 11–15 November 2019
Boyle, E., Couteau, G., Gilboa, N., Ishai, Y., Kohl, L., Scholl, P.: Efficient pseudorandom correlation generators: silent OT extension and more. In: Boldyreva, A., Micciancio, D. (eds.) CRYPTO 2019, Part III. LNCS, vol. 11694, pp. 489–518. Springer, Cham (2019). https://doi.org/10.1007/978-3-030-26954-8_16
Boyle, E., Gilboa, N., Ishai, Y.: Breaking the circuit size barrier for secure computation under DDH. In: Robshaw, M., Katz, J. (eds.) CRYPTO 2016, Part I. LNCS, vol. 9814, pp. 509–539. Springer, Heidelberg (2016). https://doi.org/10.1007/978-3-662-53018-4_19
Boyle, E., Goldwasser, S., Ivan, I.: Functional signatures and pseudorandom functions. In: Krawczyk, H. (ed.) PKC 2014. LNCS, vol. 8383, pp. 501–519. Springer, Heidelberg (2014). https://doi.org/10.1007/978-3-642-54631-0_29
Brakerski, Z., Branco, P., Döttling, N., Garg, S., Malavolta, G.: Constant ciphertext-rate non-committing encryption from standard assumptions. In: Pass, R., Pietrzak, K. (eds.) TCC 2020, Part I. LNCS, vol. 12550, pp. 58–87. Springer, Cham (2020). https://doi.org/10.1007/978-3-030-64375-1_3
Brakerski, Z., Döttling, N., Garg, S., Malavolta, G.: Leveraging linear decryption: rate-1 fully-homomorphic encryption and time-lock puzzles. In: Hofheinz, D., Rosen, A. (eds.) TCC 2019, Part II. LNCS, vol. 11892, pp. 407–437. Springer, Cham (2019). https://doi.org/10.1007/978-3-030-36033-7_16
Brakerski, Z., Vaikuntanathan, V.: Efficient fully homomorphic encryption from (standard) LWE. In: Ostrovsky, R. (ed.) 52nd Annual Symposium on Foundations of Computer Science, pp. 97–106. IEEE Computer Society Press, Palm Springs, 22–25 October 2011
Branco, P., Döttling, N., Mateus, P.: Two-round oblivious linear evaluation from learning with errors. Cryptology ePrint Archive, Report 2020/635 (2020). https://eprint.iacr.org/2020/635
Canetti, R.: Universally composable security: a new paradigm for cryptographic protocols. In: 42nd Annual Symposium on Foundations of Computer Science, pp. 136–145. IEEE Computer Society Press, Las Vegas, 14–17 October 2001
Chase, M., et al.: Reusable non-interactive secure computation. In: Boldyreva, A., Micciancio, D. (eds.) CRYPTO 2019, Part III. LNCS, vol. 11694, pp. 462–488. Springer, Cham (2019). https://doi.org/10.1007/978-3-030-26954-8_15
Chase, M., Garg, S., Hajiabadi, M., Li, J., Miao, P.: Amortizing rate-1 OT and applications to PIR and PSI. In: Nissim, K., Waters, B. (eds.) TCC 2021. LNCS, vol. 13044, pp. 126–156. Springer, Cham (2021). https://doi.org/10.1007/978-3-030-90456-2_5
Cho, C., Döttling, N., Garg, S., Gupta, D., Miao, P., Polychroniadou, A.: Laconic oblivious transfer and its applications. In: Katz, J., Shacham, H. (eds.) CRYPTO 2017, Part II. LNCS, vol. 10402, pp. 33–65. Springer, Cham (2017). https://doi.org/10.1007/978-3-319-63715-0_2
Chor, B., Goldreich, O., Kushilevitz, E., Sudan, M.: Private information retrieval. In: 36th Annual Symposium on Foundations of Computer Science, pp. 41–50. IEEE Computer Society Press, Milwaukee, 23–25, October 1995
Döttling, N.: Low noise LPN: KDM secure public key encryption and sample amplification. In: Katz, J. (ed.) PKC 2015. LNCS, vol. 9020, pp. 604–626. Springer, Heidelberg (2015). https://doi.org/10.1007/978-3-662-46447-2_27
Döttling, N., Garg, S., Ishai, Y., Malavolta, G., Mour, T., Ostrovsky, R.: Trapdoor hash functions and their applications. In: Boldyreva, A., Micciancio, D. (eds.) CRYPTO 2019, Part III. LNCS, vol. 11694, pp. 3–32. Springer, Cham (2019). https://doi.org/10.1007/978-3-030-26954-8_1
Even, S., Goldreich, O., Lempel, A.: A randomized protocol for signing contracts. In: Chaum, D., Rivest, R.L., Sherman, A.T. (eds.) Advances in Cryptology - CRYPTO 1982, pp. 205–210. Plenum Press, New York, Santa Barbara (1982)
Garg, S., Hajiabadi, M., Ostrovsky, R.: Efficient range-trapdoor functions and applications: rate-1 OT and more. In: Pass, R., Pietrzak, K. (eds.) TCC 2020, Part I. LNCS, vol. 12550, pp. 88–116. Springer, Cham (2020). https://doi.org/10.1007/978-3-030-64375-1_4
Genise, N., Micciancio, D., Peikert, C., Walter, M.: Improved discrete gaussian and subgaussian analysis for lattice cryptography. In: Kiayias, A., Kohlweiss, M., Wallden, P., Zikas, V. (eds.) PKC 2020, Part I. LNCS, vol. 12110, pp. 623–651. Springer, Cham (2020). https://doi.org/10.1007/978-3-030-45374-9_21
Gentry, C., Halevi, S.: Compressible FHE with applications to PIR. In: Hofheinz, D., Rosen, A. (eds.) TCC 2019, Part II. LNCS, vol. 11892, pp. 438–464. Springer, Cham (2019). https://doi.org/10.1007/978-3-030-36033-7_17
Ghosh, S., Nielsen, J.B., Nilges, T.: Maliciously secure oblivious linear function evaluation with constant overhead. In: Takagi, T., Peyrin, T. (eds.) ASIACRYPT 2017, Part I. LNCS, vol. 10624, pp. 629–659. Springer, Cham (2017). https://doi.org/10.1007/978-3-319-70694-8_22
Goldreich, O., Goldwasser, S., Micali, S.: On the cryptographic applications of random functions (extended abstract). In: Blakley, G.R., Chaum, D. (eds.) CRYPTO 1984. LNCS, vol. 196, pp. 276–288. Springer, Heidelberg (1985). https://doi.org/10.1007/3-540-39568-7_22
Goldreich, O., Goldwasser, S., Micali, S.: How to construct random functions. J. ACM 33(4), 792–807 (1986). https://doi.org/10.1145/6490.6503
Goldreich, O., Micali, S., Wigderson, A.: How to play any mental game, or a completeness theorem for protocols with honest majority. In: Providing Sound Foundations for Cryptography: On the Work of Shafi Goldwasser and Silvio Micali, pp. 307–328 (2019)
Goyal, R., Vusirikala, S., Waters, B.: New constructions of hinting PRGs, OWFs with encryption, and more. In: Micciancio, D., Ristenpart, T. (eds.) CRYPTO 2020, Part I. LNCS, vol. 12170, pp. 527–558. Springer, Cham (2020). https://doi.org/10.1007/978-3-030-56784-2_18
Ishai, Y., Kilian, J., Nissim, K., Petrank, E.: Extending oblivious transfers efficiently. In: Boneh, D. (ed.) CRYPTO 2003. LNCS, vol. 2729, pp. 145–161. Springer, Heidelberg (2003). https://doi.org/10.1007/978-3-540-45146-4_9
Ishai, Y., Prabhakaran, M., Sahai, A.: Secure arithmetic computation with no honest majority. In: Reingold, O. (ed.) TCC 2009. LNCS, vol. 5444, pp. 294–314. Springer, Heidelberg (2009). https://doi.org/10.1007/978-3-642-00457-5_18
Micciancio, D., Regev, O.: Worst-case to average-case reductions based on Gaussian measures. In: 45th Annual Symposium on Foundations of Computer Science, pp. 372–381. IEEE Computer Society Press, Rome, 17–19 October 2004
Peikert, C.: An efficient and parallel gaussian sampler for lattices. In: Rabin, T. (ed.) CRYPTO 2010. LNCS, vol. 6223, pp. 80–97. Springer, Heidelberg (2010). https://doi.org/10.1007/978-3-642-14623-7_5
Quach, W., Wee, H., Wichs, D.: Laconic function evaluation and applications. In: Thorup, M. (ed.) 59th Annual Symposium on Foundations of Computer Science, pp. 859–870. IEEE Computer Society Press, Paris, 7–9 October 2018
Rabin, M.O.: How to exchange secrets with oblivious transfer. IACR Cryptol. ePrint Arch. 2005(187) (2005)
Regev, O.: On lattices, learning with errors, random linear codes, and cryptography. In: Gabow, H.N., Fagin, R. (eds.) 37th Annual ACM Symposium on Theory of Computing, pp. 84–93. ACM Press, Baltimore, 22–24 May 2005
Acknowledgment
Zvika Brakerski is supported by the Israel Science Foundation (Grant No. 3426/21), and by the European Union Horizon 2020 Research and Innovation Program via ERC Project REACT (Grant 756482) and via Project PROMETHEUS (Grant 780701).
Pedro Branco thanks the support from DP-PMI and FCT (Portugal) through the grant PD/BD/135181/2017. This work is supported by Security and Quantum Information Group of Instituto de Telecomunicações, by the Fundação para a Ciência e a Tecnologia (FCT) through national funds, by FEDER, COMPETE 2020, and by Regional Operational Program of Lisbon, under UIDB/50008/2020.
Nico Döttling and Sihang Pu were supported by the Helmholtz Association within the project “Trustworthy Federated Data Analytics” (TFDA) (funding number ZT-I- OO1 4).
Author information
Authors and Affiliations
Corresponding authors
Editor information
Editors and Affiliations
A Additional Preliminaries
A Additional Preliminaries
1.1 A.1 UC Security
In terms of security, we work in the standard UC-framework [13]. Let \(\mathcal {F}\) be a functionality, \(\pi \) a protocol that implements \(\mathcal {F}\) and \(\mathcal {E}\) be a environment, an entity that oversees the execution of the protocol in both the real and the ideal worlds. Let \(\mathsf {IDEAL}_{\mathcal {F},\mathsf {Sim},\mathcal {E}}\) be a random variable that represents the output of \(\mathcal {E}\) after the execution of \(\mathcal {F}\) with adversary \(\mathsf {Sim}\). Similarly, let \(\mathsf {REAL}_{\pi ,\mathcal {A},\mathcal {E}}\) be a random variable that represents the output of \(\mathcal {E}\) after the execution of \(\pi \) with adversary \(\mathcal {A}\).
In this work, we only consider semi-honest adversaries.
Definition 13
A protocol \(\pi \) implements \(\mathcal {F}\) if for every PPT adversary \(\mathcal {A}\) there is a PPT simulator \(\mathsf {Sim}\) such that for all PPT environments \(\mathcal {E}\), the distributions \(\mathsf {IDEAL}_{\mathcal {F},\mathsf {Sim},\mathcal {E}}\) and \( \mathsf {REAL}_{\pi ,\mathcal {A},\mathcal {E}}\) are computationally indistinguishable.
1.2 A.2 Learning Parity with Noise
The LPN assumption is closely related to the problem of decoding a random linear code. Informally, it states that it is hard to find a solution for a noisy system of linear equations over \(\mathbb {Z}_2\).
Definition 14
(LPN assumption). Let \(n,m,t\in \mathbb {N}\) such that \(n\in \mathsf {poly}(\lambda )\) and let \(\chi _{m,t}\) be uniform distribution over the set of error vectors of size m and hamming weight t. The Learning Parity with Noise (LPN) assumption \(\mathsf {LPN}(n,m,\rho )\) holds if for any PPT adversary \(\mathcal {A}\) we have that
where \(\rho =m/t\) (\(\rho \) is called the noise rate).
In this work, we assume that the noise rate \(\rho \) is \(m^{1-\varepsilon }\) for any constant \(\varepsilon >0\). The LPN assumption is believed to be hard for that noise rate (see e.g. [5] and references therein).
For other missing preliminaries please refer to the full version paper.
Rights and permissions
Copyright information
© 2022 International Association for Cryptologic Research
About this paper
Cite this paper
Brakerski, Z., Branco, P., Döttling, N., Pu, S. (2022). Batch-OT with Optimal Rate. In: Dunkelman, O., Dziembowski, S. (eds) Advances in Cryptology – EUROCRYPT 2022. EUROCRYPT 2022. Lecture Notes in Computer Science, vol 13276. Springer, Cham. https://doi.org/10.1007/978-3-031-07085-3_6
Download citation
DOI: https://doi.org/10.1007/978-3-031-07085-3_6
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-031-07084-6
Online ISBN: 978-3-031-07085-3
eBook Packages: Computer ScienceComputer Science (R0)