Function Secret Sharing: Improvements and Extensions
Open accessThe DOI matches its Crossref record; 58 of the 58 references it cites were found in a registry or an index.
Abstract
Function Secret Sharing (FSS), introduced by Boyle et al. (Eurocrypt 2015), provides a way for additively secret-sharing a function from a given function family F. More concretely, an m-party FSS scheme splits a function f : {0, 1}n -> G, for some abelian group G, into functions f1,...,fm, described by keys k1,...,km, such that f = f1 + ... + fm and every strict subset of the keys hides f. A Distributed Point Function (DPF) is a special case where F is the family of point functions, namely functions f_{a,b} that evaluate to b on the input a and to 0 on all other inputs. FSS schemes are useful for applications that involve privately reading from or writing to distributed databases while minimizing the amount of communication. These include different flavors of private information retrieval (PIR), as well as a recent application of DPF for large-scale anonymous messaging.
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
Shamir, A. (1979) · Communications of the ACM · doi:10.1145/359168.359176 · Cited by 13,756
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
Goldreich, O., Micali, S., & Wigderson, A. (1987) · Proceedings of the nineteenth annual ACM conference on Theory of computing - STOC '87 · doi:10.1145/28395.28420 · Cited by 3,590
Protocols for secure computations
Yao, A. C. (1982) · 23rd Annual Symposium on Foundations of Computer Science (sfcs 1982) · doi:10.1109/sfcs.1982.38 · Cited by 3,306
Completeness theorems for non-cryptographic fault-tolerant distributed computation
Ben-Or, M., & Wigderson, A. (1988) · Proceedings of the twentieth annual ACM symposium on Theory of computing - STOC '88 · doi:10.1145/62212.62213 · Cited by 2,524
On lattices, learning with errors, random linear codes, and cryptography
Regev, O. (2005) · Proceedings of the thirty-seventh annual ACM symposium on Theory of computing · doi:10.1145/1060590.1060603 · Cited by 2,313
Goldreich, O. (2001) · Cambridge University Press eBooks · doi:10.1017/cbo9780511546891 · Cited by 2,181
How to construct random functions
Goldreich, O., Goldwasser, S., & Micali, S. (1986) · Journal of the ACM · doi:10.1145/6490.6503 · Cited by 2,115
(Leveled) fully homomorphic encryption without bootstrapping
Brakerski, Z., Gentry, C., & Vaikuntanathan, V. (2012) · Proceedings of the 3rd Innovations in Theoretical Computer Science Conference · doi:10.1145/2090236.2090262 · Cited by 1,782
A Pseudorandom Generator from any One-way Function
HÅstad, J., Impagliazzo, R., Levin, L. A., & Luby, M. (1999) · SIAM Journal on Computing · doi:10.1137/s0097539793244708 · Cited by 1,653
Software protection and simulation on oblivious RAMs
Goldreich, O., & Ostrovsky, R. (1996) · Journal of the ACM · doi:10.1145/233551.233553 · Cited by 1,617
Chor, B., Kushilevitz, E., Goldreich, O., & Sudan, M. (1998) · Journal of the ACM · doi:10.1145/293347.293350 · Cited by 1,612
Gentry, C., Sahai, A., & Waters, B. (2013) · Lecture Notes in Computer Science · doi:10.1007/978-3-642-40041-4_5 · Cited by 1,492
Efficient Fully Homomorphic Encryption from (Standard) LWE
Brakerski, Z., & Vaikuntanathan, V. (2011) · 2011 IEEE 52nd Annual Symposium on Foundations of Computer Science · doi:10.1109/focs.2011.12 · Cited by 1,449
Multiparty Computation from Somewhat Homomorphic Encryption
Damgård, I., Pastro, V., Smart, N., & Zakarias, S. (2012) · Lecture Notes in Computer Science · doi:10.1007/978-3-642-32009-5_38 · Cited by 1,331 · cited 1×
“, [5, 12] for efficient solutions to the latter.”
BackgroundDesmedt, Y., & Frankel, Y. (2007) · Lecture Notes in Computer Science · doi:10.1007/0-387-34805-0_28 · Cited by 1,131
Foundations of Cryptography: Basic Tools
Goldreich, O. (2000) · Cambridge University Press eBooks · Cited by 1,019
Replication is not needed: single database, computationally-private information retrieval
Kushilevitz, E., & Ostrovsky, R. (2002) · Proceedings 38th Annual Symposium on Foundations of Computer Science · doi:10.1109/sfcs.1997.646125 · Cited by 932
Efficient Multiparty Protocols Using Circuit Randomization
Beaver, D. (2007) · Lecture Notes in Computer Science · doi:10.1007/3-540-46766-1_34 · Cited by 893
Extending Oblivious Transfers Efficiently
Ishai, Y., Kilian, J., Nissim, K., & Petrank, E. (2003) · Lecture Notes in Computer Science · doi:10.1007/978-3-540-45146-4_9 · Cited by 746
Self-citationHow to use indistinguishability obfuscation: deniable encryption, and more
Sahai, A., & Waters, B. (2014) · Proceedings of the forty-sixth annual ACM symposium on Theory of computing · doi:10.1145/2591796.2591825 · Cited by 624
On the (im)possibility of obfuscating programs
Barak, B., Goldreich, O., Impagliazzo, R., Rudich, S., Sahai, A., Vadhan, S., & Yang, K. (2012) · Journal of the ACM · doi:10.1145/2160158.2160159 · Cited by 595
Computationally Private Information Retrieval with Polylogarithmic Communication
Cachin, C., Micali, S., & Stadler, M. (1999) · Lecture Notes in Computer Science · doi:10.1007/3-540-48910-x_28 · Cited by 579
Multi-Dimensional Range Query over Encrypted Data
Shi, E., Bethencourt, J., Chan, T.-H. H., Song, D., & Perrig, A. (2007) · IEEE Symposium on Security and Privacy (S&P) · doi:10.1109/sp.2007.29 · Cited by 552
Reusable garbled circuits and succinct functional encryption
Goldwasser, S., Kalai, Y., Popa, R. A., Vaikuntanathan, V., & Zeldovich, N. (2013) · Proceedings of the forty-fifth annual ACM symposium on Theory of Computing · doi:10.1145/2488608.2488678 · Cited by 457
Multiparty Computation with Low Communication, Computation and Interaction via Threshold FHE
Asharov, G., Jain, A., López-Alt, A., Tromer, E., Vaikuntanathan, V., & Wichs, D. (2012) · Lecture Notes in Computer Science · doi:10.1007/978-3-642-29011-4_29 · Cited by 454
Society and Group Oriented Cryptography: a New Concept
Desmedt, Y. (1988) · Lecture Notes in Computer Science · doi:10.1007/3-540-48184-2_8 · Cited by 433
Semi-homomorphic Encryption and Multiparty Computation
Bendlin, R., Damgård, I., Orlandi, C., & Zakarias, S. (2011) · Lecture Notes in Computer Science · doi:10.1007/978-3-642-20465-4_11 · Cited by 354
How to share a function securely
De Santis, A., Desmedt, Y., Frankel, Y., & Yung, M. (1994) · Proceedings of the twenty-sixth annual ACM symposium on Theory of computing - STOC '94 · doi:10.1145/195058.195405 · Cited by 328
Boyle, E., Gilboa, N., & Ishai, Y. (2015) · Lecture Notes in Computer Science · doi:10.1007/978-3-662-46803-6_12 · Cited by 328
Self-citationSingle-Database Private Information Retrieval with Constant Communication Rate
Gentry, C., & Ramzan, Z. (2005) · Lecture Notes in Computer Science · doi:10.1007/11523468_65 · Cited by 313
Succinct Non-interactive Arguments via Linear Interactive Proofs
Bitansky, N., Chiesa, A., Ishai, Y., Paneth, O., & Ostrovsky, R. (2013) · Lecture Notes in Computer Science · doi:10.1007/978-3-642-36594-2_18 · Cited by 274
Self-citationAn Oblivious Transfer Protocol with Log-Squared Communication
Lipmaa, H. (2005) · Lecture Notes in Computer Science · doi:10.1007/11556992_23 · Cited by 271
Lattice-based FHE as secure as PKE
Brakerski, Z., & Vaikuntanathan, V. (2014) · Proceedings of the 5th conference on Innovations in theoretical computer science · doi:10.1145/2554797.2554799 · Cited by 266
Riposte: An Anonymous Messaging System Handling Millions of Users
Corrigan-Gibbs, H., Boneh, D., & Mazières, D. (2015) · IEEE Symposium on Security and Privacy (S&P) · doi:10.1109/sp.2015.27 · Cited by 265
3-Query Locally Decodable Codes of Subexponential Length
Efremenko, K. (2012) · SIAM Journal on Computing · doi:10.1137/090772721 · Cited by 256
Computationally private information retrieval (extended abstract)
Chor, B., & Gilboa, N. (1997) · Proceedings of the twenty-ninth annual ACM symposium on Theory of computing - STOC '97 · doi:10.1145/258533.258609 · Cited by 249
Self-citationCorrelated pseudorandomness and the complexity of private computations
Beaver, D. (1996) · Proceedings of the twenty-eighth annual ACM symposium on Theory of computing - STOC '96 · doi:10.1145/237814.237996 · Cited by 233
Evaluating Branching Programs on Encrypted Data
Ishai, Y., & Paskin, A. (2007) · Lecture Notes in Computer Science · doi:10.1007/978-3-540-70936-7_31 · Cited by 228
Self-citationPrivate information storage (extended abstract)
Ostrovsky, R., & Shoup, V. (1997) · Proceedings of the twenty-ninth annual ACM symposium on Theory of computing - STOC '97 · doi:10.1145/258533.258606 · Cited by 225
Distributed Point Functions and Their Applications
Gilboa, N., & Ishai, Y. (2014) · Lecture Notes in Computer Science · doi:10.1007/978-3-642-55220-5_35 · Cited by 205
Self-citationGilboa, N. (1999) · Lecture Notes in Computer Science · doi:10.1007/3-540-48405-1_8 · Cited by 189
Self-citationXPIR: Private information retrieval for everyone
Aguilar-Melchor, C., Barrier, J., Fousse, L., & Killijian, M.-O. (2016) · Proceedings on Privacy Enhancing Technologies · doi:10.1515/popets-2016-0010 · Cited by 185 · cited 1×
“Indeed all known single-server PIR protocols require (additively homomorphic) public-key encryption of the whole database to evaluate a PIR query (cf. [25] and references therein).”
BackgroundPrivate Information Retrieval by Keywords
Chor, B., Gilboa, N., & Naor, M. (1997) · Cited by 175
Self-citationPrivate Searching on Streaming Data
Ostrovsky, R., & Skeith, W. E. (2005) · Lecture Notes in Computer Science · doi:10.1007/11535218_14 · Cited by 159
Single Database Private Information Retrieval Implies Oblivious Transfer
Di Crescenzo, G., Malkin, T., & Ostrovsky, R. (2000) · Lecture Notes in Computer Science · doi:10.1007/3-540-45539-6_10 · Cited by 158
Obfuscation of Probabilistic Circuits and Applications
Canetti, R., Lin, H., Tessaro, S., & Vaikuntanathan, V. (2015) · Lecture notes in computer science · doi:10.1007/978-3-662-46497-7_19 · Cited by 155
Efficient Arguments without Short PCPs
Ishai, Y., Kushilevitz, E., & Ostrovsky, R. (2007) · IEEE Conference on Computational Complexity (CCC) · doi:10.1109/ccc.2007.10 · Cited by 153
Self-citationSecure Arithmetic Computation with No Honest Majority
Ishai, Y., Prabhakaran, M., & Sahai, A. (2009) · Lecture notes in computer science · doi:10.1007/978-3-642-00457-5_18 · Cited by 145
Self-citationSpooky Encryption and Its Applications
Dodis, Y., Halevi, S., Rothblum, R. D., & Wichs, D. (2016) · Lecture notes in computer science · doi:10.1007/978-3-662-53015-3_4 · Cited by 128
Circuits resilient to additive attacks with applications to secure computation
Genkin, D., Ishai, Y., Prabhakaran, M., Sahai, A., & Tromer, E. (2014) · ACM Symposium on Theory of Computing (STOC) · doi:10.1145/2591796.2591861 · Cited by 109
Self-citationRiposte: An Anonymous Messaging System Handling Millions of Users
Corrigan-Gibbs, H., Boneh, D., & Mazières, D. (2015) · Cited by 106
Private Information StoragePreprint
Ostrovsky, R., & Shoup, V. (1996) · IACR Cryptology ePrint Archive · Cited by 97
Private Searching on Streaming Data
Ostrovsky, R., & Skeith, W. E. (2007) · Journal of Cryptology · doi:10.1007/s00145-007-0565-3 · Cited by 84
Improved Lower Bounds for Locally Decodable Codes and Private Information Retrieval
Wehner, S., & de Wolf, R. (2004) · Data Archiving and Networked Services (DANS) · Cited by 69
Share Conversion and Private Information Retrieval
Beimel, A., Ishai, Y., Kushilevitz, E., & Orlov, I. (2012) · IEEE Conference on Computational Complexity (CCC) · doi:10.1109/ccc.2012.23 · Cited by 68
Self-citationScalable and private media consumption with Popcorn.Preprint
Gupta, T., Crooks, N., Setty, S., Alvisi, L., & Walfish, M. (2015) · IACR Cryptology ePrint Archive · Cited by 66
Private Stream Search at the same communication cost as a regular search: Role of LDPC codes
Finiasz, M., & Ramchandran, K. (2012) · IEEE International Symposium on Information Theory (ISIT) · doi:10.1109/isit.2012.6283979 · Cited by 20
Cited by
End-to-end privacy preserving deep learning on multi-institutional medical imaging
Kaissis, G., Ziller, A., Passerat-Palmbach, J., Ryffel, T., Usynin, D., Trask, A., Lima, I., Mancuso, J., Jungmann, F., Steinborn, M.-M., et al. (2021) · Nature Machine Intelligence · doi:10.1038/s42256-021-00337-8 · Cited by 513
“In our recent work, we introduced AriaNN 26 , an SMPC protocol leveraging function secret sharing (FSS) 28 and building upon SPDZ 25 .”
MethodInfluentialA Pragmatic Introduction to Secure Multi-Party Computation
Evans, D., Kolesnikov, V., & Rosulek, M. (2018) · Foundations and Trends® in Privacy and Security · doi:10.1561/3300000019 · Cited by 321
Metadata
- Authors
- Boyle, E., Gilboa, N., & Ishai, Y.
- Venue
- Proceedings of the 2016 ACM SIGSAC Conference on Computer and Communications Security
- Publisher
- ACM
- Published
- 2016-10-24
- Pages
- 1292-1303
- OpenAlex
- W2533357737
- Cited by
- 358
- References
- 58
- FWCI
- 10.53
- Type
- conference paper
- Language
- en
- Open access
- bronze
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.