{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,7]],"date-time":"2026-04-07T18:04:56Z","timestamp":1775585096984,"version":"3.50.1"},"reference-count":0,"publisher":"Universitatsbibliothek der Ruhr-Universitat Bochum","issue":"4","license":[{"start":{"date-parts":[[2025,9,5]],"date-time":"2025-09-05T00:00:00Z","timestamp":1757030400000},"content-version":"unspecified","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["TCHES"],"abstract":"<jats:p>Amortized bootstrapping techniques have been proposed for FHEW\/TFHE to efficiently refresh multiple ciphertexts simultaneously within a polynomial modulus. Although recent proposals have very efficient asymptotic complexity, reducing the amortized cost essentially to \u00d5(1) FHE multiplications, the practicality of such algorithms still suffers from substantial overhead and high decryption failure rates (DFR). In this study, we improve upon one of the state-of-the-art amortized bootstrapping algorithms (Guimar\u00e3es et al., ASIACRYPT 2023) for FHEW\/TFHE-like schemes by introducing an alternative algorithmic strategy. Specifically, we combine Guimar\u00e3es et al.\u2019s strategy based on a two-part NTT with an incomplete Number Theoretic Transform (NTT) algorithm. The resulting construction is such that the multiplication of higher-degree polynomials that would usually create a bottleneck in an incomplete NTT setting actually comes for free. As a result, we demonstrate a 2.12x speedup compared to the algorithm of Guimar\u00e3es et al. and a 1.12x improvement over the state-of-the-art (sequential) TFHE-rs while achieving a DFR close to 2\u221232 for 7-bit messages, although the DFR is higher for 8-bit messages. We also explore trade-offs between execution time and DFR, identifying parameter sets that improve the execution time of Guimar\u00e3es et al. by 1.41x, while simultaneously reducing the DFR by a factor of 2\u221222 for 8-bit messages.<\/jats:p>","DOI":"10.46586\/tches.v2025.i4.520-543","type":"journal-article","created":{"date-parts":[[2025,9,5]],"date-time":"2025-09-05T13:10:23Z","timestamp":1757077823000},"page":"520-543","source":"Crossref","is-referenced-by-count":1,"title":["Faster amortized bootstrapping using the incomplete NTT for free"],"prefix":"10.46586","volume":"2025","author":[{"given":"Thales B.","family":"Paiva","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Gabrielle","family":"De Micheli","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Syed Mahbub","family":"Hafiz","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Marcos A.","family":"Simplicio Jr.","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Bahattin","family":"Yildiz","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"25480","published-online":{"date-parts":[[2025,9,5]]},"container-title":["IACR Transactions on Cryptographic Hardware and Embedded Systems"],"original-title":[],"link":[{"URL":"https:\/\/tches.iacr.org\/index.php\/TCHES\/article\/download\/12420\/12148","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/tches.iacr.org\/index.php\/TCHES\/article\/download\/12420\/12148","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,9,5]],"date-time":"2025-09-05T13:10:24Z","timestamp":1757077824000},"score":1,"resource":{"primary":{"URL":"https:\/\/tches.iacr.org\/index.php\/TCHES\/article\/view\/12420"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,9,5]]},"references-count":0,"journal-issue":{"issue":"4","published-online":{"date-parts":[[2025,9,5]]}},"URL":"https:\/\/doi.org\/10.46586\/tches.v2025.i4.520-543","relation":{},"ISSN":["2569-2925"],"issn-type":[{"value":"2569-2925","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025,9,5]]}}}