The DOI matches its Crossref record; 46 of the 46 references it cites were found in a registry or an index.
Verifiable Computation over Large Database with Incremental Updates
Abstract
The notion of verifiable database (VDB) enables a resource-constrained client to securely outsource a very large database to an untrusted server so that it could later retrieve a database record and update a record by assigning a new value. Also, any attempt by the server to tamper with the data will be detected by the client. When the database undergoes frequent while small modifications, the client must re-compute and update the encrypted version (ciphertext) on the server at all times. For very large data, it is extremely expensive for the resources-constrained client to perform both operations from scratch. In this paper, we formalize the notion of verifiable database with incremental updates (Inc-VDB). Besides, we propose a general Inc-VDB framework by incorporating the primitive of vector commitment and the encrypt-then-incremental MAC mode of encryption. We also present a concrete Inc-VDB scheme based on the computational Diffie-Hellman (CDH) assumption. Furthermore, we prove that our construction can achieve the desired security properties.
Overview
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Citations
Cites
Fully homomorphic encryption using ideal lattices
Gentry, C. (2009) · Proceedings of the forty-first annual ACM symposium on Theory of computing · doi:10.1145/1536414.1536440 · Cited by 6,806
The knowledge complexity of interactive proof systems
Goldwasser, S., Micali, S., & Rackoff, C. (1989) · SIAM Journal on Computing · doi:10.1137/0218012 · Cited by 3,285
Short Signatures from the Weil Pairing
Boneh, D., Lynn, B., & Shacham, H. (2001) · Lecture Notes in Computer Science · doi:10.1007/3-540-45682-1_30 · Cited by 2,993
Wallet Databases with Observers
Chaum, D., & Pedersen, T. P. (2007) · Lecture Notes in Computer Science · doi:10.1007/3-540-48071-4_7 · Cited by 1,292
CryptDB: protecting confidentiality with encrypted query processing
Popa, R. A., Redfield, C. M. S., Zeldovich, N., & Balakrishnan, H. (2011) · Proceedings of the Twenty-Third ACM Symposium on Operating Systems Principles · doi:10.1145/2043556.2043566 · Cited by 1,155
Non-interactive Verifiable Computing: Outsourcing Computation to Untrusted Workers
Gennaro, R., Gentry, C., & Parno, B. (2010) · Lecture Notes in Computer Science · doi:10.1007/978-3-642-14623-7_25 · Cited by 1,145
Implementing Gentry’s Fully-Homomorphic Encryption Scheme
Gentry, C., & Halevi, S. (2011) · Lecture Notes in Computer Science · doi:10.1007/978-3-642-20465-4_9 · Cited by 889
Authenticated Encryption: Relations among Notions and Analysis of the Generic Composition Paradigm
Bellare, M., & Namprempre, C. (2000) · Lecture Notes in Computer Science · doi:10.1007/3-540-44448-3_41 · Cited by 879
Dynamic Accumulators and Application to Efficient Revocation of Anonymous Credentials
Camenisch, J., & Lysyanskaya, A. (2002) · Lecture Notes in Computer Science · doi:10.1007/3-540-45708-9_5 · Cited by 732
Self-testing/correcting with applications to numerical problems
Blum, M., Luby, M., & Rubinfeld, R. (1993) · Journal of Computer and System Sciences · doi:10.1016/0022-0000(93)90044-w · Cited by 712
Authenticated Encryption: Relations among Notions and Analysis of the Generic Composition Paradigm
Bellare, M., & Namprempre, C. (2008) · Journal of Cryptology · doi:10.1007/s00145-008-9026-x · Cited by 652
A note on efficient zero-knowledge proofs and arguments (extended abstract)
Kilian, J. (1992) · Proceedings of the twenty-fourth annual ACM symposium on Theory of computing - STOC '92 · doi:10.1145/129712.129782 · Cited by 606
Certificate revocation and certificate update
Naor, M., & Nissim, K. (2000) · IEEE Journal on Selected Areas in Communications · doi:10.1109/49.839932 · Cited by 493
Delegating computation: interactive proofs for muggles
Goldwasser, S., Kalai, Y. T., & Rothblum, G. N. (2008) · Proceedings of the fortieth annual ACM symposium on Theory of computing · doi:10.1145/1374376.1374396 · Cited by 484
Multi-prover interactive proofs: how to remove intractability
Ben-Or, M., Goldwasser, S., Kilian, J., & Widgerson, A. (1988) · Proceedings of the twentieth annual ACM symposium on Theory of computing - STOC '88 · doi:10.1145/62212.62223 · Cited by 468
Vector Commitments and Their Applications
Catalano, D., & Fiore, D. (2013) · Lecture notes in computer science · doi:10.1007/978-3-642-36362-7_5 · Cited by 445
Accumulators from Bilinear Pairings and Applications
Nguyen, L. (2005) · Lecture Notes in Computer Science · doi:10.1007/978-3-540-30574-3_19 · Cited by 431
Verifiable Delegation of Computation over Large Datasets
Benabbas, S., Gennaro, R., & Vahlis, Y. (2011) · Lecture Notes in Computer Science · doi:10.1007/978-3-642-22792-9_7 · Cited by 379
How to Securely Outsource Cryptographic Computations
Hohenberger, S., & Lysyanskaya, A. (2005) · Lecture Notes in Computer Science · doi:10.1007/978-3-540-30576-7_15 · Cited by 361
How to Delegate and Verify in Public: Verifiable Computation from Attribute-Based Encryption
Parno, B., Raykova, M., & Vaikuntanathan, V. (2012) · Lecture Notes in Computer Science · doi:10.1007/978-3-642-28914-9_24 · Cited by 355
Incremental Cryptography: The Case of Hashing and Signing
Bellare, M., Goldreich, O., & Goldwasser, S. (2007) · Lecture Notes in Computer Science · doi:10.1007/3-540-48658-5_22 · Cited by 312
Secure and practical outsourcing of linear programming in cloud computing
Wang, C., Ren, K., & Wang, J. (2011) · 2011 Proceedings IEEE INFOCOM · doi:10.1109/infcom.2011.5935305 · Cited by 312
New Algorithms for Secure Outsourcing of Modular Exponentiations
Chen, X., Li, J., Ma, J., Tang, Q., & Lou, W. (2014) · IEEE Transactions on Parallel and Distributed Systems · doi:10.1109/tpds.2013.180 · Cited by 307
Self-citationMicali, S. (2002) · Proceedings 35th Annual Symposium on Foundations of Computer Science · doi:10.1109/sfcs.1994.365746 · Cited by 293
An Accumulator Based on Bilinear Maps and Efficient Revocation for Anonymous Credentials
Camenisch, J., Kohlweiss, M., & Soriente, C. (2009) · Lecture Notes in Computer Science · doi:10.1007/978-3-642-00468-1_27 · Cited by 288
Secure outsourcing of scientific computations
Atallah, M. J., Pantazopoulos, K. N., Rice, J. R., & Spafford, E. E. (2002) · Advances in Computers · doi:10.1016/s0065-2458(01)80019-x · Cited by 266
Securely outsourcing linear algebra computations
Atallah, M. J., & Frikken, K. B. (2010) · Proceedings of the 5th ACM Symposium on Information, Computer and Communications Security · doi:10.1145/1755688.1755695 · Cited by 263
Uncheatable Distributed Computations
Golle, P., & Mironov, I. (2001) · Lecture Notes in Computer Science · doi:10.1007/3-540-45353-9_31 · Cited by 256
A New Paradigm for Collision-Free Hashing: Incrementality at Reduced Cost
Bellare, M., & Micciancio, D. (1997) · Lecture Notes in Computer Science · doi:10.1007/3-540-69053-0_13 · Cited by 250
A General Model for Authenticated Data Structures
Martel, C., Nuckolls, G., Devanbu, P., Gertz, M., Kwong, A., & Stubblebine, S. G. (2004) · Algorithmica · doi:10.1007/s00453-003-1076-8 · Cited by 210
Verifiable delegation of computation on outsourced data
Backes, M., Fiore, D., & Reischuk, R. M. (2013) · Proceedings of the 2013 ACM SIGSAC conference on Computer & communications security - CCS '13 · doi:10.1145/2508859.2516681 · Cited by 193
Private and Cheating-Free Outsourcing of Algebraic Computations
Benjamin, D., & Atallah, M. J. (2008) · 2008 Sixth Annual Conference on Privacy, Security and Trust · doi:10.1109/pst.2008.12 · Cited by 176
Practical delegation of computation using multiple servers
Canetti, R., Riva, B., & Rothblum, G. N. (2011) · ACM SIGSAC Conference on Computer and Communications Security (CCS) · doi:10.1145/2046707.2046759 · Cited by 171
Linear zero-knowledge---a note on efficient zero-knowledge proofs and arguments
Cramer, R., & Damgård, I. (1997) · Proceedings of the twenty-ninth annual ACM symposium on Theory of computing - STOC '97 · doi:10.1145/258533.258635 · Cited by 170
Batch Verification of Short Signatures
Camenisch, J., Hohenberger, S., & Pedersen, M. Ø. (2007) · Lecture Notes in Computer Science · doi:10.1007/978-3-540-72540-4_14 · Cited by 170
Secure outsourcing of sequence comparisons
Atallah, M. J., & Li, J. (2005) · International Journal of Information Security · doi:10.1007/s10207-005-0070-3 · Cited by 163
Self-citationHarnessing the Cloud for Securely Outsourcing Large-Scale Systems of Linear Equations
Wang, C., Ren, K., Wang, J., & Wang, Q. (2012) · IEEE Transactions on Parallel and Distributed Systems · doi:10.1109/tpds.2012.206 · Cited by 153
Incremental cryptography and application to virus protection
Bellare, M., Goldreich, O., & Goldwasser, S. (1995) · ACM Symposium on Theory of Computing (STOC) · doi:10.1145/225058.225080 · Cited by 132
New Algorithms for Secure Outsourcing of Modular Exponentiations
Chen, X., Li, J., Ma, J., Tang, Q., & Lou, W. (2012) · Lecture notes in computer science · doi:10.1007/978-3-642-33167-1_31 · Cited by 123
Self-citationEfficient Fair Conditional Payments for Outsourcing Computations
Chen, X., Li, J., & Susilo, W. (2012) · IEEE Transactions on Information Forensics and Security · doi:10.1109/tifs.2012.2210880 · Cited by 119
Self-citationSecure Delegation of Elliptic-Curve Pairing
Chevallier-Mames, B., Coron, J.-S., McCullagh, N., Naccache, D., & Scott, M. (2010) · Lecture notes in computer science · doi:10.1007/978-3-642-12510-2_3 · Cited by 105
Secure and Efficient Outsourcing of Sequence Comparisons
Blanton, M., Atallah, M. J., Frikken, K. B., & Malluhi, Q. M. (2012) · Lecture notes in computer science · doi:10.1007/978-3-642-33167-1_29 · Cited by 74
Improved Efficient Arguments (Preliminary Version)
Kilian, J. (1995) · International Cryptology Conference · Cited by 56
Program result checking against adaptive programs and in cryptographic settings
Blum, M., Luby, M. G., & Rubinfeld, R. (1991) · DIMACS series in discrete mathematics and theoretical computer science · doi:10.1090/dimacs/002/06 · Cited by 36
Verifiable Computation over Large Database with Incremental Updates
Chen, X., Li, J., Weng, J., Ma, J., & Lou, W. (2014) · Lecture notes in computer science · doi:10.1007/978-3-319-11203-9_9 · Cited by 35
Self-citationImproved Conditional E-Payments
Blanton, M. (2008) · Lecture notes in computer science · doi:10.1007/978-3-540-68914-0_12 · Cited by 31
Cited by
Secure Multi-Party Computation: Theory, practice and applications
Zhao, C., Zhao, S., Zhao, M., Chen, Z., Gao, C.-Z., Li, H., & Tan, Y.-A. (2019) · Information Sciences · doi:10.1016/j.ins.2018.10.024 · Cited by 508
Blockchain based searchable encryption for electronic health record sharing
Chen, L., Lee, W.-K., Chang, C.-C., Choo, K.-K. R., & Zhang, N. (2019) · Future Generation Computer Systems · doi:10.1016/j.future.2019.01.018 · Cited by 484
Lin, C., He, D., Huang, X., Choo, K.-K. R., & Vasilakos, A. V. (2018) · Journal of Network and Computer Applications · doi:10.1016/j.jnca.2018.05.005 · Cited by 404
Bus-Trajectory-Based Street-Centric Routing for Message Delivery in Urban Vehicular Ad Hoc Networks
Sun, G., Zhang, Y., Liao, D., Yu, H., Du, X., & Guizani, M. (2018) · IEEE Transactions on Vehicular Technology · doi:10.1109/tvt.2018.2828651 · Cited by 270
Anonymous and Traceable Group Data Sharing in Cloud Computing
Shen, J., Zhou, T., Chen, X., Li, J., & Susilo, W. (2018) · IEEE Transactions on Information Forensics and Security · doi:10.1109/tifs.2017.2774439 · Cited by 253
Self-citation
Metadata
- Authors
- Chen, X., Li, J., Weng, J., Ma, J., & Lou, W.
- Venue
- IEEE Transactions on Computers
- Published
- 2016-10-01
- Volume
- 65
- Issue
- 10
- Pages
- 3184-3195
- ISSN
- 0018-9340 (ISSN-L)
- OpenAlex
- W2344670370
- Cited by
- 257
- References
- 46
- FWCI
- 47.24
- Type
- journal article
- Language
- en
- Open access
- closed
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.