More Efficient Oblivious Transfer Extensions with Security for Malicious Adversaries

发表于 更新于 分类于

更有效的，对恶意对手有安全保障的 OT 扩展

不经意传输（OT）是密码学中最基本的基元之一，被广泛用于安全的双方和多方计算的协议中。随着安全计算变得更加实用，对实用的大规模不经意传输协议的需求也变得更加明显。不经意传输扩展是使相对较少的 "基础 OT" 能够以较低的成本被用来计算非常多的 OT 的协议。在半诚实的情况下，Ishai 等人（CRYPTO 2003）提出了一个 OT 扩展协议，其中每个 OT（基于基础 OT）的成本只是几个哈希函数操作。在恶意设置中，Nielsen 等人（CRYPTO 2012）提出了一个有效的主动对手设置的 OT 扩展协议，在随机预言机模型中是安全的。

在这项工作中，我们提出了一个针对恶意对手设置的 OT 扩展协议，该协议比以前的工作更有效，使用的通信更少。此外，我们的协议可以被证明在随机预言机模型和标准模型中都是安全的，并具有一定的相关性稳健性。鉴于 OT 在许多安全计算协议中的重要性，提高 OT 扩展的效率是使安全计算实用化的另一个重要步骤。

1 介绍

1.1 背景

Rabin [33] 提出的不经意传输（OT）是一个基本的加密协议，涉及两方，一个发送者和一个接收者。在最常用的 选 版本中 [9]，发送方有一对消息 ，接收方有一个选择位 ；在协议结束时，接收方得知 （但对 一无所知），而发送方对 一无所知。不经意传输是实现安全计算的基本工具，在姚氏协议 [35] 中起着关键的作用，在姚氏协议中，客户端的每一位输入都需要 OT，在 GMW 协议 [12] 中，布尔电路中计算函数的每个 门都需要 OT。

安全计算的协议在存在对抗性行为的情况下提供安全性。文献中已经考虑了许多对抗模型。最常见的对手是：被动或半诚实的对手，他们遵循协议规范，但试图通过检查协议抄本来学习更多允许的内容；主动或恶意的对手，他们运行任何任意的策略，试图破坏协议。在这两种情况下，协议的安全性保证了对手在其合法输出之外没有学到任何东西。另一个概念是在存在隐蔽对手的情况下的安全性；在这种情况下，对手可以遵循任何任意的策略，但如果它试图作弊，保证会有很大的概率被抓住。设计高效协议的最终目标是构建对强大（主动或隐蔽）对手安全的协议，同时与被动变体相比，增加很少的开销。在我们的论文中，我们主要关注主动对手的情况，但也提供了一个隐蔽安全的变体。

OT 扩展：正如我们所提到的，OT 在安全计算的协议中被广泛地使用。在许多情况下，这意味着必须运行几百万次的不经意传输，这可能变得过于昂贵。具体来说，[31] 的最先进的协议在活跃对手存在的情况下实现 OT 的安全，在标准 PC 上每秒可实现约 350 个随机 OT。然而，以这种速度实现一百万个 OT 将需要超过 45 分钟。为了解决这个问题，可以使用 OT 扩展 [4]。OT 扩展协议的工作方式是根据安全参数运行少量的 "基础 OT"（例如，几百个），这些 OT 被用作基础，仅通过使用廉价的对称加密操作获得许多 OT。这在概念上类似于公钥加密，即不使用 RSA 对大的信息进行加密，因为 RSA 太昂贵了，而是使用混合加密方案，这样 RSA 计算只用来加密一个对称密钥，然后用它来加密大的信息。这样的 OT 扩展可以以非凡的效率实现；具体来说，[16] 的协议对于被动对手来说，每个 OT 只需要三次哈希函数计算（超出初始的基数 OT）。在 [1] 中，通过应用额外的算法和密码学优化，被动对手的 OT 扩展成本非常低，基本上通信是瓶颈。具体来说，随机输入的 个 OT（这对许多应用来说已经足够了）可以在 4 个线程的局域网上仅用 2.62 秒进行 [1]。

对于主动的对手，OT 扩展的成本要高一些。在这项工作之前，已知的对主动对手具有安全性的 OT 扩展的最佳协议是由 [30] 介绍的。该协议的计算成本是由于获得安全所需的基础 OT 的数量、扩展中每个 OT 所需的对称操作（如哈希函数计算）的数量以及带宽。相对于 [16] 的被动 OT 扩展，[30] 的运行时间大约是花在基础 OT 上的 4 倍，扩展中每个 OT 的成本是 1.7 倍，而通信是 2.7 倍。渐进地，关于基础 OT 的数量，对于安全参数 （例如 ），在被动情况下只需运行 个基础 OT。相比之下，[30] 需要 个基础 OT。

恶意敌手模型的 OT 的应用：最突出的是，OT 在当今最有效的安全计算协议中被大量使用，这些协议允许两方或多方在其隐私输入上安全地评估一个以布尔电路表示的函数。例子包括姚氏基于混淆电路的方法，如 [10,11,14,19,22,24,25,32,34]，其中每个输入都需要 OT，或者 Tiny-OT [21,30] 和 MiniMac 协议 [5,6]，其中每个 门都需要 OT。其他应用包括纯粹基于 OT 的 [7] 隐私集合求交协议，以及 [17] 基于 Yao 的零知识协议，该协议允许一方以零知识证明以布尔电路表示的谓词，并且每一位证人需要一个 OT。

在上述许多应用中，需要的不经意转移的数量可能是巨大的。例如，对于许多有实际意义的应用，[5-7,21,30] 的两方和多方协议可能需要几亿个 OT，使 OT 的成本成为协议的瓶颈。具体来说，目前在恶意设置中的安全计算的实现，AES 电路需要大约 个 OT，PSI 电路（Sort-Compare-Shuffle）需要大约 个 OT，进一步细节见完整版 [2]。因此，改进的 OT 扩展立即产生更快的安全计算的两方和多方协议。

1.2 我们的贡献

在本文中，我们提出了一个新的 OT 扩展协议，在恶意对手存在的情况下具有安全性，它超过了现有的最有效的协议 [30]。我们遵循先前工作 [1,11] 的见解，表明有效的 OT 扩展的瓶颈是通信，并专注于以稍微增加的计算为代价减少通信。此外，我们的协议可以用不同的参数进行实例化，使我们能够对通信和计算进行权衡。这一点很重要，因为在局域网上运行时，计算时间比在广域网上运行时更重要，因为广域网上的通信成本占主导地位。我们实现并比较了我们的协议与 [16] 的半诚实协议（有 [1,18] 的优化）和 [30] 的恶意协议（有 [11] 的优化）。从表 1 给出的结果总结中可以看出，我们的主动安全协议比之前最快的 [30] 协议表现得更好，运行成本不到 [30] 的基础 OT 的 60%，扩展中每个 OT 成本的 70%，以及本地设置中通信的 55%。由于较低的通信量，我们的协议在云环境（美东和欧洲之间，因此有较高的延迟）中比 [30] 有更大的改进，大约是基础 OTs 的 45% 的时间和扩展中每个 OT 的 55% 的时间。

将我们的协议与 [16] 的被动 OT 扩展相比较，我们的主动安全协议在本地（局域网）设置中，基础 OT 的运行时间只增加了 133%，扩展中的每个 OT 的运行时间增加了 20%，而通信时间增加了 50%。在云环境中，扩展中的每个 OT 的成本比 [16] 多 63%（而 [30] 则多 293%）。最后，我们在获得隐蔽安全的同时，只比被动安全的成本略高（在本地设置中，每个扩展中的 OT 只多 10%，在云设置中多 30%）。我们的协议将获得恶意安全所需的基础 OT 的数量从 [30] 的 减少到 ，其中 是统计安全参数（例如， ）， 是计算和通信之间的交易参数。具体来说，对于 位的安全性，我们的协议在本地将基础 OT 的数量从 个减少到 个，在云环境中减少到 个。

除了更有效之外，我们还可以用相关稳健性的版本证明我们协议的变体的安全性（其中秘密值的选择具有高的最小熵，但不一定是均匀的），并且不需要随机预言机（见 §3.3）。相比之下，[30] 在随机预言机模型中被证明是安全的。我们的实现在 http://encrypto.de/code/OTExtension，并被集成到 SCAPI 库 [8]：https://github.com/cryptobiu/scapi。

1.3 相关工作

2 预备工作

2.1 记号

2.2 不经意传输

2.3 OT 扩展

2.4 [16] 中的恶性安全

3 我们的协议

3.1 我们协议的安全性

3.2 减少检查的次数

3.3 相关的稳健性而不是一个随机预言机

3.4 实现隐蔽性安全

4 效果评估

4.1 实现

4.2 参数评估

4.3 与相关工作的比较

参考文献

  1. Asharov, G., Lindell, Y., Schneider, T., Zohner, M.: More efficient oblivious transfer and extensions for faster secure computation. In: ACM Computer and Communications Security (CCS 2013), pp. 535–548. ACM (2013). Code: http://encrypto. de/code/OTExtension

  2. Asharov, G., Lindell, Y., Schneider, T., Zohner, M.: More efficient oblivious transfer extensions with security for malicious adversaries (full version). IACR Cryptology ePrint Archive 2015, 061 (2015). Online: http://eprint.iacr.org/2015/061

  3. Aumann, Y., Lindell, Y.: Security against covert adversaries: Efficient protocols for realistic adversaries. Journal of Cryptology 23(2), 281–343 (2010)

  4. Beaver, D.: Correlated pseudorandomness and the complexity of private computations. In: Symposium on the Theory of Computing (STOC 1996), pp. 479–488. ACM (1996)

  5. Damg ̊ard, I., Lauritsen, R., Toft, T.: An empirical study and some improvements of the MiniMac protocol for secure computation. In: Abdalla, M., De Prisco, R. (eds.) SCN 2014. LNCS, vol. 8642, pp. 398–415. Springer, Heidelberg (2014)

  6. Damg ̊ard, I., Zakarias, S.: Constant-overhead secure computation of Boolean circuits using preprocessing. In: Sahai, A. (ed.) TCC 2013. LNCS, vol. 7785, pp. 621–641. Springer, Heidelberg (2013)

  7. Dong, C., Chen, L., Wen, Z.: When private set intersection meets big data: An efficient and scalable protocol. In: ACM Computer and Communications Security (CCS 2013), pp. 789–800. ACM (2013)

  8. Ejgenberg, Y., Farbstein, M., Levy, M., Lindell, Y.: SCAPI: the secure computation application programming interface. IACR Cryptology ePrint Archive 2012, 629 (2012). Online: http://eprint.iacr.org/2012/629

  9. Even, S., Goldreich, O., Lempel, A.: A randomized protocol for signing contracts. Communications of the ACM 28(6), 637–647 (1985)

  10. Frederiksen, T.K., Jakobsen, T.P., Nielsen, J.B.: Faster maliciously secure twoparty computation using the GPU. In: Abdalla, M., De Prisco, R. (eds.) SCN 2014. LNCS, vol. 8642, pp. 358–379. Springer, Heidelberg (2014)

  11. Frederiksen, T.K., Nielsen, J.B.: Fast and maliciously secure two-party computation using the GPU. In: Jacobson, M., Locasto, M., Mohassel, P., Safavi-Naini, R. (eds.) ACNS 2013. LNCS, vol. 7954, pp. 339–356. Springer, Heidelberg (2013)

  12. Goldreich, O., Micali, S., Wigderson, A.: How to play any mental game or a completeness theorem for protocols with honest majority. In: Symposium on Theory of Computing (STOC 1987), pp. 218–229. ACM (1987)

  13. Harnik, D., Ishai, Y., Kushilevitz, E., Nielsen, J.B.: OT-combiners via secure computation. In: Canetti, R. (ed.) TCC 2008. LNCS, vol. 4948, pp. 393–411. Springer, Heidelberg (2008)

  14. Huang, Y., Katz, J., Kolesnikov, V., Kumaresan, R., Malozemoff, A.J.: Amortizing garbled circuits. In: Garay, J.A., Gennaro, R. (eds.) CRYPTO 2014, Part II. LNCS, vol. 8617, pp. 458–475. Springer, Heidelberg (2014)

  15. Impagliazzo, R., Rudich, S.: Limits on the provable consequences of one-way permutations. In: Goldwasser, S. (ed.) CRYPTO 1988. LNCS, vol. 403, pp. 8–26. Springer, Heidelberg (1990)

  16. 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)

  17. Jawurek, M., Kerschbaum, F., Orlandi, C.: Zero-knowledge using garbled circuits: How to prove non-algebraic statements efficiently. In: ACM Computer and Communications Security (CCS 2013), pp. 955–966. ACM (2013)

  18. Kolesnikov, V., Kumaresan, R.: Improved OT extension for transferring short secrets. In: Canetti, R., Garay, J.A. (eds.) CRYPTO 2013, Part II. LNCS, vol. 8043, pp. 54–70. Springer, Heidelberg (2013)

  19. Kreuter, B., Shelat, A., Shen, C.: Billion-gate secure computation with malicious adversaries. In: USENIX Security Symposium 2012, pp. 285–300. USENIX (2012)

  20. Larraia, E.: Extending oblivious transfer efficiently, or - how to get active security with constant cryptographic overhead. In: Aranha, D.F., Menezes, A. (eds.) LATINCRYPT 2014. LNCS, vol. 8895, pp. 336–384. Springer, Heidelberg (2015). Online: http://eprint.iacr.org/2014/692

  21. Larraia, E., Orsini, E., Smart, N.P.: Dishonest majority multi-party computation for binary circuits. In: Garay, J.A., Gennaro, R. (eds.) CRYPTO 2014, Part II. LNCS, vol. 8617, pp. 495–512. Springer, Heidelberg (2014)

  22. Lindell, Y., Pinkas, B.: An efficient protocol for secure two-party computation in the presence of malicious adversaries. In: Naor, M. (ed.) EUROCRYPT 2007. LNCS, vol. 4515, pp. 52–78. Springer, Heidelberg (2007)

  23. Lindell, Y., Pinkas, B.: Secure two-party computation via cut-and-choose oblivious transfer. In: Ishai, Y. (ed.) TCC 2011. LNCS, vol. 6597, pp. 329–346. Springer, Heidelberg (2011)

  24. Lindell, Y., Pinkas, B., Smart, N.P.: Implementing two-party computation efficiently with security against malicious adversaries. In: Ostrovsky, R., De Prisco, R., Visconti, I. (eds.) SCN 2008. LNCS, vol. 5229, pp. 2–20. Springer, Heidelberg (2008)

  25. Lindell, Y., Riva, B.: Cut-and-choose Yao-based secure computation in the online/offline and batch settings. In: Garay, J.A., Gennaro, R. (eds.) CRYPTO 2014, Part II. LNCS, vol. 8617, pp. 476–494. Springer, Heidelberg (2014)

  26. Lindell, Y., Zarosim, H.: On the feasibility of extending oblivious transfer. In: Sahai, A. (ed.) TCC 2013. LNCS, vol. 7785, pp. 519–538. Springer, Heidelberg (2013)

  27. Lov ́asz, L., Plummer, M.: Matching Theory. Akad ́emiai Kiad ́o, Budapest (1986), also published as, Vol. 121 of the North-Holland Mathematics Studies, NorthHolland Publishing, Amsterdam

  28. Naor, M., Pinkas, B.: Efficient oblivious transfer protocols. In: Symposium on Discrete Algorithms (SODA 2001), pp. 448–457. ACM/SIAM (2001)

  29. Nielsen, J.B.: Extending oblivious transfers efficiently - how to get robustness almost for free. IACR Cryptology ePrint Archive 2007, 215 (2007). Online: http:// eprint.iacr.org/2007/215

  30. Nielsen, J.B., Nordholt, P.S., Orlandi, C., Burra, S.S.: A new approach to practical active-secure two-party computation. In: Safavi-Naini, R., Canetti, R. (eds.) CRYPTO 2012. LNCS, vol. 7417, pp. 681–700. Springer, Heidelberg (2012)

  31. Peikert, C., Vaikuntanathan, V., Waters, B.: A framework for efficient and composable oblivious transfer. In: Wagner, D. (ed.) CRYPTO 2008. LNCS, vol. 5157, pp. 554–571. Springer, Heidelberg (2008)

  32. Pinkas, B., Schneider, T., Smart, N.P., Williams, S.C.: Secure two-party computation is practical. In: Matsui, M. (ed.) ASIACRYPT 2009. LNCS, vol. 5912, pp. 250–267. Springer, Heidelberg (2009)

  33. Rabin, M.O.: How to exchange secrets with oblivious transfer, TR-81 edn. Aiken Computation Lab, Harvard University (1981)

  34. Shelat, A., Shen, C.H.: Fast two-party secure computation with minimal assumptions. In: ACM Computer and Communications Security (CCS 2013), pp. 523–534. ACM (2013)

  35. Yao, A.C.: How to generate and exchange secrets. In: Foundations of Computer Science (FOCS 1986), pp. 162–167. IEEE (1986)

A 实施细节

A.1 架构

A.2 3 个步骤的 OT 扩展

A.3 成对比较协议的优点

B [30] 的主动安全 OT 扩展