Bootstrapping Optimization for Fully Homomorphic Encryption Schemes

Bootstrapping Optimization for Fully Homomorphic Encryption Schemes | Research Square window.SnipcartSettings = { analytics: { enabled: false } }; (function() { var accessVector = localStorage.getItem('access_vector') || ''; window.dataLayer = window.dataLayer || []; if (accessVector) { window.dataLayer.push({ user: { profile: { profileInfo: { snid: accessVector } } } }); } })(); (function(w,d,s,l,i){w[l]=w[l]||[];w[l].push({'gtm.start':new Date().getTime(),event:'gtm.js'});var f=d.getElementsByTagName(s)[0],j=d.createElement(s),dl=l!='dataLayer'?'&l='+l:'';j.async=true;j.src='https://www.googletagmanager.com/gtm.js?id='+i+dl;f.parentNode.insertBefore(j,f);})(window,document,'script','dataLayer','GTM-K279D39R'); Browse Preprints In Review Journals COVID-19 Preprints AJE Video Bytes Research Tools Research Promotion AJE Professional Editing AJE Rubriq About Preprint Platform In Review Editorial Policies Our Team Advisory Board Help Center Sign In Submit a Preprint Cite Share Download PDF Research Article Bootstrapping Optimization for Fully Homomorphic Encryption Schemes Meng Wu, Xiufeng Zhao, Weitao Song This is a preprint; it has not been peer reviewed by a journal. https://doi.org/ 10.21203/rs.3.rs-4194403/v1 This work is licensed under a CC BY 4.0 License Status: Posted Version 1 posted You are reading this latest preprint version Abstract With the advent of cloud computing and the era of big data, there is an increasing focus on privacy computing. Consequently, homomorphic encryption, being a primary technique for achieving privacy computing, is held in high regard. Nevertheless, the efficiency of homomorphic encryption schemes is significantly impacted by boostrapping. FINAL scheme (ASIACRYPT 2022) is a fully homomorphic encryption scheme based on number theory research unit (NTRU) and learning with errors (LWE) assumptions proposed by Charlotte Bonte et al. The performance of the FINAL scheme is better than TFHE scheme, with a faster bootstrapping and smaller bootstrapping and key-switching keys. In this paper, we introduce ellipsoidal Gaussian sampling to generate the keys f and g in bootstrapping of FINAL scheme, so that the standard deviations of the keys f and g are different and reduce the bootstrapping noise. As a result, larger decomposition bases is used in bootstrapping to reduce the total number of polynomial multiplications, thus improving the efficiency of FINAL scheme. The optimization scheme outperforms the original FINAL scheme with a 33.3\% faster bootstrapping. number theory research unit bootstrapping fully homomorphic encryption learning with errors Full Text Additional Declarations No competing interests reported. Cite Share Download PDF Status: Posted Version 1 posted You are reading this latest preprint version Research Square lets you share your work early, gain feedback from the community, and start making changes to your manuscript prior to peer review in a journal. As a division of Research Square Company, we’re committed to making research communication faster, fairer, and more useful. We do this by developing innovative software and high quality services for the global research community. Our growing team is made up of researchers and industry professionals working together to solve the most critical problems facing scientific publishing. Also discoverable on Platform About Our Team In Review Editorial Policies Advisory Board Help Center Resources Author Services Accessibility API Access RSS feed Manage Cookie Preferences © Research Square 2026 | ISSN 2693-5015 (online) Privacy Policy Terms of Service Do Not Sell My Personal Information {"props":{"pageProps":{"initialData":{"identity":"rs-4194403","acceptedTermsAndConditions":true,"allowDirectSubmit":true,"archivedVersions":[],"articleType":"Research Article","associatedPublications":[],"authors":[{"id":291743386,"identity":"58c338a3-e02c-42cb-afa6-301cc74503a0","order_by":0,"name":"Meng Wu","email":"","orcid":"","institution":"PLA Information Engineering University","correspondingAuthor":false,"prefix":"","firstName":"Meng","middleName":"","lastName":"Wu","suffix":""},{"id":291743387,"identity":"92fdd88b-54e8-44b6-9299-315de6635567","order_by":1,"name":"Xiufeng Zhao","email":"data:image/png;base64,iVBORw0KGgoAAAANSUhEUgAAAZAAAAAyAQMAAABI0h/eAAAABlBMVEX///8AAABVwtN+AAAACXBIWXMAAA7EAAAOxAGVKw4bAAAA60lEQVRIiWNgGAWjYDACCRjJfABIV0jIyROvhS0BSJ+xMDZsIE4LA0QLY1tFIsMBAjrkZzc/fMDYZpHYwMZ87OHXeRIJjA3MDx/dwKOFcc4xYwOGMxJALWzpxrLbJPLYGdiMjXPwaGGWSDCTAPo6sUG+x0xacptEMWMDD5s0Pi1sEunfJBgMQLbwf5OWnANkHCCghUciB2oLGw+b5McGIrRISOQUg/xiDPSLmTTDMQljw2YCfpGfkb4RGGJ1ssAQeyb5o6ZOTp69+eFjfFpAgPkPkLA/AGTwgLkElKMAxh+kqB4Fo2AUjIIRAwCurT6vaXll8gAAAABJRU5ErkJggg==","orcid":"","institution":"PLA Information Engineering University","correspondingAuthor":true,"prefix":"","firstName":"Xiufeng","middleName":"","lastName":"Zhao","suffix":""},{"id":291743388,"identity":"9b927fc2-9093-4345-9165-7a3646458b35","order_by":2,"name":"Weitao Song","email":"","orcid":"","institution":"PLA Information Engineering University","correspondingAuthor":false,"prefix":"","firstName":"Weitao","middleName":"","lastName":"Song","suffix":""}],"badges":[],"createdAt":"2024-03-31 06:29:19","currentVersionCode":1,"declarations":"","doi":"10.21203/rs.3.rs-4194403/v1","doiUrl":"https://doi.org/10.21203/rs.3.rs-4194403/v1","draftVersion":[],"editorialEvents":[],"editorialNote":"","failedWorkflow":false,"files":[{"id":58286239,"identity":"867bb44f-07a3-425c-a6f4-5c0e1f2a618b","added_by":"auto","created_at":"2024-06-13 12:17:18","extension":"pdf","order_by":1,"title":"","display":"","copyAsset":false,"role":"manuscript-pdf","size":1036031,"visible":true,"origin":"","legend":"","description":"","filename":"BootstrappingOptimization1.pdf","url":"https://assets-eu.researchsquare.com/files/rs-4194403/v1_covered_a1ff0416-9b08-4eaf-869a-a6df1d1208c0.pdf"}],"financialInterests":"No competing interests reported.","formattedTitle":"Bootstrapping Optimization for Fully Homomorphic Encryption Schemes","fulltext":[],"fulltextSource":"","fullText":"","funders":[],"hasAdminPriorityOnWorkflow":false,"hasManuscriptDocX":false,"hasOptedInToPreprint":true,"hasPassedJournalQc":"","hasAnyPriority":false,"hideJournal":true,"highlight":"","institution":"","isAcceptedByJournal":false,"isAuthorSuppliedPdf":true,"isDeskRejected":"","isHiddenFromSearch":false,"isInQc":false,"isInWorkflow":false,"isPdf":true,"isPdfUpToDate":true,"isWithdrawnOrRetracted":false,"journal":{"display":true,"email":"[email protected]","identity":"researchsquare","isNatureJournal":false,"hasQc":true,"allowDirectSubmit":true,"externalIdentity":"","sideBox":"","snPcode":"","submissionUrl":"/submission","title":"Research Square","twitterHandle":"researchsquare","acdcEnabled":true,"dfaEnabled":false,"editorialSystem":"","reportingPortfolio":"","inReviewEnabled":false,"inReviewRevisionsEnabled":true},"keywords":"number theory research unit, bootstrapping, fully homomorphic encryption, learning with errors","lastPublishedDoi":"10.21203/rs.3.rs-4194403/v1","lastPublishedDoiUrl":"https://doi.org/10.21203/rs.3.rs-4194403/v1","license":{"name":"CC BY 4.0","url":"https://creativecommons.org/licenses/by/4.0/"},"manuscriptAbstract":"\u003cp\u003eWith the advent of cloud computing and the era of big data, there is an increasing focus on privacy computing. Consequently, homomorphic encryption, being a primary technique for achieving privacy computing, is held in high regard. Nevertheless, the efficiency of homomorphic encryption schemes is significantly impacted by boostrapping. FINAL scheme (ASIACRYPT 2022) is a fully homomorphic encryption scheme based on number theory research unit (NTRU) and learning with errors (LWE) assumptions proposed by Charlotte Bonte et al. The performance of the FINAL scheme is better than TFHE scheme, with a faster bootstrapping and smaller bootstrapping and key-switching keys. In this paper, we introduce ellipsoidal Gaussian sampling to generate the keys \u003cem\u003ef\u003c/em\u003e and \u003cem\u003eg\u003c/em\u003e in bootstrapping of FINAL scheme, so that the standard deviations of the keys \u003cem\u003ef\u003c/em\u003e and \u003cem\u003eg\u003c/em\u003e are different and reduce the bootstrapping noise. As a result, larger decomposition bases is used in bootstrapping to reduce the total number of polynomial multiplications, thus improving the efficiency of FINAL scheme. The optimization scheme outperforms the original FINAL scheme with a 33.3\\% faster bootstrapping.\u003c/p\u003e","manuscriptTitle":"Bootstrapping Optimization for Fully Homomorphic Encryption Schemes","msid":"","msnumber":"","nonDraftVersions":[{"code":1,"date":"2024-04-19 12:20:00","doi":"10.21203/rs.3.rs-4194403/v1","editorialEvents":[{"type":"communityComments","content":0}],"status":"published","journal":{"display":true,"email":"[email protected]","identity":"researchsquare","isNatureJournal":false,"hasQc":true,"allowDirectSubmit":true,"externalIdentity":"","sideBox":"","snPcode":"","submissionUrl":"/submission","title":"Research Square","twitterHandle":"researchsquare","acdcEnabled":true,"dfaEnabled":false,"editorialSystem":"","reportingPortfolio":"","inReviewEnabled":false,"inReviewRevisionsEnabled":true}}],"origin":"","ownerIdentity":"6b15448b-aec1-4f43-9005-cd49d40e5c8b","owner":[],"postedDate":"April 19th, 2024","published":true,"recentEditorialEvents":[],"rejectedJournal":[],"revision":"","amendment":"","status":"posted","subjectAreas":[],"tags":[],"updatedAt":"2024-06-13T12:09:11+00:00","versionOfRecord":[],"versionCreatedAt":"2024-04-19 12:20:00","video":"","vorDoi":"","vorDoiUrl":"","workflowStages":[]},"version":"v1","identity":"rs-4194403","journalConfig":"researchsquare"},"__N_SSP":true},"page":"/article/[identity]/[[...version]]","query":{"redirect":"/article/rs-4194403","identity":"rs-4194403","version":["v1"]},"buildId":"qtupq5eGEP_6zYnWcrvyt","isFallback":false,"isExperimentalCompile":false,"dynamicIds":[84888],"gssp":true,"scriptLoader":[]}