Amortizing rate-1 OT and applications to PIR and PSI. (English) Zbl 1511.94069
Nissim, Kobbi (ed.) et al., Theory of cryptography. 19th international conference, TCC 2021, Raleigh, NC, USA, November 8–11, 2021. Proceedings. Part III. Cham: Springer. Lect. Notes Comput. Sci. 13044, 126-156 (2021).
Summary: Recent new constructions of rate-1 OT [N. Döttling et al., Lect. Notes Comput. Sci. 11694, 3–32 (2019; Zbl 1436.94054)] have brought this primitive under the spotlight and the techniques have led to new feasibility results for private-information retrieval, and homomorphic encryption for branching programs. The receiver communication of this construction consists of a quadratic (in the sender’s input size) number of group elements for a single instance of rate-1 OT. Recently [S. Garg et al., ibid. 12550, 88–116 (2020; Zbl 1479.94176)] improved the receiver communication to a linear number of group elements for a single string-OT. However, most applications of rate-1 OT require executing it multiple times, resulting in large communication costs for the receiver.
In this work, we introduce a new technique for amortizing the cost of multiple rate-1 OTs. Specifically, based on standard pairing assumptions, we obtain a two-message rate-1 OT protocol for which the amortized cost per string-OT is asymptotically reduced to only four group elements. Our results lead to significant communication improvements in PSI and PIR, special cases of SFE for branching programs.
For the entire collection see [Zbl 1508.94004].
In this work, we introduce a new technique for amortizing the cost of multiple rate-1 OTs. Specifically, based on standard pairing assumptions, we obtain a two-message rate-1 OT protocol for which the amortized cost per string-OT is asymptotically reduced to only four group elements. Our results lead to significant communication improvements in PSI and PIR, special cases of SFE for branching programs.
- 1.
- PIR: We obtain a rate-1 PIR scheme with client communication cost of \(O(\lambda \cdot \log N)\) group elements for security parameter \(\lambda\) and database size \(N\). Notably, after a one-time setup (or one PIR instance), any following PIR instance only requires communication cost \(O(\log N)\) number of group elements.
- 2.
- PSI with unbalanced inputs: We apply our techniques to private set intersection with unbalanced set sizes (where the receiver has a smaller set) and achieve receiver communication of \(O((m+\lambda) \log N)\) group elements where \(m\), \(N\) are the sizes of the receiver and sender sets, respectively. Similarly, after a one-time setup (or one PSI instance), any following PSI instance only requires communication cost \(O(m \cdot \log N)\) number of group elements. All previous sublinear-communication non-FHE based PSI protocols for the above unbalanced setting were also based on rate-1 OT, but incurred at least \(O(\lambda^2 m \log N)\) group elements.
For the entire collection see [Zbl 1508.94004].
MSC:
| 94A60 | Cryptography |
References:
| [1] | Ateniese, G.; De Cristofaro, E.; Tsudik, G.; Catalano, D.; Fazio, N.; Gennaro, R.; Nicolosi, A., (If) size matters: size-hiding private set intersection, Public Key Cryptography - PKC 2011, 156-173 (2011), Heidelberg: Springer, Heidelberg · Zbl 1281.94012 · doi:10.1007/978-3-642-19379-8_10 |
| [2] | Aiello, B.; Ishai, Y.; Reingold, O.; Pfitzmann, B., Priced oblivious transfer: how to sell digital goods, Advances in Cryptology — EUROCRYPT 2001, 119-135 (2001), Heidelberg: Springer, Heidelberg · Zbl 0981.94042 · doi:10.1007/3-540-44987-6_8 |
| [3] | Password Monitoring - Apple Platform Security. https://support.apple.com/en-al/guide/security/sec78e79fc3b/web |
| [4] | Brakerski, Z.; Branco, P.; Döttling, N.; Garg, S.; Malavolta, G.; Pass, R.; Pietrzak, K., Constant ciphertext-rate non-committing encryption from standard assumptions, Theory of Cryptography, 58-87 (2020), Cham: Springer, Cham · Zbl 1479.94135 · doi:10.1007/978-3-030-64375-1_3 |
| [5] | Beaver, D.: Correlated pseudorandomness and the complexity of private computations. In: 28th ACM STOC, Philadelphia, PA, USA, 22-24 May 1996, pp. 479-488. ACM Press (1996) · Zbl 0917.94012 |
| [6] | Ballard, L., Green, M., de Medeiros, B., Monrose, F.: Correlation-resistant storage via keyword-searchable encryption. Cryptology ePrint Archive, Report 2005/417 (2005). https://eprint.iacr.org/2005/417 |
| [7] | Boyle, E.; Gilboa, N.; Ishai, Y.; Robshaw, M.; Katz, J., Breaking the circuit size barrier for secure computation under DDH, Advances in Cryptology - CRYPTO 2016, 509-539 (2016), Heidelberg: Springer, Heidelberg · Zbl 1384.94038 · doi:10.1007/978-3-662-53018-4_19 |
| [8] | Badrinarayanan, S.; Garg, S.; Ishai, Y.; Sahai, A.; Wadia, A.; Takagi, T.; Peyrin, T., Two-message witness indistinguishability and secure computation in the plain model from new assumptions, Advances in Cryptology - ASIACRYPT 2017, 275-303 (2017), Cham: Springer, Cham · Zbl 1417.94040 · doi:10.1007/978-3-319-70700-6_10 |
| [9] | Brakerski, Z.; Koppula, V.; Mour, T.; Micciancio, D.; Ristenpart, T., NIZK from LPN and trapdoor hash via correlation intractability for approximable relations, Advances in Cryptology - CRYPTO 2020, 738-767 (2020), Cham: Springer, Cham · Zbl 1504.94110 · doi:10.1007/978-3-030-56877-1_26 |
| [10] | Brakerski, Z.; Lombardi, A.; Segev, G.; Vaikuntanathan, V.; Nielsen, JB; Rijmen, V., Anonymous IBE, leakage resilience and circular security from new assumptions, Advances in Cryptology - EUROCRYPT 2018, 535-564 (2018), Cham: Springer, Cham · Zbl 1423.94056 · doi:10.1007/978-3-319-78381-9_20 |
| [11] | Chan, J., PACT: privacy-sensitive protocols and mechanisms for mobile contact tracing, IEEE Data Eng. Bull., 43, 2, 15-35 (2020) |
| [12] | Cho, C.; Döttling, N.; Garg, S.; Gupta, D.; Miao, P.; Polychroniadou, A.; Katz, J.; Shacham, H., Laconic oblivious transfer and its applications, Advances in Cryptology - CRYPTO 2017, 33-65 (2017), Cham: Springer, Cham · Zbl 1409.94866 · doi:10.1007/978-3-319-63715-0_2 |
| [13] | Chor, B., Gilboa, N., Naor, M.: Private information retrieval by keywords. Cryptology ePrint Archive, Report 1998/003 (1998). https://eprint.iacr.org/1998/003 |
| [14] | Chen, H., Laine, K., Rindal, P.: Fast private set intersection from homomorphic encryption. In: ACM CCS 2017, Dallas, TX, USA, 31 October-2 November 2017, pp. 1243-1255. ACM Press (2017) |
| [15] | Chase, M.; Miao, P.; Micciancio, D.; Ristenpart, T., Private set intersection in the internet setting from lightweight oblivious PRF, Advances in Cryptology - CRYPTO 2020, 34-63 (2020), Cham: Springer, Cham · Zbl 1504.94118 · doi:10.1007/978-3-030-56877-1_2 |
| [16] | Döttling, N.; Garg, S.; Katz, J.; Shacham, H., Identity-based encryption from the Diffie-Hellman assumption, Advances in Cryptology - CRYPTO 2017, 537-569 (2017), Cham: Springer, Cham · Zbl 1385.94033 · doi:10.1007/978-3-319-63688-7_18 |
| [17] | Döttling, N.; Garg, S.; Hajiabadi, M.; Masny, D.; Wichs, D.; Canteaut, A.; Ishai, Y., Two-round oblivious transfer from CDH or LPN, Advances in Cryptology - EUROCRYPT 2020, 768-797 (2020), Cham: Springer, Cham · Zbl 1492.94091 · doi:10.1007/978-3-030-45724-2_26 |
| [18] | Döttling, N.; Garg, S.; Ishai, Y.; Malavolta, G.; Mour, T.; Ostrovsky, R.; Boldyreva, A.; Micciancio, D., Trapdoor hash functions and their applications, Advances in Cryptology - CRYPTO 2019, 3-32 (2019), Cham: Springer, Cham · Zbl 1436.94054 · doi:10.1007/978-3-030-26954-8_1 |
| [19] | Even, S., Goldreich, O., Lempel, A.: A randomized protocol for signing contracts. In: CRYPTO 1982, Santa Barbara, CA, USA, pp. 205-210. Plenum Press, New York, USA (1982) · Zbl 0538.94011 |
| [20] | Garg, S.; Gay, R.; Hajiabadi, M.; Ishai, Y.; Rijmen, V., New techniques for efficient trapdoor functions and applications, Advances in Cryptology - EUROCRYPT 2019, 33-63 (2019), Cham: Springer, Cham · Zbl 1494.94039 · doi:10.1007/978-3-030-17659-4_2 |
| [21] | Garg, S.; Hajiabadi, M.; Shacham, H.; Boldyreva, A., Trapdoor functions from the computational Diffie-Hellman assumption, Advances in Cryptology - CRYPTO 2018, 362-391 (2018), Cham: Springer, Cham · Zbl 1436.94067 · doi:10.1007/978-3-319-96881-0_13 |
| [22] | Garg, S.; Hajiabadi, M.; Ostrovsky, R.; Pass, R.; Pietrzak, K., Efficient range-Trapdoor functions and applications: rate-1 OT and more, Theory of Cryptography, 88-116 (2020), Cham: Springer, Cham · Zbl 1479.94176 · doi:10.1007/978-3-030-64375-1_4 |
| [23] | Goldreich, O., Micali, S., Wigderson, A.: How to play any mental game or A completeness theorem for protocols with honest majority. In: 19th ACM STOC, New York City, NY, USA, 25-27 May, pp. 218-229. ACM Press (1987) |
| [24] | Goyal, R.; Vusirikala, S.; Waters, B.; Micciancio, D.; Ristenpart, T., New constructions of hinting prgs, owfs with encryption, and more, Advances in Cryptology - CRYPTO 2020, 527-558 (2020), Cham: Springer, Cham · Zbl 1503.94029 · doi:10.1007/978-3-030-56784-2_18 |
| [25] | Huang, Y., Evans, D., Katz, J.: Private set intersection: are garbled circuits better than custom protocols? In: NDSS 2012, San Diego, CA, USA, 5-8 February 2012. The Internet Society (2012) |
| [26] | Huberman, B.A., Franklin, M.K., Hogg, T.: Enhancing privacy and trust in electronic communities. In: Proceedings of the 1st ACM Conference on Electronic Commerce, EC 1999, Denver, CO, USA, 3-5 November 1999, pp. 78-86. ACM (1999) |
| [27] | Halevi, S.; Kalai, YT, Smooth projective hashing and two-message oblivious transfer, J. Cryptol., 25, 1, 158-193 (2012) · Zbl 1272.94033 · doi:10.1007/s00145-010-9092-8 |
| [28] | Hohenberger, S.; Koppula, V.; Waters, B.; Micciancio, D.; Ristenpart, T., Chosen ciphertext security from injective trapdoor functions, Advances in Cryptology - CRYPTO 2020, 836-866 (2020), Cham: Springer, Cham · Zbl 1504.94146 · doi:10.1007/978-3-030-56784-2_28 |
| [29] | Ion, M., et al.: On deploying secure computing: Private intersection-sum-with-cardinality. In: IEEE European Symposium on Security and Privacy, EuroS&P 2020, Genoa, Italy, 7-11 September 2020, pp. 370-389. IEEE (2020) |
| [30] | Ishai, Y.; Kilian, J.; Nissim, K.; Petrank, E.; Boneh, D., Extending oblivious transfers efficiently, Advances in Cryptology - CRYPTO 2003, 145-161 (2003), Heidelberg: Springer, Heidelberg · Zbl 1122.94422 · doi:10.1007/978-3-540-45146-4_9 |
| [31] | Ishai, Y.; Paskin, A.; Vadhan, SP, Evaluating branching programs on encrypted data, Theory of Cryptography, 575-594 (2007), Heidelberg: Springer, Heidelberg · Zbl 1156.94354 · doi:10.1007/978-3-540-70936-7_31 |
| [32] | Kolesnikov, V., Kumaresan, R., Rosulek, M., Trieu, N.: Efficient batched oblivious PRF with applications to private set intersection. In: ACM CCS 2016, Vienna, Austria, 24-28 October 2016, pp. 818-829. ACM Press (2016) |
| [33] | Kitagawa, F.; Matsuda, T.; Tanaka, K.; Boldyreva, A.; Micciancio, D., CCA security and trapdoor functions via key-dependent-message security, Advances in Cryptology - CRYPTO 2019, 33-64 (2019), Cham: Springer, Cham · Zbl 1436.94076 · doi:10.1007/978-3-030-26954-8_2 |
| [34] | Kales, D., Rechberger, C., Schneider, T., Senker, M., Weinert, C.: Mobile private contact discovery at scale. In: USENIX Security (2019) |
| [35] | Koppula, V.; Waters, B.; Boldyreva, A.; Micciancio, D., Realizing chosen ciphertext security generically in attribute-based encryption and predicate encryption, Advances in Cryptology - CRYPTO 2019, 671-700 (2019), Cham: Springer, Cham · Zbl 1509.94105 · doi:10.1007/978-3-030-26951-7_23 |
| [36] | Lepoint, T., Patel, S., Raykova, M., Seth, K., Trieu, N.: Private join and compute from PIR with default. Cryptology ePrint Archive, Report 2020/1011 (2020). https://eprint.iacr.org/2020/1011 |
| [37] | Lombardi, A.; Quach, W.; Rothblum, RD; Wichs, D.; Wu, DJ; Boldyreva, A.; Micciancio, D., New constructions of reusable designated-verifier NIZKs, Advances in Cryptology - CRYPTO 2019, 670-700 (2019), Cham: Springer, Cham · Zbl 1509.94117 · doi:10.1007/978-3-030-26954-8_22 |
| [38] | Password Monitor: Safeguarding passwords in Microsoft Edge. https://www.microsoft.com/en-us/research/blog/password-monitor-safeguarding-passwords-in-microsoft-edge/ |
| [39] | Naor, M., Pinkas, B.: Efficient oblivious transfer protocols. In: 12th SODA, Washington, DC, USA, 7-9 January 2001, pp. 448-457. ACM-SIAM (2001) · Zbl 0991.94045 |
| [40] | Pinkas, B.; Rosulek, M.; Trieu, N.; Yanai, A.; Boldyreva, A.; Micciancio, D., SpOT-light: lightweight private set intersection from sparse OT extension, Advances in Cryptology - CRYPTO 2019, 401-431 (2019), Cham: Springer, Cham · Zbl 1509.94129 · doi:10.1007/978-3-030-26954-8_13 |
| [41] | Pinkas, B.; Rosulek, M.; Trieu, N.; Yanai, A.; Canteaut, A.; Ishai, Y., PSI from PaXoS: fast, malicious private set intersection, Advances in Cryptology - EUROCRYPT 2020, 739-767 (2020), Cham: Springer, Cham · Zbl 1492.94160 · doi:10.1007/978-3-030-45724-2_25 |
| [42] | Pinkas, B., Schneider, T., Segev, G., Zohner, M.: Phasing: private set intersection using permutation-based hashing. In: USENIX Security 2015, Washington, DC, USA, 12-14 August 2015, pp. 515-530. USENIX Association (2015) |
| [43] | Pinkas, B.; Schneider, T.; Tkachenko, O.; Yanai, A.; Ishai, Y.; Rijmen, V., Efficient circuit-based psi with linear communication, Advances in Cryptology - EUROCRYPT 2019, 122-153 (2019), Cham: Springer, Cham · Zbl 1509.94130 · doi:10.1007/978-3-030-17659-4_5 |
| [44] | Pinkas, B.; Schneider, T.; Weinert, C.; Wieder, U.; Nielsen, JB; Rijmen, V., Efficient circuit-based psi via Cuckoo hashing, Advances in Cryptology - EUROCRYPT 2018, 125-157 (2018), Cham: Springer, Cham · Zbl 1415.94456 · doi:10.1007/978-3-319-78372-7_5 |
| [45] | Peikert, C.; Vaikuntanathan, V.; Waters, B.; Wagner, D., A framework for efficient and composable oblivious transfer, Advances in Cryptology - CRYPTO 2008, 554-571 (2008), Heidelberg: Springer, Heidelberg · Zbl 1183.94046 · doi:10.1007/978-3-540-85174-5_31 |
| [46] | Rabin, M.O.: How to exchange secrets with oblivious transfer. Cryptology ePrint Archive, Report 2005/187 (2005). https://eprint.iacr.org/2005/187 |
| [47] | Rindal, P., Schoppmann, P.: VOLE-PSI: fast OPRF and circuit-PSI from vector-OLE. In: International Conference on the Theory and Applications of Cryptographic Techniques, EUROCRYPT 2021. Advances in Cryptology (2021) |
| [48] | Thomas, K., et al.: Protecting accounts from credential stuffing with password breach alerting. In: USENIX Security (2019) |
| [49] | Trieu, N.; Shehata, K.; Saxena, P.; Shokri, R.; Song, D., Epione: lightweight contact tracing with strong privacy, IEEE Data Eng. Bull., 43, 2, 95-107 (2020) |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
