Skip to main content
Springer Nature Link
Log in

Optimal Verifiable Data Streaming Protocol with Data Auditing

  • Conference paper
  • First Online:
Computer Security – ESORICS 2021 (ESORICS 2021)

Part of the book series: Lecture Notes in Computer Science ((LNSC,volume 12973))

Included in the following conference series:

Abstract

As smart devices connected to networks like Internet of Things and 5G become popular, the volume of data generated over time (i.e., stream data) by them is growing rapidly. As a consequence, for these resources-limited client-side devices, it becomes very challenging to store the continuously generated stream data locally. Although the cloud storage provides a perfect solution to this problem, the data owner still needs to ensure the integrity of the outsourced stream data, since various applications built upon stream data are sensitive of both its context and order. To this end, the notion of verifiable data streaming (VDS) was proposed to effectively append and update stream data outsourced to an untrusted cloud server, and has received significant attention. However, previous VDS constructions adopt Merkle hash tree to capture the integrity of outsourced data, and thus inevitably have logarithmic costs. In this paper, we further optimize the construction of VDS in terms of communication and computation costs. Specifically, we use the digital signature scheme to ensure the integrity of outsourced stream data, and employ a recently proposed RSA accumulator (v.s. Merkle hash tree) to invalidate the corresponding signature after each data update operation. Benefited from this approach, the resulted VDS construction achieves optimal, i.e., having constant costs. Furthermore, by specifying the underly signature scheme with the BLS short signature and carefully combining it with the RSA accumulator, we finally obtain an optimal verifiable data streaming protocol with data auditing. We prove the security of the proposed VDS construction in the random oracle model.

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Log in via an institution

Subscribe and save

Springer+ Basic
CHF34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Chapter
CHF 24.95
Price includes VAT (Switzerland)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
CHF 104.00
Price excludes VAT (Switzerland)
  • Available as EPUB and PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
CHF 130.00
Price excludes VAT (Switzerland)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Purchases are for personal use only

Institutional subscriptions

Similar content being viewed by others

Notes

  1. 1.

    The verification key is updated after each data update operation.

  2. 2.

    In Sun et al.’s construction, they used the notion of adaptive trapdoor hash authentication tree. But we note that it is essentially the fully dynamic CATs constructed by Schröder and Simkin.

  3. 3.

    For different tasks (i.e. query and auditing), the corresponding proofs are also different.

  4. 4.

    We assume that each signature has a unique tag. So we can use it to identify the corresponding signature as we do in the \(\mathsf {Query}\) protocol.

  5. 5.

    Note that the value \(z^*\) is computed with the revocation list R and is independent of i, and thus can be refreshed after each update operation.

  6. 6.

    Due to limited space, here we omit how to extend our VADS protocol to support concurrent queries. In fact, it is straightforward, and just needs to create an aggregated non-membership proof for those requested data items by invoking the Algorithm 1.

References

  1. Arasu, A., et al.: STREAM: the Stanford stream data manager. In: Proceedings of the 2003 ACM SIGMOD International Conference on Management of Data, p. 665. ACM (2003)

    Google Scholar 

  2. Babcock, B., Babu, S., Datar, M., Motwani, R., Widom, J.: Models and issues in data stream systems. In: Proceedings of the Twenty-first ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, pp. 1–16. ACM (2002)

    Google Scholar 

  3. Bellare, M., Keelveedhi, S., Ristenpart, T.: Message-locked encryption and secure deduplication. In: Johansson, T., Nguyen, P.Q. (eds.) EUROCRYPT 2013. LNCS, vol. 7881, pp. 296–312. Springer, Heidelberg (2013). https://doi.org/10.1007/978-3-642-38348-9_18

    Chapter  Google Scholar 

  4. Benabbas, S., Gennaro, R., Vahlis, Y.: Verifiable delegation of computation over large datasets. In: Rogaway, P. (ed.) CRYPTO 2011. LNCS, vol. 6841, pp. 111–131. Springer, Heidelberg (2011). https://doi.org/10.1007/978-3-642-22792-9_7

    Chapter  Google Scholar 

  5. Boneh, D., Bünz, B., Fisch, B.: Batching techniques for accumulators with applications to IOPs and stateless blockchains. In: Boldyreva, A., Micciancio, D. (eds.) CRYPTO 2019. LNCS, vol. 11692, pp. 561–586. Springer, Cham (2019). https://doi.org/10.1007/978-3-030-26948-7_20

    Chapter  Google Scholar 

  6. Boneh, D., Lynn, B., Shacham, H.: Short signatures from the weil pairing. In: Boyd, C. (ed.) ASIACRYPT 2001. LNCS, vol. 2248, pp. 514–532. Springer, Heidelberg (2001). https://doi.org/10.1007/3-540-45682-1_30

    Chapter  Google Scholar 

  7. Campanelli, M., Fiore, D., Greco, N., Kolonelos, D., Nizzardo, L.: Incrementally aggregatable vector commitments and applications to verifiable decentralized storage. In: Moriai, S., Wang, H. (eds.) ASIACRYPT 2020. LNCS, vol. 12492, pp. 3–35. Springer, Cham (2020). https://doi.org/10.1007/978-3-030-64834-3_1

    Chapter  Google Scholar 

  8. Catalano, D., Fiore, D.: Vector commitments and their applications. In: Kurosawa, K., Hanaoka, G. (eds.) PKC 2013. LNCS, vol. 7778, pp. 55–72. Springer, Heidelberg (2013). https://doi.org/10.1007/978-3-642-36362-7_5

    Chapter  Google Scholar 

  9. Chen, C., Wu, H., Wang, L., Yu, C.: Practical integrity preservation for data streaming in cloud-assisted healthcare sensor systems. Comput. Netw. 129, 472–480 (2017)

    Article  Google Scholar 

  10. Chen, X., et al.: Publicly verifiable databases with all efficient updating operations. IEEE Trans. Knowl. Data Eng. (2020). https://doi.org/10.1109/TKDE.2020.2975777

  11. Chen, X., Li, J., Huang, X., Ma, J., Lou, W.: New publicly verifiable databases with efficient updates. IEEE Trans. Dependable Secure Comput. 12(5), 546–556 (2015)

    Article  Google Scholar 

  12. Cugola, G., Margara, A.: Processing flows of information: from data stream to complex event processing. ACM Comput. Surv. 44(3), 15:1–15:62 (2012)

    Google Scholar 

  13. Erway, C.C., Küpçü, A., Papamanthou, C., Tamassia, R.: Dynamic provable data possession. ACM Trans. Inf. Syst. Secur. 17(4), 15:1–15:29 (2015)

    Google Scholar 

  14. Esiner, E., Kachkeev, A., Braunfeld, S., Küpçü, A., Özkasap, Ö.: FlexDPDP: flexlist-based optimized dynamic provable data possession. ACM Trans. Storage 12(4), 23:1–23:44 (2016)

    Google Scholar 

  15. Etemad, M., Küpçü, A.: Generic dynamic data outsourcing framework for integrity verification. ACM Comput. Surv. 53(1), 8:1–8:32 (2020)

    Google Scholar 

  16. Grobauer, B., Walloschek, T., Stöcker, E.: Understanding cloud computing vulnerabilities. IEEE Secur. Priv. 9(2), 50–57 (2011)

    Article  Google Scholar 

  17. Juels, A., Kaliski Jr, B.S.: PORs: proofs of retrievability for large files. In: Proceedings of the 2007 ACM Conference on Computer and Communications Security, pp. 584–597. ACM (2007)

    Google Scholar 

  18. Krupp, J., Schröder, D., Simkin, M., Fiore, D., Ateniese, G., Nuernberger, S.: Nearly optimal verifiable data streaming. In: Cheng, C.-M., Chung, K.-M., Persiano, G., Yang, B.-Y. (eds.) PKC 2016. LNCS, vol. 9614, pp. 417–445. Springer, Heidelberg (2016). https://doi.org/10.1007/978-3-662-49384-7_16

    Chapter  Google Scholar 

  19. Lai, R.W.F., Malavolta, G.: Subvector commitments with application to succinct arguments. In: Boldyreva, A., Micciancio, D. (eds.) CRYPTO 2019. LNCS, vol. 11692, pp. 530–560. Springer, Cham (2019). https://doi.org/10.1007/978-3-030-26948-7_19

    Chapter  Google Scholar 

  20. Li, S., Zhang, Y., Xu, C., Chen, K.: Cryptoanalysis of an authenticated data structure scheme with public privacy-preserving auditing. IEEE Trans. Inf. Forensics Secur. 16, 2564–2565 (2021)

    Article  Google Scholar 

  21. Merkle, R.C.: Protocols for public key cryptosystems. In: Proceedings of the 1980 IEEE Symposium on Security and Privacy, pp. 122–134. IEEE Computer Society (1980)

    Google Scholar 

  22. Miao, M., Ma, J., Huang, X., Wang, Q.: Efficient verifiable databases with insertion/deletion operations from delegating polynomial functions. IEEE Trans. Inf. Forensics Secur. 13(2), 511–520 (2018)

    Article  Google Scholar 

  23. Papamanthou, C., Shi, E., Tamassia, R., Yi, K.: Streaming authenticated data structures. In: Johansson, T., Nguyen, P.Q. (eds.) EUROCRYPT 2013. LNCS, vol. 7881, pp. 353–370. Springer, Heidelberg (2013). https://doi.org/10.1007/978-3-642-38348-9_22

    Chapter  Google Scholar 

  24. Schröder, D., Schröder, H.: Verifiable data streaming. In: 19th ACM Conference on Computer and Communications Security (CCS’12), pp. 953–964. ACM (2012)

    Google Scholar 

  25. Schöder, D., Simkin, M.: VeriStream – a framework for verifiable data streaming. In: Böhme, R., Okamoto, T. (eds.) FC 2015. LNCS, vol. 8975, pp. 548–566. Springer, Heidelberg (2015). https://doi.org/10.1007/978-3-662-47854-7_34

    Chapter  Google Scholar 

  26. Shacham, H., Waters, B.: Compact proofs of retrievability. J. Cryptol. 26(3), 442–483 (2013). https://doi.org/10.1007/s00145-012-9129-2

    Article  MathSciNet  MATH  Google Scholar 

  27. Sun, Y., Liu, Q., Chen, X., Du, X.: An adaptive authenticated data structure with privacy-preserving for big data stream in cloud. IEEE Trans. Inf. Forensics Secur. 15, 3295–3310 (2020)

    Article  Google Scholar 

  28. Wang, F., Mickens, J., Zeldovich, N., Vaikuntanathan, V.: Sieve: cryptographically enforced access control for user data in untrusted clouds. In: 13th USENIX Symposium on Networked Systems Design and Implementation, pp. 611–626. USENIX Association (2016)

    Google Scholar 

  29. Wang, J., Chen, X., Huang, X., You, I., Xiang, Y.: Verifiable auditing for outsourced database in cloud computing. IEEE Trans. Comput. 64(11), 3293–3303 (2015)

    Article  MathSciNet  Google Scholar 

  30. Wang, Q., Wang, C., Ren, K., Lou, W., Li, J.: Enabling public auditability and data dynamics for storage security in cloud computing. IEEE Trans. Parallel Distrib. Syst. 22(5), 847–859 (2011)

    Article  Google Scholar 

  31. Xu, J., Meng, Q., Wu, J., Zheng, J.X., Zhang, X., Sharma, S.: Efficient and lightweight data streaming authentication in industrial control and automation systems. IEEE Trans. Ind. Inf. 17(6), 4279–4287 (2021)

    Article  Google Scholar 

  32. Xu, J., Wei, L., Zhang, Y., Wang, A., Zhou, F., Gao, C.: Dynamic fully homomorphic encryption-based Merkle tree for lightweight streaming authenticated data structures. J. Netw. Comput. Appl. 107, 113–124 (2018)

    Article  Google Scholar 

  33. Xue, K., Li, S., Hong, J., Xue, Y., Yu, N., Hong, P.: Two-cloud secure database for numeric-related SQL range queries with privacy preserving. IEEE Trans. Inf. Forensics Secur. 12(7), 1596–1608 (2017)

    Article  Google Scholar 

  34. Zhang, Y., Blanton, M.: Efficient dynamic provable possession of remote data via update trees. ACM Trans. Storage 12(2), 9:1–9:45 (2016)

    Google Scholar 

  35. Zhang, Y., Genkin, D., Katz, J., Papadopoulos, D., Papamanthou, C.: VSQL: verifying arbitrary SQL queries over dynamic outsourced databases. In: 2017 IEEE Symposium on Security and Privacy, pp. 863–880. IEEE Computer Society (2017)

    Google Scholar 

  36. Zhang, Z., Chen, X., Ma, J., Tao, X.: New efficient constructions of verifiable data streaming with accountability. Ann. Telecommun. 74(7–8), 483–499 (2019). https://doi.org/10.1007/s12243-018-0687-7

    Article  Google Scholar 

Download references

Acknowledgment

This work was supported by the National Nature Science Foundation of China under Grants 61960206014 and 62172434, and in part by the Project funded by China Postdoctoral Science Foundation No. 2020M673348 and No. 2021T140531.

Author information

Authors and Affiliations

  1. State Key Laboratory of Integrated Service Networks, Xidian University, Xi’an, China

    Jianghong Wei, Guohua Tian, Jun Shen & Xiaofeng Chen

  2. State Key Laboratory of Cryptology, P. O. Box 5159, Beijing, 100878, China

    Jianghong Wei & Xiaofeng Chen

  3. State Key Laboratory of Mathematical Engineering and Advanced Computing, PLA Strategic Support Force Information Engineering University, Zhengzhou, China

    Jianghong Wei

  4. School of Computing and IT, University of Wollongong, Wollongong, 2522, NSW, Australia

    Willy Susilo

Authors
  1. Jianghong Wei
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Guohua Tian
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Jun Shen
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. Xiaofeng Chen
    View author publications

    You can also search for this author in PubMed Google Scholar

  5. Willy Susilo
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Xiaofeng Chen .

Editor information

Editors and Affiliations

  1. Purdue University, West Lafayette, IN, USA

    Elisa Bertino

  2. National Research Center for Applied Cybersecurity ATHENE, Fraunhofer Institute for Secure Information Technology SIT, Darmstadt, Germany

    Haya Shulman

  3. National Research Center for Applied Cybersecurity ATHENE, Technische Universität Darmstadt, Fraunhofer Institute for Secure Information Technology SIT, Darmstadt, Germany

    Michael Waidner

Rights and permissions

Reprints and permissions

Copyright information

© 2021 Springer Nature Switzerland AG

About this paper

Check for updates. Verify currency and authenticity via CrossMark

Cite this paper

Wei, J., Tian, G., Shen, J., Chen, X., Susilo, W. (2021). Optimal Verifiable Data Streaming Protocol with Data Auditing. In: Bertino, E., Shulman, H., Waidner, M. (eds) Computer Security – ESORICS 2021. ESORICS 2021. Lecture Notes in Computer Science(), vol 12973. Springer, Cham. https://doi.org/10.1007/978-3-030-88428-4_15

Download citation

  • DOI: https://doi.org/10.1007/978-3-030-88428-4_15

  • Published:

  • Publisher Name: Springer, Cham

  • Print ISBN: 978-3-030-88427-7

  • Online ISBN: 978-3-030-88428-4

  • eBook Packages: Computer ScienceComputer Science (R0)

Publish with us

Policies and ethics

Search

Navigation

  NODES
Association 1
INTERN 2
Note 5
Project 1
Verify 1