Confidential Greedy Graph Algorithm

• Autorzy: Waszkiewicz D. , Horubala A. , Sapiecha P. , Andrzejczak M.

Identyfikatory

DOI

10.24425/119367

• Języki publikacji: EN

Abstrakty

EN

Confidential algorithm for the approximate graph vertex covering problem is presented in this article. It can preserve privacy of data at every stage of the computation, which is very important in context of cloud computing. Security of our solution is based on fully homomorphic encryption scheme. The time complexity and the security aspects of considered algorithm are described.

Słowa kluczowe

EN

cryptography; fully homomorphic encryption; confidential graph algorithm; cloud computing

• Wydawca: Polish Academy of Sciences, Committee of Electronics and Telecommunication
• Czasopismo: International Journal of Electronics and Telecommunications
• Rocznik: 2018
• Tom: Vol. 64, No. 2
• Strony: 179--183
• Opis fizyczny: Bibliogr. 15 poz., rys., tab., wykr.

Twórcy

autor

Waszkiewicz D.

• Warsaw University of Technology, Poland

autor

Horubala A.

• Warsaw University of Technology, Poland

autor

Sapiecha P.

• Warsaw University of Technology, Poland

autor

Andrzejczak M.

• Military University of Technology in Warsaw, Poland

Bibliografia

• [1] X. Liao, S. Uluagac, and R. A. Beyah, “S-match: Verifiable privacypreserving profile matching for mobile social services,” in 2014 44th Annual IEEE/IFIP International Conference on Dependable Systems and Networks, June 2014, pp. 287-298.
• [2] S. Chatterjee and M. P. L. Das, “Property preserving symmetric encryption revisited,” in Advances in Cryptology - ASIACRYPT 2015, T. Iwata and J. H. Cheon, Eds. Berlin, Heidelberg: Springer Berlin Heidelberg, 2015, pp. 658-682.
• [3] M. Naveed, S. Kamara, and C. V. Wright, “Inference attacks on property-preserving encrypted databases,” in Proceedings of the 22Nd ACM SIGSAC Conference on Computer and Communications Security, ser. CCS ’15. New York, NY, USA: ACM, 2015, pp. 644-655. [Online]. Available: http://doi.acm.org/10.1145/2810103.2813651
• [4] A. C. Yao, “Protocols for secure computations.” Washington, DC, USA: IEEE Computer Society, 1982, pp. 160-164.
• [5] C. Gentry, “Fully homomorphic encryption using ideal lattices,” in Proceedings of the Forty-first Annual ACM Symposium on Theory of Computing, ser. STOC ’09. New York, NY, USA: ACM, 2009, pp. 169-178. [Online]. Available: http://doi.acm.org/10.1145/1536414.1536440
• [6] J. Fan and F. Vercauteren, “Somewhat practical fully homomorphic encryption,” Cryptology ePrint Archive, Report 2012/144, 2012, http://eprint.iacr.org/2012/144.
• [7] Z. Brakerski, C. Gentry, and V. Vaikuntanathan, “(leveled) fully homomorphic encryption without bootstrapping,” in Proceedings of the 3rd Innovations in Theoretical Computer Science Conference, ser. ITCS ’12. New York, NY, USA: ACM, 2012, pp. 309-325. [Online]. Available: http://doi.acm.org/10.1145/2090236.2090262
• [8] O. Regev, “On lattices, learning with errors, random linear codes, and cryptography,” in Proceedings of the Thirty-seventh Annual ACM Symposium on Theory of Computing, ser. STOC ’05. New York, NY, USA: ACM, 2005, pp. 84-93. [Online]. Available: http://doi.acm.org/10.1145/1060590.1060603
• [9] X. Meng, S. Kamara, K. Nissim, and G. Kollios, “Grecs: Graph encryption for approximate shortest distance queries,” Cryptology ePrint Archive, Report 2015/266, 2015, http://eprint.iacr.org/2015/266.
• [10] R. M. Karp, Reducibility among Combinatorial Problems. Boston, MA: Springer US, 1972, pp. 85-103. [Online]. Available: http://dx.doi.org/10.1007/978-1-4684-2001-2 9
• [11] C. Aguilar-Melchor, J. Barrier, S. Guelton, A. Guinet, M.-O. Killijian, and T. Lepoint, “NFLlib: NTT-based Fast Lattice Library,” in RSA Conference Cryptographers’ Track, San Francisco, United States, Feb. 2016. [Online]. Available: https://hal.archives-ouvertes.fr/hal-01242273
• [12] K. Laine and R. Player, “Simple encrypted arithmetic library - seal (v2.0),” Tech. Rep., September 2016. [Online]. Available: https://www.microsoft.com/en-us/research/publication/simple-encrypted-arithmetic-library-seal-v2-0/
• [13] W. Stein and D. Joyner, “Sage: system for algebra and geometry experimentation,” ACM SIGSAM Bulletin, vol. 39, no. 2, pp. 61-64, 2005. [Online]. Available: http://modular.math.washington.edu/sage/misc/sage sigsam updated.pdf
• [14] S. Halevi and V. Shoup, Algorithms in HElib. Berlin, Heidelberg: Springer Berlin Heidelberg, 2014, pp. 554-571. [Online]. Available: https://doi.org/10.1007/978-3-662-44371-2 31
• [15] C. Jayet-Griffon, M.-A. Cornelie, P. Maistri, P. Elbaz-Vincent, and R. Leveugle, “Polynomial multipliers for Fully Homomorphic Encryption on FPGA,” in International Conference on ReConFigurable Computing and FPGAs (ReConFig’15), ser. Proceedings IEEE Catalog Number CFP15389-CDR. Mayan Riviera, Mexico: IEEE, Dec. 2015, collection Persyval Lab. [Online]. Available: https://hal.archives-ouvertes.fr/hal-01240658

Uwagi

Opracowanie rekordu w ramach umowy 509/P-DUN/2018 ze środków MNiSW przeznaczonych na działalność upowszechniającą naukę (2018).