Fully Homomorphic Encryption: de geschiedenis

Dit bericht is deel 2 van de serie Fully Homomorphic Encryption.
HE heeft al een behoorlijke geschiedenis en is op verschillende manieren aangevlogen. Er is jarenlang geprobeerd om FHE werkend te krijgen, zonder succes. Totdat Craig Gentry bij IBM in oktober 2008 de eerste volledig homomorfe encryptie had bedacht.
Thomas van den Nieuwenhoff

Thomas van den Nieuwenhoff

Security Blogger voor SALT Cyber Security en student HBO-ICT Infrastructure Design & Security op Windesheim.
De pre-FHE generatie speelt zich af voor 2007. De eerste generatie speelt tussen 2009 en 2010, de tweede tussen 2011 en 2012, de derde tussen 2013 en 2016. De vierde en huidige generatie begint in 2017.
De verschillende FHE-generaties op een tijdlijn.

Pre-FHE

Voor zover men weet, bestaat het idee dat homomorfe encryptie gebruikt kan worden voor het beschermen van data al decennia3. Het probleem van het vormen van een volledig homomorfe encryptie, werd voor het eerste voorgesteld in 19784. Er werden speciale encryptie functies genaamd “privacy homomorphisms” voorgesteld. De auteurs bespreken het gebruiken van hardware om data veilig te verwerken. De data zouden dan alleen ontcijferd worden op een fysiek veilige processor. Op deze manier wordt de data altijd versleuteld wanneer het de processor verlaat (bv. wanneer het naar het geheugen wordt verplaatst). Het probleem met deze soort chips, is dat het op maat gemaakte hardware is, duur om te implementeren en altijd nog een decoderingssleutel nodig heeft. Voor meer dan 30 jaar was het onduidelijk of er een oplossing bestond voor dit probleem. In die periode zijn er een aantal gedeeltelijke oplossingen verschenen1:

  • RSA-cryptosysteem (onbeperkt aantal modulaire vermenigvuldigingen);
  • ElGamal cryptosysteem (onbeperkt aantal modulaire vermenigvuldigingen);
  • Goldwasser-Micali cryptosysteem (onbeperkt aantal XOR-operaties);
  • Benaloh cryptosysteem (onbeperkt aantal modulaire toevoegingen);
  • Paillier cryptosysteem (onbeperkt aantal modulaire toevoegingen);
  • Sander-Young-Yung-systeem (loste na meer dan 20 jaar het probleem op voor logaritmische diepteschakelingen)25;
  • Boneh-Goh-Nissim cryptosysteem (onbeperkt aantal optelbewerkingen, maar maximaal één vermenigvuldiging)26;
  • Ishai-Paskin cryptosysteem (vertakkingsprogramma’s van polynoomgrootte)27.

Eerste generatie FHE

Craig Gentry beschreef de eerste plausibele constructie voor een volledig homomorfe encryptie met behulp van op roosters gebaseerd cryptografie* 1,5. Gentry’s constructie ondersteunt zowel optel- als vermenigvuldigingsbewerkingen op versleutelde teksten, van waaruit het mogelijk is om schakelingen te maken voor het uitvoeren van willekeurige berekeningen. De constructie volgt een aantal stappen waarin eerst ruis** wordt geïntroduceerd en vervolgens wordt gereduceerd. Hierdoor is het mogelijk om een willekeurig aantal optellingen en vermenigvuldigen te berekenen zonder de ruis te veel te verhogen. De Gentry-Halevi implementatie van Gentry’s originele cryptosysteem rapporteerde een timing van ongeveer 30 minuten per simpele bit operatie6. Uitgebreide ontwerp- en implementatiewerkzaamheden in de daaropvolgende jaren, hebben de runtime-prestaties van deze vroege implementaties met vele ordes van grootte verbeterd.

 

In 2010 presenteerde Marten van Dijk, Craig Gentry, Shai Halevi en Vinod Vaikuntanathan7 een tweede volledig homomorf encryptieschema, wat veel van de tools van Gentry’s constructie gebruikt.

 

* Zie voor een goede uitleg van op roosters gebaseerde cryptografie de Wikipediapagina ‘Lattice-based cryptography’.

** Door de cryptografische bewerkingen bevat elke cijfertekst een hoeveelheid ruis1. Deze ruis groeit wanneer cijferteksten bij elkaar opgeteld of met elkaar vermenigvuldigd worden, totdat de ruis de cijfertekst uiteindelijk niet meer ontcijferbaar maakt.

Tweede generatie FHE

De homomorfe cryptosystemen die momenteel worden gebruikt, zijn afgeleid van technieken die vanaf 2011-2012 zijn ontwikkeld door Zvika Brakerski, Craig Gentry, Vinod Vaikuntanathan en anderen1. Deze innovaties leidden tot de ontwikkeling van veel efficiëntere enigszins en volledig homomorfe cryptosystemen. Deze omvatten:

  • Het Brakerski-Gentry-Vaikuntanathan-schema8, voortbouwend op technieken van Brakerski-Vaikuntanathan9;
  • Het op NTRU*** gebaseerde schema van Lopez-Alt, Tromer en Vaikuntanathan (LTV)10;
  • Het Brakerski/Fan-Vercauteren-schema11, wat voortbouwt op Brakerski’s schaal-invariante cryptosysteem12;
  • Het op NTRU*** gebaseerde schema van Bos, Lauter, Loftus en Naehrig (BLNN)13, voortbouwend op het schaal-invariante cryptosysteem van LTV en Brakerski12.

 

De beveiliging van de meeste van deze schema’s, is gebaseerd op de hardheid van het (Ring) Leren Met Fouten (Engels: Ring Learning With Errors of RLWE) probleem. Behalve de LTV- en BLLN-schema’s, want die vertrouwen op een overbelaste14 variant van het NTRU-rekenprobleem*** 15. Deze NTRU-variant bleek vervolgens kwetsbaar te zijn voor sub-veldroosteraanvallen, en daarom worden deze twee schema’s in de praktijk niet meer gebruikt.

 

Alle cryptosystemen van de tweede generatie volgen nog steeds de basisblauwdruk van de oorspronkelijke constructie van Gentry. Ze construeren namelijk eerst een ietwat homomorf cryptosysteem en converteren het vervolgens naar een volledig homomorf cryptosysteem met behulp van ‘bootstrapping’.

 

Een onderscheidend kenmerk van de tweede generatie cryptosystemen is dat ze allemaal een veel langzamere groei van de ruis vertonen tijdens de homomorfe edit-berekeningen. Een ander kenmerk is dat ze efficiënt genoeg zijn voor veel toepassingen, zelfs zonder ‘bootstrapping’ aan te roepen, in plaats daarvan opereren ze in de ‘leveled’ FHE-modus.

 

*** NTRU is een open source public-key cryptosysteem wat op roosters gebaseerde cryptografie gebruikt om gegevens te coderen en decoderen16.

Derde generatie FHE

In 2013 stelden Craig Gentry, Amit Sahai en Brent Waters (GSW) een nieuwe techniek voor, voor het bouwen van FHE-schema’s die een dure stap van ‘relinearisering’ bij homomorfe vermenigvuldigingen vermijden17. Zvika Brakerski en Vinod Vaikuntanathan merkten op dat het GSW-cryptosysteem, voor bepaalde typen schakelingen, een nog langzamere groeisnelheid van ruis vertoont18. Dit geeft dus een betere efficiëntie en sterkere beveiliging. Jacob Alperin-Sheriff en Chris Peikert beschreven vervolgens een zeer efficiënte ‘bootstrapping’-techniek op basis van deze observatie19.

 

Deze technieken werden verder verbeterd om efficiënte ringvarianten van het GSW-cryptosysteem te ontwikkelen. Hier kwamen het FHEW-20 en TFHE-schema21 uit voort. Het FHEW-schema was het eerste wat aantoonde dat door de versleutelde teksten na elke bewerking te vernieuwen, het mogelijk is om de ‘bootstrapping’-tijd terug te brengen tot een fractie van een seconde. FHEW introduceerde een nieuwe methode om Booleaanse poorten op versleutelde gegevens te berekenen. Hiermee werd ‘bootstrapping’ aanzienlijk vereenvoudigt en werd een variant van de ‘bootstrapping’-methode geïmplementeerd19. De efficiëntie van FHEW werd verder verbeterd door het TFHE-schema, wat een ringvariant van de ‘bootstrapping’-procedure22 implementeert met behulp van een methode die vergelijkbaar is met die in FHEW.

Vierde generatie FHE

Het CKKS-schema23 ondersteunt efficiënte afrondings-bewerkingen in versleutelde toestand1. De afrondings-bewerking regelt de toename van de ruis bij gecodeerde vermenigvuldiging, waardoor het aantal ‘bootstrapping’ in een schakeling wordt verminderd. In Crypto2018 is op CKKS gefocust als een oplossing voor versleutelde machine learning. Dit komt door een kenmerk van het CKKS-schema dat geschatte waarden codeert in plaats van exacte waarden. Wanneer computers gegevens met een reële waarde opslaan, onthouden ze waarden bij benadering met lange significante bits, niet exact met werkelijke waarden. Het CKKS-schema is ontworpen om efficiënt om te gaan met de fouten die voortvloeien uit de benaderingen. Het schema is bekend bij machine learning, wat inherent ruis in zijn structuur heeft. Ieder schema heeft zo zijn sterke en zwakke punten.

 

Doordat CKKS met afgeronde waarden werkt, in plaats van exacte is het mogelijk dat hierdoor kwetsbaarheden ontstaan. Een artikel uit 2021 van Baiyu Li en Daniele Micciancio bespreekt passieve aanvallen tegen CKKS24. De auteurs passen de aanval toe op vier moderne homomorfe encryptie libraries (HEAAN, SEAL, HElib en PALISADE) en melden dat het mogelijk is om de geheime sleutel te herstellen in verschillende parameter-configuraties. Volgens het artikel zou een mogelijke beperking, het bijwerken van het encryptiealgoritme van CKKS vereisen om te voorkomen dat de encryptieruis van een versleutelde tekst wordt achterhaald.

  1. Wikipedia contributors, “Homomorphic Encryption”, Wikipedia, The Free Encyclopedia, 2021. [Online]. Available: https://en.wikipedia.org/w/index.php?title=Homomorphic_encryption&oldid=1002934075.
  2. V. Vaikuntanathan, “Homomorphic Encryption: WHAT, WHY, and HOW”, 2012. Available: https://www.cs.toronto.edu/~vinodv/Homomorphic-MCSS.pptx.
  3. M. Will and R. Ko, “A guide to homomorphic encryption”, in The Cloud Security Ecosystem, R. Ko and R. Choo, Ed. 2015.
  4. R.L. Rivest, L. Adleman, M.L. Dertouzos, “On Data Banks and Privacy Homomorphisms”, Foundations of Secure Computation, 1978. Available: https://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.500.3989&rep=rep1&type=pdf.
  5. C. Gentry, “Fully Homomorphic Encryption Using Ideal Lattices”, 41st ACM Symposium on Theory of Computing (STOC), 2009. Available: https://www.cs.cmu.edu/~odonnell/hits09/gentry-homomorphic-encryption.pdf.
  6. C. Gentry, S. Halevi, “Implementing Gentry’s Fully-Homomorphic Encryption Scheme”, 2011. [Online]. Available: https://eprint.iacr.org/2010/520.pdf.
  7. M. van Dijk, C. Gentry, S. Halevi, V. Vaikuntanathan, “Fully Homomorphic Encryption over the Integers”, Eurocrypt 2010, 2010. Available: https://eprint.iacr.org/2009/616.pdf.
  8. Z. Brakerski, C. Gentry, V. Vaikuntanathan, “Fully Homomorphic Encryption without Bootstrapping”, ITCS 2012, 2011. Available: https://eprint.iacr.org/2011/277.pdf.
  9. Z. Brakerski, V. Vaikuntanathan, “Efficient Fully Homomorphic Encryption from (Standard) LWE”, FOCS 2011, 2011. Available: https://eprint.iacr.org/2011/344.pdf.
  10. A. Lopez-Alt, E. Tromer, V. Vaikuntanathan, “On-the-Fly Multiparty Computation on the Cloud via Multikey Fully Homomorphic Encryption”, STOC 2012, 2013. Available: https://eprint.iacr.org/2013/094.pdf.
  11. J. Fan, F. Vercauteren, “Somewhat Practical Fully Homomorphic Encryption”, 2012. [Online]. Available: https://eprint.iacr.org/2012/144.pdf.
  12. Z. Brakerski, “Fully Homomorphic Encryption without Modulus Switching from Classical GapSVP”, CRYPTO 2012, 2012. Available: https://eprint.iacr.org/2012/078.pdf.
  13. J. Bos, K. Lauter, J. Loftus, M. Naehrig, “Improved Security for a Ring-Based Fully Homomorphic Encryption Scheme”, IMACC 2013, 2013. Available: https://eprint.iacr.org/2013/075.pdf.
  14. M. Albrecht, S. Bai, L. Ducas, “A subfield lattice attack on overstretched NTRU assumptions”, CRYPTO 2016, 2016. Available: https://eprint.iacr.org/2016/127.pdf.
  15. J.H. Cheon, J. Jeong, C. Lee, “An algorithm for NTRU problems and cryptanalysis of the GGH multilinear map without a low-level encoding of zero”, LMS Journal of Computation and Mathematics, vol. 19, no. A, pp. 255-266, 2016. Available: https://www.cambridge.org/core/journals/lms-journal-of-computation-and-mathematics/article/an-algorithm-for-ntru-problems-and-cryptanalysis-of-the-ggh-multilinear-map-without-a-lowlevel-encoding-of-zero/230ECFEEE6AF4D8027FF3E13998D560C.
  16. Wikipedia contributors, “NTRU”, Wikipedia, The Free Encyclopedia, 2020. [Online]. Available: https://en.wikipedia.org/w/index.php?title=NTRU&oldid=997278152.
  17. C. Gentry, A. Sahai, B. Waters, “Homomorphic Encryption from Learning with Errors: Conceptually-Simpler, Asymptotically-Faster, Attribute-Based”, CRYPTO 2013, 2013. Available: https://eprint.iacr.org/2013/340.pdf.
  18. Z. Brakerski, V. Vaikuntanathan, “Lattice-Based FHE as Secure as PKE”, ITCS 2014, 2013. Available: https://eprint.iacr.org/2013/541.pdf.
  19. J. Alperin-Sheriff, C. Peikert, “Faster Bootstrapping with Polynomial Error”, CRYPTO 2014, 2014. Available: https://eprint.iacr.org/2014/094.pdf.
  20. L. Ducas, D. Micciancio, “FHEW: A Fully Homomorphic Encryption library”, 2014. [Online]. Available: https://github.com/lducas/FHEW/tree/0959af.
  21. S. Carpov, I. Chillotti, N. Gama, M. Georgieva, M. Izabachene, “TFHE: Fast Fully Homomorphic Encryption Library”, 2016. [Online]. Available: https://tfhe.github.io/tfhe/. [Accessed 9 February 2021].
  22. N. Gama, M. Izabachene, P.Q. Nguyen, X. Xie, “Structural Lattice Reduction: Generalized Worst-Case to Average-Case Reductions and Homomorphic Cryptosystems”, EUROCRYPT 2016, 2014. Available: https://eprint.iacr.org/2014/283.pdf.
  23. J.H. Cheon, A. Kim, M. Kim, Y. Song, “Homomorphic Encryption for Arithmetic of Approximate Numbers”, ASIACRYPT 2017, pp. 409-437, 2017. Available: https://link.springer.com/content/pdf/10.1007/978-3-319-70694-8_15.pdf.
  24. B. Li, D. Micciancio, “On the Security of Homomorphic Encryption on Approximate Numbers”, 2020. [Online]. Available: https://eprint.iacr.org/2020/1533.pdf.
  25. T. Sander, A.L. Young, M. Yung, “Non-Interactive CryptoComputing For NC1”, pp. 554-566, 1999.
  26. D. Boneh, E.J. Goh, K. Nissim, “Evaluating 2-DNF Formulas on Ciphertexts“, Theory of Cryptography Conference, 2005. Available: https://link.springer.com/content/pdf/10.1007/978-3-540-30576-7_18.pdf.
  27. Y. Ishai, A. Paskin, “Evaluating Branching Programs on Encrypted Data“, Theory of Cryptography, 2007. Available: https://link.springer.com/content/pdf/10.1007%2F978-3-540-70936-7_31.pdf.