TY - GEN
T1 - Explicit and Nearly Tight Lower Bound for 2-Party Perfectly Secure FSS
AU - Hiwatashi, Keitaro
AU - Nuida, Koji
N1 - Publisher Copyright:
© 2023, The Author(s), under exclusive license to Springer Nature Switzerland AG.
PY - 2023
Y1 - 2023
N2 - Function Secret Sharing (FSS) is a cryptographic tool introduced by Boyle et al. (EUROCRYPT 2015) and is useful for several applications such as private information retrieval, oblivious-RAM, multi-party computation, etc. Most of the known FSS schemes are based on a pseudorandom generator and hence with computational security. In contrast, there are only a few known constructions of information-theoretic FSS, which are just for restricted function classes. It has not been well studied how efficient information-theoretic FSS can be in general. In this paper, we focus on (2-party) perfectly secure information-theoretic FSS and prove that the key size is explicitly (i.e., not just asymptotically) bounded below by the size of the subgroup generated by the function class. To the best of our knowledge, this is the first lower bound for information-theoretic FSS for an arbitrary function class. Our result shows that for several practically meaningful function classes, perfectly secure information-theoretic FSS must be much inefficient, not only asymptotically but also in practical parameters. Furthermore, we prove that this explicit lower bound is nearly tight by constructing perfectly secure information-theoretic FSS schemes for arbitrary function classes almost achieving our lower bound.
AB - Function Secret Sharing (FSS) is a cryptographic tool introduced by Boyle et al. (EUROCRYPT 2015) and is useful for several applications such as private information retrieval, oblivious-RAM, multi-party computation, etc. Most of the known FSS schemes are based on a pseudorandom generator and hence with computational security. In contrast, there are only a few known constructions of information-theoretic FSS, which are just for restricted function classes. It has not been well studied how efficient information-theoretic FSS can be in general. In this paper, we focus on (2-party) perfectly secure information-theoretic FSS and prove that the key size is explicitly (i.e., not just asymptotically) bounded below by the size of the subgroup generated by the function class. To the best of our knowledge, this is the first lower bound for information-theoretic FSS for an arbitrary function class. Our result shows that for several practically meaningful function classes, perfectly secure information-theoretic FSS must be much inefficient, not only asymptotically but also in practical parameters. Furthermore, we prove that this explicit lower bound is nearly tight by constructing perfectly secure information-theoretic FSS schemes for arbitrary function classes almost achieving our lower bound.
UR - http://www.scopus.com/inward/record.url?scp=85179757258&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85179757258&partnerID=8YFLogxK
U2 - 10.1007/978-3-031-33491-7_20
DO - 10.1007/978-3-031-33491-7_20
M3 - Conference contribution
AN - SCOPUS:85179757258
SN - 9783031334900
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 541
EP - 554
BT - Applied Cryptography and Network Security - 21st International Conference, ACNS 2023, Proceedings
A2 - Tibouchi, Mehdi
A2 - Wang, XiaoFeng
PB - Springer Science and Business Media Deutschland GmbH
T2 - 21st International Conference on Applied Cryptography and Network Security, ACNS 2023
Y2 - 19 June 2023 through 22 June 2023
ER -