New Realizations of Somewhere Statistically Binding Hashing and Positional Accumulators

详细信息    查看全文

• 刊名：Lecture Notes in Computer Science
• 出版年：2015
• 出版时间：2015
• 年：2015
• 卷：9452
• 期：1
• 页码：121-145
• 全文大小：389 KB
• 参考文献：[BdM93]Benaloh, J.C., de Mare, M.: One-way accumulators: a decentralized alternative to digital signatures. In: Helleseth, T. (ed.) EUROCRYPT 1993. LNCS, vol. 765, pp. 274–285. Springer, Heidelberg (1994)CrossRef
  [BGI+12]Barak, B., Goldreich, O., Impagliazzo, R., Rudich, S., Sahai, A., Vadhan, S.P., Yang, K.: On the (im)possibility of obfuscating programs. J. ACM 59(2), 6 (2012)MathSciNet CrossRef MATH
  [BHK11]Braverman, M., Hassidim, A., Kalai, Y.T.: Leaky pseudo-entropy functions. In: Proceedings of the Innovations in Computer Science - ICS 2010, Tsinghua University, Beijing, China, 7–9 January 2011, pp. 353–366 (2011)
  [CCC+15]Chen, Y.C., Chow, S.S., Chung, K.M., Lai, R.W., Lin, W.K., Zhou, H.S.: Computation-trace indistinguishability obfuscation and its applications. Cryptology ePrint Archive, Report 2015/406 (2015). http://​eprint.​iacr.​org/​
  [CH15]Canetti, R., Holmgren, J.: Fully succinct garbled RAM. Cryptology ePrint Archive, Report 2015/388 (2015). http://​eprint.​iacr.​org/​
  [CMS99]Cachin, C., Micali, S., Stadler, M.A.: Computationally private information retrieval with polylogarithmic communication. In: Stern, J. (ed.) EUROCRYPT 1999. LNCS, vol. 1592, p. 402. Springer, Heidelberg (1999)CrossRef
  [DJ01]Damgård, I., Jurik, M.: A generalisation, a simplification and some applications of Paillier’s probabilistic public-key system. In: Kim, K. (ed.) PKC 2001. LNCS, vol. 1992, pp. 119–136. Springer, Heidelberg (2001)CrossRef
  [GGH+13]Garg, S., Gentry, C., Halevi, S., Raykova, M., Sahai, A., Waters, B.: Candidate indistinguishability obfuscation and functional encryption for all circuits. In: FOCS (2013)
  [HW15]Hubacek, P., Wichs, D.: On the communication complexity of secure function evaluation with long output. In: Proceedings of the 2015 Conference on Innovations in Theoretical Computer Science, ITCS 2015, Rehovot, Israel, 11–13 January 2015, pp. 163–172 (2015)
  [KLW15]Koppula, V., Lewko, A.B., Waters, B.: Indistinguishability obfuscation for turing machines with unbounded memory. In: STOC (2015)
  [KOS10]Kiltz, E., O’Neill, A., Smith, A.: Instantiability of RSA-OAEP under chosen-plaintext attack. In: Rabin, T. (ed.) CRYPTO 2010. LNCS, vol. 6223, pp. 295–313. Springer, Heidelberg (2010)CrossRef
  [Lip05]Lipmaa, H.: An oblivious transfer protocol with log-squared communication. In: Zhou, J., López, J., Deng, R.H., Bao, F. (eds.) ISC 2005. LNCS, vol. 3650, pp. 314–328. Springer, Heidelberg (2005)CrossRef
  [NS12]Naor, M., Segev, G.: Public-key cryptosystems resilient to key leakage. SIAM J. Comput. 41(4), 772–814 (2012)MathSciNet CrossRef MATH
  [Pai99]Paillier, P.: Public-key cryptosystems based on composite degree residuosity classes. In: Stern, J. (ed.) EUROCRYPT 1999. LNCS, vol. 1592, pp. 223–238. Springer, Heidelberg (1999)CrossRef
  [PW08]Peikert, C., Waters, B.: Lossy trapdoor functions and their applications. In: Proceedings of the 40th Annual ACM Symposium on Theory of Computing, Victoria, British Columbia, Canada, 17–20 May 2008, pp. 187–196 (2008)
  [SW14]Sahai, A., Waters, B.: How to use indistinguishability obfuscation: deniable encryption, and more. In: STOC, pp. 475–484 (2014)
  [Zha14]Zhandry, M.: Adaptively secure broadcast encryption with small system parameters. In: IACR Cryptology ePrint Archive 2014, p. 757 (2014)
  
• 作者单位：Tatsuaki Okamoto (15)
  Krzysztof Pietrzak (16)
  Brent Waters (17)
  Daniel Wichs (18)
  
  15. NTT Laboratories, Tokyo, Japan
  16. IST Austria, Klosterneuburg, Austria
  17. UT Austin, Austin, USA
  18. Northeastern University, Boston, USA
  
• 丛书名：Advances in Cryptology -- ASIACRYPT 2015
• ISBN：978-3-662-48797-6
• 刊物类别：Computer Science
• 刊物主题：Artificial Intelligence and Robotics
  Computer Communication Networks
  Software Engineering
  Data Encryption
  Database Management
  Computation by Abstract Devices
  Algorithm Analysis and Problem Complexity
  
• 出版者：Springer Berlin / Heidelberg
• ISSN：1611-3349

文摘

A somewhere statistically binding (SSB) hash, introduced by Hubáček and Wichs (ITCS ’15), can be used to hash a long string x to a short digest \(y = H_{\mathsf {hk}}(x)\) using a public hashing-key \(\mathsf {hk}\). Furthermore, there is a way to set up the hash key \(\mathsf {hk}\) to make it statistically binding on some arbitrary hidden position i, meaning that: (1) the digest y completely determines the i’th bit (or symbol) of x so that all pre-images of y have the same value in the i’th position, (2) it is computationally infeasible to distinguish the position i on which \(\mathsf {hk}\) is statistically binding from any other position \(i'\). Lastly, the hash should have a local opening property analogous to Merkle-Tree hashing, meaning that given x and \(y = H_{\mathsf {hk}}(x)\) it should be possible to create a short proof \(\pi \) that certifies the value of the i’th bit (or symbol) of x without having to provide the entire input x. A similar primitive called a positional accumulator, introduced by Koppula, Lewko and Waters (STOC ’15) further supports dynamic updates of the hashed value. These tools, which are interesting in their own right, also serve as one of the main technical components in several recent works building advanced applications from indistinguishability obfuscation (iO).