Confidential greedy graph algorithm

Daniel Waszkiewicz, Aleksandra Horubała, Piotr Sapiecha, Michał Andrzejczak


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.

Full Text:



R. M. Karp, “Reducibility among combinatorial problems”, in Complexity of Computer Computations: Proceedings of a symposium on the Complexity of Computer Computations, held March 20–22, 1972, at the IBM Thomas J. Watson Research Center, Yorktown Heights, New York, and sponsored by the Office of Naval Research, Mathematics Program, IBM World Trade Corporation, and the IBM Research Mathematical Sciences Department, R. E. Miller, J. W. Thatcher, and J. D. Bohlinger, Eds. Boston, MA: Springer US, 1972, pp. 85–103, ISBN: 978-1-4684-2001-2. DOI: 10.1007/ 978- 1- 4684- 2001- 2 9. [Online]. Available: http://dx. 9.

A. C. Yao, “Protocols for secure computations”, Washington, DC, USA: IEEE Computer Society, 1982, pp. 160–164.

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, Baltimore, MD, USA: ACM, 2005, pp. 84–93, ISBN: 1-58113-960-8. DOI: 10. 1145/1060590.1060603. [Online]. Available: http://doi.

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.

C. Gentry, “Fully homomorphic encryption using ideal lattices”, in Proceedings of the Forty-first Annual ACM Symposium on Theory of Computing, ser. STOC ’09, Bethesda, MD, USA: ACM, 2009, pp. 169–178, ISBN: 978-1-60558-506-2. DOI: 10 . 1145/ 1536414 . 1536440. [Online]. Available: http : / / doi . acm . org / 10 . 1145 / 1536414.1536440.

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, Cambridge, Massachusetts: ACM, 2012, pp. 309–325, ISBN: 978-1-4503-1115-1. DOI: 10 . 1145 / 2090236 . 2090262. [Online]. Available: http:// doi.acm. org/ 10. 1145/2090236.2090262.

J. Fan and F. Vercauteren, Somewhat practical fully homomorphic encryption, Cryptology ePrint Archive, Report 2012/144,, 2012.

S. Halevi and V. Shoup, “Algorithms in helib”, in Advances in Cryptology – CRYPTO 2014: 34th Annual Cryptology Conference, Santa Barbara, CA, USA, August 17-21, 2014, Proceedings, Part I, J. A. Garay and R. Gennaro, Eds. Berlin, Heidelberg: Springer Berlin Heidelberg, 2014, pp. 554–571, ISBN: 978-3- 662-44371-2. DOI: 10.1007/978 - 3 - 662 - 44371 - 2 31. [Online]. Available: 44371-2 31.

X. Liao, S. Uluagac, and R. A. Beyah, “S-match: Verifiable privacy-preserving profile matching for mobile social services”, in 2014 44th Annual IEEE/IFIP International Conference on Dependable Systems and Networks, Jun. 2014, pp. 287–298. DOI: 10.1109/DSN. 2014.37.

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, ISBN: 978-3-662-48800-3.

C. Jayet-Griffon, M.-A. Cornelie, P. Maistri, P. ElbazVincent, 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, collection Persyval Lab., Mayan Riviera, Mexico: IEEE, Dec. 2015. [Online]. JOURNAL OF LATEX CLASS FILES, VOL. 6, NO. 1, JANUARY 2007 6 Available: https : / / hal . archives - ouvertes . fr / hal - 01240658.

X. Meng, S. Kamara, K. Nissim, and G. Kollios, Grecs: Graph encryption for approximate shortest distance queries, Cryptology ePrint Archive, Report 2015/266,, 2015.


  • There are currently no refbacks.

International Journal of Electronics and Telecommunications
is a periodical of Electronics and Telecommunications Committee
of Polish Academy of Sciences

eISSN: 2300-1933