1. bookVolume 2017 (2017): Issue 1 (January 2017)
Journal Details
First Published
16 Apr 2015
Publication timeframe
4 times per year
access type Open Access

Are you The One to Share? Secret Transfer with Access Structure

Published Online: 22 Dec 2016
Page range: 149 - 169
Received: 31 May 2016
Accepted: 02 Sep 2016
Journal Details
First Published
16 Apr 2015
Publication timeframe
4 times per year

Sharing information to others is common nowadays, but the question is with whom to share. To address this problem, we propose the notion of secret transfer with access structure (STAS). STAS is a twoparty computation protocol that enables the server to transfer a secret to a client who satisfies the prescribed access structure. In this paper, we focus on threshold secret transfer (TST), which is STAS for threshold policy and can be made more expressive by using linear secret sharing. TST enables a number of applications including a simple construction of oblivious transfer (OT) with threshold access control, and (a variant of) threshold private set intersection (t-PSI), which are the first of their kinds in the literature to the best of our knowledge. The underlying primitive of STAS is a variant of OT, which we call OT for a sparse array. We provide two constructions which are inspired by state-of-the-art PSI techniques including oblivious polynomial evaluation (OPE) and garbled Bloom filter (GBF). The OPEbased construction is secure in the malicious model, while the GBF-based one is more efficient. We implemented the latter one and showed its performance in applications such as privacy-preserving matchmaking.


[1] A. Abadi, S. Terzis, and C. Dong. O-PSI: delegated private set intersection on outsourced datasets. In IFIP SEC, 2015.Search in Google Scholar

[2] R. Agrawal, A. V. Evfimievski, and R. Srikant. Information sharing across private databases. In ACM SIGMOD, 2003.Search in Google Scholar

[3] G. Ateniese, E. D. Cristofaro, and G. Tsudik. (if) size matters: Size-hiding private set intersection. In PKC, 2011.Search in Google Scholar

[4] A. Beimel. Secure Schemes for Secret Sharing and Key Distribution. PhD thesis, Technion, Israel, 1996.Search in Google Scholar

[5] B. H. Bloom. Space/time trade-offs in hash coding with allowable errors. Commun. ACM, 13(7):422-426, 1970.Search in Google Scholar

[6] P. Bose, H. Guo, E. Kranakis, A. Maheshwari, P. Morin, J. Morrison, M. H. M. Smid, and Y. Tang. On the false-positive rate of Bloom filters. Inf. Process. Lett., 108(4):210-213, 2008.Search in Google Scholar

[7] E. Bursztein, M. Hamburg, J. Lagarenne, and D. Boneh.Openconflict: Preventing real time map hacks in online games. In IEEE Symp. on Security and Privacy, S&P, 2011.Search in Google Scholar

[8] J. Camenisch, M. Dubovitskaya, and G. Neven. Oblivious transfer with access control. In ACM CCS, 2009.Search in Google Scholar

[9] J. Camenisch and V. Shoup. Practical verifiable encryption and decryption of discrete logarithms. In CRYPTO, 2003.Search in Google Scholar

[10] J. Camenisch and G. M. Zaverucha. Private intersection of certified sets. In FC, 2009.Search in Google Scholar

[11] E. D. Cristofaro, J. Kim, and G. Tsudik. Linear-complexity private set intersection protocols secure in malicious model. In ASIACRYPT, 2010.Search in Google Scholar

[12] E. D. Cristofaro and G. Tsudik. Practical private set intersection protocols with linear complexity. In FC, 2010.Search in Google Scholar

[13] D. Dachman-Soled, T. Malkin, M. Raykova, and M. Yung.Efficient robust private set intersection. In ACNS, 2009.Search in Google Scholar

[14] P. D’Arco, M. I. G. Vasco, A. L. P. del Pozo, and C. Soriente.Size-hiding in private set intersection: Existential results and constructions. In AFRICACRYPT, 2012.Search in Google Scholar

[15] Y. Desmedt and Y. Frankel. Threshold cryptosystems. In CRYPTO, 1989.Search in Google Scholar

[16] Y. Dodis and A. Yampolskiy. A verifiable random function with short proofs and keys. In PKC, 2005.Search in Google Scholar

[17] C. Dong, L. Chen, and Z. Wen. When private set intersection meets big data: an efficient and scalable protocol. In ACM CCS, 2013.Search in Google Scholar

[18] M. J. Freedman, Y. Ishai, B. Pinkas, and O. Reingold. Keyword search and oblivious pseudorandom functions. In TCC, 2005.Search in Google Scholar

[19] M. J. Freedman, K. Nissim, and B. Pinkas. Efficient private matching and set intersection. In EUROCRYPT, 2004.Search in Google Scholar

[20] O. Goldreich. The Foundations of Cryptography - Volume 2, Basic Applications. Cambridge University Press, 2004.Search in Google Scholar

[21] S. Goldwasser, S. Micali, and C. Rackoff. The knowledge complexity of interactive proof-systems. In STOC, 1985.Search in Google Scholar

[22] C. Hazay. Oblivious polynomial evaluation and secure setintersection from algebraic PRFs. In TCC Part-II, 2015.Search in Google Scholar

[23] C. Hazay and Y. Lindell. Efficient protocols for set intersection and pattern matching with security against malicious and covert adversaries. In TCC, 2008.Search in Google Scholar

[24] C. Hazay and K. Nissim. Efficient set operations in the presence of malicious adversaries. In PKC, 2010.Search in Google Scholar

[25] R. Henry, F. G. Olumofin, and I. Goldberg. Practical PIR for electronic commerce. In ACM CCS, 2011.Search in Google Scholar

[26] S. Hohenberger and S. A. Weis. Honest-verifier private disjointness testing without random oracles. In PET, 2006.Search in Google Scholar

[27] Y. Huang, D. Evans, and J. Katz. Private set intersection: Are garbled circuits better than custom protocols? In NDSS, 2012.Search in Google Scholar

[28] S. Jarecki and X. Liu. Efficient oblivious pseudorandom function with applications to adaptive OT and secure computation of set intersection. In TCC, 2009.Search in Google Scholar

[29] A. Juels and M. Sudan. A fuzzy vault scheme. Des. Codes Cryptography, 38(2):237-257, 2006.Search in Google Scholar

[30] F. Kerschbaum. Outsourced private set intersection using homomorphic encryption. In ASIACCS, 2012.Search in Google Scholar

[31] L. Kissner and D. X. Song. Privacy-preserving set operations. In CRYPTO, 2005.Search in Google Scholar

[32] I. Komargodski and M. Zhandry. Cutting-edge cryptography through the lens of secret sharing. In TCC Part II, 2016.Search in Google Scholar

[33] J. Lai, R. H. Deng, and Y. Li. Expressive CP-ABE with partially hidden access structures. In ASIACCS, 2012.Search in Google Scholar

[34] A. B. Lewko and B. Waters. Decentralizing attribute-based encryption. In EUROCRYPT, 2011.Search in Google Scholar

[35] P. D. MacKenzie, T. Shrimpton, and M. Jakobsson. Threshold password-authenticated key exchange. J. Cryptology, 19(1):27-66, 2006.Search in Google Scholar

[36] M. Nabeel, N. Shang, and E. Bertino. Efficient privacy preserving content based publish subscribe systems. In SACMAT, 2012.Search in Google Scholar

[37] S. Nagaraja, P. Mittal, C. Hong, M. Caesar, and N. Borisov. BotGrep: Finding P2P bots with structured graph analysis. In USENIX Security, 2010.Search in Google Scholar

[38] A. Narayanan, N. Thiagarajan, M. Lakhani, M. Hamburg, and D. Boneh. Location privacy via private proximity testing. In NDSS, 2011.Search in Google Scholar

[39] T. Nishide, K. Yoneyama, and K. Ohta. Attribute-based encryption with partially hidden encryptor-specified access structures. In ACNS, 2008.Search in Google Scholar

[40] P. Paillier. Public-key cryptosystems based on composite degree residuosity classes. In EUROCRYPT, 1999.Search in Google Scholar

[41] B. Pinkas, T. Schneider, G. Segev, and M. Zohner. Phasing: Private set intersection using permutation-based hashing. In USENIX Security, 2015.Search in Google Scholar

[42] B. Pinkas, T. Schneider, and M. Zohner. Faster private set intersection based on OT extension. In USENIX Security, 2014.Search in Google Scholar

[43] M. D. Raimondo and R. Gennaro. Provably secure threshold password-authenticated key exchange. J. Comput. Syst. Sci., 72(6):978-1001, 2006.Search in Google Scholar

[44] A. Shamir. How to share a secret. Commun. ACM, 22(11):612-613, 1979.Search in Google Scholar

[45] V. Shoup. Practical threshold signatures. In EUROCRYPT, 2000.Search in Google Scholar

[46] Q. Ye, R. Steinfeld, J. Pieprzyk, and H. Wang. Efficient fuzzy matching and intersection on private datasets. In ICISC, 2009.Search in Google Scholar

[47] T. H. Yuen, W. Susilo, and Y. Mu. Towards a cryptographic treatment of publish/subscribe systems. Journal of Computer Security, 22(1):33-67, 2014.Search in Google Scholar

[48] Y. Zhao and S. S. M. Chow. Are you the one to share? Secret transfer with access structure. IACR ePrint, 2015/929. Search in Google Scholar

Recommended articles from Trend MD

Plan your remote conference with Sciendo