We envision linear codes and secret sharing schemes as different mathematical objects in their final purposes, but similar in their theoretical roots. Within our project, we will approach these areas from a unified perspective, seeking synergies between them, from their interconnected mathematical background to their final applications. We build a multidisciplinary working team with researchers from diverse backgrounds (Coding Theory, Cryptography, Algebraic Geometry, Matroid Theory, Computer Science, Computer Architecture) that studied linear codes and secret sharing schemes from different perspectives. This project is an opportunity to bring together these researchers and study some of the most important open problems about AG codes, secret sharing schemes, and code-based cryptography. We will study fundamental mathematical questions as well as computational aspects that affect their practical application.
Team
Main researchers
Research team
- Dr. Julio Fernández González, UPC
- Dr. Carles Padró Laimon, UPC
- Dr. Miquel Moretó Planas, UPC
Work team
- Dr. Hebert Pérez-Rosés, URV
- Dr. Jordi Ribes-González, URV
- Dr. Amos Beimel, Ben-Gurion University, Israel
- Dr. Alonso S. Castellanos, Universidade Federal de Uberlândia, Brazil
- Dr. Kwankyu Lee, Chosun University, Korea
- Dr. Michael O’Sullivan, San Diego State University
- Dr. Naty Peter, Tel Aviv University, Israel
- Dra. Luciane Quoos, Univesidade Federal do Rio de Janeiro, Brazil
- Dra. Klara Stokes, Umeå Universitet, Sweden
- Mr. José Miquel Serradilla, URV
- Ms. Raquel Pascual, URV
- Ms. Mariana Rosas, URV
Goals
ACITHEC will study fundamental open problems related to Algebraic Geometry codes and secret sharing schemes, as well as computational aspects that affect their practical application. More precisely, the project deals with the construction of quantum codes from flags of codes, the construction of more efficient secret sharing schemes, hardware acceleration of post-quantum cryptographic schemes and finite field arithmetic, the characterization of representable matroids, and the study of the asymptotic behaviour of numerical semigroups.
Algebraic-geometry codes
One general objective for researchers in algebraic-geometry codes, is that of finding good codes, where “good” may refer to optimal code parameters (dimension, length, correction capability, etc.), may refer to the existence of efficient or fast decoding algorithms, or may refer to their suitability for specific purposes or applications. For instance, the length of AG codes is known to be bounded by the Hasse-Weil bound and so, “good codes” may be the codes obtained from maximal curves attaining this bound.
- We will work on the non-easy search for codes whose structure suits with the purpose of constructing quantum codes with known dimension and correcting capability.
- We look for alternative, more refined bounds for the length of codes (in which case the latter meaning of “good” referred to the code length may be modified) and the correction capability.
Numerical semigroups
From AG codes we will naturally move to the area of numerical semigroups, since numerical semigroups are ubiquitous in any area of AG codes. We aim at contributing to the knowledge of their asymptotic behaviour and to the solution of open conjectures from a computational approach.
- We will study the typical form of a general numerical semigroup as the genus grows to infinity.
- We will deal with applications of numerical semigroups to other areas such as in the definition of routing strategies in graphs.
Code-based PQC
In the area of code-based PQC, we are interested in the hardware acceleration of CM and other lattice-based cryptographic schemes. Until now, we accelerated CM with an HLS-based hardwaresoftware codesign, accelerating Gaussian elimination of binary matrices, and finite field arithmetic. Our objective is to move further in two directions:
- Design RISC-V accelerators for these operations and for other elemental operations in lattice-based NIST candidates.
- Design more general RISC-V accelerators for finite field arithmetic and decoding of linear codes.
General secret sharing schemes
As mentioned in the state of the art, the share size of general secret sharing schemes is poorly understood. A natural question is if upper bounds and lower bounds on the information rate of (general) secret sharing schemes for almost all access structures can be improved. This is motivated by the fact that every n/2-uniform access structure can be realized by a scheme with normalized maximum share size O(n2) (with exponentially long secrets). Since almost all access structures resemble uniform access structures one can hope that almost every access structure can be realized by a scheme with polynomial normalized share size.
Secret sharing schemes are building blocks of many cryptographic protocols, and there are reductions from many cryptographic schemes to secret sharing schemes.
- We are interested in constructing better Conditional Disclosure of Secrets (CDS) protocols and Oblivious Transfer (OT)-combiners by means of secret-sharing techniques.
- We will move further on the characterization of matroids that are linear, multilinear, algebraic, or almost entropic
Publications
Indexed journals
- O. Farràs and J.Ribes, "One-out-of-q OT Combiners", IEEE Transactions on Information Theory. To Appear. [DOI]
- M. Bras-Amoros, "On the seeds and the great-grandchildren of a numerical semigroup", Mathematics of Computation, Vol. 93, pp. 411-441, Jan 2024, ISSN: 0025-5718. [DOI]
- M. Bras-Amorós, A. S. Castellanos and L. Quoos, "Isometry-Dual Flags of Many-Point AG Codes", SIAM Journal on Applied Algebra and Geometry, Vol. 7, no. 4, pp. 786-808, Dec 2023, ISSN: 2470-6566. [DOI]
Conference papers
- V. Kostalabros, J. Ribes-González, O. Farràs, M. Moretó, C. Hernandez, "A Safety-Critical, RISC-V SoC Integrated and ASIC-Ready Classic McEliece Accelerator", International Symposium on Applied Reconfigurable Computing - ARC 2024, Aveiro, Portugal, In Lecture Notes in Computer Science vol 14553, pp. 282-295, ISBN: 978-3-031-33376-7, Mar 2024. [DOI]
- A. Beimel, O. Farràs and O. Lasri, "Improved Polynomial Secret-Sharing Schemes", 21st International Conference on Theory of Cryptography - TCC2023, Taipei (Taiwan), In Lecture Notes in Computer Science vol. 14370, pp. 374-405, ISBN: 978-3-031-33376-7, Nov 2023. [DOI]