{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,6]],"date-time":"2026-05-06T04:15:45Z","timestamp":1778040945812,"version":"3.51.4"},"reference-count":46,"publisher":"International Association for Cryptologic Research","issue":"1","license":[{"start":{"date-parts":[[2026,1,31]],"date-time":"2026-01-31T00:00:00Z","timestamp":1769817600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["IACR CiC"],"accepted":{"date-parts":[[2026,4,24]]},"abstract":"<jats:p>Multi-point function secret sharing (FSS) is a building block for pseudo-random correlation generators used in novel silent correlation generation methods for various secure multi-party computation applications. However, the main construction used so far is the naive approach to combining several point functions.     In this paper, we propose an efficient and natural generalisation of the point function FSS scheme of Boyle et al. 2016 using a tree structure, a pseudorandom generator and systems of linear equations. We propose a new notion of distributed random multi-point function. Our construction splits the distributed multi-point function scheme into a random multi-point function scheme and an algorithm to transform a random output into the desired output value. The resulting scheme, which we call SLAMP-FSS, improves upon the state of the art in terms of calls to a pseudorandom generator (PRG).<\/jats:p>","DOI":"10.62056\/avommpxqi","type":"journal-article","created":{"date-parts":[[2026,5,4]],"date-time":"2026-05-04T18:09:08Z","timestamp":1777918148000},"update-policy":"https:\/\/doi.org\/10.62056\/adfjwm02dj","source":"Crossref","is-referenced-by-count":0,"title":["SLAMP-FSS: Two-Party Multi-Point Function Secret Sharing from Simple Linear Algebra"],"prefix":"10.62056","volume":"3","author":[{"ORCID":"https:\/\/orcid.org\/0009-0008-0728-0603","authenticated-orcid":false,"given":"Erki","family":"K\u00fclaots","sequence":"first","affiliation":[{"id":[{"id":"https:\/\/ror.org\/03z77qz90","id-type":"ROR","asserted-by":"publisher"}],"name":"University of Tartu","place":["Narva mnt 18, Tartu, Tartumaa, 51009, Estonia"],"department":["Institute of Computer Science"]}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-0981-3553","authenticated-orcid":false,"given":"Toomas","family":"Krips","sequence":"additional","affiliation":[{"id":[{"id":"https:\/\/ror.org\/03z77qz90","id-type":"ROR","asserted-by":"publisher"}],"name":"University of Tartu","place":["Narva mnt 18, Tartu, Tartumaa, 51009, Estonia"],"department":["Institute of Computer Science"]}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0009-0009-9298-074X","authenticated-orcid":false,"given":"Hendrik","family":"Eerikson","sequence":"additional","affiliation":[{"id":[{"id":"https:\/\/ror.org\/054gqc795","id-type":"ROR","asserted-by":"publisher"}],"name":"Cybernetica AS","place":["M\u00e4ealuse 2\/1, Tallinn, Harjumaa, 12618, Estonia"],"department":["Information Security Research Institute"]}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0009-0005-1974-539X","authenticated-orcid":false,"given":"Darya","family":"Pisetskaya","sequence":"additional","affiliation":[{"id":[{"id":"https:\/\/ror.org\/03z77qz90","id-type":"ROR","asserted-by":"publisher"}],"name":"University of Tartu","place":["Narva mnt 18, Tartu, Tartumaa, 51009, Estonia"],"department":["Institute of Computer Science"]}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-3255-7001","authenticated-orcid":false,"given":"Pille","family":"Pullonen-Raudvere","sequence":"additional","affiliation":[{"id":[{"id":"https:\/\/ror.org\/054gqc795","id-type":"ROR","asserted-by":"publisher"}],"name":"Cybernetica AS","place":["M\u00e4ealuse 2\/1, Tallinn, Harjumaa, 12618, Estonia"],"department":["Information Security Research Institute"]}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"48349","published-online":{"date-parts":[[2026,5,4]]},"reference":[{"key":"ref1:boyle2016FSSimproved","doi-asserted-by":"publisher","first-page":"1292","DOI":"10.1145\/2976749.2978429","article-title":"Function Secret Sharing: Improvements and Extensions","author":"Elette Boyle","year":"2016"},{"key":"ref2:boyle2015FSS","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"337","DOI":"10.1007\/978-3-662-46803-6_12","article-title":"Function Secret Sharing","volume":"9057","author":"Elette Boyle","year":"2015"},{"key":"ref3:gilboa2014distributed","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"640","DOI":"10.1007\/978-3-642-55220-5_35","article-title":"Distributed Point Functions and Their Applications","volume":"8441","author":"Niv Gilboa","year":"2014"},{"key":"ref4:DBLP:conf\/eurocrypt\/CastroP22","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"150","DOI":"10.1007\/978-3-031-06944-4_6","article-title":"Lightweight, Maliciously Secure Verifiable Function Secret\n  Sharing","volume":"13275","author":"Leo de Castro","year":"2022"},{"key":"ref5:DBLP:journals\/iacr\/DittmerILOEKSS20","first-page":"1599","article-title":"Function Secret Sharing for PSI-CA: With Applications to\n  Private Contact Tracing","author":"Samuel Dittmer","year":"2020","journal-title":"IACR Cryptol. ePrint Arch."},{"key":"ref6:DoernerS17","doi-asserted-by":"publisher","first-page":"523","DOI":"10.1145\/3133956.3133967","article-title":"Scaling ORAM for Secure Computation","author":"Jack Doerner","year":"2017"},{"key":"ref7:DBLP:conf\/scn\/BunnKKO20","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"215","DOI":"10.1007\/978-3-030-57990-6_11","article-title":"Efficient 3-Party Distributed ORAM","volume":"12238","author":"Paul Bunn","year":"2020"},{"key":"ref8:DBLP:conf\/sp\/Corrigan-GibbsB15","doi-asserted-by":"publisher","first-page":"321","DOI":"10.1109\/SP.2015.27","article-title":"Riposte: An Anonymous Messaging System Handling Millions of\n  Users","author":"Henry Corrigan-Gibbs","year":"2015"},{"key":"ref9:DBLP:conf\/uss\/EskandarianCZB21","first-page":"1775","article-title":"Express: Lowering the Cost of Metadata-hiding Communication\n  with Cryptographic Privacy","author":"Saba Eskandarian","year":"2021"},{"key":"ref10:DBLP:conf\/nsdi\/NewmanSD22","first-page":"229","article-title":"Spectrum: High-bandwidth Anonymous Broadcast","author":"Zachary Newman","year":"2022"},{"key":"ref11:DBLP:journals\/popets\/Wagh22","doi-asserted-by":"publisher","first-page":"351","DOI":"10.56553\/POPETS-2022-0113","article-title":"Pika: Secure Computation using Function Secret Sharing over\n  Rings","volume":"2022","author":"Sameer Wagh","year":"2022","journal-title":"Proc. Priv. Enhancing Technol."},{"key":"ref12:DBLP:journals\/popets\/GuptaJMCGPS24","doi-asserted-by":"publisher","first-page":"61","DOI":"10.56553\/POPETS-2024-0107","article-title":"SIGMA: Secure GPT Inference with Function Secret\n  Sharing","volume":"2024","author":"Kanav Gupta","year":"2024","journal-title":"Proc. Priv. Enhancing Technol."},{"key":"ref13:DBLP:conf\/wpes\/FalkLO19","doi-asserted-by":"publisher","first-page":"26","DOI":"10.1145\/3338498.3358651","article-title":"DURASIFT: A Robust, Decentralized, Encrypted Database\n  Supporting Private Searches with Complex Policy Controls","author":"Brett Hemenway Falk","year":"2019"},{"key":"ref14:DBLP:conf\/osdi\/DautermanFLPS20","first-page":"1101","article-title":"DORY: An Encrypted Search System with Distributed Trust","author":"Emma Dauterman","year":"2020"},{"key":"ref15:DBLP:conf\/sp\/DautermanRPS22","doi-asserted-by":"publisher","first-page":"2450","DOI":"10.1109\/SP46214.2022.9833611","article-title":"Waldo: A Private Time-Series Database from Function Secret\n  Sharing","author":"Emma Dauterman","year":"2022"},{"key":"ref16:DBLP:conf\/ccs\/StorrierVLH23","doi-asserted-by":"publisher","first-page":"2143","DOI":"10.1145\/3576915.3623147","article-title":"Grotto: Screaming fast (2+1)-PC or \\(\\mathbb{Z}\\)2n via\n  (2, 2)-DPFs","author":"Kyle Storrier","year":"2023"},{"key":"ref17:DBLP:conf\/crypto\/GarimellaGM24","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"309","DOI":"10.1007\/978-3-031-68397-8_10","article-title":"Computation Efficient Structure-Aware PSI from Incremental\n  Function Secret Sharing","volume":"14927","author":"Gayathri Garimella","year":"2024"},{"key":"ref18:DBLP:conf\/sp\/BonehBCGI21","doi-asserted-by":"publisher","first-page":"762","DOI":"10.1109\/SP40001.2021.00048","article-title":"Lightweight Techniques for Private Heavy Hitters","author":"Dan Boneh","year":"2021"},{"key":"ref19:DBLP:conf\/crypto\/BoyleGIK22","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"121","DOI":"10.1007\/978-3-031-15985-5_5","article-title":"Programmable Distributed Point Functions","volume":"13510","author":"Elette Boyle","year":"2022"},{"key":"ref20:DBLP:journals\/iacr\/JiZZR24","first-page":"937","article-title":"Distributed Point Function with Constraints, Revisited","author":"Keyu Ji","year":"2024","journal-title":"IACR Cryptol. ePrint Arch."},{"key":"ref21:boyle2018compressing","doi-asserted-by":"publisher","first-page":"896","DOI":"10.1145\/3243734.3243868","article-title":"Compressing Vector OLE","author":"Elette Boyle","year":"2018"},{"key":"ref22:boyle2019silentOT","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"489","DOI":"10.1007\/978-3-030-26954-8_16","article-title":"Efficient Pseudorandom Correlation Generators: Silent OT\n  Extension and More","volume":"11694","author":"Elette Boyle","year":"2019"},{"key":"ref23:DBLP:journals\/cic\/0005PM24","doi-asserted-by":"publisher","first-page":"8","DOI":"10.62056\/A3C3C3W9P","article-title":"Compact Key Function Secret Sharing with Non-linear\n  Decoder","volume":"1","author":"Chandan Kumar","year":"2024","journal-title":"IACR Commun. Cryptol."},{"key":"ref24:DBLP:journals\/iacr\/Zhang23c","first-page":"1690","article-title":"Efficient VOLE based Multi-Party PSI with Lower\n  Communication Cost","author":"Shuqing Zhang","year":"2023","journal-title":"IACR Cryptol. ePrint Arch."},{"key":"ref25:DBLP:conf\/crypto\/Beaver91a","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"420","DOI":"10.1007\/3-540-46766-1_34","article-title":"Efficient Multiparty Protocols Using Circuit Randomization","volume":"576","author":"Donald Beaver","year":"1991"},{"key":"ref26:AngelCLS18probBatch","doi-asserted-by":"publisher","first-page":"962","DOI":"10.1109\/SP.2018.00062","article-title":"PIR with Compressed Queries and Amortized Query\n  Processing","author":"Sebastian Angel","year":"2018"},{"key":"ref27:SchoppmannGR019probBatch","doi-asserted-by":"publisher","first-page":"1055","DOI":"10.1145\/3319535.3363228","article-title":"Distributed Vector-OLE: Improved Constructions and\n  Implementation","author":"Phillipp Schoppmann","year":"2019"},{"key":"ref28:Boyle2025dmpf","doi-asserted-by":"publisher","first-page":"44","DOI":"10.1109\/SP61157.2025.00044","article-title":"Improved Constructions for Distributed Multi-Point\n  Functions","author":"Elette Boyle","year":"2025","ISSN":"https:\/\/id.crossref.org\/issn\/2375-1207","issn-type":"electronic"},{"key":"ref29:cryptoeprint:2024\/1394-initial","volume-title":"SLAMP-FSS: Two-Party Multi-Point Function Secret Sharing\n  from Simple Linear Algebra","author":"Erki K\u00fclaots","year":"2024"},{"key":"ref30:boyle2020ringLPN","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"387","DOI":"10.1007\/978-3-030-56880-1_14","article-title":"Efficient Pseudorandom Correlation Generators from\n  Ring-LPN","volume":"12171","author":"Elette Boyle","year":"2020"},{"key":"ref31:DBLP:conf\/asiacrypt\/BombarBCCDS24","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"69","DOI":"10.1007\/978-981-96-0938-3_3","article-title":"FOLEAGE: $\\mathbb\n  {F}_{\\scriptstyle 4}$OLE-Based Multi-party\n  Computation for Boolean Circuits","volume":"15489","author":"Maxime Bombar","year":"2024"},{"key":"ref32:cryptoeprint:2025\/2294","volume-title":"Fully Distributed Multi-Point Functions for PCGs and\n  Beyond","author":"Amit Agarwal","year":"2025"},{"key":"ref33:DBLP:journals\/iacr\/KruglikDKWZ24","first-page":"453","article-title":"Verifiable Information-Theoretic Function Secret Sharing","author":"Stanislav Kruglik","year":"2024","journal-title":"IACR Cryptol. ePrint Arch."},{"key":"ref34:Bar-IlanB89","doi-asserted-by":"publisher","first-page":"201","DOI":"10.1145\/72981.72995","article-title":"Non-Cryptographic Fault-Tolerant Computing in Constant\n  Number of Rounds of Interaction","author":"Judit Bar-Ilan","year":"1989"},{"key":"ref35:goldreich2001foundations","doi-asserted-by":"crossref","DOI":"10.1017\/CBO9780511546891","volume-title":"Foundations of Cryptography: Basic Tools","author":"Oded Goldreich","year":"2001"},{"key":"ref36:katz2008modernCrypto","volume-title":"Introduction to modern cryptography","author":"Jonathan Katz","year":"2008"},{"key":"ref37:shamir1979share","doi-asserted-by":"publisher","first-page":"612","DOI":"10.1145\/359168.359176","article-title":"How to Share a Secret","volume":"22","author":"Adi Shamir","year":"1979","journal-title":"Communications of the Association for Computing Machinery"},{"key":"ref38:krenn2023secretSharing","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-031-28161-7","volume-title":"An Introduction to Secret Sharing: A Systematic Overview and\n  Guide for Protocol Selection","author":"Stephan Krenn","year":"2023"},{"key":"ref39:coron2008idealCipher","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/978-3-540-85174-5_1","article-title":"The Random Oracle Model and the Ideal Cipher Model Are\n  Equivalent","volume":"5157","author":"Jean-S\u00e9bastien Coron","year":"2008"},{"key":"ref40:GuoKW020prg","doi-asserted-by":"publisher","first-page":"825","DOI":"10.1109\/SP40000.2020.00016","article-title":"Efficient and Secure Multiparty Computation from Fixed-Key\n  Block Ciphers","author":"Chun Guo","year":"2020"},{"key":"ref41:anton1991elementary","volume-title":"Elementary linear algebra: applications version","author":"Howard Anton","year":"1991"},{"key":"ref42:mullen2013finiteFields","doi-asserted-by":"crossref","first-page":"500","DOI":"10.1201\/b15006","volume-title":"Handbook of finite fields","volume":"17","author":"Gary L Mullen","year":"2013"},{"key":"ref43:Wang2017FSS","series-title":"NSDI'17","isbn-type":"print","first-page":"299","article-title":"Splinter: practical private queries on public data","author":"Frank Wang","year":"2017","ISBN":"https:\/\/id.crossref.org\/isbn\/9781931971379"},{"key":"ref44:DBLP:journals\/iacr\/GuoLHCZHWYY25","first-page":"1660","article-title":"Dory: Streaming PCG with Small Memory","volume":"2025","author":"Xiaojie Guo","year":"2025","journal-title":"IACR Cryptol. ePrint Arch."},{"key":"ref45:BaumBMS22mozzarella","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"329","DOI":"10.1007\/978-3-031-15985-5_12","article-title":"Moz$\\mathbb{Z}_{2^k}$arella: Efficient Vector-OLE and\n  Zero-Knowledge Proofs over $\\mathbb{Z}_{2^k}$","volume":"13510","author":"Carsten Baum","year":"2022"},{"key":"ref46:DBLP:conf\/uss\/BienstockPSY23","first-page":"301","article-title":"Near-Optimal Oblivious Key-Value Stores for Efficient PSI,\n  PSU and Volume-Hiding Multi-Maps","author":"Alexander Bienstock","year":"2023"}],"container-title":["IACR Communications in Cryptology"],"original-title":[],"language":"en","deposited":{"date-parts":[[2026,5,6]],"date-time":"2026-05-06T04:02:43Z","timestamp":1778040163000},"score":1,"resource":{"primary":{"URL":"https:\/\/cic.iacr.org\/p\/3\/1\/16"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,5,4]]},"references-count":46,"journal-issue":{"issue":"1","published-online":{"date-parts":[[2026,5,4]]}},"URL":"https:\/\/doi.org\/10.62056\/avommpxqi","archive":["Internet Archive","Internet Archive"],"relation":{},"ISSN":["3006-5496"],"issn-type":[{"value":"3006-5496","type":"electronic"}],"subject":[],"published":{"date-parts":[[2026,5,4]]},"assertion":[{"value":"2026-01-31","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2026-04-24","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}}],"article-number":"cc3-1-38"}}