Protocols for secure computations
Abstract
The author investigates the following problem: Suppose m people wish to compute the value of a function f(x1, x2, x3, ..., xm), which is an integer-valued function of m integer variables xi of bounded range. Assume initially person Pi knows the value of xi and no other x's. Is it possible for them to compute the value of f, by communicating among themselves, without unduly giving away any information about the values of their own variables? The author gives a precise formulation of this general problem and describe three ways of solving it by use of one-way functions (i.e., functions which are easy to evaluate but hard to invert). These results have applications to secret voting, private querying of database, oblivious negotiation, playing mental poker, etc.. He also discusses the complexity question "How many bits need to be exchanged for the computation," and describes methods to prevent participants from cheating. Finally, he studies the question "What cannot be accomplished with one-way functions."
Integrity signals
Registry
Cites
Statistics
Claims the paper makes
Claims other papers make about this one
Each is checked against this paper’s own text: does it say what the citing paper says it does?
Homomorphic encryption, secure multiparty compute, and trusted execution environments allow collaborative computations to be performed with untrusted parties while maintaining confidentiality of the inputs.
“Homomorphic encryption58, secure multiparty compute59, and trusted execution environments (TEEs)60,61 allow for collaborative computations to be performed with untrusted parties while maintaining confidentiality of the inputs to the computation.”
From Federated learning enables big data for rare cancer boundary detection (2022) · cites this paper as [59]
Blockchain has applications such as asset management, stock markets, and banking.
“Blockchain has applications such as asset management, stock markets, banking, etc. [133,134].”
From Security Aspects of Blockchain Technology Intended for Industrial Applications (2021) · cites this paper as [134]
Cites
A method for obtaining digital signatures and public-key cryptosystems
Rivest, R. L., Shamir, A., & Adleman, L. (1978) · Communications of the ACM · doi:10.1145/359340.359342 · Cited by 13,462 · see citing works
Flagged first, then by citations
Cited by
Sorted by citations
Deep learning for healthcare: review, opportunities and challenges
Miotto, R., Wang, F., Wang, S., Jiang, X., & Dudley, J. T. (2018) · Briefings in Bioinformatics · doi:10.1093/bib/bbx044 · Cited by 3,076 · see citing works
SecureML: A System for Scalable Privacy-Preserving Machine Learning
Mohassel, P., & Zhang, Y. (2017) · 2017 IEEE Symposium on Security and Privacy (SP) · doi:10.1109/sp.2017.12 · Cited by 1,936 · see citing works
Our Data, Ourselves: Privacy Via Distributed Noise Generation
Dwork, C., Kenthapadi, K., McSherry, F., Mironov, I., & Naor, M. (2006) · Lecture Notes in Computer Science · doi:10.1007/11761679_29 · Cited by 1,835 · see citing works
A Survey on Homomorphic Encryption Schemes: Theory and Implementation
Acar, A., Aksu, H., Uluagac, A. S., & Conti, M. (2019) · ACM Computing Surveys · doi:10.1145/3214303 · Cited by 1,397 · see citing works
A survey on trust management for Internet of Things
Yan, Z., Zhang, P., & Vasilakos, A. V. (2014) · Journal of Network and Computer Applications · doi:10.1016/j.jnca.2014.01.014 · Cited by 1,155 · see citing works
A Survey on Federated Learning for Resource-Constrained IoT Devices
Imteaj, A., Thakker, U., Wang, S., Li, J., & Amini, M. H. (2022) · IEEE Internet of Things Journal · doi:10.1109/jiot.2021.3095077 · Cited by 774 · see citing works
Securing Fog Computing for Internet of Things Applications: Challenges and Solutions
Ni, J., Zhang, K., Lin, X., & Shen, X. (2018) · IEEE Communications Surveys & Tutorials · doi:10.1109/comst.2017.2762345 · Cited by 659 · see citing works
Yin, X., Zhu, Y., & Hu, J. (2022) · ACM Computing Surveys · doi:10.1145/3460427 · Cited by 638 · see citing works
Privacy and Robustness in Federated Learning: Attacks and Defenses
Lyu, L., Yu, H., Ma, X., Chen, C., Sun, L., Zhao, J., Yang, Q., & Yu, P. S. (2024) · IEEE Transactions on Neural Networks and Learning Systems · doi:10.1109/tnnls.2022.3216981 · Cited by 548 · see citing works
Federated learning enables big data for rare cancer boundary detection
Pati, S., Baid, U., Edwards, B., Sheller, M., Wang, S.-H., Reina, G. A., Foley, P., Gruzdev, A., Karkada, D., Davatzikos, C., et al. (2022) · Nature Communications · doi:10.1038/s41467-022-33407-5 · Cited by 394 · see citing works
Turbo-Aggregate: Breaking the Quadratic Aggregation Barrier in Secure Federated Learning
So, J., Guler, B., & Avestimehr, A. S. (2021) · IEEE Journal on Selected Areas in Information Theory · doi:10.1109/jsait.2021.3054610 · Cited by 318 · see citing works
Big privacy: challenges and opportunities of privacy study in the age of big data
Yu, S. (2016) · IEEE Access · doi:10.1109/access.2016.2577036 · Cited by 307 · see citing works
Privacy-Preserving Byzantine-Robust Federated Learning via Blockchain Systems
Miao, Y., Liu, Z., Li, H., Choo, K.-K. R., & Deng, R. H. (2022) · IEEE Transactions on Information Forensics and Security · doi:10.1109/tifs.2022.3196274 · Cited by 303 · see citing works
Privacy in Internet of Things: From Principles to Technologies
Li, C., & Palanisamy, B. (2019) · IEEE Internet of Things Journal · doi:10.1109/jiot.2018.2864168 · Cited by 130 · see citing works
A Survey of Self-Sovereign Identity Ecosystem
Soltani, R., Nguyen, U. T., & An, A. (2021) · Security and Communication Networks · doi:10.1155/2021/8873429 · Cited by 131 · see citing works
Security Aspects of Blockchain Technology Intended for Industrial Applications
Idrees, S. M., Nowostawski, M., Jameel, R., & Mourya, A. K. (2021) · Electronics · doi:10.3390/electronics10080951 · Cited by 127 · see citing works
Privacy-preserving neural networks with Homomorphic encryption: Challenges and opportunities
Pulido-Gaytan, B., Tchernykh, A., Cortés-Mendoza, J. M., Babenko, M., Radchenko, G., Avetisyan, A., & Drozdov, A. Y. (2021) · Peer-to-Peer Networking and Applications · doi:10.1007/s12083-021-01076-8 · Cited by 126 · see citing works
Wang, S., Jiang, X., Singh, S., Marmor, R., Bonomi, L., Fox, D., Dow, M., & Ohno‐Machado, L. (2017) · Annals of the New York Academy of Sciences · doi:10.1111/nyas.13259 · Cited by 78 · see citing works
Privacy-Enhancing Technologies in Federated Learning for the Internet of Healthcare Things: A Survey
Mosaiyebzadeh, F., Pouriyeh, S., Parizi, R. M., Sheng, Q. Z., Han, M., Zhao, L., Sannino, G., Ranieri, C. M., Ueyama, J., & Batista, D. M. (2023) · Electronics · doi:10.3390/electronics12122703 · Cited by 51 · see citing works
Privacy Protection for Blockchain-Based Healthcare IoT Systems: A Survey
Qi, M., Wang, Z., Han, Q.-L., Zhang, J., Chen, S., & Xiang, Y. (2024) · IEEE/CAA Journal of Automatica Sinica · doi:10.1109/jas.2022.106058 · Cited by 44 · see citing works
Practical Key Recovery Model for Self-Sovereign Identity Based Digital Wallets
Soltani, R., Nguyen, U. T., & An, A. (2019) · 2019 IEEE Intl Conf on Dependable, Autonomic and Secure Computing, Intl Conf on Pervasive Intelligence and Computing, Intl Conf on Cloud and Big Data Computing, Intl Conf on Cyber Science and Technology Congress (DASC/PiCom/CBDCom/CyberSciTech) · doi:10.1109/dasc/picom/cbdcom/cyberscitech.2019.00066 · Cited by 39 · see citing works
Threats and Defenses in the Federated Learning Life Cycle: A Comprehensive Survey and Challenges
Li, Y., Guo, Z., Yang, N., Chen, H., Yuan, D., & Ding, W. (2025) · IEEE Transactions on Neural Networks and Learning Systems · doi:10.1109/tnnls.2025.3563537 · Cited by 38 · see citing works
Kumari, K. A., Sharma, A., Chakraborty, C., & Ananyaa, M. (2022) · Big Data · doi:10.1089/big.2021.0012 · Cited by 36 · see citing works
A Survey on Secure Computation Based on Homomorphic Encryption in Vehicular Ad Hoc Networks
Sun, X., Yu, F. R., Zhang, P., Xie, W., & Peng, X. (2020) · Sensors · doi:10.3390/s20154253 · Cited by 23 · see citing works
Chen, C., Wei, L., Zhang, L., Peng, Y., & Ning, J. (2022) · Security and Communication Networks · doi:10.1155/2022/2985308 · Cited by 8 · see citing works
Decentralized and Privacy-Preserving Key Management Model
Soltani, R., Nguyen, U. T., & An, A. (2020) · 2020 International Symposium on Networks, Computers and Communications (ISNCC) · doi:10.1109/isncc49221.2020.9297294 · Cited by 8 · see citing works
Nair, D. G., Binu, V. P., & Kumar, G. S. (2014) · 2014 International Conference on Data Science & Engineering (ICDSE) · doi:10.1109/icdse.2014.6974639 · Cited by 11 · see citing works
Open Challenges in Multi-Agent Security: Towards Secure Systems of Interacting AI Agents
de Witt, C. S., Krawiecka, K., Krawczuk, I., Hagag, B., Anderson, W. L., Belcak, P., Bucknall, B., Cai, X., Chopra, A., Cohen, D., et al. (2025) · arXiv · doi:10.48550/arxiv.2505.02077 · Cited by 2 · see citing works
- Authors
- Yao, A. C.
- Affiliations
- University of California, Berkeley (US)
- Corresponding author
- Yao, Andrew C.
- ORCID
- Yao, Andrew C.
- Venue
- 23rd Annual Symposium on Foundations of Computer Science (sfcs 1982)
- Publisher
- IEEE
- Published
- 1982-11
- Pages
- 160-164
- ISSN
- 0272-5428 (ISSN-L)
- OpenAlex
- W3141585064
- Cited by
- 3,306
- References
- 1
- Citations by year
- 2026: 144 · 2025: 262 · 2024: 268 · 2023: 252 · 2022: 241 · 2021: 217 · 2020: 188 · 2019: 176 · 2018: 175 · 2017: 162 · 2016: 148 · 2015: 131 · 2014: 110 · 2013: 108 · 2012: 109
- FWCI
- 1.07
- Type
- conference paper
- Language
- en
- Open access
- closed
- Locations
- Annual Symposium on Foundations of Computer Science (publishedVersion)
- Topics
- Physical Sciences › Computer Science › Artificial Intelligence › Cryptography and Data Security
- Physical Sciences › Computer Science › Artificial Intelligence › Internet Traffic Analysis and Secure E-voting
- Physical Sciences › Computer Science › Artificial Intelligence › Coding theory and cryptography
- Keywords
- secure multi-party computation, one-way functions, privacy-preserving computation, secret ballot, communication complexity, cheating prevention, impossibility results
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
