Efficient, Oblivious Data Structures for MPC

详细信息    查看全文

• 作者：Marcel Keller (17)
  Peter Scholl (17)
  
• 关键词：Multiparty computation ; data structures ; oblivious RAM ; shortest path algorithm
• 刊名：Lecture Notes in Computer Science
• 出版年：2014
• 出版时间：2014
• 年：2014
• 卷：8874
• 期：1
• 页码：506-525
• 全文大小：319 KB
• 参考文献：1. Aliasgari, M., Blanton, M., Zhang, Y., Steele, A.: Secure computation on floating point numbers. In: NDSS. The Internet Society (2013)
  2. Aly, A., Cuvelier, E., Mawet, S., Pereira, O., Van Vyve, M.: Securely solving simple combinatorial graph problems. In: Sadeghi, A.-R. (ed.) FC 2013. LNCS, vol.?7859, pp. 239-57. Springer, Heidelberg (2013) CrossRef
  3. Blanton, M., Steele, A., Aliasgari, M.: Data-oblivious graph algorithms for secure computation and outsourcing. In: Chen, K., Xie, Q., Qiu, W., Li, N., Tzeng, W.G. (eds.) ASIACCS, pp. 207-18. ACM (2013)
  4. Brickell, J., Shmatikov, V.: Privacy-preserving graph algorithms in the semi-honest model. In: Roy, B.K. (ed.) ASIACRYPT 2005. LNCS, vol.?3788, pp. 236-52. Springer, Heidelberg (2005) CrossRef
  5. Catrina, O., de Hoogh, S.: Improved primitives for secure multiparty integer computation. In: Garay, J.A., De Prisco, R. (eds.) SCN 2010. LNCS, vol.?6280, pp. 182-99. Springer, Heidelberg (2010) CrossRef
  6. Cormen, T.H., Leiserson, C.E., Rivest, R.L., Stein, C.: Introduction to Algorithms, 2nd edn. The MIT Press and McGraw-Hill Book Company (2001)
  7. Damg?rd, I., Fitzi, M., Kiltz, E., Nielsen, J.B., Toft, T.: Unconditionally secure constant-rounds multi-party computation for equality, comparison, bits and exponentiation. In: Halevi, S., Rabin, T. (eds.) TCC 2006. LNCS, vol.?3876, pp. 285-04. Springer, Heidelberg (2006) CrossRef
  8. Damg?rd, I., Keller, M., Larraia, E., Miles, C., Smart, N.P.: Implementing AES via an actively/covertly secure dishonest-majority MPC protocol. In: Visconti, I., De Prisco, R. (eds.) SCN 2012. LNCS, vol.?7485, pp. 241-63. Springer, Heidelberg (2012) CrossRef
  9. Damg?rd, I., Keller, M., Larraia, E., Pastro, V., Scholl, P., Smart, N.P.: Practical covertly secure MPC for dishonest majority -or: Breaking the SPDZ limits. In: Crampton, J., Jajodia, S., Mayes, K. (eds.) ESORICS 2013. LNCS, vol.?8134, pp. 1-8. Springer, Heidelberg (2013) CrossRef
  10. Damg?rd, I., Meldgaard, S., Nielsen, J.B.: Perfectly secure oblivious RAM without random oracles. In: Ishai, Y. (ed.) TCC 2011. LNCS, vol.?6597, pp. 144-63. Springer, Heidelberg (2011) CrossRef
  11. Damg?rd, I., Pastro, V., Smart, N.P., Zakarias, S.: Multiparty computation from somewhat homomorphic encryption. In: Safavi-Naini, R., Canetti, R. (eds.) CRYPTO 2012. LNCS, vol.?7417, pp. 643-62. Springer, Heidelberg (2012) CrossRef
  12. Franklin, M.K., Gondree, M., Mohassel, P.: Improved efficiency for private stable matching. In: Abe, M. (ed.) CT-RSA 2007. LNCS, vol.?4377, pp. 163-77. Springer, Heidelberg (2006) CrossRef
  13. Gentry, C., Halevi, S., Smart, N.P.: Fully homomorphic encryption with polylog overhead. In: Pointcheval, D., Johansson, T. (eds.) EUROCRYPT 2012. LNCS, vol.?7237, pp. 465-82. Springer, Heidelberg (2012) CrossRef
  14. Gentry, C., Goldman, K.A., Halevi, S., Julta, C., Raykova, M., Wichs, D.: Optimizing ORAM and using it efficiently for secure computation. In: De Cristofaro, E., Wright, M. (eds.) PETS 2013. LNCS, vol.?7981, pp. 1-8. Springer, Heidelberg (2013) CrossRef
  15. Gentry, C., Halevi, S., Lu, S., Ostrovsky, R., Raykova, M., Wichs, D.: Garbled RAM revisited. In: Nguyen, P.Q., Oswald, E. (eds.) EUROCRYPT 2014. LNCS, vol.?8441, pp. 405-22. Springer, Heidelberg (2014) CrossRef
  16. Gordon, S.D., Katz, J., Kolesnikov, V., Krell, F., Malkin, T., Raykova, M., Vahlis, Y.: Secure two-party computation in sublinear (amortized) time. In: Yu, T., Danezis, G.
• 作者单位：Marcel Keller (17)
  Peter Scholl (17)
  
  17. Department of Computer Science, University of Bristol, UK
  
• ISSN：1611-3349

文摘

We present oblivious implementations of several data structures for secure multiparty computation (MPC) such as arrays, dictionaries, and priority queues. The resulting oblivious data structures have only polylogarithmic overhead compared with their classical counterparts. To achieve this, we give secure multiparty protocols for the ORAM of Shi et al. (Asiacrypt?-1) and the Path ORAM scheme of Stefanov et al. (CCS?-3), and we compare the resulting implementations. We subsequently use our oblivious priority queue for secure computation of Dijkstra’s shortest path algorithm on general graphs, where the graph structure is secret. To the best of our knowledge, this is the first implementation of a non-trivial graph algorithm in multiparty computation with polylogarithmic overhead. We implemented and benchmarked most of our protocols using the SPDZ protocol of Damg?rd et al. (Crypto?-2), which works in the preprocessing model and ensures active security against an adversary corrupting all but one players. For two parties, the online access time for an oblivious array of size one?million is under 100 ms.