logo

SCIENCE CHINA Information Sciences, Volume 60, Issue 5: 052101(2017) https://doi.org/10.1007/s11432-015-1037-2

A new construction on randomized message-locked encryption in the standard model via UCEs

More info
  • ReceivedMar 4, 2016
  • AcceptedApr 22, 2016
  • PublishedNov 14, 2016

Abstract

We present a new primitive of randomized message-locked encryption (MLE) in this paper and define a new security model for it. The new primitive, named message-locked encryption3 (hereafter referred as MLE3), is actually a variant of randomized message-locked encryption (Bellare et al. Eurocrypt'13). In order to prevent trivial attacks, our primitive admits a semi-trusted server, which is allowed to hold a secret key of public key encryption (PKE), to verify the correctness of a tag. The new security notion, called privacy chosen-distribution attacks3 (PRV-CDA3), requires that a ciphertext generated by encrypting an unpredictable message and another ciphertext (possible invalid) chosen randomly from a ciphertext space are indistinguishable. Compared with the priori proposed security notion, privacy chosen-distribution attacks (PRV-CDA) (Bellare et al. Eurocrypt'13), which requires that two ciphertexts generated by encrypting two unpredictable messages are indistinguishable, the security notion we propose is much stronger. Based on the new primitive, under the blackbox reductions, we put forward a novel construction which achieves both privacy chosen-distribution attacks3 (PRV-CDA3) and strong tag consistency (STC) securities in the standard model via universal computational extractors (UCEs) (Bellare et al. Crypto'13). In addition, our scheme also provides the validity-testing for ciphertext.


Funded by

National Natural Science Foundation of China(NSFC61572318)

Foundation of Sichuan Educational Committee(16ZB0140)

Natural Science Foundation of Anhui Science and Technology University(ZRC2013380)

National Natural Science Foundation of China(NSFC61502400)

National Natural Science Foundation of China(NSFC61472251)

National Natural Science Foundation of China(U1536101)

National Natural Science Foundation of China(NSFC61133014)

National Natural Science Foundation of China(NSFC61272440)

National Natural Science Foundation of China(NSFC61472114)


Acknowledgment

Acknowledgments

This work was supported by National Natural Science Foundation of China (Grant Nos. NSFC61133014, NSFC61472114, NSFC61572318, NSFC61272440, NSFC61472251, U1536101, NSFC61502400), Foundation of Sichuan Educational Committee (Grant No. 16ZB0140) and Natural Science Foundation of Anhui Science and Technology University (Grant No. ZRC2013380).


References

[1] Bellare M, Keelveedhi S, Ristenpart T. Message-locked encryption and secure deduplication. In: Advances in Cryptology--EUROCRYPT 2013. Lecture Notes in Computer Science. Berlin: Springer-Verlag, 2013. 7881: 296--312. Google Scholar

[2] Xu Z W. Cloud-sea computing systems: towards thousand-fold improvement in performance per watt for the coming zettabyte era. J Comput Sci Tech, 2014, 29: 177-181 CrossRef Google Scholar

[3] Zhang T, Ma J F, Li Q, et al. Trust-based service composition in multi-domain environments under time constraint. Sci China Inf Sci, 2014, 57: 092109-181 Google Scholar

[4] Douceur J R, Adya A, Bolosky W J, et al. Reclaiming space from duplicate files in a serverless distributed file system. In: Proceedings of the 22nd International Conference on Distributed Computing Systems, Vienna, 2002. 617--624. Google Scholar

[5] Adya A, Bolosky W, Castro M, et al. Farsite: federated, available, and reliable storage for an incompletely trusted environment. In: Proceedings of the 5th Symposium on Operating Systems Design and Implementation. New York: ACM, 2002. 1--14. Google Scholar

[6] Anderson P, Zhang L. Fast and secure laptop backups with encrypted de-duplication. In: Proceedings of the 24th International Conference on Large Installation System Administration. Berkeley: USENIX Association, 2010. 1--8. Google Scholar

[7] Houssem J, Maryline L-M. Pstore: a secure peer-to-peer backup system. In: Proceedings of the 8th International Conference on New Technologies in Distributed Systems. New York: ACM, 2008. 130--139. Google Scholar

[8] Cooley J, Taylor C, Peacock A. Abs: the apportioned backup system. Proc Csee, 2011, 31: 112-118 Google Scholar

[9] Cox L P, Murray C D, Noble B D. Pastiche: making backup cheap and easy. In: Proceedings of the 5th Symposium on Operating Systems Design and Implementation. New York: ACM, 2002. 36: 285--298. Google Scholar

[10] Killijian M-O, Courtes L, Powell D. A survey of cooperative backup mechanisms. https://hal.archives-ouvertes.fr/hal-00139690/document. 2006. Google Scholar

[11] Marques L, Costa C. Secure deduplication on mobile devices. In: Proceedings of the Workshop on Open Source and Design of Communication. New York: ACM, 2011. 19--26. Google Scholar

[12] Rahumed A, Chen H C H, Tang Y, et al. A secure cloud backup system with assured deletion and versioncontrol. In: Proceedings of the 40th International Conference on Parallel Processing Workshops, Taipei City, 2011. 160--167. Google Scholar

[13] Storer M, Greenan K, Long D, et al. Secure data deduplication. In: Proceedings of the 4th ACM International Workshop on Storage Security and Survivability. New York: ACM, 2008. 1--10. Google Scholar

[14] O'Hearn Z-W, Warner B. Tahoe: the least-authority filesystem. In: Proceedings of the 4th ACM International Workshop on Storage Security and Survivability. New York: ACM, 2008. 21--26. Google Scholar

[15] Horng G B. A new method for constructing multiple assignment schemes for generalized secret sharing. J Inf Sci Eng, 2001, 17: 959-965 Google Scholar

[16] Abadi M, Boneh D, Mironov I, et al. Message-locked encryption for lock-dependent messages. In: Advances in Cryptology--CRYPTO 2013. Lecture Notes in Computer Science. Berlin: Springer-Verlag, 2013. 8042: 374--391. Google Scholar

[17] Bellare M, Keelveedhi S. Interactive message-locked encryption and secure deduplication. In: Public-Key Cryptography--PKC 2015. Lecture Notes in Computer Science. Berlin: Springer-Verlag, 2015. 9020: 516--538. Google Scholar

[18] Canetti R, Goldreich O, Halevi S. The random oracle methodology, revisited. J ACM, 2004, 51: 557-594 CrossRef Google Scholar

[19] Bellare M, Hong T, Keelveedhi S. Instantiating random oracle via UCEs. In: Advances in Cryptology--CRYPTO 2013. Lecture Notes in Computer Science. Berlin: Springer-Verlag, 2013. 8043: 398--415. Google Scholar

[20] Brzuska C, Mittelbach A. Using indistinguishability obfuscation via uces. In: Advances in Cryptology--ASIACRYPT 2014. Lecture Notes in Computer Science. Berlin: Springer-Verlag, 2014. 8874: 122--141. Google Scholar

[21] Brzuska C, Farshim P, Mittelbach A. Indistinguishability obfuscation and uces: the case of computationally unpredictable sources. In: Advances in Cryptology--CRYPTO 2014. Lecture Notes in Computer Science. Berlin: Springer-Verlag, 2014. 8616: 188--205. Google Scholar

[22] Bellare M, Rogaway P. The security of triple encryption and a framework for code-based game-playing proofs. In: Advances in Cryptology--EUROCRYPT 2006. Lecture Notes in Computer Science. Berlin: Springer-Verlag, 2006. 4004: 409--426. Google Scholar

[23] Shacham H, Ristenpart T, Shrimpton T. Careful with composition: limitations of the indiferentiability framework. In: Advances in Cryptology--EUROCRYPT 2011. Lecture Notes in Computer Science. Berlin: Springer-Verlag, 2011. 6632: 487--506. Google Scholar

[24] Sahai A, Waters B. How to use indistinguishability obfuscation: deniable encryption, and more. In: Proceedings of the 46th Annual ACM Symposium on Theory of Computing. New York: ACM, 2014. 475--484. Google Scholar

[25] Koppula V, Lewko A B, Waters B. Indistinguishability obfuscation for turing machines with unbounded memory. In: Proceedings of the 47th Annual ACM on Symposium on Theory of Computing. New York: ACM, 2015. 419--428. Google Scholar

[26] Lynn B, Prabhakaran M, Sahai A. Positive results and techniques for obfuscation. In: Advances in Cryptology--EUROCRYPT 2004. Lecture Notes in Computer Science. Berlin: Springer-Verlag, 2004. 3027: 20--39. Google Scholar

[27] Naor M, Yung M. Public-key cryptosystems provably secure against chosen ciphertext attacks. In: Proceedings of the ACM Symposium on the Theory of Computing. New York: ACM, 1990. 427--437. Google Scholar

Copyright 2019 Science China Press Co., Ltd. 《中国科学》杂志社有限责任公司 版权所有

京ICP备18024590号-1