Pasar al contenido principal

CRIPTOGRAFIA Y CODIGOS PARA APLICACIONES SEGURAS Y FIABLES

MTM2017-83271-R

•
Nombre agencia financiadora Agencia Estatal de Investigación
Acrónimo agencia financiadora AEI
Programa Programa Estatal de I+D+i Orientado a los Retos de la Sociedad
Convocatoria Proyectos I+D+i Retos de Investigación
Año convocatoria 2017
Plan Estatal 2017-2020 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): 26
Encontrada(s) 1 página(s)

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

An efficient privacy-preserving pay-by-phone system for regulated parking areas

  • Borges Llorens, Ricard
  • Sebé Feixas, Francesc
Traditional pay-and-display ticket machines are currently coexisting, but will probably be replaced in the near future, with pay-by-phone applications. Such applications facilitate the payment for parking in regulated areas. Companies providing this service collect and manage information about all the parking transactions performed by drivers. That information is very sensitive and can be used to generate reports on the parking history of drivers, posing a threat on their privacy. This paper proposes a pay-by-phone parking system in which the service provider is prevented from being able to track the parking transactions of drivers. The new proposal requires drivers to be connected only at the beginning of a parking transaction, or at the moment of indicating that a parking transaction took less time than expected. Prototype experiments have shown that the new proposal is much more efficient, in terms of computational cost, than the most complete previous existing system, while providing the same functionalities and higher security., This study was funded by the Spanish Ministry of Science, Innovation and Universities (project number MTM2017-83271-R).
Repositori Obert UdL
Publicación Artículo científico (JournalArticle)

Repairing an aggregation-based smart metering system

  • Garra Oronich, Ricard
  • Leibenger, Dominik
  • Miret, Josep M. (Josep Maria)
  • Sebé Feixas, Francesc
Smart meters inform the electricity suppliers about the consumption of their clients in short intervals. Fine-grained electricity consumption information is highly sensitive as it has been proven to permit to infer people's habits like, for instance, the time they leave or arrive home. Hence, appropriate measures have to be taken to preserve clients' privacy in smart metering systems. In this paper, we first analyze a recent proposal by Busom et al. (2016) and show how a corrupted substation is able to get the individual reading of any arbitrarily chosen smart meter without requiring the collaboration of any other party. After that, we propose a way to fix the mentioned security flaw which is based on adding an additional step in which the substation proves that it has properly followed all the protocol steps. Our solution is analyzed and shown to be computationally feasible for realistic parameter choices., This study was funded by the European Regional Development Fund of the European Union in the scope of the “Programa Operatiu FEDER de Catalunya 2014–2020” (project number COMRDI16-1-0060), by the Spanish Ministry of Science, Innovation and Universities (project number MTM2017-83271-R), and by the Federal Ministry for Economic Affairs and Energy of Germany in the SINTEG project DESIGNETZ (project number 03SIN224)
Repositori Obert UdL
Publicación Artículo científico (JournalArticle)

On the Laplacian spectra of token graphs

  • Dalfó, Cristina
  • Duque, F.
  • Fabila Monroy, R.
  • Fiol Mora, Miguel Ángel
  • Huemer, Clemens
  • Zaragoza Martínez, F.J.
  • Trujillo Negrete, A.L.
We study the Laplacian spectrum of token graphs, also called symmetric powers of graphs. The k-token graph Fk(G) of a graph G is the graph whose vertices are the k-subsets of vertices from G, two of which being adjacent whenever their symmetric difference is a pair of adjacent vertices in G. In this paper, we give a relationship between the Laplacian spectra of any two token graphs of a given graph. In particular, we show that, for any integers h and k such that 1 ≤ h ≤ k ≤ n 2 , the Laplacian spectrum of Fh(G) is contained in the Laplacian spectrum of Fk(G). We also show that the doubled odd graphs and doubled Johnson graphs can be obtained as token graphs of the complete graph Kn and the star Sn = K1,n−1, respectively. Besides, we obtain a relationship between the spectra of the k-token graph of G and the k-token graph of its complement G. This generalizes to tokens graphs a wellknown property stating that the Laplacian eigenvalues of G are closely related to the Laplacian eigenvalues of G. Finally, the doubled odd graphs and doubled Johnson graphs provide two infinite families, together with some others, in which the algebraic connectivities of the original graph and its token graph coincide. Moreover, we conjecture that this is the case for any graph G and its token graph., This research of C. Dalfó and M.A. Fiol has been partially supported by AGAUR from the Catalan Government under project 017SGR1087 and by MICINN from the Spanish Government under project PGC2018-095471-B-I00. The research of C. Dalfó has also been supported by MICINN from the Spanish Government under project MTM2017-83271-R. The research of C. Huemer was supported by MICINN from the Spanish Government under project PID2019-104129GB-I00/AEI/10.13039/501100011033 and AGAUR from the Catalan Government under project 017SGR1336. F.J. Zaragoza Martínez acknowledges the support of the National Council of Science and Technology (Conacyt) and its National System of Researchers (SNI). This research has also received funding from the European Union’s Horizon 2020 research and innovation programme under the Marie Skłodowska-Curie grant agreement No 734922
Repositori Obert UdL
Publicación Artículo científico (JournalArticle)

A general method to obtain the spectrum and local spectra of a graph from its regular partitions

  • Dalfó, Cristina
  • Fiol Mora, Miguel Ángel
It is well known that, in general, part of the spectrum of a graph can be obtained from the adjacency matrix of its quotient graph given by a regular partition. In this paper, a method that gives all the spectrum, and also the local spectra, of a graph from the quotient matrices of some of its regular partitions, is proposed. Moreover, from such partitions, the C-local multiplicities of any class of vertices C is also determined, and some applications of these parameters in the characterization of completely regular codes and their inner distributions are described. As examples, it is shown how to find the eigenvalues and (local) multiplicities of walk-regular, distance-regular, and distance-biregular graphs., Partially supported by AGAUR from the Catalan Government under project 2017SGR1087 and by MICINN from the Spanish Governmentunder projects PGC2018-095471-B-I00 and MTM2017-83271-R. Also received funding from the European Union’s Horizon 2020 research and innovation programme under the Marie Sk lodowska-Curie grant agreement no. 734922
Repositori Obert UdL
Publicación Artículo científico (JournalArticle)

Bipartite biregular Moore graphs

  • Araujo Pardo, Martha Gabriela
  • Dalfó, Cristina
  • Fiol Mora, Miguel Ángel
  • López Lorenzo, Ignacio
A bipartite graph G=(V,E) with V=V1 U V2 is biregular if all the vertices of a stable set Vi have the same degree ri for i=1,2. In this paper, we give an improved new Moore bound for an infinite family of such graphs with odd diameter. This problem was introduced in 1983 by Yebra, Fiol, and Fàbrega. Besides, we propose some constructions of bipartite biregular graphs with diameter d and large number of vertices N(r1,r2;d), together with their spectra. In some cases of diameters d=3, 4, and 5, the new graphs attaining the Moore bound are unique up to isomorphism., The research of the first author is supported by CONACyT-México under Project 282280 and PAPIIT-México under Project IN101821, PASPA-DGAPA, and CONACYT Sabbatical Year 2020. The research of the second and third authors is partially supported by AGAUR from the Catalan Government under project 2017SGR1087 and by MICINN from the Spanish Government under project PGC2018-095471-B-I00. The research of the second and fourth authors is supported by MICINN from the Spanish Government under project MTM2017-83271-R.
Repositori Obert UdL
Publicación Artículo científico (JournalArticle)

A note on a new general family of deterministic hierarchical networks

  • Dalfó, Cristina
  • Fiol Mora, Miguel Ángel
It is known that many networks modeling real-life complex systems are small-word (large local clustering and small diameter) and scale-free (power law of the degree distribution), and very often they are also hierarchical. Although most of the models are based on stochastic methods, some deterministic constructions have been recently proposed, because this allows a better computation of their properties. Here a new deterministic family of hierarchical networks is presented, which generalizes most of the previous proposals, such as the so-called binomial tree. The obtained graphs can be seen as graphs on alphabets (where vertices are labeled with words of a given alphabet, and the edges are defined by a specific rule relating different words). This allows us the characterization of their main distance-related parameters, such as the radius and diameter. Moreover, as a by-product, an efficient shortest-path local algorithm is proposed., This research has been partially supported by AGAUR from the Catalan Government under project 2017SGR1087 and by MICINN from the Spanish Government under project PGC2018- 095471-B-I00. The research of the first author has also been supported by MICINN from the Spanish Government under project MTM2017-83271-R. The research of the first author has also received funding from the European Union’s Horizon 2020 research and innovation programme under the Marie Sk lodowska-Curie grant agreement No 734922.
Repositori Obert UdL
Publicación Artículo científico (JournalArticle)

Spectra and eigenspaces of arbitrary lifts of graphs

  • Dalfó, Cristina
  • Fiol Mora, Miguel Ángel
  • Pavlíková, Sona
  • Sirán, Jozef
We describe, in a very explicit way, a method for determining the spec-tra and bases of all the corresponding eigenspaces of arbitrary lifts of graphs (regularor not)., The first author has received funding from the European Union’s Horizon 2020 research and innovation programme under the Marie Sk lodowska-Curie grant agreement No 734922. Research of the two first authors has been partially supported by AGAUR from the Catalan Government under project 2017SGR1087, and by MICINN from the Spanish Government under project PGC2018-095471-B-I00. The research of the first author has also been supported by MICINN from the Spanish Government under project MTM2017-83271-R
Repositori Obert UdL
Publicación Artículo científico (JournalArticle)

A Digital Cash Paradigm with Valued and No-Valued e-Coins

  • Borges Llorens, Ricard
  • Sebé Feixas, Francesc
Digital cash is a form of money that is stored digitally. Its main advantage when compared to traditional credit or debit cards is the possibility of carrying out anonymous transactions. Diverse digital cash paradigms have been proposed during the last decades, providing different approaches to avoid the double-spending fraud, or features like divisibility or transferability. This paper presents a new digital cash paradigm that includes the so-called no-valued e-coins, which are e-coins that can be generated free of charge by customers. A vendor receiving a payment cannot distinguish whether the received e-coin is valued or not, but the customer will receive the requested digital item only in the former case. A straightforward application of bogus transactions involving no-valued e-coins is the masking of consumption patterns. This new paradigm has also proven its validity in the scope of privacy-preserving pay-by-phone parking systems, and we believe it can become a very versatile building block in the design of privacy-preserving protocols in other areas of research. This paper provides a formal description of the new paradigm, including the features required for each of its components together with a formal analysis of its security., This research was funded by the Spanish Ministry of Science, Innovation and Universities grant number MTM2017-83271-R.
Repositori Obert UdL
Publicación Artículo científico (JournalArticle)

Identifying codes in line digraphs

  • Balbuena Martínez, Camino
  • Dalfó, Cristina
  • Martínez Barona, Berenice
Given an integer ≥1, a (1, ≤ )-identifying code in a digraph is a dominating subset C of vertices such that all distinct subsets of vertices of cardinality at most have distinct closed in-neighborhoods within C . In this paper, we prove that every line digraph of min- imum in-degree one does not admit a (1, ≤ )-identifying code for ≥3. Then we give a characterization so that a line digraph of a digraph different from a directed cycle of length 4 and minimum in-degree one admits a (1, ≤2)-identifying code. The identifying number of a digraph D , −→ γID (D ) , is the minimum size of all the identifying codes of D . We establish for digraphs without digons with both vertices of in-degree one that −→ γID (LD ) is lower bounded by the number of arcs of D minus the number of vertices with out-degree at least one. Then we show that −→ γID (LD ) attains the equality for a digraph having a 1- factor with minimum in-degree two and without digons with both vertices of in-degree two. We finish by giving an algorithm to construct identifying codes in oriented digraphs with minimum in-degree at least two and minimum out-degree at least one., This research is supported by MICINN from the Spanish Government under project PGC2018-095471-B-I00 and partially by AGAUR from the Catalan Government under project 2017SGR1087 . The research of the second author has also been supported by MICINN from the Spanish Government under project MTM2017-83271-R. The second and third authors have received funding research and innovation programme under the Marie Sklodowska-Curie grant agree- ment No 734922.
Repositori Obert UdL
Publicación Artículo científico (JournalArticle)

A Construction for Providing Reusability to Mobile Phone-Based e-Tickets

  • Borges Llorens, Ricard
  • Sebé Feixas, Francesc
Nowadays, the use of electronic tickets in public transport is a reality. Several mobile phone-based e-ticket systems have been proposed so far. Even so, very few of them include reusability in the sense that a single e-ticket allows to make several journeys. Although the identity of users is usually hidden behind a pseudonym, the existing proposals providing reusability allow the system to link all the journeys made with a given e-ticket. In this paper we present a privacy-preserving construction allowing to endow a mobile phone-based e-ticket system with reusability. The privacy of users is proven to be preserved even assuming an internal attacker with full access to all the information managed by the system servers. All the sensitive interactions of a user with the system keep anonymous and unlinkable. Further, as a result of an inspection, the system is only able to determine whether the inspected user is allowed to make the current journey., This work was supported in part by the Spanish Ministry of Science, Innovation, and Universities, under Project MTM2017-83271-R.
Repositori Obert UdL
Publicación Artículo científico (JournalArticle)

On the spectra and eigenspaces of the universal adjacency matrices of arbitrary lifts of graphs

  • Dalfó, Cristina
  • Fiol Mora, Miguel Ángel
  • Pavlíková, Sona
  • Sirán, Jozef
The universal adjacency matrix U of a graph Γ, with adjacency matrix A, is a linear combination of A, the diagonal matrix D of vertex degrees, the identity matrix I, and the all-1 matrix J with real coefficients, that is, U=c1A+c2D+c3I+c4J, with ci∈R and c1≠0. Thus, in particular cases, U may be the adjacency matrix, the Laplacian, the signless Laplacian, and the Seidel matrix. In this paper, we develop a method for determining the universal spectra and bases of all the corresponding eigenspaces of arbitrary lifts of graphs (regular or not). As an example, the method is applied to give an efficient algorithm to determine the characteristic polynomial of the Laplacian matrix of the symmetric squares of odd cycles, together with closed formulas for some of their eigenvalues., The first author has received funding from the European Union’s Horizon 2020 research and innovation programme under the Marie Sk lodowska-Curie grant agreement No 734922. The research of the two first authors is partially supported by AGAUR from the Catalan Government under project 2017SGR1087 and by MICINN from the Spanish Government under project PGC2018-095471-B-I00. The research of the first author has also been supported by MICINN from the Spanish Government under project MTM2017-83271-R. The third and fourth authors acknowledge support from the APVV Research Grants 15-0220 and 17-0428, and the VEGA Research Grants 1/0142/17 and 1/0238/19.
Repositori Obert UdL
Publicación Contribución de congreso (ConferenceOutput)

Improving a smart metering system using elliptic curves and removing the trusted dealer

  • Garra Oronich, Ricard
  • Martínez Rodríguez, Santi
  • Miret, Josep M. (Josep Maria)
  • Sebé Feixas, Francesc
Comunicació presentada a la XV Reunión Española sobre Criptología y Seguridad de la Información, celebada a Granada del 3 al 5 d'octubre de 2018., Fine-grained electricity consumption information has been proven to allow to infer people’s habits from their consumption patterns. Hence, smart metering systems need a secure way to regularly transmit the electricity consumption to the supplier in such a way that the privacy of customers is preserved. Several proposals can be found in the literature. Some of them, classified as aggregative solutions, organize the meters into groups and employ homomorphic cryptography in such a way that the supplier only obtains the aggregated consumption values of the meters in each group. In this paper we propose a technique which allows to remove the presence of a trusted dealer in one of the most efficient current proposals. Furthermore, we increase the overall performance of the resulting system by employing elliptic curve cryptography. The resulting system only requires a single message sent from each smart meter to its substation, without needing the meters to communicate among them. With the use of elliptic curve cryptography, the only relevant computation that the smart meters need to perform is a single elliptic curve point multiplication by a scalar. The system has been proven to be feasible and practical even for large neigborhoods including several thousands of meters., Research of the authors was supported in part by the European Regional Development Fund of the European Union in the scope of the “Programa Operatiu FEDER de Catalunya 2014–2020” (project COMRDI16-1-0060), and by the Spanish Ministry of Science, Innovation and Universities (project MTM2017-83271-R). The Cryptography & Graphs Research Group of Universitat de Lleida has been recognized as a Consolidated Research Group by Generalitat de Catalunya (2017 SGR 1158).
Repositori Obert UdL
Publicación Artículo científico (JournalArticle)

Spectra and eigenspaces from regular partitions of Cayley (di)graphs of permutation groups

  • Dalfó, Cristina
  • Fiol Mora, Miguel Ángel
In this paper, we present a method to obtain regular (or equitable) partitions of Cayley (di)graphs (that is, graphs, digraphs, or mixed graphs) of permutation groups on n letters. We prove that every partition of the number n gives rise to a regular partition of the Cayley graph. By using representation theory, we also obtain the complete spectra and the eigenspaces of the corresponding quotient (di)graphs. More precisely, we provide a method to find all the eigenvalues and eigenvectors of such (di)graphs, based on their irreducible representations. As examples, we apply this method to the pancake graphs P(n) and to a recent known family of mixed graphs Γ(d, n, r) (having edges with and without direction). As a byproduct, the existence of perfect codes s in P(n) allows us to give a lower bound for the multiplicity of its eigenvalue −1., This research has been partially supported by AGAUR from the Catalan Government under project 2017SGR1087 and by MICINN from the Spanish Government under project PGC2018-095471-B-I00. The research of the first author has also been supported by MICINN from the Spanish Government under project MTM2017-83271-R. The research of the first author has also received funding from the European Union's Horizon 2020 research and innovation programme under the Marie Skłodowska-Curie grant agreement No 734922.
Recercat. Dipósit de la Recerca de Catalunya
Publicación Artículo científico (JournalArticle)

Spectra and eigenspaces of arbitrary lifts of graphs

  • Dalfó, Cristina
  • Fiol Mora, Miguel Ángel
  • Pavlíková, Sona
  • Sirán, Jozef
We describe, in a very explicit way, a method for determining the spec-tra and bases of all the corresponding eigenspaces of arbitrary lifts of graphs (regularor not)., The first author has received funding from the European Union’s Horizon 2020 research and innovation programme under the Marie Sk lodowska-Curie grant agreement No 734922. Research of the two first authors has been partially supported by AGAUR from the Catalan Government under project 2017SGR1087, and by MICINN from the Spanish Government under project PGC2018-095471-B-I00. The research of the first author has also been supported by MICINN from the Spanish Government under project MTM2017-83271-R
Recercat. Dipósit de la Recerca de Catalunya
Publicación Artículo científico (JournalArticle)

A Construction for Providing Reusability to Mobile Phone-Based e-Tickets

  • Borges Llorens, Ricard
  • Sebé Feixas, Francesc
Nowadays, the use of electronic tickets in public transport is a reality. Several mobile phone-based e-ticket systems have been proposed so far. Even so, very few of them include reusability in the sense that a single e-ticket allows to make several journeys. Although the identity of users is usually hidden behind a pseudonym, the existing proposals providing reusability allow the system to link all the journeys made with a given e-ticket. In this paper we present a privacy-preserving construction allowing to endow a mobile phone-based e-ticket system with reusability. The privacy of users is proven to be preserved even assuming an internal attacker with full access to all the information managed by the system servers. All the sensitive interactions of a user with the system keep anonymous and unlinkable. Further, as a result of an inspection, the system is only able to determine whether the inspected user is allowed to make the current journey., This work was supported in part by the Spanish Ministry of Science, Innovation, and Universities, under Project MTM2017-83271-R.
Recercat. Dipósit de la Recerca de Catalunya
Publicación Artículo científico (JournalArticle)

A Digital Cash Paradigm with Valued and No-Valued e-Coins

  • Borges Llorens, Ricard
  • Sebé Feixas, Francesc
Digital cash is a form of money that is stored digitally. Its main advantage when compared to traditional credit or debit cards is the possibility of carrying out anonymous transactions. Diverse digital cash paradigms have been proposed during the last decades, providing different approaches to avoid the double-spending fraud, or features like divisibility or transferability. This paper presents a new digital cash paradigm that includes the so-called no-valued e-coins, which are e-coins that can be generated free of charge by customers. A vendor receiving a payment cannot distinguish whether the received e-coin is valued or not, but the customer will receive the requested digital item only in the former case. A straightforward application of bogus transactions involving no-valued e-coins is the masking of consumption patterns. This new paradigm has also proven its validity in the scope of privacy-preserving pay-by-phone parking systems, and we believe it can become a very versatile building block in the design of privacy-preserving protocols in other areas of research. This paper provides a formal description of the new paradigm, including the features required for each of its components together with a formal analysis of its security., This research was funded by the Spanish Ministry of Science, Innovation and Universities grant number MTM2017-83271-R.
Recercat. Dipósit de la Recerca de Catalunya
Publicación Artículo científico (JournalArticle)

A note on a new general family of deterministic hierarchical networks

  • Dalfó, Cristina
  • Fiol Mora, Miguel Ángel
It is known that many networks modeling real-life complex systems are small-word (large local clustering and small diameter) and scale-free (power law of the degree distribution), and very often they are also hierarchical. Although most of the models are based on stochastic methods, some deterministic constructions have been recently proposed, because this allows a better computation of their properties. Here a new deterministic family of hierarchical networks is presented, which generalizes most of the previous proposals, such as the so-called binomial tree. The obtained graphs can be seen as graphs on alphabets (where vertices are labeled with words of a given alphabet, and the edges are defined by a specific rule relating different words). This allows us the characterization of their main distance-related parameters, such as the radius and diameter. Moreover, as a by-product, an efficient shortest-path local algorithm is proposed., This research has been partially supported by AGAUR from the Catalan Government under project 2017SGR1087 and by MICINN from the Spanish Government under project PGC2018- 095471-B-I00. The research of the first author has also been supported by MICINN from the Spanish Government under project MTM2017-83271-R. The research of the first author has also received funding from the European Union’s Horizon 2020 research and innovation programme under the Marie Sk lodowska-Curie grant agreement No 734922.
Recercat. Dipósit de la Recerca de Catalunya
Publicación Contribución de congreso (ConferenceOutput)

Improving a smart metering system using elliptic curves and removing the trusted dealer

  • Garra Oronich, Ricard
  • Martínez Rodríguez, Santi
  • Miret, Josep M. (Josep Maria)
  • Sebé Feixas, Francesc
Comunicació presentada a la XV Reunión Española sobre Criptología y Seguridad de la Información, celebada a Granada del 3 al 5 d'octubre de 2018., Fine-grained electricity consumption information has been proven to allow to infer people’s habits from their consumption patterns. Hence, smart metering systems need a secure way to regularly transmit the electricity consumption to the supplier in such a way that the privacy of customers is preserved. Several proposals can be found in the literature. Some of them, classified as aggregative solutions, organize the meters into groups and employ homomorphic cryptography in such a way that the supplier only obtains the aggregated consumption values of the meters in each group. In this paper we propose a technique which allows to remove the presence of a trusted dealer in one of the most efficient current proposals. Furthermore, we increase the overall performance of the resulting system by employing elliptic curve cryptography. The resulting system only requires a single message sent from each smart meter to its substation, without needing the meters to communicate among them. With the use of elliptic curve cryptography, the only relevant computation that the smart meters need to perform is a single elliptic curve point multiplication by a scalar. The system has been proven to be feasible and practical even for large neigborhoods including several thousands of meters., Research of the authors was supported in part by the European Regional Development Fund of the European Union in the scope of the “Programa Operatiu FEDER de Catalunya 2014–2020” (project COMRDI16-1-0060), and by the Spanish Ministry of Science, Innovation and Universities (project MTM2017-83271-R). The Cryptography & Graphs Research Group of Universitat de Lleida has been recognized as a Consolidated Research Group by Generalitat de Catalunya (2017 SGR 1158).
Recercat. Dipósit de la Recerca de Catalunya
Publicación Artículo científico (JournalArticle)

On the spectra and eigenspaces of the universal adjacency matrices of arbitrary lifts of graphs

  • Dalfó, Cristina
  • Fiol Mora, Miguel Ángel
  • Pavlíková, Sona
  • Sirán, Jozef
The universal adjacency matrix U of a graph Γ, with adjacency matrix A, is a linear combination of A, the diagonal matrix D of vertex degrees, the identity matrix I, and the all-1 matrix J with real coefficients, that is, U=c1A+c2D+c3I+c4J, with ci∈R and c1≠0. Thus, in particular cases, U may be the adjacency matrix, the Laplacian, the signless Laplacian, and the Seidel matrix. In this paper, we develop a method for determining the universal spectra and bases of all the corresponding eigenspaces of arbitrary lifts of graphs (regular or not). As an example, the method is applied to give an efficient algorithm to determine the characteristic polynomial of the Laplacian matrix of the symmetric squares of odd cycles, together with closed formulas for some of their eigenvalues., The first author has received funding from the European Union’s Horizon 2020 research and innovation programme under the Marie Sk lodowska-Curie grant agreement No 734922. The research of the two first authors is partially supported by AGAUR from the Catalan Government under project 2017SGR1087 and by MICINN from the Spanish Government under project PGC2018-095471-B-I00. The research of the first author has also been supported by MICINN from the Spanish Government under project MTM2017-83271-R. The third and fourth authors acknowledge support from the APVV Research Grants 15-0220 and 17-0428, and the VEGA Research Grants 1/0142/17 and 1/0238/19.
Recercat. Dipósit de la Recerca de Catalunya
Publicación Artículo científico (JournalArticle)

Spectra and eigenspaces from regular partitions of Cayley (di)graphs of permutation groups

  • Dalfó, Cristina
  • Fiol Mora, Miguel Ángel
In this paper, we present a method to obtain regular (or equitable) partitions of Cayley (di)graphs (that is, graphs, digraphs, or mixed graphs) of permutation groups on n letters. We prove that every partition of the number n gives rise to a regular partition of the Cayley graph. By using representation theory, we also obtain the complete spectra and the eigenspaces of the corresponding quotient (di)graphs. More precisely, we provide a method to find all the eigenvalues and eigenvectors of such (di)graphs, based on their irreducible representations. As examples, we apply this method to the pancake graphs P(n) and to a recent known family of mixed graphs Γ(d, n, r) (having edges with and without direction). As a byproduct, the existence of perfect codes s in P(n) allows us to give a lower bound for the multiplicity of its eigenvalue −1., This research has been partially supported by AGAUR from the Catalan Government under project 2017SGR1087 and by MICINN from the Spanish Government under project PGC2018-095471-B-I00. The research of the first author has also been supported by MICINN from the Spanish Government under project MTM2017-83271-R. The research of the first author has also received funding from the European Union's Horizon 2020 research and innovation programme under the Marie Skłodowska-Curie grant agreement No 734922.
Recercat. Dipósit de la Recerca de Catalunya
Publicación Artículo científico (JournalArticle)

An efficient privacy-preserving pay-by-phone system for regulated parking areas

  • Borges Llorens, Ricard
  • Sebé Feixas, Francesc
Traditional pay-and-display ticket machines are currently coexisting, but will probably be replaced in the near future, with pay-by-phone applications. Such applications facilitate the payment for parking in regulated areas. Companies providing this service collect and manage information about all the parking transactions performed by drivers. That information is very sensitive and can be used to generate reports on the parking history of drivers, posing a threat on their privacy. This paper proposes a pay-by-phone parking system in which the service provider is prevented from being able to track the parking transactions of drivers. The new proposal requires drivers to be connected only at the beginning of a parking transaction, or at the moment of indicating that a parking transaction took less time than expected. Prototype experiments have shown that the new proposal is much more efficient, in terms of computational cost, than the most complete previous existing system, while providing the same functionalities and higher security., This study was funded by the Spanish Ministry of Science, Innovation and Universities (project number MTM2017-83271-R).
Recercat. Dipósit de la Recerca de Catalunya
Publicación Artículo científico (JournalArticle)

Identifying codes in line digraphs

  • Balbuena Martínez, Camino
  • Dalfó, Cristina
  • Martínez Barona, Berenice
Given an integer ≥1, a (1, ≤ )-identifying code in a digraph is a dominating subset C of vertices such that all distinct subsets of vertices of cardinality at most have distinct closed in-neighborhoods within C . In this paper, we prove that every line digraph of min- imum in-degree one does not admit a (1, ≤ )-identifying code for ≥3. Then we give a characterization so that a line digraph of a digraph different from a directed cycle of length 4 and minimum in-degree one admits a (1, ≤2)-identifying code. The identifying number of a digraph D , −→ γID (D ) , is the minimum size of all the identifying codes of D . We establish for digraphs without digons with both vertices of in-degree one that −→ γID (LD ) is lower bounded by the number of arcs of D minus the number of vertices with out-degree at least one. Then we show that −→ γID (LD ) attains the equality for a digraph having a 1- factor with minimum in-degree two and without digons with both vertices of in-degree two. We finish by giving an algorithm to construct identifying codes in oriented digraphs with minimum in-degree at least two and minimum out-degree at least one., This research is supported by MICINN from the Spanish Government under project PGC2018-095471-B-I00 and partially by AGAUR from the Catalan Government under project 2017SGR1087 . The research of the second author has also been supported by MICINN from the Spanish Government under project MTM2017-83271-R. The second and third authors have received funding research and innovation programme under the Marie Sklodowska-Curie grant agree- ment No 734922.
Recercat. Dipósit de la Recerca de Catalunya
Publicación Artículo científico (JournalArticle)

Bipartite biregular Moore graphs

  • Araujo Pardo, Martha Gabriela
  • Dalfó, Cristina
  • Fiol Mora, Miguel Ángel
  • López Lorenzo, Ignacio
A bipartite graph G=(V,E) with V=V1 U V2 is biregular if all the vertices of a stable set Vi have the same degree ri for i=1,2. In this paper, we give an improved new Moore bound for an infinite family of such graphs with odd diameter. This problem was introduced in 1983 by Yebra, Fiol, and Fàbrega. Besides, we propose some constructions of bipartite biregular graphs with diameter d and large number of vertices N(r1,r2;d), together with their spectra. In some cases of diameters d=3, 4, and 5, the new graphs attaining the Moore bound are unique up to isomorphism., The research of the first author is supported by CONACyT-México under Project 282280 and PAPIIT-México under Project IN101821, PASPA-DGAPA, and CONACYT Sabbatical Year 2020. The research of the second and third authors is partially supported by AGAUR from the Catalan Government under project 2017SGR1087 and by MICINN from the Spanish Government under project PGC2018-095471-B-I00. The research of the second and fourth authors is supported by MICINN from the Spanish Government under project MTM2017-83271-R.
Recercat. Dipósit de la Recerca de Catalunya
Publicación Artículo científico (JournalArticle)

Repairing an aggregation-based smart metering system

  • Garra Oronich, Ricard
  • Leibenger, Dominik
  • Miret, Josep M. (Josep Maria)
  • Sebé Feixas, Francesc
Smart meters inform the electricity suppliers about the consumption of their clients in short intervals. Fine-grained electricity consumption information is highly sensitive as it has been proven to permit to infer people's habits like, for instance, the time they leave or arrive home. Hence, appropriate measures have to be taken to preserve clients' privacy in smart metering systems. In this paper, we first analyze a recent proposal by Busom et al. (2016) and show how a corrupted substation is able to get the individual reading of any arbitrarily chosen smart meter without requiring the collaboration of any other party. After that, we propose a way to fix the mentioned security flaw which is based on adding an additional step in which the substation proves that it has properly followed all the protocol steps. Our solution is analyzed and shown to be computationally feasible for realistic parameter choices., This study was funded by the European Regional Development Fund of the European Union in the scope of the “Programa Operatiu FEDER de Catalunya 2014–2020” (project number COMRDI16-1-0060), by the Spanish Ministry of Science, Innovation and Universities (project number MTM2017-83271-R), and by the Federal Ministry for Economic Affairs and Energy of Germany in the SINTEG project DESIGNETZ (project number 03SIN224)
Recercat. Dipósit de la Recerca de Catalunya
Publicación Artículo científico (JournalArticle)

On the Laplacian spectra of token graphs

  • Dalfó, Cristina
  • Duque, F.
  • Fabila Monroy, R.
  • Fiol Mora, Miguel Ángel
  • Huemer, Clemens
  • Zaragoza Martínez, F.J.
  • Trujillo Negrete, A.L.
We study the Laplacian spectrum of token graphs, also called symmetric powers of graphs. The k-token graph Fk(G) of a graph G is the graph whose vertices are the k-subsets of vertices from G, two of which being adjacent whenever their symmetric difference is a pair of adjacent vertices in G. In this paper, we give a relationship between the Laplacian spectra of any two token graphs of a given graph. In particular, we show that, for any integers h and k such that 1 ≤ h ≤ k ≤ n 2 , the Laplacian spectrum of Fh(G) is contained in the Laplacian spectrum of Fk(G). We also show that the doubled odd graphs and doubled Johnson graphs can be obtained as token graphs of the complete graph Kn and the star Sn = K1,n−1, respectively. Besides, we obtain a relationship between the spectra of the k-token graph of G and the k-token graph of its complement G. This generalizes to tokens graphs a wellknown property stating that the Laplacian eigenvalues of G are closely related to the Laplacian eigenvalues of G. Finally, the doubled odd graphs and doubled Johnson graphs provide two infinite families, together with some others, in which the algebraic connectivities of the original graph and its token graph coincide. Moreover, we conjecture that this is the case for any graph G and its token graph., This research of C. Dalfó and M.A. Fiol has been partially supported by AGAUR from the Catalan Government under project 017SGR1087 and by MICINN from the Spanish Government under project PGC2018-095471-B-I00. The research of C. Dalfó has also been supported by MICINN from the Spanish Government under project MTM2017-83271-R. The research of C. Huemer was supported by MICINN from the Spanish Government under project PID2019-104129GB-I00/AEI/10.13039/501100011033 and AGAUR from the Catalan Government under project 017SGR1336. F.J. Zaragoza Martínez acknowledges the support of the National Council of Science and Technology (Conacyt) and its National System of Researchers (SNI). This research has also received funding from the European Union’s Horizon 2020 research and innovation programme under the Marie Skłodowska-Curie grant agreement No 734922
Recercat. Dipósit de la Recerca de Catalunya
Publicación Artículo científico (JournalArticle)

A general method to obtain the spectrum and local spectra of a graph from its regular partitions

  • Dalfó, Cristina
  • Fiol Mora, Miguel Ángel
It is well known that, in general, part of the spectrum of a graph can be obtained from the adjacency matrix of its quotient graph given by a regular partition. In this paper, a method that gives all the spectrum, and also the local spectra, of a graph from the quotient matrices of some of its regular partitions, is proposed. Moreover, from such partitions, the C-local multiplicities of any class of vertices C is also determined, and some applications of these parameters in the characterization of completely regular codes and their inner distributions are described. As examples, it is shown how to find the eigenvalues and (local) multiplicities of walk-regular, distance-regular, and distance-biregular graphs., Partially supported by AGAUR from the Catalan Government under project 2017SGR1087 and by MICINN from the Spanish Governmentunder projects PGC2018-095471-B-I00 and MTM2017-83271-R. Also received funding from the European Union’s Horizon 2020 research and innovation programme under the Marie Sk lodowska-Curie grant agreement no. 734922