{"id":899,"date":"2020-10-06T15:44:33","date_gmt":"2020-10-06T13:44:33","guid":{"rendered":"https:\/\/www.uni.lu\/snt-fr\/events\/phd-defense-homomorphic-encryption-and-multilinear-maps-based-on-the-approximate-gcd-problem\/"},"modified":"2020-10-06T15:44:33","modified_gmt":"2020-10-06T13:44:33","slug":"phd-defense-homomorphic-encryption-and-multilinear-maps-based-on-the-approximate-gcd-problem","status":"publish","type":"events","link":"https:\/\/www.uni.lu\/snt-fr\/events\/phd-defense-homomorphic-encryption-and-multilinear-maps-based-on-the-approximate-gcd-problem\/","title":{"rendered":"PhD Defense: Homomorphic Encryption and Multilinear Maps Based on the Approximate-GCD Problem"},"content":{"rendered":"<section class=\"wp-block-unilux-blocks-free-section section\"><div class=\"container xl:max-w-screen-xl\"><p>Please <a href=\"https:\/\/unilu.webex.com\/unilu\/onstage\/g.php?MTID=eafda58f644a0477d9fb4896e4b9151aa\" target=\"_self\" title=\"\" rel=\"noopener\">click on this link<\/a> to both register and connect on the day of the event.<\/p><p><strong>Members of the defence committee:<\/strong><\/p><ul class=\"ulux-list\"><li class=\"ulux-list-item\">Chairman : Prof. Dr Alex Biryukov, Universit\u00e9 du Luxembourg<\/li><li class=\"ulux-list-item\">Vice-chairman : A.-Prof. Dr Volker M\u00fcller, Universit\u00e9 du Luxembourg<\/li><li class=\"ulux-list-item\">Supervisor : Prof. Dr Jean-S\u00e9bastien Coron, Universit\u00e9 du Luxembourg<\/li><li class=\"ulux-list-item\">Member: Prof. Dr Frederik Vercauteren, Katholieke Universteit Leuven, Belgium<\/li><li class=\"ulux-list-item\">Member: A-Prof. Dr Diego F. Aranha, Aarhus University, Denmark<\/li><\/ul><p><strong>Abstract:<\/strong><\/p><p>Cryptographic schemes are constructed on top of problems that are believed to be hard. In particular, recent advanced schemes, as homomorphic primitives and obfuscators, use the approximate greatest common divisor (AGCD) problem, which is simple to describe and easy to implement, since it does not require complex algebraic structures nor hard-to-sample probability distributions. However, in spite of its simplicity, the AGCD problem generally yields inefficient schemes, usually with large ciphertext expansion.<\/p><p>In this thesis, we analyze the AGCD problem and several existing variants thereof and propose a new attack on the multi-prime AGCD problem. <\/p><p>Then, we propose two new variants:<\/p><p>1. The vector AGCD problem (VAGCD), in which AGCD instances are represented as vectors and randomized with a secret random matrix;<\/p><p>2. The polynomial randomized AGCD problem (RAGCD), that consists of representing AGCD samples as polynomials and randomizing them with a secret random polynomial.<\/p><p>We show that these new variants cannot be easier than the original AGCD problem and that all the known attacks, when adapted to the VAGCD and the RAGCD problem, are more expensive both in terms of time and of memory, allowing us then to chose smaller parameters and to improve the efficiency of the schemes using the AGCD as the underlying problem. Thus, by combining techniques from multilinear maps and indistinguishability obfuscation with the VAGCD problem, we provide the first implementation of a N-party non-interactive key exchange resistant against all known attacks. Still aiming to show that the VAGCD problem can lead to performance improvements in cryptographic primitives, we use it to construct a homomorphic encryption scheme that can natively and efficiently operate with vectors and matrices. For instance, for 100 bits of security, we can perform a sequence of 128 homomorphic products between 128-dimensional vectors and 128&#215;128 matrices in less than one second. We also use our scheme in two applications: homomorphic evaluation of nondeterministic finite automata and a Na\u00efve Bayes classifier.<\/p><p>Finally, using the RAGCD problem, we construct a new homomorphic scheme for polynomials and we propose new fast bootstrapping procedures for fully homomorphic scheme (FHE) over the integers. Therewith, we can for the first time bootstrap AGCD-based FHE schemes in less than one second in a common personal computer. For the best of our knowledge, only FHE schemes based on the LWE problem had subsecond bootstrapping procedures, while AGCD-based schemes required several seconds or even minutes to be bootstrapped.<\/p><\/div><\/section>","protected":false},"excerpt":{"rendered":"","protected":false},"author":0,"featured_media":900,"parent":0,"menu_order":0,"comment_status":"open","ping_status":"closed","template":"","format":"standard","meta":{"featured_image_focal_point":[],"show_featured_caption":false,"ulux_newsletter_groups":"","uluxPostTitle":"","uluxPrePostTitle":"","_trash_the_other_posts":false,"_price":"","_stock":"","_tribe_ticket_header":"","_tribe_default_ticket_provider":"","_tribe_ticket_capacity":"0","_ticket_start_date":"","_ticket_end_date":"","_tribe_ticket_show_description":"","_tribe_ticket_show_not_going":false,"_tribe_ticket_use_global_stock":"","_tribe_ticket_global_stock_level":"","_global_stock_mode":"","_global_stock_cap":"","_tribe_rsvp_for_event":"","_tribe_ticket_going_count":"","_tribe_ticket_not_going_count":"","_tribe_tickets_list":"[]","_tribe_ticket_has_attendee_info_fields":false,"event_start_date":"2020-10-20 10:00:00","event_end_date":"2020-10-20 12:00:00","event_speaker_name":"Vitor Pereira","event_speaker_link":"","event_is_online":false,"event_location":"","event_street":"","event_location_link":"","event_zip_code":"","event_city":"","event_country":"LU"},"events-topic":[],"events-type":[],"organisation":[183],"authorship":[],"acf":[],"yoast_head":"<!-- This site is optimized with the Yoast SEO Premium plugin v22.3 (Yoast SEO v22.3) - https:\/\/yoast.com\/wordpress\/plugins\/seo\/ -->\n<title>PhD Defense: Homomorphic Encryption and Multilinear Maps Based on the Approximate-GCD Problem - SnT - Universit\u00e9 du Luxembourg I Uni.lu<\/title>\n<meta name=\"robots\" content=\"index, follow, max-snippet:-1, max-image-preview:large, max-video-preview:-1\" \/>\n<link rel=\"canonical\" href=\"https:\/\/www.uni.lu\/snt-fr\/events\/phd-defense-homomorphic-encryption-and-multilinear-maps-based-on-the-approximate-gcd-problem\/\" \/>\n<meta property=\"og:locale\" content=\"fr_FR\" \/>\n<meta property=\"og:type\" content=\"article\" \/>\n<meta property=\"og:title\" content=\"PhD Defense: Homomorphic Encryption and Multilinear Maps Based on the Approximate-GCD Problem\" \/>\n<meta property=\"og:url\" content=\"https:\/\/www.uni.lu\/snt-fr\/events\/phd-defense-homomorphic-encryption-and-multilinear-maps-based-on-the-approximate-gcd-problem\/\" \/>\n<meta property=\"og:site_name\" content=\"SnT FR\" \/>\n<meta property=\"og:image\" content=\"https:\/\/www.uni.lu\/wp-content\/uploads\/sites\/13\/2026\/03\/03112647\/SNT_SM-Profile_1600x1600px-scaled.jpg\" \/>\n\t<meta property=\"og:image:width\" content=\"2560\" \/>\n\t<meta property=\"og:image:height\" content=\"2560\" \/>\n\t<meta property=\"og:image:type\" content=\"image\/jpeg\" \/>\n<meta name=\"twitter:card\" content=\"summary_large_image\" \/>\n<meta name=\"twitter:label1\" content=\"Dur\u00e9e de lecture estim\u00e9e\" \/>\n\t<meta name=\"twitter:data1\" content=\"2 minutes\" \/>\n<script type=\"application\/ld+json\" class=\"yoast-schema-graph\">{\"@context\":\"https:\/\/schema.org\",\"@graph\":[{\"@type\":\"WebPage\",\"@id\":\"https:\/\/www.uni.lu\/snt-fr\/events\/phd-defense-homomorphic-encryption-and-multilinear-maps-based-on-the-approximate-gcd-problem\/\",\"url\":\"https:\/\/www.uni.lu\/snt-fr\/events\/phd-defense-homomorphic-encryption-and-multilinear-maps-based-on-the-approximate-gcd-problem\/\",\"name\":\"PhD Defense: Homomorphic Encryption and Multilinear Maps Based on the Approximate-GCD Problem - SnT - Universit\u00e9 du Luxembourg I Uni.lu\",\"isPartOf\":{\"@id\":\"https:\/\/www.uni.lu\/snt-fr\/#website\"},\"primaryImageOfPage\":{\"@id\":\"https:\/\/www.uni.lu\/snt-fr\/events\/phd-defense-homomorphic-encryption-and-multilinear-maps-based-on-the-approximate-gcd-problem\/#primaryimage\"},\"image\":{\"@id\":\"https:\/\/www.uni.lu\/snt-fr\/events\/phd-defense-homomorphic-encryption-and-multilinear-maps-based-on-the-approximate-gcd-problem\/#primaryimage\"},\"thumbnailUrl\":\"https:\/\/www.uni.lu\/wp-content\/uploads\/sites\/13\/2020\/10\/phd_defense_homomorphic_encryption_and_multilinear_maps_based_on_the_approximate_gcd_problem.jpg\",\"datePublished\":\"2020-10-06T13:44:33+00:00\",\"dateModified\":\"2020-10-06T13:44:33+00:00\",\"breadcrumb\":{\"@id\":\"https:\/\/www.uni.lu\/snt-fr\/events\/phd-defense-homomorphic-encryption-and-multilinear-maps-based-on-the-approximate-gcd-problem\/#breadcrumb\"},\"inLanguage\":\"fr-FR\",\"potentialAction\":[{\"@type\":\"ReadAction\",\"target\":[\"https:\/\/www.uni.lu\/snt-fr\/events\/phd-defense-homomorphic-encryption-and-multilinear-maps-based-on-the-approximate-gcd-problem\/\"]}]},{\"@type\":\"ImageObject\",\"inLanguage\":\"fr-FR\",\"@id\":\"https:\/\/www.uni.lu\/snt-fr\/events\/phd-defense-homomorphic-encryption-and-multilinear-maps-based-on-the-approximate-gcd-problem\/#primaryimage\",\"url\":\"https:\/\/www.uni.lu\/wp-content\/uploads\/sites\/13\/2020\/10\/phd_defense_homomorphic_encryption_and_multilinear_maps_based_on_the_approximate_gcd_problem.jpg\",\"contentUrl\":\"https:\/\/www.uni.lu\/wp-content\/uploads\/sites\/13\/2020\/10\/phd_defense_homomorphic_encryption_and_multilinear_maps_based_on_the_approximate_gcd_problem.jpg\",\"width\":800,\"height\":600},{\"@type\":\"BreadcrumbList\",\"@id\":\"https:\/\/www.uni.lu\/snt-fr\/events\/phd-defense-homomorphic-encryption-and-multilinear-maps-based-on-the-approximate-gcd-problem\/#breadcrumb\",\"itemListElement\":[{\"@type\":\"ListItem\",\"position\":1,\"name\":\"Home\",\"item\":\"https:\/\/www.uni.lu\/fr\"},{\"@type\":\"ListItem\",\"position\":2,\"name\":\"Interdisciplinary Centre for Security, Reliability and Trust (SnT)\",\"item\":\"https:\/\/www.uni.lu\/snt-fr\/\"},{\"@type\":\"ListItem\",\"position\":3,\"name\":\"Events\",\"item\":\"https:\/\/www.uni.lu\/snt-fr\/events\/\"},{\"@type\":\"ListItem\",\"position\":4,\"name\":\"PhD Defense: Homomorphic Encryption and Multilinear Maps Based on the Approximate-GCD Problem\"}]},{\"@type\":\"WebSite\",\"@id\":\"https:\/\/www.uni.lu\/snt-fr\/#website\",\"url\":\"https:\/\/www.uni.lu\/snt-fr\/\",\"name\":\"SnT\",\"description\":\"Interdisciplinary Centre for Security, Reliability and Trust I Uni.lu\",\"publisher\":{\"@id\":\"https:\/\/www.uni.lu\/snt-fr\/#organization\"},\"alternateName\":\"Interdisciplinary Centre for Security, Reliability and Trust I Universit\u00e9 du Luxembourg\",\"potentialAction\":[{\"@type\":\"SearchAction\",\"target\":{\"@type\":\"EntryPoint\",\"urlTemplate\":\"https:\/\/www.uni.lu\/snt-fr\/?s={search_term_string}\"},\"query-input\":\"required name=search_term_string\"}],\"inLanguage\":\"fr-FR\"},{\"@type\":\"Organization\",\"@id\":\"https:\/\/www.uni.lu\/snt-fr\/#organization\",\"name\":\"SnT - Universit\u00e9 du Luxembourg I Uni.lu\",\"alternateName\":\"Interdisciplinary Centre for Security, Reliability and Trust\",\"url\":\"https:\/\/www.uni.lu\/snt-fr\/\",\"logo\":{\"@type\":\"ImageObject\",\"inLanguage\":\"fr-FR\",\"@id\":\"https:\/\/www.uni.lu\/snt-fr\/#\/schema\/logo\/image\/\",\"url\":\"https:\/\/www.uni.lu\/wp-content\/uploads\/sites\/13\/2026\/03\/03112647\/SNT_SM-Profile_1600x1600px-scaled.jpg\",\"contentUrl\":\"https:\/\/www.uni.lu\/wp-content\/uploads\/sites\/13\/2026\/03\/03112647\/SNT_SM-Profile_1600x1600px-scaled.jpg\",\"width\":2560,\"height\":2560,\"caption\":\"SnT - Universit\u00e9 du Luxembourg I Uni.lu\"},\"image\":{\"@id\":\"https:\/\/www.uni.lu\/snt-fr\/#\/schema\/logo\/image\/\"},\"sameAs\":[\"https:\/\/www.linkedin.com\/school\/snt-lu\/\"]}]}<\/script>\n<!-- \/ Yoast SEO Premium plugin. -->","yoast_head_json":{"title":"PhD Defense: Homomorphic Encryption and Multilinear Maps Based on the Approximate-GCD Problem - SnT - Universit\u00e9 du Luxembourg I Uni.lu","robots":{"index":"index","follow":"follow","max-snippet":"max-snippet:-1","max-image-preview":"max-image-preview:large","max-video-preview":"max-video-preview:-1"},"canonical":"https:\/\/www.uni.lu\/snt-fr\/events\/phd-defense-homomorphic-encryption-and-multilinear-maps-based-on-the-approximate-gcd-problem\/","og_locale":"fr_FR","og_type":"article","og_title":"PhD Defense: Homomorphic Encryption and Multilinear Maps Based on the Approximate-GCD Problem","og_url":"https:\/\/www.uni.lu\/snt-fr\/events\/phd-defense-homomorphic-encryption-and-multilinear-maps-based-on-the-approximate-gcd-problem\/","og_site_name":"SnT FR","og_image":[{"width":2560,"height":2560,"url":"https:\/\/www.uni.lu\/wp-content\/uploads\/sites\/13\/2026\/03\/03112647\/SNT_SM-Profile_1600x1600px-scaled.jpg","type":"image\/jpeg"}],"twitter_card":"summary_large_image","twitter_misc":{"Dur\u00e9e de lecture estim\u00e9e":"2 minutes"},"schema":{"@context":"https:\/\/schema.org","@graph":[{"@type":"WebPage","@id":"https:\/\/www.uni.lu\/snt-fr\/events\/phd-defense-homomorphic-encryption-and-multilinear-maps-based-on-the-approximate-gcd-problem\/","url":"https:\/\/www.uni.lu\/snt-fr\/events\/phd-defense-homomorphic-encryption-and-multilinear-maps-based-on-the-approximate-gcd-problem\/","name":"PhD Defense: Homomorphic Encryption and Multilinear Maps Based on the Approximate-GCD Problem - SnT - Universit\u00e9 du Luxembourg I Uni.lu","isPartOf":{"@id":"https:\/\/www.uni.lu\/snt-fr\/#website"},"primaryImageOfPage":{"@id":"https:\/\/www.uni.lu\/snt-fr\/events\/phd-defense-homomorphic-encryption-and-multilinear-maps-based-on-the-approximate-gcd-problem\/#primaryimage"},"image":{"@id":"https:\/\/www.uni.lu\/snt-fr\/events\/phd-defense-homomorphic-encryption-and-multilinear-maps-based-on-the-approximate-gcd-problem\/#primaryimage"},"thumbnailUrl":"https:\/\/www.uni.lu\/wp-content\/uploads\/sites\/13\/2020\/10\/phd_defense_homomorphic_encryption_and_multilinear_maps_based_on_the_approximate_gcd_problem.jpg","datePublished":"2020-10-06T13:44:33+00:00","dateModified":"2020-10-06T13:44:33+00:00","breadcrumb":{"@id":"https:\/\/www.uni.lu\/snt-fr\/events\/phd-defense-homomorphic-encryption-and-multilinear-maps-based-on-the-approximate-gcd-problem\/#breadcrumb"},"inLanguage":"fr-FR","potentialAction":[{"@type":"ReadAction","target":["https:\/\/www.uni.lu\/snt-fr\/events\/phd-defense-homomorphic-encryption-and-multilinear-maps-based-on-the-approximate-gcd-problem\/"]}]},{"@type":"ImageObject","inLanguage":"fr-FR","@id":"https:\/\/www.uni.lu\/snt-fr\/events\/phd-defense-homomorphic-encryption-and-multilinear-maps-based-on-the-approximate-gcd-problem\/#primaryimage","url":"https:\/\/www.uni.lu\/wp-content\/uploads\/sites\/13\/2020\/10\/phd_defense_homomorphic_encryption_and_multilinear_maps_based_on_the_approximate_gcd_problem.jpg","contentUrl":"https:\/\/www.uni.lu\/wp-content\/uploads\/sites\/13\/2020\/10\/phd_defense_homomorphic_encryption_and_multilinear_maps_based_on_the_approximate_gcd_problem.jpg","width":800,"height":600},{"@type":"BreadcrumbList","@id":"https:\/\/www.uni.lu\/snt-fr\/events\/phd-defense-homomorphic-encryption-and-multilinear-maps-based-on-the-approximate-gcd-problem\/#breadcrumb","itemListElement":[{"@type":"ListItem","position":1,"name":"Home","item":"https:\/\/www.uni.lu\/fr"},{"@type":"ListItem","position":2,"name":"Interdisciplinary Centre for Security, Reliability and Trust (SnT)","item":"https:\/\/www.uni.lu\/snt-fr\/"},{"@type":"ListItem","position":3,"name":"Events","item":"https:\/\/www.uni.lu\/snt-fr\/events\/"},{"@type":"ListItem","position":4,"name":"PhD Defense: Homomorphic Encryption and Multilinear Maps Based on the Approximate-GCD Problem"}]},{"@type":"WebSite","@id":"https:\/\/www.uni.lu\/snt-fr\/#website","url":"https:\/\/www.uni.lu\/snt-fr\/","name":"SnT","description":"Interdisciplinary Centre for Security, Reliability and Trust I Uni.lu","publisher":{"@id":"https:\/\/www.uni.lu\/snt-fr\/#organization"},"alternateName":"Interdisciplinary Centre for Security, Reliability and Trust I Universit\u00e9 du Luxembourg","potentialAction":[{"@type":"SearchAction","target":{"@type":"EntryPoint","urlTemplate":"https:\/\/www.uni.lu\/snt-fr\/?s={search_term_string}"},"query-input":"required name=search_term_string"}],"inLanguage":"fr-FR"},{"@type":"Organization","@id":"https:\/\/www.uni.lu\/snt-fr\/#organization","name":"SnT - Universit\u00e9 du Luxembourg I Uni.lu","alternateName":"Interdisciplinary Centre for Security, Reliability and Trust","url":"https:\/\/www.uni.lu\/snt-fr\/","logo":{"@type":"ImageObject","inLanguage":"fr-FR","@id":"https:\/\/www.uni.lu\/snt-fr\/#\/schema\/logo\/image\/","url":"https:\/\/www.uni.lu\/wp-content\/uploads\/sites\/13\/2026\/03\/03112647\/SNT_SM-Profile_1600x1600px-scaled.jpg","contentUrl":"https:\/\/www.uni.lu\/wp-content\/uploads\/sites\/13\/2026\/03\/03112647\/SNT_SM-Profile_1600x1600px-scaled.jpg","width":2560,"height":2560,"caption":"SnT - Universit\u00e9 du Luxembourg I Uni.lu"},"image":{"@id":"https:\/\/www.uni.lu\/snt-fr\/#\/schema\/logo\/image\/"},"sameAs":["https:\/\/www.linkedin.com\/school\/snt-lu\/"]}]}},"_links":{"self":[{"href":"https:\/\/www.uni.lu\/snt-fr\/wp-json\/wp\/v2\/events\/899"}],"collection":[{"href":"https:\/\/www.uni.lu\/snt-fr\/wp-json\/wp\/v2\/events"}],"about":[{"href":"https:\/\/www.uni.lu\/snt-fr\/wp-json\/wp\/v2\/types\/events"}],"replies":[{"embeddable":true,"href":"https:\/\/www.uni.lu\/snt-fr\/wp-json\/wp\/v2\/comments?post=899"}],"version-history":[{"count":0,"href":"https:\/\/www.uni.lu\/snt-fr\/wp-json\/wp\/v2\/events\/899\/revisions"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/www.uni.lu\/snt-fr\/wp-json\/wp\/v2\/media\/900"}],"wp:attachment":[{"href":"https:\/\/www.uni.lu\/snt-fr\/wp-json\/wp\/v2\/media?parent=899"}],"wp:term":[{"taxonomy":"events-topic","embeddable":true,"href":"https:\/\/www.uni.lu\/snt-fr\/wp-json\/wp\/v2\/events-topic?post=899"},{"taxonomy":"events-type","embeddable":true,"href":"https:\/\/www.uni.lu\/snt-fr\/wp-json\/wp\/v2\/events-type?post=899"},{"taxonomy":"organisation","embeddable":true,"href":"https:\/\/www.uni.lu\/snt-fr\/wp-json\/wp\/v2\/organisation?post=899"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}