{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,6]],"date-time":"2026-05-06T04:16:11Z","timestamp":1778040971071,"version":"3.51.4"},"reference-count":39,"publisher":"International Association for Cryptologic Research","issue":"1","license":[{"start":{"date-parts":[[2026,2,3]],"date-time":"2026-02-03T00:00:00Z","timestamp":1770076800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["IACR CiC"],"accepted":{"date-parts":[[2026,4,10]]},"abstract":"<jats:p>Sorting encrypted values is an open research problem that plays a crucial role in the broader objective of providing efficient and practical privacy-preserving online services. The current state of the art work by Mazzone, Everts, Hahn and Peter [USENIX Security '25] proposes efficient algorithms for indexing and sorting based on the CKKS scheme, which deviates from the compare-and-swap paradigm, typically used by sorting networks, using a permutation-based approach.<\/jats:p>\n                  <jats:p>In this work, we follow up their work and explore different approaches to approximate the nonlinear functions required by the circuit. We propose simpler and concrete solutions that allow for faster computations, smaller memory requirements and higher precision. For example, our framework allows to sort 128 real elements in roughly 22 seconds, while maintaining a precision of 0.001 and requiring 3 GB of memory. Furthermore, we propose an implementation of a swap-based bitonic network that is not based on approximations of the sgn function, which scales linearly with the number of values, useful when the number of available slots is small.<\/jats:p>","DOI":"10.62056\/a3ksdkmol","type":"journal-article","created":{"date-parts":[[2026,5,4]],"date-time":"2026-05-04T18:09:08Z","timestamp":1777918148000},"update-policy":"https:\/\/doi.org\/10.62056\/adfjwm02dj","source":"Crossref","is-referenced-by-count":0,"title":["Lightweight sorting in approximate homomorphic encryption"],"prefix":"10.62056","volume":"3","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-5093-7932","authenticated-orcid":false,"given":"Lorenzo","family":"Rovida","sequence":"first","affiliation":[{"id":[{"id":"https:\/\/ror.org\/00bgk9508","id-type":"ROR","asserted-by":"publisher"}],"name":"Polytechnic University of Turin","place":["Corso Duca degli Abruzzi, 24, Turin, 10239, Italy"],"department":["Dept. of Mathematical Sciences"]}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-8105-4371","authenticated-orcid":false,"given":"Alberto","family":"Leporati","sequence":"additional","affiliation":[{"id":[{"id":"https:\/\/ror.org\/01ynf4891","id-type":"ROR","asserted-by":"publisher"}],"name":"University of Milano-Bicocca","place":["Viale Sarca, 336, Milan, 20125, Italy"],"department":["Dept. of Informatics, Systems and Communication"]}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Simone","family":"Basile","sequence":"additional","affiliation":[{"id":[{"id":"https:\/\/ror.org\/01ynf4891","id-type":"ROR","asserted-by":"publisher"}],"name":"University of Milano-Bicocca","place":["Viale Sarca, 336, Milan, 20125, Italy"],"department":["Dept. of Informatics, Systems and Communication"]}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"48349","published-online":{"date-parts":[[2026,5,4]]},"reference":[{"key":"ref1:Khanal2020","doi-asserted-by":"publisher","first-page":"2635","DOI":"10.1007\/s10639-019-10063-9","article-title":"A systematic review: machine learning based recommendation\n  systems for e-learning","volume":"25","author":"Shristi Shakya Khanal","year":"2020","journal-title":"Education and Information Technologies"},{"key":"ref2:10.1007\/978-3-031-09234-3_26","doi-asserted-by":"publisher","first-page":"521","DOI":"10.1007\/978-3-031-09234-3_26","article-title":"Bootstrapping for Approximate Homomorphic Encryption with\n  Negligible Failure-Probability by Using Sparse-Secret Encapsulation","author":"Jean-Philippe Bossuat","year":"2022"},{"key":"ref3:lazzaretti2023near","doi-asserted-by":"publisher","first-page":"406","DOI":"10.1007\/978-3-031-48618-0_14","article-title":"Near-optimal private information retrieval with\n  preprocessing","author":"Arthur Lazzaretti","year":"2023"},{"key":"ref4:Chillotti2020","doi-asserted-by":"publisher","first-page":"34","DOI":"10.1007\/s00145-019-09319-x","article-title":"TFHE: Fast Fully Homomorphic Encryption Over the Torus","volume":"33","author":"Ilaria Chillotti","year":"2020","journal-title":"Journal of Cryptology"},{"key":"ref5:PRANTL2025104110","doi-asserted-by":"publisher","first-page":"104110","DOI":"10.1016\/j.jisa.2025.104110","article-title":"Quo Vadis CKKS: Comparison of the realization of basic\n  mathematical functions for the homomorphic cryptosystem CKKS using De Bello\n  and polynomial approximations","volume":"93","author":"Thomas Prantl","year":"2025","journal-title":"Journal of Information Security and Applications","ISSN":"https:\/\/id.crossref.org\/issn\/2214-2126","issn-type":"electronic"},{"key":"ref6:10.5555\/580470","isbn-type":"print","volume-title":"Introduction to Algorithms","author":"Thomas H. Cormen","year":"2001","ISBN":"https:\/\/id.crossref.org\/isbn\/0070131511"},{"key":"ref7:doi:10.1137\/0202007","doi-asserted-by":"publisher","first-page":"60","DOI":"10.1137\/0202007","article-title":"On the Number of Nonscalar Multiplications Necessary to\n  Evaluate Polynomials","volume":"2","author":"Michael S. Paterson","year":"1973","journal-title":"SIAM Journal on Computing"},{"key":"ref8:mazzone2025efficient","doi-asserted-by":"publisher","DOI":"10.1007\/978-981-95-3182-0_18","article-title":"Efficient Ranking, Order Statistics, and Sorting under\n  CKKS","author":"Federico Mazzone","year":"2025"},{"key":"ref9:9520302","doi-asserted-by":"publisher","first-page":"4389","DOI":"10.1109\/tifs.2021.3106167","article-title":"Efficient Sorting of Homomorphic Encrypted Data With k-Way\n  Sorting Network","volume":"16","author":"Seungwan Hong","year":"2021","journal-title":"IEEE Transactions on Information Forensics and Security"},{"key":"ref10:CKK20","doi-asserted-by":"publisher","first-page":"221","DOI":"10.1007\/978-3-030-64834-3_8","article-title":"Efficient Homomorphic Comparison Methods with Optimal\n  Complexity","author":"Jung Hee Cheon","year":"2020"},{"key":"ref11:10.1145\/355592.365646","doi-asserted-by":"publisher","first-page":"366","DOI":"10.1145\/355592.365646","article-title":"Flow diagrams, turing machines and languages with only two\n  formation rules","volume":"9","author":"Corrado B\u00f6hm","year":"1966","journal-title":"Communications of the ACM"},{"key":"ref12:Lee1","doi-asserted-by":"publisher","first-page":"26163","DOI":"10.1109\/access.2022.3155882","article-title":"Optimization of Homomorphic Comparison Algorithm on RNS-CKKS\n  Scheme","volume":"10","author":"Eunsang Lee","year":"2022","journal-title":"IEEE Access"},{"key":"ref13:Akl2011","doi-asserted-by":"publisher","first-page":"139","DOI":"10.1007\/978-0-387-09766-4_124","volume-title":"Encyclopedia of Parallel Computing","author":"Selim G. Akl","year":"2011"},{"key":"ref14:11240997","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1109\/iccad66269.2025.11240997","article-title":"PATHE: A Privacy-Preserving Database Pattern Search Platform\n  with Homomorphic Encryption","author":"Xuan Wang","year":"2025"},{"key":"ref15:APS15","doi-asserted-by":"publisher","first-page":"169","DOI":"10.1515\/jmc-2015-0016","article-title":"On the concrete hardness of Learning with Errors","volume":"9","author":"Martin R. Albrecht","year":"2015","journal-title":"Journal of Mathematical Cryptology"},{"key":"ref16:10.1007\/978-3-319-70694-8_15","isbn-type":"print","doi-asserted-by":"publisher","first-page":"409","DOI":"10.1007\/978-3-319-70694-8_15","article-title":"Homomorphic Encryption for Arithmetic of Approximate\n  Numbers","author":"Jung Hee Cheon","year":"2017","ISBN":"https:\/\/id.crossref.org\/isbn\/9783319706948"},{"key":"ref17:openfhe","series-title":"WAHC'22","doi-asserted-by":"publisher","first-page":"53","DOI":"10.1145\/3560827.3563379","article-title":"OpenFHE: Open-Source Fully Homomorphic Encryption Library","author":"Ahmad Al Badawi","year":"2022"},{"key":"ref18:10.1145\/1536414.1536440","series-title":"STOC '09","doi-asserted-by":"publisher","first-page":"169","DOI":"10.1145\/1536414.1536440","article-title":"Fully homomorphic encryption using ideal lattices","author":"Craig Gentry","year":"2009"},{"key":"ref19:cryptoeprint:2025\/1534","volume-title":"RBOOT: Accelerating Homomorphic Neural Network Inference\n  by Fusing ReLU within Bootstrapping","author":"Zhaomin Yang","year":"2025"},{"key":"ref20:zhao2025hermeshighperformancehomomorphicallyencrypted","volume-title":"Hermes: High-Performance Homomorphically Encrypted Vector\n  Databases","author":"Dongfang Zhao","year":"2025"},{"key":"ref21:10.1007\/978-3-030-17656-3_2","doi-asserted-by":"publisher","first-page":"34","DOI":"10.1007\/978-3-030-17656-3_2","article-title":"Improved Bootstrapping for Approximate Homomorphic\n  Encryption","author":"Hao Chen","year":"2019"},{"key":"ref22:10.1007\/978-3-642-40084-1_30","doi-asserted-by":"publisher","first-page":"536","DOI":"10.1007\/978-3-642-40084-1_30","article-title":"How to Run Turing Machines on Encrypted Data","author":"Shafi Goldwasser","year":"2013"},{"key":"ref23:10.1007\/978-3-031-82852-2_1","doi-asserted-by":"publisher","first-page":"3","DOI":"10.1007\/978-3-031-82852-2_1","article-title":"Revisiting Oblivious Top-k Selection with Applications to\n  Secure k-NN Classification","author":"Kelong Cong","year":"2025"},{"key":"ref24:Lee2","doi-asserted-by":"publisher","first-page":"3711","DOI":"10.1109\/tdsc.2021.3105111","article-title":"Minimax Approximation of Sign Function by Composite\n  Polynomial for Homomorphic Comparison","volume":"19","author":"Eunsang Lee","year":"2022","journal-title":"IEEE Transactions on Dependable and Secure Computing"},{"key":"ref25:10.1007\/978-3-030-95312-6_6","doi-asserted-by":"publisher","first-page":"120","DOI":"10.1007\/978-3-030-95312-6_6","article-title":"Approximate Homomorphic Encryption with Reduced\n  Approximation Error","author":"Andrey Kim","year":"2022"},{"key":"ref26:lu2021pegasus","doi-asserted-by":"publisher","first-page":"1057","DOI":"10.1109\/sp40001.2021.00043","article-title":"PEGASUS: bridging polynomial and non-polynomial evaluations\n  in homomorphic encryption","author":"Wen-jie Lu","year":"2021"},{"key":"ref27:10.1145\/2535925","doi-asserted-by":"publisher","DOI":"10.1145\/2535925","article-title":"On Ideal Lattices and Learning with Errors over Rings","volume":"60","author":"Vadim Lyubashevsky","year":"2013","journal-title":"J. ACM"},{"key":"ref28:10.1145\/1468075.1468121","series-title":"AFIPS '68 (Spring)","doi-asserted-by":"publisher","first-page":"307","DOI":"10.1145\/1468075.1468121","article-title":"Sorting networks and their applications","author":"K. E. Batcher","year":"1968"},{"key":"ref29:cryptoeprint:2025\/1170","volume-title":"Optimized Rank Sort for Encrypted Real Numbers","author":"Seunghu Kim","year":"2025"},{"key":"ref30:10.5555\/280635","isbn-type":"print","volume-title":"The art of computer programming, volume 3: (2nd ed.) sorting\n  and searching","author":"Donald E. Knuth","year":"1998","ISBN":"https:\/\/id.crossref.org\/isbn\/0201896850"},{"key":"ref31:10.1145\/3725843.3756060","series-title":"MICRO '25","doi-asserted-by":"publisher","first-page":"1749","DOI":"10.1145\/3725843.3756060","article-title":"SmartPIR: A Private Information Retrieval System using\n  Computational Storage Devices","author":"Zehao Chen","year":"2025"},{"key":"ref32:10.1016\/j.jisa.2022.103372","doi-asserted-by":"publisher","DOI":"10.1016\/j.jisa.2022.103372","article-title":"Secure word-level sorting based on fully homomorphic\n  encryption","volume":"71","author":"Hai Huang","year":"2022","journal-title":"J. Inf. Secur. Appl.","ISSN":"https:\/\/id.crossref.org\/issn\/2214-2126","issn-type":"electronic"},{"key":"ref33:10.1007\/978-3-319-78381-9_14","doi-asserted-by":"publisher","first-page":"360","DOI":"10.1007\/978-3-319-78381-9_14","article-title":"Bootstrapping for Approximate Homomorphic Encryption","author":"Jung Hee Cheon","year":"2018"},{"key":"ref34:10.1145\/3564246.3585175","series-title":"STOC 2023","doi-asserted-by":"publisher","first-page":"595","DOI":"10.1145\/3564246.3585175","article-title":"Doubly Efficient Private Information Retrieval and Fully\n  Homomorphic RAM Computation from Ring LWE","author":"Wei-Kai Lin","year":"2023"},{"key":"ref35:doi:10.1137\/1.9781611975949","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611975949","volume-title":"Approximation Theory and Approximation Practice, Extended\n  Edition","author":"Lloyd N. Trefethen","year":"2019"},{"key":"ref36:parberry1992pairwise","doi-asserted-by":"publisher","first-page":"205","DOI":"10.1142\/s0129626492000337","article-title":"The pairwise sorting network","volume":"2","author":"Ian Parberry","year":"1992","journal-title":"Parallel Processing Letters"},{"key":"ref37:discreteCKKS","doi-asserted-by":"publisher","DOI":"10.1007\/s00145-023-09483-1","article-title":"BLEACH: Cleaning Errors in Discrete Computations Over CKKS","volume":"37","author":"Nir Drucker","year":"2023","journal-title":"J. Cryptol."},{"key":"ref38:garimella2025helrmencrypteddeeplearning","volume-title":"HE-LRM: Encrypted Deep Learning Recommendation Models using\n  Fully Homomorphic Encryption","author":"Karthik Garimella","year":"2025"},{"key":"ref39:rivest1978data","first-page":"169","article-title":"On data banks and privacy homomorphisms","volume":"4","author":"Ronald L Rivest","year":"1978","journal-title":"Foundations of secure computation"}],"container-title":["IACR Communications in Cryptology"],"original-title":[],"language":"en","deposited":{"date-parts":[[2026,5,6]],"date-time":"2026-05-06T04:04:27Z","timestamp":1778040267000},"score":1,"resource":{"primary":{"URL":"https:\/\/cic.iacr.org\/p\/3\/1\/32"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,5,4]]},"references-count":39,"journal-issue":{"issue":"1","published-online":{"date-parts":[[2026,5,4]]}},"URL":"https:\/\/doi.org\/10.62056\/a3ksdkmol","archive":["Internet Archive","Internet Archive"],"relation":{},"ISSN":["3006-5496"],"issn-type":[{"value":"3006-5496","type":"electronic"}],"subject":[],"published":{"date-parts":[[2026,5,4]]},"assertion":[{"value":"2026-02-03","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2026-04-10","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}}],"article-number":"cc3-1-92"}}