Better security-efficiency trade-offs in permutation-based two-party computation. (English) Zbl 07684784
Tibouchi, Mehdi (ed.) et al., Advances in cryptology – ASIACRYPT 2021. 27th international conference on the theory and application of cryptology and information security, Singapore, December 6–10, 2021. Proceedings. Part II. Cham: Springer. Lect. Notes Comput. Sci. 13091, 275-304 (2021).
Summary: We improve upon the security of (tweakable) correlation-robust hash functions, which are essential components of garbling schemes and oblivious-transfer extension schemes. We in particular focus on constructions from permutations, and improve upon the work by Guo et al. (IEEE S&P ’20) in terms of security and efficiency.
We present a tweakable one-call construction which matches the security of the most secure two-call construction – the resulting security bound takes form \(O((p+q)q/2^n)\), where \(q\) is the number of construction evaluations and \(p\) is the number of direct adversarial queries to the underlying \(n\)-bit permutation, which is modeled as random.
Moreover, we present a new two-call construction with much better security degradation – in particular, for applications of interest, where only a constant number of evaluations per tweak are made, the security degrades as \(O((\sqrt{q} p+q^2)/2^n)\). Our security proof relies on the sum-capture theorems (Babai ’02; Steinberger ’12, Cogliati and Seurin ’18), as well as on new balls-into-bins combinatorial lemmas for limited independence ball-throws.
Of independent interest, we also provide a self-contained concrete security treatment of oblivious transfer extension.
For the entire collection see [Zbl 1510.94003].
We present a tweakable one-call construction which matches the security of the most secure two-call construction – the resulting security bound takes form \(O((p+q)q/2^n)\), where \(q\) is the number of construction evaluations and \(p\) is the number of direct adversarial queries to the underlying \(n\)-bit permutation, which is modeled as random.
Moreover, we present a new two-call construction with much better security degradation – in particular, for applications of interest, where only a constant number of evaluations per tweak are made, the security degrades as \(O((\sqrt{q} p+q^2)/2^n)\). Our security proof relies on the sum-capture theorems (Babai ’02; Steinberger ’12, Cogliati and Seurin ’18), as well as on new balls-into-bins combinatorial lemmas for limited independence ball-throws.
Of independent interest, we also provide a self-contained concrete security treatment of oblivious transfer extension.
For the entire collection see [Zbl 1510.94003].
Software:
JustGarbleReferences:
| [1] | Abdalla, M.; Benhamouda, F.; Passelègue, A.; Galbraith, SD; Moriai, S., Algebraic XOR-RKA-secure pseudorandom functions from post-zeroizing multilinear maps, Advances in Cryptology - ASIACRYPT 2019, 386-412 (2019), Cham: Springer, Cham · Zbl 1455.94098 · doi:10.1007/978-3-030-34621-8_14 |
| [2] | Gilad, A., Yehuda, L., Thomas, S., Michael, Z.: More efficient oblivious transfer and extensions for faster secure computation. In: Sadeghi, A.Z., Gligor, V.D., Yung, M., (Eds.) ACM CCS 2013, pp. 535-548. ACM Press, November 2013 |
| [3] | Babai, L.: The fourier transform and equations over finite abelian groups: An introduction to the method of trigonometric sums (lecture notes) |
| [4] | Bellare, M., Hoang, V.T., Keelveedhi, S., Rogaway, P.: Efficient garbling from a fixed-key blockcipher. In: 2013 IEEE Symposium on Security and Privacy, pp. 478-492. IEEE Computer Society Press, May 2013 |
| [5] | Bellare, M., Hoang, V.T., Rogaway, P.: Foundations of garbled circuits. In: Yu, T., Danezis, G., Gligor, V.D. (Eds.) ACM CCS 2012, pp. 784-796. ACM Press, October 2012 |
| [6] | Bellare, M.; Kohno, T.; Cachin, C.; Camenisch, JL, Hash function balance and its impact on birthday attacks, Advances in Cryptology - EUROCRYPT 2004, 401-418 (2004), Heidelberg: Springer, Heidelberg · Zbl 1122.94351 · doi:10.1007/978-3-540-24676-3_24 |
| [7] | Chen, S.; Steinberger, J.; Nguyen, PQ; Oswald, E., Tight security bounds for key-alternating ciphers, Advances in Cryptology - EUROCRYPT 2014, 327-350 (2014), Heidelberg: Springer, Heidelberg · Zbl 1317.94096 · doi:10.1007/978-3-642-55220-5_19 |
| [8] | Choi, S.G., Katz, J., Kumaresan, R., Zhou, H.S.: On the security of the “free-XOR” technique. In: Cramer, R. (ed.) TCC 2012. LNCS, vol. 7194, pp. 39-53. Springer, Heidelberg, March 2012 · Zbl 1303.94075 |
| [9] | Cogliati, B.; Seurin, Y.; Oswald, E.; Fischlin, M., On the provable security of the iterated even-mansour cipher against related-key and chosen-key attacks, Advances in Cryptology - EUROCRYPT 2015, 584-613 (2015), Heidelberg: Springer, Heidelberg · Zbl 1370.94500 · doi:10.1007/978-3-662-46800-5_23 |
| [10] | Cogliati, B.; Seurin, Y., Analysis of the single-permutation encrypted davies-meyer construction, Des. Codes Cryptogr., 86, 12, 2703-2723 (2018) · Zbl 1442.94035 · doi:10.1007/s10623-018-0470-9 |
| [11] | Even, S.; Mansour, Y., A construction of a cipher from a single pseudorandom permutation, J. Cryptol., 10, 3, 151-161 (1997) · Zbl 1053.94552 · doi:10.1007/s001459900025 |
| [12] | Farshim, P.; Procter, G.; Leander, G., The related-key security of iterated even-mansour ciphers, Fast Software Encryption, 342-363 (2015), Heidelberg: Springer, Heidelberg · Zbl 1382.94102 · doi:10.1007/978-3-662-48116-5_17 |
| [13] | Goldreich, O., Foundations of Cryptography: Basic Applications (2004), Cambridge: Cambridge University Press, Cambridge · Zbl 1179.94063 · doi:10.1017/CBO9780511721656 |
| [14] | Gueron, S.; Lindell, Y.; Nof, A.; Pinkas, B., Fast garbling of circuits under standard assumptions, J. Cryptol., 31, 3, 798-844 (2018) · Zbl 1400.94146 · doi:10.1007/s00145-017-9271-y |
| [15] | Guo, C.; Katz, J.; Wang, X.; Weng, C.; Yu, Y.; Micciancio, D.; Ristenpart, T., Better concrete security for half-gates garbling (in the multi-instance setting), Advances in Cryptology - CRYPTO 2020, 793-822 (2020), Cham: Springer, Cham · Zbl 07614588 · doi:10.1007/978-3-030-56880-1_28 |
| [16] | Guo, C., Katz, J., Wang, X., Yu, Y.: Efficient and secure multiparty computation from fixed-key block ciphers. In: 2020 IEEE Symposium on Security and Privacy, pp. 825-841. IEEE Computer Society Press, May 2020 |
| [17] | Impagliazzo, R.; Kabanets, V.; Serna, M.; Shaltiel, R.; Jansen, K.; Rolim, J., Constructive proofs of concentration bounds, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, 617-631 (2010), Heidelberg: Springer, Heidelberg · Zbl 1305.68331 · doi:10.1007/978-3-642-15369-3_46 |
| [18] | 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 |
| [19] | Keller, M.; Orsini, E.; Scholl, P.; Gennaro, R.; Robshaw, M., Actively secure ot extension with optimal overhead, Advances in Cryptology - CRYPTO 2015, 724-741 (2015), Heidelberg: Springer, Heidelberg · Zbl 1375.94138 · doi:10.1007/978-3-662-47989-6_35 |
| [20] | Krawczyk, H.; Desmedt, YG, LFSR-based hashing and authentication, Advances in Cryptology — CRYPTO ’94, 129-139 (1994), Heidelberg: Springer, Heidelberg · Zbl 0939.94567 · doi:10.1007/3-540-48658-5_15 |
| [21] | Liskov, M.; Rivest, RL; Wagner, D., Tweakable block ciphers, J. Cryptol., 24, 3, 588-613 (2011) · Zbl 1258.94040 · doi:10.1007/s00145-010-9073-y |
| [22] | Panconesi, A.; Srinivasan, A., Randomized distributed edge coloring via an extension of the chernoff-hoeffding bounds, SIAM J. Comput., 26, 2, 350-368 (1997) · Zbl 0867.05063 · doi:10.1137/S0097539793250767 |
| [23] | Patarin, J.: The “coefficients H” technique (invited talk). In: Avanzi, R.M., Keliher, L., Sica, F. (eds.) SAC 2008, volume 5381 of LNCS, pp. 328-345. Springer, Heidelberg, August 2009. doi:10.1007/978-0-387-30440-3 · Zbl 1256.94060 |
| [24] | Steinberger, J.P.: The sum-capture problem for abelian groups. arXiv preprint arXiv:1309.5582 (2013) |
| [25] | Tessaro, S.: Optimally secure block ciphers from ideal primitives. In: Iwata, T., Cheon, J.H. (eds.) ASIACRYPT 2015, Part II, volume 9453 of LNCS, pp. 437-462. Springer, Heidelberg, November/December 2015 · Zbl 1382.94165 |
| [26] | Yao, A.C.C.: How to generate and exchange secrets (extended abstract). In: 27th FOCS, pp. 162-167. IEEE Computer Society Press, October 1986 |
| [27] | Zahur, S.; Rosulek, M.; Evans, D.; Oswald, E.; Fischlin, M., Two halves make a whole, Advances in Cryptology - EUROCRYPT 2015, 220-250 (2015), Heidelberg: Springer, Heidelberg · Zbl 1371.94662 · doi:10.1007/978-3-662-46803-6_8 |
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.
