Pasar al contenido principal

RETOS EN CODIGOS ALGEBRAICOS Y EN CRIPTOGRAFIA BASADA EN LA TEORIA DE LA INFORMACION PARA UN ENTORNO DE COMUNICACIONES DIGITALES (ACITHEC)

PID2021-124928NB-I00

•
Nombre agencia financiadora Agencia Estatal de Investigación
Acrónimo agencia financiadora AEI
Programa Programa Estatal para Impulsar la Investigación Científico-Técnica y su Transferencia
Subprograma Subprograma Estatal de Generación de Conocimiento
Convocatoria Proyectos de I+D+i (Generación de Conocimiento y Retos Investigación)
Año convocatoria 2021
Plan Estatal 2021-2023 Plan Estatal de Investigación Científica y Técnica y de Innovación
Centro beneficiario UNIVERSITAT ROVIRA I VIRGILI

Resultados relacionados

Resultados totales (Incluyendo duplicados): 15
Encontrada(s) 1 página(s)

RiuNet. Repositorio Institucional de la Universitat Politécnica de Valéncia
Publicación Artículo científico (JournalArticle)

Leveraging HLS to Design a Versatile &amp, High-Performance Classic McEliece Accelerator

  • Kostalabros, Ioannis-Vatistas
  • Ribes, Jordi
  • Carril, Xavier
  • Farràs, Oriol
  • Moreto, Miquel
  • Hernández Luz, Carles|||0000-0003-1192-6223
[EN] By harnessing fundamental quantum properties, a large-scale quantum computer could undermine currently deployed public-key algorithms. The post-quantum, code-based cryptosystem Classic McEliece (CM)addresses this security concern. However, its large public key size (up to 1.3 MB) poses various hardware implementation challenges. In this article, we focus on the high memory bandwidth requirements of the CM encoding function, in the context of heterogeneous CPU-FPGA devices. More concretely, we target the acceleration of public-key loading and processing from any globally shared or accelerator-private memory system. We present a novel and constant-time accelerator eEnc that exploits the elevated parallelization potential of FPGA devices to yield high-performance results. Our accelerator implements the encoding and the random error vector generation functions, which comprise the main computational load of Encapsulation. Two accelerator design variants are introduced, providing different hardware tradeoffs. Regarding intra-accelerator data communication, and unlike other state-of-the-art (SOTA) works, we combine a streaming protocol with task-level parallelization to remove the need to store the public key in accelerator-private memories. Our proposed design shows new record execution times over its SOTA counterparts, ranging on average from 3.5x up to 7.7x across the five security level parameter sets. Our end-to-end implementation in a Zynq SoC shows an average speedup of 2.2x compared to a 64-bit vectorized CM software-baseline. The elevated logic resource consumption, characteristic of HLS designs, can be readily adjusted with a performance tradeoff., This work has been partially supported by the European HiPEAC Network of Excellence, by the Spanish Ministry of Science and Innovation MCIN/AEI 10.13039/501100011033 (contracts ACITHEC PID2021-124928NB-I00, PID2019-107255GB-C21 and "Ramon y Cajal" fellowship No. RYC2020-030685-I) , by the Generalitat de Catalunya (contract 2021-SGR-00763, 2021-SGR-00115 and 2023-146511NB-I00) , by the Agency for Management of University and Research Grants (AGAUR) of the Government of Catalonia under "Ajuts per a la contractacio de personal investigador novell" (fellowships No. 2019FI B01274 and 2024 FI-1 00520) , by the European Union within the framework of the ERDF of Catalonia 2014-2020 under the DRAC project [001-P-001723] , and by the project HERMES funded by the European NextGenerationEU/PRTR via INCIBE.
RiuNet. Repositorio Institucional de la Universitat Politécnica de Valéncia
Publicación Artículo científico (JournalArticle)

Hardware Acceleration for High-Volume Operations of CRYSTALS-Kyber and CRYSTALS-Dilithium

  • Carril, Xavier
  • Kardaris, Charalampos
  • Ribes-González, Jordi
  • Farràs, Oriol
  • Kostalabros, Vatistas
  • González-Jiménez, Joel Ulises
  • Moreto, Miquel
  • Hernández Luz, Carles|||0000-0003-1192-6223
[EN] Many high-demand digital services need to perform several cryptographic operations, such as key exchange or security credentialing, in a concise amount of time. In turn, the security of some of these cryptographic schemes is threatened by advances in quantum computing, as quantum computer could break their security in the near future. Post-quantum cryptography (PQC) is an emerging field that studies cryptographic algorithms that resist such attacks. The National Institute of Standards and Technology (NIST) has selected the CRYSTALSKyber Key Encapsulation Mechanism and the CRYSTALS-Dilithium Digital Signature algorithm as primary PQC standards. In this article, we present field-programmable gate array (FPGA)-based hardware accelerators for high-volume operations of both schemes. We apply high-level synthesis (HLS) for hardware optimization, leveraging a batch processing approach to maximize the memory throughput and applying custom HLS logic to specific algorithmic components. Using reconfigurable FPGAs, we show that our hardware accelerators achieve speedups between 3x and 9x over software baseline implementations, even over ones leveraging CPU vector architectures. Furthermore, the methods used in this study can also be extended to the new CRYSTALS-based NIST FIPS drafts, ML-KEM and ML-DSA, with similar acceleration results., This work was part of the project (ISOLDE) , funded by MICIU/AEI/10.13039/501100011033 and the European Union NextGenerationEU/PRTR under Grant No. PCI2023-143372, and the European Union's Horizon Europe Programme under project Chips Joint Undertaking (JU) under Grant No. 101112274. At the same time, this work has been partially supported by the European HiPEAC Network of Excellence, by the Spanish Ministry of Science and Innovation MCIN/AEI/10.13039/501100011033 (contract PID2019-107255GB-C21) , and by the Government of Catalonia (contract 2021-SGR-763) .X. Carril has the support of the predoctoral programme AGAUR-FI grants (2024 FI-1 00520) Joan Oro from the Secretariat for Universities and Research of the Department of Research and Universities of the Generalitat de Catalunya and theEuropean Social Fund Plus. J. Ribes-Gonzalez and O. Farras are supported by grant 2021-SGR-00115 from the Government of Catalonia, by the project HERMES, funded by INCIBE and by the European Union NextGeneration EU/PRTR, and the project ACITHEC PID2021-124928NB-I00, funded by MCIN/AEI/10.13039/501100011033. C. Hernandez was supported by "Ramony Cajal" fellowship No. RYC2020-030685-I. V. Kostalabros was supported by the Agency for Management of Universityand Research Grants (AGAUR) of the Government of Catalonia under "Ajuts per a la contractacio de personal investigadornovell" fellowship No. 2019FIB01274.
UPCommons. Portal del coneixement obert de la UPC
Publicación Contribución de congreso (ConferenceOutput)

A safety-critical, RISC-V SoC integrated and ASIC-ready classic McEliece accelerator

  • Kostalampros, Ioannis-Vatistas|||0000-0003-1912-5092
  • Ribes González, Jordi
  • Farràs Ventura, Oriol
  • Moretó Planas, Miquel|||0000-0002-9848-8758
  • Hernández Luz, Carles
Security is an integral part of ensuring the integrity of safety-critical systems. Safety-critical systems with extremely long-lifespan, such as the ones employed in the space and automotive industry, need additional security measures that can guarantee the thwarting of both current and future attacks. In that respect, the future advent of large-scale quantum computers, could potentially compromise the security of such systems leading to catastrophic consequences. To this end, in this paper we present the integration of the post-quantum cryptosystem of Classic McEliece (CM) in an open-source platform for high-performance safety-critical systems (SELENE). The SELENE project proposed a new family of safety-critical computing platforms, which builds upon open source components such as the RISC-V instruction set architecture, GNU/Linux, and the Jailhouse hypervisor. This work capitalizes on the modularity of the SELENE hardware platform and proposes a high-performance and constant-time HLS-based accelerator of the encoding and decoding subroutines of CM. We specifically present the first integration of a CM accelerator in a Linux-capable and RISC-V based System-on-Chip (SoC). Our experiments show significant speedups of up to 4.9x and 198x compared to a scalar software implementation of CM encoding and decoding subroutines respectively, executed on an x86 core. We additionally showcase a successful implementation of our accelerator in an ASIC context using the Global Foundries 22 nm technology node operating at >1 GHz frequency., This work has been partially supported by the European HiPEAC Network of Excellence, by the Spanish Ministry of Science and Innovation MCIN/AEI 10.13039/501100011033 (contracts ACITHEC PID2021-124928NBI00, PID2019-107255GB-C21 and “Ramón y Cajal” fellowship No. RYC2020-030685- I), by the Generalitat de Catalunya (contract 2021-SGR-00763), by the Agency for Management of University and Research Grants (AGAUR) of the Government of Catalonia under “Ajuts per a la contractació de personal investigador novell” fellowship No. 2019FI B01274 and the grant 2021SGR 00115, by the European Union within the framework of the ERDF of Catalonia 2014–2020 under the DRAC project [001-P001723], by the project HERMES funded by INCIBE, and by the European NextGenerationEU/PRTR., Peer Reviewed
UPCommons. Portal del coneixement obert de la UPC
Publicación Artículo científico (JournalArticle)

On the seeds and the great-grandchildren of a numerical semigroup

  • Bras Amorós, Maria|||0000-0002-3481-004X
We present a revisit of the seeds algorithm to explore the semigroup tree. First, an equivalent definition of seed is presented, which seems easier to manage. Second, we determine the seeds of semigroups with at most three left elements. And third, we find the great-grandchildren of any numerical semigroup in terms of its seeds. The the right-generators descendant (RGD) algorithm is the fastest known algorithm at the moment. But if one compares the originary seeds algorithm with the RGD algorithm, one observes that the seeds algorithm uses more elaborated mathematical tools while the RGD algorithm uses data structures that are better adapted to the final C implementations. For genera up to around one half of the maximum size of native integers, the newly defined seeds algorithm performs significantly better than the RGD algorithm. For future compilators allowing larger native sized integers this may constitute a powerful tool to explore the semigroup tree up to genera never explored before. The new seeds algorithm uses bitwise integer operations, the knowledge of the seeds of semigroups with at most three left elements and of the great-grandchildren of any numerical semigroup, apart from techniques such as parallelization and depth first search as wisely introduced in this context by Fromentin and Hivert [Math. Comp. 85 (2016) pp. 2553-2568]. The algorithm has been used to prove that there are no Eliahou semigroups of genus 66, hence proving the Wilf conjecture for genus up to 66. We also found three Eliahou semigroups of genus 67. One of these semigroups is neither of Eliahou-Fromentin type, nor of Delgado's type. However, it is a member of a new family suggested by Shalom Eliahou., The author was supported by the Spanish government under grant PID2021-124928NB-I00, and by the Catalan government under grant 2021 SGR 00115., Peer Reviewed
UPCommons. Portal del coneixement obert de la UPC
Publicación Artículo científico (JournalArticle)

Hardware acceleration for high-volume operations of CRYSTALS-Kyber and CRYSTALS-Dilithium

  • Carril Gil, Xavier|||0009-0008-8392-7579
  • Kardaris, Charalampos
  • Ribes González, Jordi
  • Farràs Ventura, Oriol
  • Hernández Luz, Carles
  • Kostalabros, Vatistas
  • González Jiménez, Joel Ulises
  • Moretó Planas, Miquel|||0000-0002-9848-8758
Many high-demand digital services need to perform several cryptographic operations, such as key exchange or security credentialing, in a concise amount of time. In turn, the security of some of these cryptographic schemes is threatened by advances in quantum computing, as quantum computer could break their security in the near future. Post-Quantum Cryptography (PQC) is an emerging field that studies cryptographic algorithms that resist such attacks. The National Institute of Standards and Technology (NIST) has selected the CRYSTALS-Kyber Key Encapsulation Mechanism and the CRYSTALSDilithium Digital Signature algorithm as primary PQC standards. In this paper, we present FPGA-based hardware accelerators for high-volume operations of both schemes. We apply High-Level Synthesis (HLS) for hardware optimization, leveraging a batch processing approach to maximize the memory throughput, and applying custom HLS logic to specific algorithmic components. Using reconfigurable field-programmable gate arrays (FPGAs), we show that our hardware accelerators achieve speedups between 3x and 9x over software baseline implementations, even over ones leveraging CPU vector architectures. Furthermore, the methods used in this study can also be extended to the new CRYSTALS-based NIST FIPS drafts, ML-KEM and ML-DSA, with similar acceleration results., This work was part of the project (ISOLDE), funded by MICIU/AEI/10.13039/501100011033 and the European Union NextGenerationEU/PRTR under Grant No. PCI2023-143372, and the European Union’s Horizon Europe Programme under project Chips Joint Undertaking (JU) under Grant No. 101112274. At the same time, this work has been partially supported by the European HiPEAC Network of Excellence, by the Spanish Ministry of Science and Innovation MCIN/AEI/ 10.13039/501100011033 (contract PID2019-107255GB-C21), and by the Government of Catalonia (contract 2021-SGR-763). X. Carril has the support of the predoctoral programme AGAUR-FI grants (2024 FI-1 00520) Joan Oró from the Secretariat for Universities and Research of the Department of Research and Universities of the Generalitat de Catalunya and the European Social Fund Plus. J. Ribes-González and O. Farràs are supported by grant 2021-SGR-00115 from the Government of Catalonia, by the project HERMES, funded by INCIBE and by the European Union NextGeneration EU/PRTR, and the project ACITHEC PID2021-124928NB-I00, funded by MCIN/AEI/10.13039/501100011033. C. Hernandez was supported by “Ramón y Cajal” fellowship No. RYC2020-030685-I. V. Kostalabros was supported by the Agency for Management of University and Research Grants (AGAUR) of the Government of Catalonia under “Ajuts per a la contractació de personal investigador novell” fellowship No. 2019FI B01274., Peer Reviewed
UPCommons. Portal del coneixement obert de la UPC
Publicación Artículo científico (JournalArticle)

Infinite chains in the tree of numerical semigroups

  • Rosas Ribeiro, Mariana
  • Bras Amorós, Maria|||0000-0002-3481-004X
One major problem in the study of numerical semigroups is determining the growth of the semigroup tree. We study infinite chains of numerical semigroups in the semigroup tree, firstly introduced by Bras-Amorós (Semigroup Forum, 71:561–574, 2009). Computational results show that these chains are rare, but without them the tree would not be infinite. It is proved that for each genus g = 5 there are more semigroups of that genus not belonging to infinite chains than semigroups belonging. Bras-Amorós (Semigroup Forum, 71:561–574, 2009) presented a characterization of the semigroups that belong to infinite chains in terms of the coprimality of the left elements of the semigroup as well as a result on the cardinality of the set of infinite chains to which a numerical semigroup belongs in terms of the primality of the greatest common divisor of these left elements. We revisit these results and fix an imprecision on the cardinality of the set of infinite chains to which a semigroup belongs in the case when the greatest common divisor of the left elements is a prime number. We then look at infinite chains in subtrees with fixed multiplicity. When the multiplicity is a prime number there is only one infinite chain in the tree of semigroups with such multiplicity. When the multiplicity is 4 or 6 we prove a self-replication behavior in the subtree and provide a formula for the number of semigroups in infinite chains of a given genus and multiplicity 4 and 6, respectively., The first author was supported by the Catalan government under grant 2021 FISDUR 00189. Both authors were supported by the Spanish government under grant PID2021-124928NB-I00, and by the Catalan government under grant 2021 SGR 00115., Peer Reviewed
UPCommons. Portal del coneixement obert de la UPC
Publicación Artículo científico (JournalArticle)

Leveraging HLS to design a versatile & high-performance Classic McEliece accelerator

  • Kostalabros, Vatistas
  • Ribes González, Jordi
  • Carril Gil, Xavier|||0009-0008-8392-7579
  • Farràs Ventura, Oriol
  • Hernández Luz, Carles
  • Moretó Planas, Miquel|||0000-0002-9848-8758
By harnessing fundamental quantum properties, a large-scale quantum computer could undermine currently deployed public-key algorithms. The post-quantum, code-based cryptosystem Classic McEliece (CM) addresses this security concern. However, its large public key size (up to 1.3 MB) poses various hardware implementation challenges. In this article, we focus on the high memory bandwidth requirements of the CM encoding function, in the context of heterogeneous CPU-FPGA devices. More concretely, we target the acceleration of public-key loading and processing from any globally shared or accelerator-private memory system. We present a novel and constant-time accelerator eEnc that exploits the elevated parallelization potential of FPGA devices to yield high-performance results. Our accelerator implements the encoding and the random error vector generation functions, which comprise the main computational load of Encapsulation. Two accelerator design variants are introduced, providing different hardware tradeoffs. Regarding intra-accelerator data communication, and unlike other state-of-the-art (SOTA) works, we combine a streaming protocol with task-level parallelization to remove the need to store the public key in accelerator-private memories. Our proposed design shows new record execution times over its SOTA counterparts, ranging on average from 3.5× up to 7.7× across the five security level parameter sets. Our end-to-end implementation in a Zynq SoC shows an average speedup of 2.2× compared to a 64-bit vectorized CM software-baseline. The elevated logic resource consumption, characteristic of HLS designs, can be readily adjusted with a performance tradeoff., This work has been partially supported by the European HiPEAC Network of Excellence, by the Spanish Ministry of Scienceand Innovation MCIN/AEI 10.13039/501100011033 (contracts ACITHEC PID2021-124928NB-I00, PID2019-107255GB-C21and ”Ramón y Cajal” fellowship No. RYC2020-030685-I), by the Generalitat de Catalunya (contract 2021-SGR-00763, 2021-SGR-00115 and 2023-146511NB-I00), by the Agency for Management of University and Research Grants (AGAUR) of theGovernment of Catalonia under ”Ajuts per a la contractació de personal investigador novell” (fellowships No. 2019FI B01274and 2024 FI-1 00520), by the European Union within the framework of the ERDF of Catalonia 2014–2020 under the DRACproject [001-P-001723], and by the project HERMES funded by the European NextGenerationEU/PRTR via INCIBE., Peer Reviewed
UPCommons. Portal del coneixement obert de la UPC
Publicación Artículo científico (JournalArticle)

Construction of an endgame rulebook for Sylver Coinage using trees of numerical semigroups

  • Bras Amorós, Maria|||0000-0002-3481-004X
  • Moskowitz, Gilad
  • Ponomarenko, Vadim
This is an original manuscript of an article published by Taylor & Francis in Communications in Algebra on 04 Feb 2025, available at: https://doi.org/10.1080/00927872.2025.2456089., In this paper we show how the algorithms to explore the tree of numerical semigroups can be used to calculate the winningness of positions in the game of Sylver Coinage. We introduce a new invariant for numerical semigroups, the minimal distance, and show how it can be used to prune the tree of numerical semigroups for an efficient way of calculating the winningness of positions in the game of Sylver Coinage. We end with a few open questions that were spawned as a result of this research., The first author was supported by the Spanish Ministerio de Ciencia e Innovación under grant PID2021-124928NB-I00, and by the Catalan Agéncia de Gestió d’Ajuts Universitaris i de Recerca under grant 2021 SGR 00115., Peer Reviewed
UPCommons. Portal del coneixement obert de la UPC
Publicación Artículo científico (JournalArticle)

Efficient representation of lattice path matroids

  • Padró Laimon, Carles|||0000-0002-8644-5929
Efficient deterministic algorithms to construct representations of lattice path matroids over finite fields are presented. They are built on known constructions of hierarchical secret sharing schemes, a recent characterization of hierarchical matroid ports, and the existence of isolating weight functions for lattice path matroids whose values are polynomial on the size of the ground set., Thanks to Anna de Mier for an enlightening discussion about transversal matroids. The author’s work was supported by the Spanish Government under projects PID2019-109379RB-I00 and PID2021-124928NB-I00., Peer Reviewed
Recercat. Dipósit de la Recerca de Catalunya
Publicación Contribución de congreso (ConferenceOutput)

A safety-critical, RISC-V SoC integrated and ASIC-ready classic McEliece accelerator

  • Kostalampros, Ioannis-Vatistas
  • Ribes González, Jordi
  • Farràs Ventura, Oriol
  • Moretó Planas, Miquel
  • Hernández Luz, Carles
Security is an integral part of ensuring the integrity of safety-critical systems. Safety-critical systems with extremely long-lifespan, such as the ones employed in the space and automotive industry, need additional security measures that can guarantee the thwarting of both current and future attacks. In that respect, the future advent of large-scale quantum computers, could potentially compromise the security of such systems leading to catastrophic consequences. To this end, in this paper we present the integration of the post-quantum cryptosystem of Classic McEliece (CM) in an open-source platform for high-performance safety-critical systems (SELENE). The SELENE project proposed a new family of safety-critical computing platforms, which builds upon open source components such as the RISC-V instruction set architecture, GNU/Linux, and the Jailhouse hypervisor. This work capitalizes on the modularity of the SELENE hardware platform and proposes a high-performance and constant-time HLS-based accelerator of the encoding and decoding subroutines of CM. We specifically present the first integration of a CM accelerator in a Linux-capable and RISC-V based System-on-Chip (SoC). Our experiments show significant speedups of up to 4.9x and 198x compared to a scalar software implementation of CM encoding and decoding subroutines respectively, executed on an x86 core. We additionally showcase a successful implementation of our accelerator in an ASIC context using the Global Foundries 22 nm technology node operating at >1 GHz frequency., This work has been partially supported by the European HiPEAC Network of Excellence, by the Spanish Ministry of Science and Innovation MCIN/AEI 10.13039/501100011033 (contracts ACITHEC PID2021-124928NBI00, PID2019-107255GB-C21 and “Ramón y Cajal” fellowship No. RYC2020-030685- I), by the Generalitat de Catalunya (contract 2021-SGR-00763), by the Agency for Management of University and Research Grants (AGAUR) of the Government of Catalonia under “Ajuts per a la contractació de personal investigador novell” fellowship No. 2019FI B01274 and the grant 2021SGR 00115, by the European Union within the framework of the ERDF of Catalonia 2014–2020 under the DRAC project [001-P001723], by the project HERMES funded by INCIBE, and by the European NextGenerationEU/PRTR., Peer Reviewed, Postprint (author's final draft)
Recercat. Dipósit de la Recerca de Catalunya
Publicación Artículo científico (JournalArticle)

Efficient representation of lattice path matroids

  • Padró Laimon, Carles
Efficient deterministic algorithms to construct representations of lattice path matroids over finite fields are presented. They are built on known constructions of hierarchical secret sharing schemes, a recent characterization of hierarchical matroid ports, and the existence of isolating weight functions for lattice path matroids whose values are polynomial on the size of the ground set., Thanks to Anna de Mier for an enlightening discussion about transversal matroids. The author’s work was supported by the Spanish Government under projects PID2019-109379RB-I00 and PID2021-124928NB-I00., Peer Reviewed, Postprint (author's final draft)
Recercat. Dipósit de la Recerca de Catalunya
Publicación Artículo científico (JournalArticle)

On the seeds and the great-grandchildren of a numerical semigroup

  • Bras Amorós, Maria
We present a revisit of the seeds algorithm to explore the semigroup tree. First, an equivalent definition of seed is presented, which seems easier to manage. Second, we determine the seeds of semigroups with at most three left elements. And third, we find the great-grandchildren of any numerical semigroup in terms of its seeds. The the right-generators descendant (RGD) algorithm is the fastest known algorithm at the moment. But if one compares the originary seeds algorithm with the RGD algorithm, one observes that the seeds algorithm uses more elaborated mathematical tools while the RGD algorithm uses data structures that are better adapted to the final C implementations. For genera up to around one half of the maximum size of native integers, the newly defined seeds algorithm performs significantly better than the RGD algorithm. For future compilators allowing larger native sized integers this may constitute a powerful tool to explore the semigroup tree up to genera never explored before. The new seeds algorithm uses bitwise integer operations, the knowledge of the seeds of semigroups with at most three left elements and of the great-grandchildren of any numerical semigroup, apart from techniques such as parallelization and depth first search as wisely introduced in this context by Fromentin and Hivert [Math. Comp. 85 (2016) pp. 2553-2568]. The algorithm has been used to prove that there are no Eliahou semigroups of genus 66, hence proving the Wilf conjecture for genus up to 66. We also found three Eliahou semigroups of genus 67. One of these semigroups is neither of Eliahou-Fromentin type, nor of Delgado's type. However, it is a member of a new family suggested by Shalom Eliahou., The author was supported by the Spanish government under grant PID2021-124928NB-I00, and by the Catalan government under grant 2021 SGR 00115., Peer Reviewed, Postprint (author's final draft)
Recercat. Dipósit de la Recerca de Catalunya
Publicación Artículo científico (JournalArticle)

Infinite chains in the tree of numerical semigroups

  • Rosas Ribeiro, Mariana
  • Bras Amorós, Maria
One major problem in the study of numerical semigroups is determining the growth of the semigroup tree. We study infinite chains of numerical semigroups in the semigroup tree, firstly introduced by Bras-Amorós (Semigroup Forum, 71:561–574, 2009). Computational results show that these chains are rare, but without them the tree would not be infinite. It is proved that for each genus g = 5 there are more semigroups of that genus not belonging to infinite chains than semigroups belonging. Bras-Amorós (Semigroup Forum, 71:561–574, 2009) presented a characterization of the semigroups that belong to infinite chains in terms of the coprimality of the left elements of the semigroup as well as a result on the cardinality of the set of infinite chains to which a numerical semigroup belongs in terms of the primality of the greatest common divisor of these left elements. We revisit these results and fix an imprecision on the cardinality of the set of infinite chains to which a semigroup belongs in the case when the greatest common divisor of the left elements is a prime number. We then look at infinite chains in subtrees with fixed multiplicity. When the multiplicity is a prime number there is only one infinite chain in the tree of semigroups with such multiplicity. When the multiplicity is 4 or 6 we prove a self-replication behavior in the subtree and provide a formula for the number of semigroups in infinite chains of a given genus and multiplicity 4 and 6, respectively., The first author was supported by the Catalan government under grant 2021 FISDUR 00189. Both authors were supported by the Spanish government under grant PID2021-124928NB-I00, and by the Catalan government under grant 2021 SGR 00115., Peer Reviewed, Postprint (published version)
Recercat. Dipósit de la Recerca de Catalunya
Publicación Artículo científico (JournalArticle)

Construction of an endgame rulebook for Sylver Coinage using trees of numerical semigroups

  • Bras Amorós, Maria
  • Moskowitz, Gilad
  • Ponomarenko, Vadim
This is an original manuscript of an article published by Taylor & Francis in Communications in Algebra on 04 Feb 2025, available at: https://doi.org/10.1080/00927872.2025.2456089., In this paper we show how the algorithms to explore the tree of numerical semigroups can be used to calculate the winningness of positions in the game of Sylver Coinage. We introduce a new invariant for numerical semigroups, the minimal distance, and show how it can be used to prune the tree of numerical semigroups for an efficient way of calculating the winningness of positions in the game of Sylver Coinage. We end with a few open questions that were spawned as a result of this research., The first author was supported by the Spanish Ministerio de Ciencia e Innovación under grant PID2021-124928NB-I00, and by the Catalan Agéncia de Gestió d’Ajuts Universitaris i de Recerca under grant 2021 SGR 00115., Peer Reviewed, Preprint
Recercat. Dipósit de la Recerca de Catalunya
Publicación Artículo científico (JournalArticle)

Hardware acceleration for high-volume operations of CRYSTALS-Kyber and CRYSTALS-Dilithium

  • Carril Gil, Xavier
  • Kardaris, Charalampos
  • Ribes González, Jordi
  • Farràs Ventura, Oriol
  • Hernández Luz, Carles
  • Kostalabros, Vatistas
  • González Jiménez, Joel Ulises
  • Moretó Planas, Miquel
Many high-demand digital services need to perform several cryptographic operations, such as key exchange or security credentialing, in a concise amount of time. In turn, the security of some of these cryptographic schemes is threatened by advances in quantum computing, as quantum computer could break their security in the near future. Post-Quantum Cryptography (PQC) is an emerging field that studies cryptographic algorithms that resist such attacks. The National Institute of Standards and Technology (NIST) has selected the CRYSTALS-Kyber Key Encapsulation Mechanism and the CRYSTALSDilithium Digital Signature algorithm as primary PQC standards. In this paper, we present FPGA-based hardware accelerators for high-volume operations of both schemes. We apply High-Level Synthesis (HLS) for hardware optimization, leveraging a batch processing approach to maximize the memory throughput, and applying custom HLS logic to specific algorithmic components. Using reconfigurable field-programmable gate arrays (FPGAs), we show that our hardware accelerators achieve speedups between 3x and 9x over software baseline implementations, even over ones leveraging CPU vector architectures. Furthermore, the methods used in this study can also be extended to the new CRYSTALS-based NIST FIPS drafts, ML-KEM and ML-DSA, with similar acceleration results., This work was part of the project (ISOLDE), funded by MICIU/AEI/10.13039/501100011033 and the European Union NextGenerationEU/PRTR under Grant No. PCI2023-143372, and the European Union’s Horizon Europe Programme under project Chips Joint Undertaking (JU) under Grant No. 101112274. At the same time, this work has been partially supported by the European HiPEAC Network of Excellence, by the Spanish Ministry of Science and Innovation MCIN/AEI/ 10.13039/501100011033 (contract PID2019-107255GB-C21), and by the Government of Catalonia (contract 2021-SGR-763). X. Carril has the support of the predoctoral programme AGAUR-FI grants (2024 FI-1 00520) Joan Oró from the Secretariat for Universities and Research of the Department of Research and Universities of the Generalitat de Catalunya and the European Social Fund Plus. J. Ribes-González and O. Farràs are supported by grant 2021-SGR-00115 from the Government of Catalonia, by the project HERMES, funded by INCIBE and by the European Union NextGeneration EU/PRTR, and the project ACITHEC PID2021-124928NB-I00, funded by MCIN/AEI/10.13039/501100011033. C. Hernandez was supported by “Ramón y Cajal” fellowship No. RYC2020-030685-I. V. Kostalabros was supported by the Agency for Management of University and Research Grants (AGAUR) of the Government of Catalonia under “Ajuts per a la contractació de personal investigador novell” fellowship No. 2019FI B01274., Peer Reviewed, Postprint (author's final draft)