FHE

Fully Homomorphic Encryptions [#t39cef88]

Before Gentry's FHE [#n7f1a036]

  • [[[BGN05-TCC]]] Dan Boneh, Eu-Jin Goh, Kobbi Nissim: Evaluating 2-DNF Formulas on Ciphertexts. TCC 2005
  • [[[GHV10-EC]]] Craig Gentry, Shai Halevi, Vinod Vaikuntanathan: A Simple BGN-Type Cryptosystem from LWE. EUROCRYPT 2010

From Ideal

  • [[[Gen09-STOC]]] Craig Gentry: Fully homomorphic encryption using ideal lattices. STOC 2009
    • Based on ideal lattices. KDM-CPA security serves fully homomorphic encryption by simulating the decryption circuit. The descriptions and several proofs appeared in [[[Gen09-Thesis]]].
  • [[[SV10-PKC]]] N. P. Smart and F. Vercauteren: Fully Homomorphic Encryption with Relatively Small Key and Ciphertext Sizes. PKC 2010, [[ePrint 2009/571:http://eprint.iacr.org/2009/571]]
    • The ciphertext is an element in Z_p by basing the special ideal lattice.
  • [[[Gen10-C]]] Craig Gentry: Toward Basing Fully Homomorphic Encryption on Worst-Case Hardness. CRYPTO 2010
    • See also his thesis.
  • [[[SS10-AC]]] Damien Stehlé and Ron Steinfeld: Faster Fully Homomorphic Encryption. ASIACRYPT 2010, [[ePrint 2010/299:http://eprint.iacr.org/2010/299]]
  • [[[Mik12-Tatra]]] Michal Mikus. Experiments with the plaintext space in Gentry's somewhat homomorphic scheme. Tatra Mountains Mathematical Publications Vol.53, 2012, No.3
    • http://www.sav.sk/journals/uploads/1227125609mikus.pdf

From (Ring/Poly)LWE

  • [[[BV11-C]]] Zvika Brakerski, Vinod Vaikuntanathan: Fully Homomorphic Encryption from Ring-LWE and Security for Key Dependent Messages. CRYPTO 2011
  • [[[BV11-FOCS]]] Zvika Brakerski, Vinod Vaikuntanathan: Efficient Fully Homomorphic Encryption from (Standard) LWE. FOCS 2011
  • [[[BGV12-ITCS]]] Zvika Brakerski, Craig Gentry, Vinod Vaikuntanathan: (Leveled) fully homomorphic encryption without bootstrapping. ITCS 2012
  • [[[Bra12-C]]] Zvika Brakerski: Fully Homomorphic Encryption without Modulus Switching from Classical GapSVP. CRYPTO 2012, [[ePrint 2012/078:http://eprint.iacr.org/2012/078]]
  • [[[FV12]]] Junfeng Fan and Frederik Vercauteren: Somewhat Practical Fully Homomorphic Encryption. [[ePrint 2012/144:http://eprint.iacr.org/2012/144]]
    • Porting the scheme in [[[Bra12-C]]] to Ring-LWE setting.
  • [[[GHPS12-SCN]]]] Craig Gentry, Shai Halevi, Chris Peikert, and Nigel P. Smart: Ring Switching in BGV-Style Homomorphic Encryption. SCN 2012
  • [[[??13-SCIS]]] 早藤智暉, 満保雅浩: 省資源デバイスへの完全準同型暗号の応用. SCIS 2013, 4D1-1 (in Japanese)
  • [[[AP13-C]]] Jacob Alperin-Sheriff and Chris Peikert: Practical Bootstrapping in Quasilinear time. CRYPTO 2013.
  • [[[GSW13-C]]] Craig Gentry and Amit Sahai and Brent Waters: Homomorphic Encryption from Learning with Errors: Conceptually-Simpler, Asymptotically-Faster, Attribute-Based. CRYPTO 2013, [[ePrint 2013/340:http://eprint.iacr.org/2013/340]]
  • [[[BV14-ITCS]]] Zvika Brakerski, Vinod Vaikuntanathan: Lattice-Based FHE as Secure as PKE. ITCS 2014, [[ePrint 2013/541:http://eprint.iacr.org/2013/541]]
    • Gen, Enc, and Dec are the same as those of [[[GSW13-C]]]. The key points are careful analysis of noises and use of branching programs.
  • [[[ZXJXZ13-FGCS]]] Xiaojun Zhang, Chunxiang Xua, Chunhua Jina, Run Xie, Jining Zhao: Efficient fully homomorphic encryption from RLWE with an extension to threshold encryption scheme (Future Generation Computer Systems. In Press, Accepted Manuscript)
    • http://www.sciencedirect.com/science/article/pii/S0167739X13002422

From NTRU-Like Enc.

  • [[[LTV12-STOC]]] Adriana López-Alt, Eran Tromer, Vinod Vaikuntanathan: On-the-Fly Multiparty Computation on the Cloud via Multikey Fully Homomorphic Encryption. STOC 2012, [[ePrint 2013/094:http://eprint.iacr.org/2013/094]]
    • NTRU-based FHE allows multi-key operations.
  • [[[BLLN13-eP]]] Joppe W. Bos and Kristin Lauter and Jake Loftus and Michael Naehrig: Improved Security for a Ring-Based Fully Homomorphic Encryption Scheme. [[ePrint 2013/075:http://eprint.iacr.org/2013/075]]
    • ... Removing the strong assumption by bit-docomp.

From approximate GCD and its variants

  • [[[vDGHV10-EC]]] Marten van Dijk, Craig Gentry, Shai Halevi, and Vinod Vaikuntanathan: Fully Homomorphic Encryption over the Integers. EUROCRYPT 2010, [[ePrint 2009/616:http://eprint.iacr.org/2009/616]]
    • This variant is not based on the lattice but has a similar structure to the Regev03 encryption scheme [[[Reg04]]].
  • [[[CMNT11-C]]] Jean-Sébastien Coron, Avradip Mandal, David Naccache, Mehdi Tibouchi: Fully Homomorphic Encryption over the Integers with Shorter Public Keys. CRYPTO 2011
    • |pk| \in [1,800] MB
  • [[[CNT12-EC]]] Jean-Sébastien Coron, David Naccache, Mehdi Tibouchi: Public Key Compression and Modulus Switching for Fully Homomorphic Encryption over the Integers. EUROCRYPT 2012
  • [[[CLT13-eP]]] Jean-Sébastien Coron and Tancrède Lepoint and Mehdi Tibouchi: Batch Fully Homomorphic Encryption over the Integers ?[[ePrint 2013/036:https://eprint.iacr.org/2013/036]]
  • [[[KLYC13-eP]]] Jinsu Kim, Moon Sung Lee, Aaram Yun, Jung Hee Cheon: CRT-based Fully Homomorphic Encryption over the Integers. [[ePrint 2013/057:https://eprint.iacr.org/2013/057]]
  • [[[MHMONOSC13-WAHC]]] Ciara Moore, Neil Hanley, John McAllister, Máire O'Neill, Elizabeth O'Sullivan and Xiaolin Cao: Targeting FPGA DSP Slices for a Large Integer Multiplier for Integer Based FHE. WAHC 2013
  • [[[CCKLLTY13-EC]]] Jung Hee Cheon, Jean-Sébastien Coron, Jinsu Kim, Moon Sung Lee, Tancrède Lepoint, Mehdi Tibouchi, and Aaram Yun: Batch Fully Homomorphic Encryption over the Integers. EUROCRYPT 2013
    • Merged version of [[[KLYC13-eP]]] and [[[CLT13-eP]]]

Attacks or Estimations

  • [[[Ngu11-CANS]]] Phong Q. Nguyen: Breaking Fully-Homomorphic-Encryption Challenges. CANS 2011
  • [[[CN12-EC]]] Yuanmi Chen, Phong Q. Nguyen: Faster Algorithms for Approximate Common Divisors: Breaking Fully-Homomorphic-Encryption Challenges over the Integers. EUROCRYPT 2012
  • [[[YYSK12-EuroPKI]]] Masaya Yasuda, Jun Yajima, Takeshi Shimoyama, Jun Kogure: Analysis of Lattice Reduction Attack against the Somewhat Homomorphic Encryption Based on Ideal Lattices. EuroPKI 2012

  • [[[ZPS11-ICISC]]] Z. Zhang, T. Plantard and W. Susilo: Reaction Attack on Outsourced Computing with Fully Homomorphic Encryption Schemes. ICISC 2011

  • [[[ZPS12-ISPEC]]] Z. Zhang, T. Plantard and W. Susilo: On the CCA-1 Security of Somewhat Homomorphic Encryption over the Integers. ISPEC 2012

Implementations

  • [[[OYKU10-IWSEC]]] N. Ogura, G. Yamamoto, T. Kobayashi, and S. Uchiyama: An Improvement of Key Generation Algorithm for Gentry's Homomorphic Encryption Scheme. IWSEC 2010
  • [[[GH11-EC]]] Craig Gentry, Shai Halevi: Implementing Gentry's Fully-Homomorphic Encryption Scheme. EUROCRYPT 2011
  • [[[GH11-FOCS]]] Craig Gentry, Shai Halevi: Fully Homomorphic Encryption without Squashing Using Depth-3 Arithmetic Circuits. FOCS 2011
  • [[[GHS12-PKC]]] Craig Gentry, Shai Halevi, Nigel P. Smart: Better Bootstrapping in Fully Homomorphic Encryption. PKC 2012
  • [[[GHS12-EC]]] Craig Gentry, Shai Halevi, Nigel P. Smart: Fully Homomorphic Encryption with Polylog Overhead. EUROCRYPT 2012
  • [[[HYWX12-IMCCC]]] Jing-Li Han, Ming Yang, Cai-Ling Wang, Shan-Shan Xu: The Implemention and Application of Fully Homomorphic Encryption Scheme. IMCCC 2012
  • [[[BGH13-PKC]]] Zvika Brakerski, Craig Gentry, and Shai Halevi: Packed Ciphertexts in LWE-based Homomorphic Encryption. PKC 2013.
  • [[[YSYK13-SCIS-a]]] 安田雅哉, 下山武司, 横山和弘, 小暮淳: イデアル格子準同型暗号を用いた秘匿内積の実装. SCIS 2013, 1A2-1 (in Japanese)
  • [[[YSYK13-SCIS-b]]] 安田雅哉, 下山武司, 横山和弘, 小暮淳: イデアル格子準同型暗号を用いた秘匿内積計算. SCIS 2013, 2A3-2 (in Japanese)

From Code

  • [[[AAPS11-IMACC]]] Frederik Armknecht, Daniel Augot, Ludovic Perret, Ahmad-Reza Sadeghi: On Constructing Homomorphic Encryption Schemes from Coding Theory. IMA CC 2011, [[ePrint 2011/309:http://eprint.iacr.org/2011/309]]
    • symmetric-key bounded-homomorphic encryption from code
    • they showed impossibility results.
  • [[[BL11-eP]]] Andrej Bogdanov and Chin Ho Lee: Homomorphic encryption from codes. [[ePrint 2011/622:http://eprint.iacr.org/2011/622]]
    • ? Cryptanalysis of the Bogdanov-Lee Cryptosystem by Gottfried Herold
    • I found this attack from Gauthier's talk at CBC 2012. See http://cbc2012.mat.dtu.dk/slides/Gauthier.pdf
  • [[[GOT12-eP]]] Valéerie Gauthier and Ayoub Otmani and Jean-Pierre Tillich: A Distinguisher-Based Attack of a Homomorphic Encryption Scheme Relying on Reed-Solomon Codes. [[ePrint 2012/168:http://eprint.iacr.org/2012/168]]
    • cryptanalysis of [[[BL11-eP]]]
  • [[[Bra13-TCC]]] Zvika Brakerski: When Homomorphism Becomes a Liability. TCC 2013, [[ePrint 2012/225:http://eprint.iacr.org/2012/225]]
    • cryptanalysis of [[[BL11-eP]]]

From MQ?

  • Fellows and Koblitz: Polly Cracker.
  • [[[AFFP11-AC]]] Martin R. Albrecht, Pooya Farshim, Jean-Charles Faugère, Ludovic Perret: Polly Cracker, Revisited. ASIACRYPT 2011
  • [[[Her12-PKC]]] Gottfried Herold: Polly Cracker, Revisited, Revisited. PKC 2012
  • [[[AFFHP11-eP]]] Martin R. Albrecht, Jean-Charles Faugère and Pooya Farshim and Gottfried Herold and Ludovic Perret: Polly Cracker, Revisited [[ePrint 2011/289:http://eprint.iacr.org/2011/289]]
    • '''Publication Info: short version appeared at ASIACRYPT 2011, corrections appeared at PKC 2012'''

Fully-Homomorphic Symmetric-Key Encryptions

  • [[[KH12-eP]]] Aviad Kipnis and Eliphaz Hibshoosh: Efficient Methods for Practical Fully Homomorphic Symmetric-key Encrypton, Randomization and Verification. [[ePrint 2012/637:http://eprint.iacr.org/2012/637]]
    • Matrix-based symmetric-key encryption.
  • [[[HP13-CTRSA]]] Michal Hojsík and Veronika Půlpánová: A Fully Homomorphic Cryptosystem with Approximate Perfect Secrecy. CT-RSA 2013
    • Poly-Cracker-like Sym. Enc.

Conversion from FH-SKE to FH-PKE

  • [[[Roth11-TCC]]] Ron Rothblum: Homomorphic Encryption: from Private-Key to Public-Key. TCC 2011, [[ECCC TR10-146:http://eccc.hpi-web.de/report/2010/146/]]
  • [[[Kun11-SCIS]]] Noboru Kunihiro: 準同型な共通鍵暗号から準同型な公開鍵暗号への変換法. SCIS 2011, 3F1-3 (in Japanese)
    • An independent proposal of a very similar idea in [[[Roth11-TCC]]].
  • [[[TCS13-SCIS]]] 高橋大樹, 千田栄幸, 静谷啓樹: 完全準同型暗号の構成法に関する考察. SCIS 2013, 1A2-4 (in Japanese)
    • A FHE proposal based on [[[KH12-eP]]].

Theory

  • [[[KTZ13-PKC]]] Jonathan Katz, Aishwarya Thiruvengadam, Hong-Sheng Zhou: Feasibility and Infeasibility of Adaptively Secure Fully Homomorphic Encryption. PKC 2013

tmp

  • [[[SS11-IMACC]]] Peter Scholl, Nigel P. Smart: Improved Key Generation for Gentry's Fully Homomorphic Encryption Scheme. IMA CC. 2011, [[ePrint 2011/471:http://eprint.iacr.org/2011/471]]
  • [[[SV12-DCC]]] Nigel P. Smart, Frederik Vercauteren: Fully homomorphic SIMD operations. Designs, Codes, and Cryptography 2012 online-first, [[ePrint 2011/133:http://eprint.iacr.org/2011/133]]
  • [[[LMSV11-SAC]]] Jake Loftus, Alexander May, Nigel P. Smart, Frederik Vercauteren: On CCA-Secure Somewhat Homomorphic Encryption. Selected Areas in Cryptography 2011, [[ePrint 2010/560:http://eprint.iacr.org/2010/560]]
  • [[[AKP12-Africa]]] Frederik Armknecht, Stefan Katzenbeisser, Andreas Peter: Shift-Type Homomorphic Encryption and Its Application to Fully Homomorphic Encryption. AFRICACRYPT 2012
  • [[[JPU12-IJCIS]]] Nitin Jain, Saibal K. Pal and Dhananjay K. Upadhyay: Implementation and Analysis of Homomorphic Encryption Schemes. International Journal on Cryptography and Information Security (IJCIS) 2012, Vol. 2, No. 2
    • http://airccse.org/journal/ijcis/papers/2212ijcis03.pdf
    • An implementation of Gentry09.
  • [[[CRPS12-HPEC]]] David Cousins, Kurt Rohloff, Chris Peikert, Richard E. Schantz: An update on SIPHER (Scalable Implementation of Primitives for Homomorphic EncRyption) - FPGA implementation using Simulink. HPEC 2012
  • [[[LP13-WAHC]]] Tancrède Lepoint and Pascal Paillier: On the Minimal Number of Bootstrappings in Homomorphic Circuits. WAHC 2013
  • [[[ASP13-C]]] Jacob Alperin-Sheriff and Chris Peikert: Practical Bootstrapping in Quasilinear time. CRYPTO 2013
  • [[[YSKYK13]]] Masaya Yasuda, Takeshi Shimoyama, Jun Kogure, Kazuhiro Yokoyama. Takeshi Koshiba: Secure pattern matching using somewhat homomorphic encryption. (CCSW2013)
  • [[[PSZ13]]] T. Plantard, W. Susilo, Z. Zhang: Fully Homomorphic Encryption Using Hidden Ideal Lattice (IEEE Transactions on Infor. Forensics and Secrity (Volume:8 , Issue: 12 ))

Polly Cracker [#ec3f70cd]

  • M. R. Fellows and N. Koblitz: Combinatorial cryptosystems galore! Comtemporary Math. 168 51-61, 1994
  • Rainer Steinwandt and Willi Geiselmann: Cryptanalysis of Polly Cracker. IEEE IT, 2002.
  • Dennis Hofheinz and Rainer Steinwandt: A ``Differential'' Attack on Polly Cracker. ...?
  • Le Van Ly: Polly Two: A Public-Key Cryptosystem based on Polly Cracker. PhD Thesis, 2002
  • Massimo Caboara, Fabrizio Caruso, Carlo Traverso: Lattice Polly Cracker cryptosystems. Journal of Symbolic Computation, vol. 46, Issue 5, May, 2011
Written on January 1, 2000