Abstract
Private Stream Search allows keyword-based search queries to be performed on streaming data (or on a database) without revealing any information about the keywords being searched. Using homomorphic encryption, Ostrovsky and Skeith proposed a solution to this problem in 2005. However, their solution requires the server to send an answer of size O(mSlogm) bits when m documents of S bits match the query, while a regular (non-private) query only requires mS bits. Following this work, some improved schemes have been proposed with the aim of keeping the reply from the server linear in mS. In this work we propose two new communication optimal constructions: both allow communication linear in mS, but they also offer an expansion factor (compared to a non-private query) asymptotically equal to 1 when m and S increase. More precisely, our first scheme requires m(S + O(logt)) bits (where t is the size of the database) and our second scheme m(S + C) where C is a constant depending only on the chosen computational security level.
Chapter PDF
Similar content being viewed by others
References
Bethencourt, J., Song, D.X., Waters, B.: New constructions and practical applications for private stream searching (extended abstract). In: 2006 IEEE Symposium on Security and Privacy, pp. 132–139. IEEE Computer Society (2006)
Bethencourt, J., Song, D.X., Waters, B.: New techniques for private stream searching. ACM Trans. Inf. Syst. Secur. 12(3) (2009)
Damgård, I., Jurik, M.: A Generalisation, a Simplification and Some Applications of Paillier’s Probabilistic Public-key System. In: Kim, K.-C. (ed.) PKC 2001. LNCS, vol. 1992, pp. 119–136. Springer, Heidelberg (2001)
Danezis, G., Díaz, C.: Improving the decoding efficiency of private search. In: Anonymous Communication and its Applications. Dagstuhl Seminar Proceedings, vol. 05411. IBFI, Schloss Dagstuhl, Germany (2006)
Danezis, G., Diaz, C.: Space-Efficient Private Search with Applications to Rateless Codes. In: Dietrich, S., Dhamija, R. (eds.) FC 2007 and USEC 2007. LNCS, vol. 4886, pp. 148–162. Springer, Heidelberg (2007)
Gallager, R.G.: Low-density parity-check codes. M.I.T. Press, Cambridge (1963)
Luby, M.G.: LT codes. In: FOCS, pp. 271–280. IEEE (2002)
Luby, M.G., Mitzenmacher, M.: Verification codes. In: Proc. Allerton Conf. on Communication, Control, and Computing (2002)
Luby, M.G., Mitzenmacher, M., Shokrollahi, M.A.: Analysis of random processes via and-or tree evaluation. In: SODA, pp. 364–373 (1998)
Luby, M.G., Mitzenmacher, M., Shokrollahi, M.A., Spielman, D.A.: Analysis of low density codes and improved designs using irregular graphs. In: Proceedings of the 30th Annual ACM Symposium on Theory of Computing, STOC 1998, pp. 249–258. ACM (1998)
Luby, M.G., Mitzenmacher, M., Shokrollahi, M.A., Spielman, D.A.: Efficient erasure correcting codes. IEEE Transactions on Information Theory 47(2), 569–584 (2001)
Ostrovsky, R., Skeith, W.E.: Private Searching on Streaming Data. In: Shoup, V. (ed.) CRYPTO 2005. LNCS, vol. 3621, pp. 223–240. Springer, Heidelberg (2005)
Ostrovsky, R., Skeith, W.E.: Private searching on streaming data. Journal of Cryptology 20(4), 397–430 (2007)
Paillier, P.: Public-Key Cryptosystems Based on Composite Degree Residuosity Classes. In: Stern, J. (ed.) EUROCRYPT 1999. LNCS, vol. 1592, pp. 223–238. Springer, Heidelberg (1999)
Reed, I.S., Solomon, G.: Polynomial codes over certain finite fields. Journal of the SIAM 8(2), 300–304 (1960)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2013 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Finiasz, M., Ramchandran, K. (2013). Private Stream Search at Almost the Same Communication Cost as a Regular Search. In: Knudsen, L.R., Wu, H. (eds) Selected Areas in Cryptography. SAC 2012. Lecture Notes in Computer Science, vol 7707. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-35999-6_24
Download citation
DOI: https://doi.org/10.1007/978-3-642-35999-6_24
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-35998-9
Online ISBN: 978-3-642-35999-6
eBook Packages: Computer ScienceComputer Science (R0)