The DOI matches its Crossref record; 49 of the 49 references it cites were found in a registry or an index.
New Algorithms for Secure Outsourcing of Modular Exponentiations
Open accessAbstract
With the rapid development of cloud services, the techniques for securely outsourcing the prohibitively expensive computations to untrusted servers are getting more and more attention in the scientific community. Exponentiations modulo a large prime have been considered the most expensive operations in discrete-logarithm-based cryptographic protocols, and they may be burdensome for the resource-limited devices such as RFID tags or smartcards. Therefore, it is important to present an efficient method to securely outsource such operations to (untrusted) cloud servers. In this paper, we propose a new secure outsourcing algorithm for (variable-exponent, variable-base) exponentiation modulo a prime in the two untrusted program model. Compared with the state-of-the-art algorithm, the proposed algorithm is superior in both efficiency and checkability. Based on this algorithm, we show how to achieve outsource-secure Cramer-Shoup encryptions and Schnorr signatures. We then propose the first efficient outsource-secure algorithm for simultaneous modular exponentiations. Finally, we provide the experimental evaluation that demonstrates the efficiency and effectiveness of the proposed outsourcing algorithms and schemes.
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
Handbook of applied cryptography
(1997) · Choice Reviews Online · doi:10.5860/choice.34-4512 · Cited by 10,357
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
Handbook of Applied Cryptography
Menezes, A. J., van Oorschot, P. C., & Vanstone, S. A. (2018) · CRC Press eBooks · doi:10.1201/9781439821916 · Cited by 2,896
Efficient signature generation by smart cards
Schnorr, C. P. (1991) · Journal of Cryptology · doi:10.1007/bf00196725 · Cited by 2,787
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
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
Cramer, R., & Shoup, V. (2003) · SIAM Journal on Computing · doi:10.1137/s0097539702403773 · Cited by 978
Minimum disclosure proofs of knowledge
Brassard, G., Chaum, D., & Crépeau, C. (1988) · Journal of Computer and System Sciences · doi:10.1016/0022-0000(88)90005-0 · Cited by 959
Outsourcing the decryption of abe ciphertexts
Green, M., Hohenberger, S., & Waters, B. R. (2011) · Cited by 900
Security Challenges for the Public Cloud
Ren, K., Wang, C., & Wang, Q. (2012) · IEEE Internet Computing · doi:10.1109/mic.2012.14 · Cited by 845
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
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
Chaum, D., & van Antwerpen, H. (1990) · Lecture Notes in Computer Science · doi:10.1007/0-387-34805-0_20 · Cited by 605
Enabling Secure and Efficient Ranked Keyword Search over Outsourced Cloud Data
Wang, C., Cao, N., Ren, K., & Lou, W. (2012) · IEEE Transactions on Parallel and Distributed Systems · doi:10.1109/tpds.2011.282 · Cited by 531
Self-citationDelegating 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
Improved Online/Offline Signature Schemes
Shamir, A., & Tauman, Y. (2001) · Lecture Notes in Computer Science · doi:10.1007/3-540-44647-8_21 · Cited by 384
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
On-line/off-line digital signatures
Even, S., Goldreich, O., & Micali, S. (1996) · Journal of Cryptology · doi:10.1007/bf02254791 · Cited by 318
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
Micali, S. (2002) · Proceedings 35th Annual Symposium on Foundations of Computer Science · doi:10.1109/sfcs.1994.365746 · Cited by 293
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
On the Key Exposure Problem in Chameleon Hashes
Ateniese, G., & de Medeiros, B. (2005) · Lecture Notes in Computer Science · doi:10.1007/978-3-540-30598-9_12 · Cited by 205
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
Speeding Up Secret Computations with Insecure Auxiliary Devices
Matsumoto, T., Kato, K., & Imai, H. (1990) · Lecture Notes in Computer Science · doi:10.1007/0-387-34799-2_35 · Cited by 161
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 154
Self-citationPractical 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 145
Chameleon Hashing Without Key Exposure
Chen, X., Zhang, F., & Kim, K. (2004) · Lecture notes in computer science · doi:10.1007/978-3-540-30144-8_8 · Cited by 128
Self-citationNew 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-citationSpeeding up discrete log and factoring based schemes via precomputations
Boyko, V., Peinado, M., & Venkatesan, R. (1998) · Lecture notes in computer science · doi:10.1007/bfb0054129 · Cited by 118
Gennaro, R. (2004) · Lecture notes in computer science · doi:10.1007/978-3-540-28628-8_14 · Cited by 106
Secure 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
Strengthening Zero-Knowledge Protocols Using Signatures
Garay, J. A., MACKENZIE, P. D., & Yang, K. (2005) · Journal of Cryptology · doi:10.1007/s00145-005-0307-3 · Cited by 103
Efficient Generic On-Line/Off-Line Signatures Without Key Exposure
Chen, X., Zhang, F., Susilo, W., & Mu, Y. (2007) · Lecture notes in computer science · doi:10.1007/978-3-540-72738-5_2 · Cited by 100
Self-citationOn hiding information from an oracle
Abadi, M., Feigenbaum, J., & Kilian, J. (1987) · ACM Symposium on Theory of Computing (STOC) · doi:10.1145/28395.28417 · Cited by 87
Distribution of Modular Sums and the Security of the Server Aided Exponentiation
Nguyễn, P. Q., Shparlinski, I. E., & Stern, J. (2001) · Birkhäuser Basel eBooks · doi:10.1007/978-3-0348-8295-8_24 · Cited by 84
Strengthening Zero-Knowledge Protocols Using Signatures
Garay, J. A., MACKENZIE, P. D., & Yang, K. (2003) · Lecture notes in computer science · doi:10.1007/3-540-39200-9_11 · Cited by 77
Server-Aided Verification: Theory and Practice
Girault, M., & Lefranc, D. (2005) · Lecture notes in computer science · doi:10.1007/11593447_33 · Cited by 75
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
Locally random reductions: Improvements and applications
Beaver, D., Feigenbaum, J., Kilian, J., & Rogaway, P. (1997) · Journal of Cryptology · doi:10.1007/s001459900017 · Cited by 73
Improved Efficient Arguments (Preliminary Version)
Kilian, J. (1995) · International Cryptology Conference · Cited by 56
Server-Aided Verification Signatures: Definitions and New Constructions
Wu, W., Mu, Y., Susilo, W., & Huang, X. (2008) · Lecture notes in computer science · doi:10.1007/978-3-540-88733-1_10 · Cited by 43
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
Improved Conditional E-Payments
Blanton, M. (2008) · Lecture notes in computer science · doi:10.1007/978-3-540-68914-0_12 · Cited by 31
Shi, L., Cărbunar, B., & Sion, R. (2007) · Lecture notes in computer science · doi:10.1007/978-3-540-77366-5_3 · Cited by 29
Cited by
Verifiable Computation over Large Database with Incremental Updates
Chen, X., Li, J., Weng, J., Ma, J., & Lou, W. (2016) · IEEE Transactions on Computers · doi:10.1109/tc.2015.2512870 · Cited by 257
Self-citationAnonymous 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-citationBlockchain based Efficient and Robust Fair Payment for Outsourcing Services in Cloud Computing
Zhang, Y., Deng, R. H., Liu, X., & Zheng, D. (2018) · Information Sciences · doi:10.1016/j.ins.2018.06.018 · Cited by 228
Zhang, H., Yu, J., Tian, C., Zhao, P., Xu, G., & Lin, J. (2018) · IEEE Access · doi:10.1109/access.2018.2857205 · Cited by 45
Metadata
- Authors
- Chen, X., Li, J., Ma, J., Tang, Q., & Lou, W.
- Venue
- IEEE Transactions on Parallel and Distributed Systems
- Published
- 2014-09
- Volume
- 25
- Issue
- 9
- Pages
- 2386-2396
- ISSN
- 1045-9219 (ISSN-L)
- OpenAlex
- W2114486350
- Cited by
- 307
- References
- 49
- FWCI
- 22.82
- Type
- journal article
- Language
- en
- Open access
- green
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.