Pasar al contenido principal

EL RETO POST-CUANTICO: PROTEGIENDO LA SOCIEDAD CON ISOGENIAS Y CODIGOS

PID2021-124613OB-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 UNIVERSIDAD DE LLEIDA

Resultados relacionados

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

Repositori Obert UdL
Publicación Artículo científico (JournalArticle)

A quantum-resistant unlinkable and strongly-unsplittable multi-coupon system

  • Sebé Feixas, Francesc
  • Simón, Sergi
A multi-coupon is a batch of coupons (or tokens) a customer can redeem to a merchant in order to obtain some good or service. When all the tokens are intended to be redeemed by the same customer, their sharing is a fraud. Completely preventing token sharing is not possible when the system is endowed with privacy-preserving features such as anonymity and unlinkability. So, several options to make multi-coupon splitting difficult have been proposed in the research literature. One of them is the so-called strong unsplittability approach. All the existing unsplittable multi-coupon systems proposed so far have been designed using cryptography whose security assumes the existence of a hard to factor RSA modulus. Since the integer factorization problem will cease to be hard if a powerful enough quantum computer is eventually built, all these systems are constructed over quantum-vulnerable technology. In this paper, we prove strongly unsplittable multi-coupons can be designed using quantum-resistant cryptography. The proposal employs lattice-based cryptography whose security holds on the assumed hardness of variants of the short integer solution (SIS) and learning with errors (LWE) problems. To the best of authors’ knowledge, no such system has been proposed so far., This research is a result of the Strategic Project “Advances in post-quantum cryptography applied to the development of a coupon system” (C039/24), resulting from an agreement between the Spanish National Cybersecurity Institute (INCIBE) and University of Lleida. This initiative is carried out in the scope of the funds from the Recovery, Transformation and Resilience Plan, funded by the European Union (Next Generation). This research is also part of the R&D+i project PID2021-124613OB-I00 funded by MICIU/ AEI/10.13039/501100011033 and FEDER, EU.
Repositori Obert UdL
Publicación Artículo científico (JournalArticle)

Exceptional zero formulas for anticyclotomic p-adic L-functions

  • Hernández Barrios, Víctor
  • Molina Blanco, Santiago
In this note we define anticyclotomic p-adic measures attached to a modular elliptic curve E over a general number field F, a quadratic extension, and a set of places S of F above p. We study the exceptional zero phenomenon that arises when E has multiplicative reduction at some place in S. In this direction, we obtain p-adic Gross-Zagier formulas relating derivatives of the corresponding p-adic L-functions to the extended Mordell-Weil group of E. Our main result uses the recent construction of plectic points on elliptic curves due to Fornea and Gehrmann and generalizes their main result in [9]. We obtain a formula that computes the r-th derivative of the p-adic L-function, where r is the number of places in S where E has multiplicative reduction, in terms of plectic points and Tate periods of E., This project has received funding from the European Research Council (ERC) under the European Union's Horizon 2020 research and innovation programme (grant agreement No. 682152). Moreover, the second author has been partially funded by the projects PID2021-124613OB-I00 and PID2022-137605NB-I00 from Ministerio de Ciencia e innovación. We would also like to thank Lennart Gehrmann and Marc Masdeu for all their helpful remarks and comments.
Repositori Obert UdL
Publicación Artículo científico (JournalArticle)

On the Nonexistence of Almost Moore Digraphs with Self-Repeats

  • Messegué, Arnau
  • Miret, Josep M. (Josep Maria)
  • Sillasen, Anita A.
An almost Moore digraph is a diregular digraph of degree d > 1, diameter k > 1 and order d + d 2 + · · · + dk. Their existence has only been shown for k = 2. It has also been conjectured that there are no more almost Moore digraphs, but so far their nonexistence has only been proven for k = 3, 4 and for d = 2, 3 when k ⩾ 3. In this paper we study the structure of the subdigraphs of an almost Moore digraph induced by the vertices fixed by an automorphism determined by a power of the permutation r of repeats of the digraph. We deduce that each almost Moore digraph of degree d and diameter k with self-repeats has such a subdigraph whose vertices have order ⩽ d − 1 under r. From this, we extend the results about the nonexistence of almost Moore digraphs with self-repeats of degrees 4 and 5 to those whose diameter is large enough with respect to the degree. More precisely, we prove their nonexistence when k ⩾ 2(d−1) if k is odd and when k ⩾ 2(d−1)2 if k is even. We also show that these findings jointly with other results imply that there are no almost Moore digraphs with self-repeats for degrees d, 6 ⩽ d ⩽ 12, and k > 2., The authors would like to thank the anonymous referees, whose comments highly improved the quality of this paper. Arnau Messegué was supported in part by grant 2021SGR-00434 and Josep Miret was supported in part by grants PID2021-124613OB-I00 and 2021SGR00434.
Repositori Obert UdL
Publicación Artículo científico (JournalArticle)

On the permutation cycle structures for almost Moore digraphs of degrees 4 and 5

  • Miret, Josep M. (Josep Maria)
  • Simanjuntak, Rinovia
  • Simón, Sergi
Almost Moore digraphs of degree d and diameter k, for short (d, k)-digraphs, appear in the degree/diameter problem as a class of extremal directed graphs. Their order is one less than the unattainable Moore bound M(d, k) = 1 + d + · · · + d k . So far, their existence has only been shown for k = 2. Their nonexistence has been proven for k = 3, 4 and for d = 2, 3, when k ≥ 3. In this paper, we study the possible cycle structures of the permutation of repeats for the (4, k) and (5, k)-digraphs., Research of the first and third authors was supported in part by grants PID2021-124613OB-I00 and 2021SGR-00434. The research of the second author was supported by Institut Teknologi Bandung under the grant Riset Unggulan. The authors would also like to thank the anonymous referees, whose comments have significantly improved the quality of this paper.
Repositori Obert UdL
Publicación Artículo científico (JournalArticle)

Point (de)compression for elliptic curves over highly 2-adic finite fields

  • Koshelev, Dmitrii
This article addresses the issue of efficient and safe (de)compression of Fq-points on an elliptic curve E over a highly 2-adic finite field Fq of characteristic 5 or greater. The given issue was overlooked by cryptography experts, probably because, until recently, such fields were not in trend. Therefore, there was no difficulty (with rare exceptions) in finding a square Fq-root. However, in our days, fields with large 2-adicities have gained particular popularity in the ZK (zero-knowledge) community, despite the fact that √ · ∈ Fq should be computed via more sophisticated square-root algorithms such as (Cipolla–Lehmer–)Müller’s one. The article explains why the classical x-coordinate (de)compression method based on Müller’s algorithm often contains Achilles’ heel to successfully perform a novel fault attack, which also fits the definition of a (D)DoS attack. In a nutshell, the trouble stems from the non-eterministic initialization of Müller’s algorithm. Moreover, the article suggests a countermeasure, namely an alternative (still simple) (de)compression method that completely prevents the discovered attack whenever the curve E/Fq is of even order. In particular, all twisted Edwards (i.e., Montgomery) curves are relevant. The decompression stage of the new method equally suffers from one square-root extraction in Fq. But the corresponding quadratic residue is inherently equipped with additional information, providing an opportunity to launch M¨uller’s algorithm immediately from its main deterministic part. In turn, the compression stage of the new method remains (almost) free as well as for the x-coordinate method., his research is a result of the strategic project “Avances en criptografía postcuántica aplicados al desarrollo de un sistema de cupones” (C039/24), resulting from an agreement between the National Cybersecurity Institute (INCIBE) and University of Lleida. This initiative is carried out in the scope of the funds from the Recovery, Transformation and Resilience Plan, funded by the European Union (Next Generation). The paper is also a part of the R&D+i project PID2021-124613OB-I00 funded by MICIU/AEI/10.13039/501100011033 and FEDER, EU.
Repositori Obert UdL
Publicación Artículo científico (JournalArticle)

Triple product 𝑝-adic 𝐿-functions for Shimura curves over totally real number fields

  • Barrera Salazar, Daniel
  • Molina Blanco, Santiago
Let 𝐹 be a totally real number field. Using a recent geometric approach developed by Andreatta and Iovita we construct several variables 𝑝-adic families of finite slope quaternionic automorphic forms over 𝐹. It is achieved by interpolating the modular sheaves defined over some auxiliary unitary Shimura curves. Secondly, we attach 𝑝-adic 𝐿-functions to triples of ordinary 𝑝-adic families of quaternionic automorphic eigenforms. This is done by relating trilinear periods to some trilinear products over unitary Shimura curves which can be interpolated adapting the work of Liu–Zhang–Zhang to our families., The authors are supported in part by DGICYT Grant MTM2015-63829-P. This project has received funding from the European Research Council (ERC) under the European Union’s Horizon 2020 research and innovation programme (grant agreement No. 682152). D.B. was also funded by ANID FONDECYT grants 11201025 and 1241702. S. M. is also funded by Ministerio de Ciencia e innovación, project PID2022-137605NBI00, and this paper is part of the R&D+i project PID2021-124613OB-I00 funded by MICIU/AEI/10.13039/501100011033 and FEDER, EU.
Repositori Obert UdL
Publicación Artículo científico (JournalArticle)

A reusable public transport electronic ticket system with fast validation

  • Borges Llorens, Ricard
  • Sebé Feixas, Francesc
This paper presents an electronic ticket system for public transport which provides reusability in the sense that, after the validation of a ticket, a traveler is enabled to perform a journey which can include a limited number of transfers before an expiration time. The proposal has been designed following a privacy-by-design approach. Travelers are only required to identify themselves if requested to prove possession of a valid ticket by an officer. Otherwise, they can travel without being required to disclose their identity (anonymity). Also, the diverse interactions of a traveler with the system cannot be related to them (unlinkability). The security and privacy requirements are achieved by making use of advanced cryptographic techniques. The system has been simulated and proven to provide running times which make it appropriate for a real deployment. When compared to an existing proposal designed for an equivalent scenario, the reduction in the time required for ticket validation is especially remarkable. In effect, all the use cases with real-time constraints (“Ticket validation”, “Get-in”, and “Get-out”) can be run in less than one second., Open Access funding provided thanks to the CRUE-CSIC agreement with Springer Nature. This paper is part of the R&D+i project PID2021-124613OB-I00 funded by MICIU/ AEI/10.13039/501100011033 and FEDER,EU.
Repositori Obert UdL
Publicación Artículo científico (JournalArticle)

E-Coin-Based Priced Oblivious Transfer with a Fast Item Retrieval

  • Sebé Feixas, Francesc
  • Simón, Sergi
Priced oblivious transfer (POT) is a cryptographic protocol designed for privacy-preserving e-commerce of digital content. It involves two parties: the merchant, who provides a set of priced items as input, and a customer, who acquires one of them. After the protocol has run, the customer obtains the item they chose, while the merchant cannot determine which one. Moreover, the protocol guarantees that the customer gets the content only if they have paid the price established by the merchant. In a recent paper, the authors proposed a POT system where the payments employed e-coin transactions. The strong point of the proposal was the absence of zero-knowledge proofs required in preceding systems to guarantee the correctness of payments. In this paper, we propose a novel e-coin-based POT system with a fast item retrieval procedure whose running time does not depend on the number of items for sale. This is an improvement over the aforementioned existing proposal whose execution time becomes prohibitively long when the catalog is extensive. The use of zero-knowledge proofs is neither required., This research was funded by the Spanish Ministry of Science and Innovation (grant number PID2021-124613OB-I00).
Repositori Obert UdL
Publicación Artículo científico (JournalArticle)

Privacy-Preserving Electricity Trading for Connected Microgrids

  • Alàs Cercós, Oriol
  • Sebé Feixas, Francesc
The electricity market is evolving from the traditional unidirectional model into a bidirectional one in which households also generate and sell energy. This new scenario requires technology able to manage the available energy and guarantee that all the participants pay or are paid appropriately. Unfortunately, fine-grained monitoring of energy production and consumption makes it possible to infer sensitive information about confidential aspects of people’s private life. In this paper, we propose a system designed for privacy-preserving electricity trading in a connected microgrid. The system guarantees that at the end of a billing period, the distribution system operator can compute the quantity to be charged or paid to each household while being unable to trace its consumption details., This research was funded by the Spanish Ministry of Science and Innovation (grant number PID2021-124613OB-I00)
Repositori Obert UdL
Publicación Contribución de congreso (ConferenceOutput)

Generación mejorada de ruido para oráculos de descifrado de la cifra Kyber

  • Sebé Feixas, Francesc
La cifra Kyber es un estandar NIST de cifrado de clave publica cuya seguridad depende de la supuesta intratabilidad del problema M-LWE (module learning with errors). En este artículo estudiamos el uso de Kyber en un entorno donde el poseedor de la clave privada actua como un oráculo que colabora en el descifrado de textos cifrados que le proporcionan otras partes con el requisito de que el oraculo no debe obtener información sobre los textos en claro resultantes. Veremos que, en un escenario como el descrito, existe un riesgo de que se revele informacin que permite la reconstrucción de la clave privada. Esto obliga a limitar el numero de veces que el oráculo puede utilizar una determinada clave. El artículo propone una solución para incrementar el numero máximo de usos de cada clave., Este trabajo es parte del proyecto R&D+i PID2021-124613OB-I00 financiado por MICIU/ AEI/10.13039/501100011033 y FEDER, EU. Esta investigacion también resulta del Proyecto Estratégico Avances en criptografía post-cuantica aplicados al desarrollo de un sistema de cupones (C039/24), fruto del convenio de colaboracion suscrito entre el Instituto Nacional de Ciberseguridad (INCIBE) y la Universidad de Lleida. Esta iniciativa se realiza en el marco de los fondos del Plan de Recuperacion, Transformación y Resiliencia, financiados por la Unión Europea (Next Generation).
Repositori Obert UdL
Publicación Artículo científico (JournalArticle)

An e-coin based construction for unlinkable priced oblivious transfer

  • Borges Llorens, Ricard
  • Sebé Feixas, Francesc
A 1-out-of-n Oblivious Transfer (OT) protocol involves two participants: a sender, who provides a set of items as input, and a receiver. The protocol guarantees that the receiver gets exactly one of the items of the input set, while the sender is unable to determine which. Priced Oblivious Transfer (POT) protocols further allow each item of the input set to be assigned a price in such a way that, after a proper execution of the protocol, the receiver gets the requested item if and only if the corresponding sum of money has been paid. In this paper, we present a construction which takes a 1-out-of-n OT protocol and transform it into a POT one. Moreover, the resulting system is unlinkable in the sense that the sender is unable to determine whether two executions of the protocol were run by the same receiver or not. When compared to existing unlinkable POT protocols, our construction offers a lower conceptual complexity as it does not involve the use of zero-knowledge proofs., This work was supported by the Spanish Ministry of Science and Innovation (project number PID2021-124613OB-I00).
Repositori Obert UdL
Publicación Artículo científico (JournalArticle)

Trisections and cubes in elliptic curves

  • Pujolàs Boix, Jordi
  • Thériault, Nicolas
We show how to compute the pre-images of multiplication by 3 in the group of points of an elliptic curve E over a field k of characteristic different from 2 and 3 such that E[3](k) = E[3]. We show Q = (xQ, yQ) ∈ [3]E(k) if and only if yQ − d − m(xQ − c) is a cube in k for every 3-torsion point (c, d) ∈ E[3], where m is the slope of the tangent to E at (c, d). We reduce our problem to the computation of at most 2 independent cubic roots plus a few polynomial operations., Research of the authors was supported in part by grants PID2021-124613OB-I00 (Spanish Ministerio de Ciencia e Innovación) and DICYT 041933T (Universidad de Santiago de Chile), and CyTeD (“Programa Iberoamericano de Ciencia y Tecnología para el Desarrollo”) project 522RT0131
Repositori Obert UdL
Publicación Artículo científico (JournalArticle)

Quantum-resistant asymmetric secure computation with applications to priced oblivious transfer

  • Sebé Feixas, Francesc
  • Simón, Sergi
Priced oblivious transfer (POT) is a cryptographic protocol in which a merchant provides a set of items for sale and a customer acquires one of them. The protocol guarantees that the customer receives the item if and only if they have paid its price, while the merchant remains oblivious to the acquired item. Obviously, the merchant cannot not know what price the client has paid, as such price could be unique. A recent paper proposes a POT protocol that is built from two blocks: an e-coin system and an asymmetric secure computation protocol. In this paper, we present a quantum-resistant proposal for the latter building block. As a result, we are able to construct a quantum-resistant POT protocol implemented from the newly proposed asymmetric secure computation protocol and a post-quantum implementation of the mentioned e-coin system. To our knowledge, no quantum-resistant POT protocol has been proposed so far., This paper is part of the R&D+i project PID2021-124613OB-I00 funded by the Spanish Research Agency MICIU/AEI/10.13039/501100011033 and FEDER, EU. This paper is also part of the project “Advances in post-quantum cryptography applied to the development of a coupon system,” financed by “European Union NextGeneration–UE, the Recovery Plan, Transformation and Resilience, through INCIBE.”
Repositori Obert UdL
Publicación Contribución de congreso (ConferenceOutput)

A Quantum-Resistant Implementation of a Digital Cash System with Valued and no-Valued e-Coins

  • Miret, Josep M. (Josep Maria)
  • Sebé Feixas, Francesc
  • Simón, Sergi
Digital cash is a form of money that is minted, stored, and spent digitally. As opposed to debit or credit cards, it enables untraceable payments in the sense that the payer can acquire products while keeping their identity secret. In a recent paper, a new digital cash paradigm including the so-called no-valued e-coins was proposed. No-valued e-coins are used to perform bogus transactions which mask consumption patterns. In this paper, we analyze the aforementioned cash paradigm and investigate the possibility of implementing it over quantumresistant cryptographic schemes. This objective has been achieved using off-the-shelf cryptosystems for data encryption and digital signature which have been deeply analyzed to check they provide the required features., This paper is also part of the project “Avances en criptografía post-cuántica aplicados al desarrollo de un sistema de cupones”, financed by “European Union NextGeneration–UE, the Recovery Plan, Transformation and Resilience, through INCIBE”.
Repositori Obert UdL
Publicación Artículo científico (JournalArticle)

Nonexistence of Almost Moore Digraphs of Degrees 4 and 5 with Self-Repeats

  • López Lorenzo, Ignacio
  • Messegué, Arnau
  • Miret, Josep M. (Josep Maria)
An almost Moore (d, k)-digraph is a regular digraph of degree d > 1, diameter k > 1 and order N(d, k) = d + d2 + · · · + dk . So far, their existence has only been shown for k = 2, whilst it is known that there are no such digraphs for k = 3, 4 and for d = 2, 3 when k ! 3. Furthermore, under certain assumptions, the nonexistence for the remaining cases has also been shown. In this paper, we prove that (4, k) and (5, k)-almost Moore digraphs with self-repeats do not exist for k ! 5., Supported in part by grants PID2020-115442RB-I00 and 2021SGR-00434. Supported in part by grants Margarita Salaand 2021SGR-00434. Supported in part by grants PID2021-124613OB-I00 and 2021SGR-00434
Repositori Obert UdL
Publicación Artículo científico (JournalArticle)

A strongly unsplittable multi-coupon system with off-line verification and selectively-revocable anonymity

  • Sebé Feixas, Francesc
  • Valls Marsal, Magda
This paper firstly reports a security flaw and a way to fix it detected in a multi-coupon system presented by Liu et al. in a paper published in 2017. That proposal provides selectively-revocable anonymity in the sense that the anonymity of customers is guaranteed unless they act dishonestly by redeeming a multi-coupon more times than allowed. Nevertheless, that system lacks two important security properties of multi-coupons: unlinkability and unsplittability. After that, we propose a novel multi-coupon construction which takes Brands off-line e-coin system as a building block. In this way, the multi-coupon system inherits the selective-revocability property of the mentioned e-coin system without the need to develop new ad-hoc cryptography. Furthermore, the proposed system is also proven to be unlinkable and strongly unsplittable. Its design makes use of a novel extension of the RSA blind signature protocol which endows it with conditional secret recovery., This paper is part of the R&D+i project PID2021-124613OB-I00 funded by MICIU/AEI/10.13039/501100011033 and FEDER, EU. The Cryptography and Graphs Research Group has been recognized as a consolidated research group 2021-SGR-00434 by Generalitat de Catalunya.
Recercat. Dipósit de la Recerca de Catalunya
Publicación Artículo científico (JournalArticle)

A quantum-resistant unlinkable and strongly-unsplittable multi-coupon system

  • Sebé Feixas, Francesc
  • Simón, Sergi
A multi-coupon is a batch of coupons (or tokens) a customer can redeem to a merchant in order to obtain some good or service. When all the tokens are intended to be redeemed by the same customer, their sharing is a fraud. Completely preventing token sharing is not possible when the system is endowed with privacy-preserving features such as anonymity and unlinkability. So, several options to make multi-coupon splitting difficult have been proposed in the research literature. One of them is the so-called strong unsplittability approach. All the existing unsplittable multi-coupon systems proposed so far have been designed using cryptography whose security assumes the existence of a hard to factor RSA modulus. Since the integer factorization problem will cease to be hard if a powerful enough quantum computer is eventually built, all these systems are constructed over quantum-vulnerable technology. In this paper, we prove strongly unsplittable multi-coupons can be designed using quantum-resistant cryptography. The proposal employs lattice-based cryptography whose security holds on the assumed hardness of variants of the short integer solution (SIS) and learning with errors (LWE) problems. To the best of authors’ knowledge, no such system has been proposed so far., This research is a result of the Strategic Project “Advances in post-quantum cryptography applied to the development of a coupon system” (C039/24), resulting from an agreement between the Spanish National Cybersecurity Institute (INCIBE) and University of Lleida. This initiative is carried out in the scope of the funds from the Recovery, Transformation and Resilience Plan, funded by the European Union (Next Generation). This research is also part of the R&D+i project PID2021-124613OB-I00 funded by MICIU/ AEI/10.13039/501100011033 and FEDER, EU.
Recercat. Dipósit de la Recerca de Catalunya
Publicación Artículo científico (JournalArticle)

Nonexistence of Almost Moore Digraphs of Degrees 4 and 5 with Self-Repeats

  • López Lorenzo, Ignacio
  • Messegué, Arnau
  • Miret, Josep M. (Josep Maria)
An almost Moore (d, k)-digraph is a regular digraph of degree d > 1, diameter k > 1 and order N(d, k) = d + d2 + · · · + dk . So far, their existence has only been shown for k = 2, whilst it is known that there are no such digraphs for k = 3, 4 and for d = 2, 3 when k ! 3. Furthermore, under certain assumptions, the nonexistence for the remaining cases has also been shown. In this paper, we prove that (4, k) and (5, k)-almost Moore digraphs with self-repeats do not exist for k ! 5., Supported in part by grants PID2020-115442RB-I00 and 2021SGR-00434. Supported in part by grants Margarita Salaand 2021SGR-00434. Supported in part by grants PID2021-124613OB-I00 and 2021SGR-00434
Recercat. Dipósit de la Recerca de Catalunya
Publicación Artículo científico (JournalArticle)

A strongly unsplittable multi-coupon system with off-line verification and selectively-revocable anonymity

  • Sebé Feixas, Francesc
  • Valls Marsal, Magda
This paper firstly reports a security flaw and a way to fix it detected in a multi-coupon system presented by Liu et al. in a paper published in 2017. That proposal provides selectively-revocable anonymity in the sense that the anonymity of customers is guaranteed unless they act dishonestly by redeeming a multi-coupon more times than allowed. Nevertheless, that system lacks two important security properties of multi-coupons: unlinkability and unsplittability. After that, we propose a novel multi-coupon construction which takes Brands off-line e-coin system as a building block. In this way, the multi-coupon system inherits the selective-revocability property of the mentioned e-coin system without the need to develop new ad-hoc cryptography. Furthermore, the proposed system is also proven to be unlinkable and strongly unsplittable. Its design makes use of a novel extension of the RSA blind signature protocol which endows it with conditional secret recovery., This paper is part of the R&D+i project PID2021-124613OB-I00 funded by MICIU/AEI/10.13039/501100011033 and FEDER, EU. The Cryptography and Graphs Research Group has been recognized as a consolidated research group 2021-SGR-00434 by Generalitat de Catalunya.
Recercat. Dipósit de la Recerca de Catalunya
Publicación Artículo científico (JournalArticle)

Point (de)compression for elliptic curves over highly 2-adic finite fields

  • Koshelev, Dmitrii
This article addresses the issue of efficient and safe (de)compression of Fq-points on an elliptic curve E over a highly 2-adic finite field Fq of characteristic 5 or greater. The given issue was overlooked by cryptography experts, probably because, until recently, such fields were not in trend. Therefore, there was no difficulty (with rare exceptions) in finding a square Fq-root. However, in our days, fields with large 2-adicities have gained particular popularity in the ZK (zero-knowledge) community, despite the fact that √ · ∈ Fq should be computed via more sophisticated square-root algorithms such as (Cipolla–Lehmer–)Müller’s one. The article explains why the classical x-coordinate (de)compression method based on Müller’s algorithm often contains Achilles’ heel to successfully perform a novel fault attack, which also fits the definition of a (D)DoS attack. In a nutshell, the trouble stems from the non-eterministic initialization of Müller’s algorithm. Moreover, the article suggests a countermeasure, namely an alternative (still simple) (de)compression method that completely prevents the discovered attack whenever the curve E/Fq is of even order. In particular, all twisted Edwards (i.e., Montgomery) curves are relevant. The decompression stage of the new method equally suffers from one square-root extraction in Fq. But the corresponding quadratic residue is inherently equipped with additional information, providing an opportunity to launch M¨uller’s algorithm immediately from its main deterministic part. In turn, the compression stage of the new method remains (almost) free as well as for the x-coordinate method., his research is a result of the strategic project “Avances en criptografía postcuántica aplicados al desarrollo de un sistema de cupones” (C039/24), resulting from an agreement between the National Cybersecurity Institute (INCIBE) and University of Lleida. This initiative is carried out in the scope of the funds from the Recovery, Transformation and Resilience Plan, funded by the European Union (Next Generation). The paper is also a part of the R&D+i project PID2021-124613OB-I00 funded by MICIU/AEI/10.13039/501100011033 and FEDER, EU.
Recercat. Dipósit de la Recerca de Catalunya
Publicación Artículo científico (JournalArticle)

Privacy-Preserving Electricity Trading for Connected Microgrids

  • Alàs Cercós, Oriol
  • Sebé Feixas, Francesc
The electricity market is evolving from the traditional unidirectional model into a bidirectional one in which households also generate and sell energy. This new scenario requires technology able to manage the available energy and guarantee that all the participants pay or are paid appropriately. Unfortunately, fine-grained monitoring of energy production and consumption makes it possible to infer sensitive information about confidential aspects of people’s private life. In this paper, we propose a system designed for privacy-preserving electricity trading in a connected microgrid. The system guarantees that at the end of a billing period, the distribution system operator can compute the quantity to be charged or paid to each household while being unable to trace its consumption details., This research was funded by the Spanish Ministry of Science and Innovation (grant number PID2021-124613OB-I00)
Recercat. Dipósit de la Recerca de Catalunya
Publicación Artículo científico (JournalArticle)

Quantum-resistant asymmetric secure computation with applications to priced oblivious transfer

  • Sebé Feixas, Francesc
  • Simón, Sergi
Priced oblivious transfer (POT) is a cryptographic protocol in which a merchant provides a set of items for sale and a customer acquires one of them. The protocol guarantees that the customer receives the item if and only if they have paid its price, while the merchant remains oblivious to the acquired item. Obviously, the merchant cannot not know what price the client has paid, as such price could be unique. A recent paper proposes a POT protocol that is built from two blocks: an e-coin system and an asymmetric secure computation protocol. In this paper, we present a quantum-resistant proposal for the latter building block. As a result, we are able to construct a quantum-resistant POT protocol implemented from the newly proposed asymmetric secure computation protocol and a post-quantum implementation of the mentioned e-coin system. To our knowledge, no quantum-resistant POT protocol has been proposed so far., This paper is part of the R&D+i project PID2021-124613OB-I00 funded by the Spanish Research Agency MICIU/AEI/10.13039/501100011033 and FEDER, EU. This paper is also part of the project “Advances in post-quantum cryptography applied to the development of a coupon system,” financed by “European Union NextGeneration–UE, the Recovery Plan, Transformation and Resilience, through INCIBE.”
Recercat. Dipósit de la Recerca de Catalunya
Publicación Contribución de congreso (ConferenceOutput)

Generación mejorada de ruido para oráculos de descifrado de la cifra Kyber

  • Sebé Feixas, Francesc
La cifra Kyber es un estandar NIST de cifrado de clave publica cuya seguridad depende de la supuesta intratabilidad del problema M-LWE (module learning with errors). En este artículo estudiamos el uso de Kyber en un entorno donde el poseedor de la clave privada actua como un oráculo que colabora en el descifrado de textos cifrados que le proporcionan otras partes con el requisito de que el oraculo no debe obtener información sobre los textos en claro resultantes. Veremos que, en un escenario como el descrito, existe un riesgo de que se revele informacin que permite la reconstrucción de la clave privada. Esto obliga a limitar el numero de veces que el oráculo puede utilizar una determinada clave. El artículo propone una solución para incrementar el numero máximo de usos de cada clave., Este trabajo es parte del proyecto R&D+i PID2021-124613OB-I00 financiado por MICIU/ AEI/10.13039/501100011033 y FEDER, EU. Esta investigacion también resulta del Proyecto Estratégico Avances en criptografía post-cuantica aplicados al desarrollo de un sistema de cupones (C039/24), fruto del convenio de colaboracion suscrito entre el Instituto Nacional de Ciberseguridad (INCIBE) y la Universidad de Lleida. Esta iniciativa se realiza en el marco de los fondos del Plan de Recuperacion, Transformación y Resiliencia, financiados por la Unión Europea (Next Generation).
Recercat. Dipósit de la Recerca de Catalunya
Publicación Artículo científico (JournalArticle)

An e-coin based construction for unlinkable priced oblivious transfer

  • Borges Llorens, Ricard
  • Sebé Feixas, Francesc
A 1-out-of-n Oblivious Transfer (OT) protocol involves two participants: a sender, who provides a set of items as input, and a receiver. The protocol guarantees that the receiver gets exactly one of the items of the input set, while the sender is unable to determine which. Priced Oblivious Transfer (POT) protocols further allow each item of the input set to be assigned a price in such a way that, after a proper execution of the protocol, the receiver gets the requested item if and only if the corresponding sum of money has been paid. In this paper, we present a construction which takes a 1-out-of-n OT protocol and transform it into a POT one. Moreover, the resulting system is unlinkable in the sense that the sender is unable to determine whether two executions of the protocol were run by the same receiver or not. When compared to existing unlinkable POT protocols, our construction offers a lower conceptual complexity as it does not involve the use of zero-knowledge proofs., This work was supported by the Spanish Ministry of Science and Innovation (project number PID2021-124613OB-I00).
Recercat. Dipósit de la Recerca de Catalunya
Publicación Artículo científico (JournalArticle)

E-Coin-Based Priced Oblivious Transfer with a Fast Item Retrieval

  • Sebé Feixas, Francesc
  • Simón, Sergi
Priced oblivious transfer (POT) is a cryptographic protocol designed for privacy-preserving e-commerce of digital content. It involves two parties: the merchant, who provides a set of priced items as input, and a customer, who acquires one of them. After the protocol has run, the customer obtains the item they chose, while the merchant cannot determine which one. Moreover, the protocol guarantees that the customer gets the content only if they have paid the price established by the merchant. In a recent paper, the authors proposed a POT system where the payments employed e-coin transactions. The strong point of the proposal was the absence of zero-knowledge proofs required in preceding systems to guarantee the correctness of payments. In this paper, we propose a novel e-coin-based POT system with a fast item retrieval procedure whose running time does not depend on the number of items for sale. This is an improvement over the aforementioned existing proposal whose execution time becomes prohibitively long when the catalog is extensive. The use of zero-knowledge proofs is neither required., This research was funded by the Spanish Ministry of Science and Innovation (grant number PID2021-124613OB-I00).
Recercat. Dipósit de la Recerca de Catalunya
Publicación Artículo científico (JournalArticle)

Triple product 𝑝-adic 𝐿-functions for Shimura curves over totally real number fields

  • Barrera Salazar, Daniel
  • Molina Blanco, Santiago
Let 𝐹 be a totally real number field. Using a recent geometric approach developed by Andreatta and Iovita we construct several variables 𝑝-adic families of finite slope quaternionic automorphic forms over 𝐹. It is achieved by interpolating the modular sheaves defined over some auxiliary unitary Shimura curves. Secondly, we attach 𝑝-adic 𝐿-functions to triples of ordinary 𝑝-adic families of quaternionic automorphic eigenforms. This is done by relating trilinear periods to some trilinear products over unitary Shimura curves which can be interpolated adapting the work of Liu–Zhang–Zhang to our families., The authors are supported in part by DGICYT Grant MTM2015-63829-P. This project has received funding from the European Research Council (ERC) under the European Union’s Horizon 2020 research and innovation programme (grant agreement No. 682152). D.B. was also funded by ANID FONDECYT grants 11201025 and 1241702. S. M. is also funded by Ministerio de Ciencia e innovación, project PID2022-137605NBI00, and this paper is part of the R&D+i project PID2021-124613OB-I00 funded by MICIU/AEI/10.13039/501100011033 and FEDER, EU.
Recercat. Dipósit de la Recerca de Catalunya
Publicación Contribución de congreso (ConferenceOutput)

A Quantum-Resistant Implementation of a Digital Cash System with Valued and no-Valued e-Coins

  • Miret, Josep M. (Josep Maria)
  • Sebé Feixas, Francesc
  • Simón, Sergi
Digital cash is a form of money that is minted, stored, and spent digitally. As opposed to debit or credit cards, it enables untraceable payments in the sense that the payer can acquire products while keeping their identity secret. In a recent paper, a new digital cash paradigm including the so-called no-valued e-coins was proposed. No-valued e-coins are used to perform bogus transactions which mask consumption patterns. In this paper, we analyze the aforementioned cash paradigm and investigate the possibility of implementing it over quantumresistant cryptographic schemes. This objective has been achieved using off-the-shelf cryptosystems for data encryption and digital signature which have been deeply analyzed to check they provide the required features., This paper is also part of the project “Avances en criptografía post-cuántica aplicados al desarrollo de un sistema de cupones”, financed by “European Union NextGeneration–UE, the Recovery Plan, Transformation and Resilience, through INCIBE”.
Recercat. Dipósit de la Recerca de Catalunya
Publicación Artículo científico (JournalArticle)

Trisections and cubes in elliptic curves

  • Pujolàs Boix, Jordi
  • Thériault, Nicolas
We show how to compute the pre-images of multiplication by 3 in the group of points of an elliptic curve E over a field k of characteristic different from 2 and 3 such that E[3](k) = E[3]. We show Q = (xQ, yQ) ∈ [3]E(k) if and only if yQ − d − m(xQ − c) is a cube in k for every 3-torsion point (c, d) ∈ E[3], where m is the slope of the tangent to E at (c, d). We reduce our problem to the computation of at most 2 independent cubic roots plus a few polynomial operations., Research of the authors was supported in part by grants PID2021-124613OB-I00 (Spanish Ministerio de Ciencia e Innovación) and DICYT 041933T (Universidad de Santiago de Chile), and CyTeD (“Programa Iberoamericano de Ciencia y Tecnología para el Desarrollo”) project 522RT0131
Recercat. Dipósit de la Recerca de Catalunya
Publicación Artículo científico (JournalArticle)

On the permutation cycle structures for almost Moore digraphs of degrees 4 and 5

  • Miret, Josep M. (Josep Maria)
  • Simanjuntak, Rinovia
  • Simón, Sergi
Almost Moore digraphs of degree d and diameter k, for short (d, k)-digraphs, appear in the degree/diameter problem as a class of extremal directed graphs. Their order is one less than the unattainable Moore bound M(d, k) = 1 + d + · · · + d k . So far, their existence has only been shown for k = 2. Their nonexistence has been proven for k = 3, 4 and for d = 2, 3, when k ≥ 3. In this paper, we study the possible cycle structures of the permutation of repeats for the (4, k) and (5, k)-digraphs., Research of the first and third authors was supported in part by grants PID2021-124613OB-I00 and 2021SGR-00434. The research of the second author was supported by Institut Teknologi Bandung under the grant Riset Unggulan. The authors would also like to thank the anonymous referees, whose comments have significantly improved the quality of this paper.
Recercat. Dipósit de la Recerca de Catalunya
Publicación Artículo científico (JournalArticle)

Exceptional zero formulas for anticyclotomic p-adic L-functions

  • Hernández Barrios, Víctor
  • Molina Blanco, Santiago
In this note we define anticyclotomic p-adic measures attached to a modular elliptic curve E over a general number field F, a quadratic extension, and a set of places S of F above p. We study the exceptional zero phenomenon that arises when E has multiplicative reduction at some place in S. In this direction, we obtain p-adic Gross-Zagier formulas relating derivatives of the corresponding p-adic L-functions to the extended Mordell-Weil group of E. Our main result uses the recent construction of plectic points on elliptic curves due to Fornea and Gehrmann and generalizes their main result in [9]. We obtain a formula that computes the r-th derivative of the p-adic L-function, where r is the number of places in S where E has multiplicative reduction, in terms of plectic points and Tate periods of E., This project has received funding from the European Research Council (ERC) under the European Union's Horizon 2020 research and innovation programme (grant agreement No. 682152). Moreover, the second author has been partially funded by the projects PID2021-124613OB-I00 and PID2022-137605NB-I00 from Ministerio de Ciencia e innovación. We would also like to thank Lennart Gehrmann and Marc Masdeu for all their helpful remarks and comments.
Recercat. Dipósit de la Recerca de Catalunya
Publicación Artículo científico (JournalArticle)

A reusable public transport electronic ticket system with fast validation

  • Borges Llorens, Ricard
  • Sebé Feixas, Francesc
This paper presents an electronic ticket system for public transport which provides reusability in the sense that, after the validation of a ticket, a traveler is enabled to perform a journey which can include a limited number of transfers before an expiration time. The proposal has been designed following a privacy-by-design approach. Travelers are only required to identify themselves if requested to prove possession of a valid ticket by an officer. Otherwise, they can travel without being required to disclose their identity (anonymity). Also, the diverse interactions of a traveler with the system cannot be related to them (unlinkability). The security and privacy requirements are achieved by making use of advanced cryptographic techniques. The system has been simulated and proven to provide running times which make it appropriate for a real deployment. When compared to an existing proposal designed for an equivalent scenario, the reduction in the time required for ticket validation is especially remarkable. In effect, all the use cases with real-time constraints (“Ticket validation”, “Get-in”, and “Get-out”) can be run in less than one second., Open Access funding provided thanks to the CRUE-CSIC agreement with Springer Nature. This paper is part of the R&D+i project PID2021-124613OB-I00 funded by MICIU/ AEI/10.13039/501100011033 and FEDER,EU.