Pasar al contenido principal

CRIPTOGRAFIA PARA RETOS DIGITALES EMERGENTES: ESCENARIOS MULTI-USUARIO Y SEGURIDAD POST-CUANTICA

PID2019-109379RB-I00

•
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 de I+D+i (Generación de Conocimiento y Retos Investigación)
Año convocatoria 2019
Plan Estatal 2017-2020 Plan Estatal de Investigación Científica y Técnica y de Innovación
Centro beneficiario UNIVERSITAT POLITECNICA DE CATALUNYA

Resultados relacionados

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

UPCommons. Portal del coneixement obert de la UPC
Publicación Contribución de congreso (ConferenceOutput)

Shorter lattice-based zero-knowledge proofs for the correctness of a shuffle

  • Herranz Sotoca, Javier|||0000-0001-5141-7234
  • Martínez Pinilla, Ramiro|||0000-0003-0496-6462
  • Sánchez Torrón, Manuel
In an electronic voting procedure, mixing networks are used to ensure anonymity of the casted votes. Each node of the network re-encrypts the input list of ciphertexts and randomly permutes it in a process named shuffle, and must prove (in zero-knowledge) that the process was applied honestly. To maintain security of such a process in a post-quantum scenario, new proofs are based on different mathematical assumptions, such as lattice-based problems. Nonetheless, the best lattice-based protocols to ensure verifiable shuffling have linear communication complexity on N, the number of shuffled ciphertexts. In this paper we propose the first sub-linear (on N) post-quantum zero-knowledge argument for the correctness of a shuffle, for which we have mainly used two ideas: arithmetic circuit satisfiability results from Baum et al. (CRYPTO'2018) and Beneš networks to model a permutation of N elements. The achieved communication complexity of our protocol with respect to N is O(v(N)log^2(N)), but we will also highlight its dependency on other important parameters of the underlying lattice ingredients., The work is partially supported by the Spanish Ministerio de Ciencia e Innovaci´on (MICINN), under Project PID2019-109379RB-I00 and by the European Union PROMETHEUS project (Horizon 2020 Research and Innovation Program, grant 780701). Authors thank Tjerand Silde for pointing out an incorrect set of parameters (Section 4.1) that we had proposed in a previous version of the manuscript.
UPCommons. Portal del coneixement obert de la UPC
Publicación Contribución de congreso (ConferenceOutput)

Coercion-resistant cast-as-intended verifiability for computationally limited voters

  • Finogina, Tamara
  • Herranz Sotoca, Javier|||0000-0001-5141-7234
In this work, we investigate if two essential properties in electronic voting, coercion-resistance and cast-as-intended verifiability, can be jointly In this work, we investigate if two essential properties in electronic voting, coercion-resistance and cast-as-intended verifiability, can be jointly achieved in settings where voters are (very) limited from a computational point of view. This may be the case in elections where voters use a voting station or webpage to cast their votes but do not have specialized software or devices to perform complicated cryptographic operations (for instance, to verify zero-knowledge proofs or to generate one-way trapdoors). We provide a solution where the only things voters have to do are: remember and compare strings of numbers, on the one hand, and press a button at the appropriate moment, on the other hand. This button activates the participation of an online entity, which is trusted to choose a random nonce for each voter and to publish it only when that voter presses the button (and not before). The most expensive part of the verif ication is an OR proof of knowledge, which can be done by any (powerful enough) external verifier.
UPCommons. Portal del coneixement obert de la UPC
Publicación Artículo científico (JournalArticle)

On remote electronic voting with both coercion resistance and cast-as-intended verifiability

  • Finogina, Tamara
  • Herranz Sotoca, Javier|||0000-0001-5141-7234
In this work, we study two essential but apparently contradictory properties of electronic voting systems: coercion resistance (CR) and cast-as-intended verifiability (CAI). Informally, the CR property ensures that a voter cannot prove to anybody else the vote content, which prevents vote selling and voting under duress. The CAI property ensures that a malicious voting device cannot cheat the voter and send to the ballot box an encryption of a voting option different from the one chosen by the voter. In this work, we formalize security definitions capturing both coercion resistance and cast-as-intended verification in settings without secure delivery channels between the election authority and voters. After that, we consider some previously proposed solutions aimed at providing these two properties. For some of them (that we call unsatisfactory solutions) we show why they fail to achieve some of the two properties. We then concentrate on one of the two generic solutions that we call satisfactory: we prove that it satisfies the two proposed definitions and we detail how it can be instantiated in both classical cryptographic (e.g., ElGamal ciphertexts) and quantum-resistant (e.g., using lattice-based cryptosystems) settings., This work has been supported by the Spanish Ministerio de Ciencia e Innovación (MICINN), under Project PID2019-109379RB-I00, and by Generalitat de Catalunya, under Project DI 2018-038.
UPCommons. Portal del coneixement obert de la UPC
Publicación Artículo científico (JournalArticle)

Attacking pairing-free attribute-based encryption schemes

  • Herranz Sotoca, Javier|||0000-0001-5141-7234
Combining several results that have been published in the last years, it is known that it is impossible to design simple and secure attribute-based encryption schemes that work in (classical) settings like the RSA or the pairing-free discrete logarithm ones. The purpose of this article is to broadcast this message through a wide (maybe non-cryptographic) audience, specially now that attribute-based encryption is considered as a useful tool to secure real systems like the Internet of Things. Today, only attribute-based encryption schemes that employ tools like bilinear pairings or lattices can provide some real (and provable) level of security. As an example of the fact that this message is still unknown for many people, we revisit a (maybe non exhaustive) list of articles proposing such insecure attribute-based encryption schemes: we recall which of these schemes have already been attacked and we describe attacks for the other ones.
UPCommons. Portal del coneixement obert de la UPC
Publicación Contribución de congreso (ConferenceOutput)

How (not) to achieve both coercion resistance and cast as intended verifiability in remote eVoting

  • Finogina, Tamara
  • Herranz Sotoca, Javier|||0000-0001-5141-7234
  • Larraia, Enrique
The version of record is available online at:10.1007/978-3-030-92548-2_25, We consider the problem of achieving, at the same time, cast-as-intended verifiability and coercion resistance, in remote electronic voting systems where there are no secure channels through which voters can receive secret information/credentials before the voting phase. We discuss why some simple solutions fail to achieve the two desired notions and we propose (a bit) more involved solutions that are satisfactory. Part of the discussion is closely related to the gap “full versus honest-verifier” when defining the zero-knowledge property of cryptographic zero-knowledge systems., Peer Reviewed
UPCommons. Portal del coneixement obert de la UPC
Publicación Artículo científico (JournalArticle)

Bipartite secret sharing and staircases

  • Csirmaz, Laszlo
  • Matús, Frantisek
  • Padró Laimon, Carles|||0000-0002-8644-5929
© 2024 Elsevier. This manuscript version is made available under the CC-BY-NC-ND 4.0 license http://creativecommons.org/licenses/by-nc-nd/4.0/, Bipartite secret sharing schemes have a bipartite access structure in which the set of participants is divided into two parts and all participants in the same part play an equivalent role. Such a bipartite scheme can be described by a staircase: the collection of its minimal points. The complexity of a scheme is the maximal share size relative to the secret size; and the ¿-complexity of an access structure is the best lower bound provided by the entropy method. An access structure is ¿-ideal if it has ¿-complexity 1. Motivated by the abundance of open problems in this area, the main results can be summarized as follows. First, a new characterization of ¿-ideal multipartite access structures is given which offers a straightforward and simple approach to describe ideal bipartite and tripartite access structures. Second, the ¿-complexity is determined for a range of bipartite access structures, including those determined by two points, staircases with equal widths and heights, and staircases with all heights 1. Third, matching linear schemes are presented for some non-ideal cases, including staircases where all heights are 1 and all widths are equal. Finally, finding the Shannon complexity of a bipartite access structure can be considered as a discrete submodular optimization problem. An interesting and intriguing continuous version is defined which might give further insight to the large-scale behavior of these optimization problems., The work of the first author was partially supported by the ERC Advanced Grant ERMiD. The work of third author was supported by the Spanish Government (MICINN) under Project PID2019-109379RB-I00., Peer Reviewed
UPCommons. Portal del coneixement obert de la UPC
Publicación Artículo científico (JournalArticle)

Efficient representation of lattice path matroids

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

Frameproof codes, separable codes and B2 codes: bounds and constructions

  • Fernández Muñoz, Marcel|||0000-0001-7655-135X
  • Livieratos, John
  • Martín Mollevi, Sebastià|||0000-0002-9799-6793
In this paper, constructions of frameproof codes, separable codes, and B2 codes are obtained. For each family of codes, the Lovász Local Lemmais used to establish lower bounds for the codes. The obtained bounds match all best known bounds in the literature. Our strategy allows us to present constructions of the aforementioned codes, by using the variable framework for the Lovász Local Lemma., Open Access funding provided thanks to the CRUE-CSIC agreement with Springer Nature. The work of Marcel Fernández has been supported by TCO-RISEBLOCK (PID2019-110224RB-I00) MINECO. The work of Sebastiá Martín has been supported by Ministerio de Ciencia e Innovación, PID2019-109379RB-I00., Peer Reviewed
UPCommons. Portal del coneixement obert de la UPC
Publicación Artículo científico (JournalArticle)

A note on extension properties and representations of matroids

  • Bamiloshin, Micahel
  • Farràs Ventura, Oriol
  • Padró Laimon, Carles|||0000-0002-8644-5929
We discuss several extension properties of matroids and polymatroids and their application as necessary conditions for the existence of different matroid representations, namely linear, folded linear, algebraic, and entropic representations. Iterations of those extension properties are checked for matroids on eight and nine elements by means of computer-aided explorations, finding in that way several new examples of non-linearly representable matroids. A special emphasis is made on sparse paving matroids on nine points containing the tic-tac-toe configuration. We present a new, more clear description of that family and we analyze extension properties on those matroids and their duals., Michael Bamiloshin received funding from the European Union’s Horizon 2020 research and innovation programme under the Marie SkłodowskaCurie grant agreement No. 713679 and from the Universitat Rovira i Virgili. Oriol Farràs is supported by grant 2021 SGR 00115 from the Government of Catalonia and by the project HERMES, funded by INCIBE and by the European Union NextGeneration EU/PRTR. Carles Padró is supported by the Spanish Government through grant PID2019-109379RB-I00. Additionally, the authors are supported by the project ACITHEC PID2021-124928NB-I00, funded by MCIN/AEI/10.13039/ 501100011033/FEDER, EU., Peer Reviewed
Recercat. Dipósit de la Recerca de Catalunya
Publicación Artículo científico (JournalArticle)

Attacking pairing-free attribute-based encryption schemes

  • Herranz Sotoca, Javier
Combining several results that have been published in the last years, it is known that it is impossible to design simple and secure attribute-based encryption schemes that work in (classical) settings like the RSA or the pairing-free discrete logarithm ones. The purpose of this article is to broadcast this message through a wide (maybe non-cryptographic) audience, specially now that attribute-based encryption is considered as a useful tool to secure real systems like the Internet of Things. Today, only attribute-based encryption schemes that employ tools like bilinear pairings or lattices can provide some real (and provable) level of security. As an example of the fact that this message is still unknown for many people, we revisit a (maybe non exhaustive) list of articles proposing such insecure attribute-based encryption schemes: we recall which of these schemes have already been attacked and we describe attacks for the other ones., Postprint (published version)
Recercat. Dipósit de la Recerca de Catalunya
Publicación Contribución de congreso (ConferenceOutput)

Coercion-resistant cast-as-intended verifiability for computationally limited voters

  • Finogina, Tamara
  • Herranz Sotoca, Javier
In this work, we investigate if two essential properties in electronic voting, coercion-resistance and cast-as-intended verifiability, can be jointly In this work, we investigate if two essential properties in electronic voting, coercion-resistance and cast-as-intended verifiability, can be jointly achieved in settings where voters are (very) limited from a computational point of view. This may be the case in elections where voters use a voting station or webpage to cast their votes but do not have specialized software or devices to perform complicated cryptographic operations (for instance, to verify zero-knowledge proofs or to generate one-way trapdoors). We provide a solution where the only things voters have to do are: remember and compare strings of numbers, on the one hand, and press a button at the appropriate moment, on the other hand. This button activates the participation of an online entity, which is trusted to choose a random nonce for each voter and to publish it only when that voter presses the button (and not before). The most expensive part of the verif ication is an OR proof of knowledge, which can be done by any (powerful enough) external verifier., Postprint (published version)
Recercat. Dipósit de la Recerca de Catalunya
Publicación Artículo científico (JournalArticle)

On remote electronic voting with both coercion resistance and cast-as-intended verifiability

  • Finogina, Tamara
  • Herranz Sotoca, Javier
In this work, we study two essential but apparently contradictory properties of electronic voting systems: coercion resistance (CR) and cast-as-intended verifiability (CAI). Informally, the CR property ensures that a voter cannot prove to anybody else the vote content, which prevents vote selling and voting under duress. The CAI property ensures that a malicious voting device cannot cheat the voter and send to the ballot box an encryption of a voting option different from the one chosen by the voter. In this work, we formalize security definitions capturing both coercion resistance and cast-as-intended verification in settings without secure delivery channels between the election authority and voters. After that, we consider some previously proposed solutions aimed at providing these two properties. For some of them (that we call unsatisfactory solutions) we show why they fail to achieve some of the two properties. We then concentrate on one of the two generic solutions that we call satisfactory: we prove that it satisfies the two proposed definitions and we detail how it can be instantiated in both classical cryptographic (e.g., ElGamal ciphertexts) and quantum-resistant (e.g., using lattice-based cryptosystems) settings., This work has been supported by the Spanish Ministerio de Ciencia e Innovación (MICINN), under Project PID2019-109379RB-I00, and by Generalitat de Catalunya, under Project DI 2018-038., Postprint (published version)
Recercat. Dipósit de la Recerca de Catalunya
Publicación Artículo científico (JournalArticle)

Efficient representation of lattice path matroids

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

How (not) to achieve both coercion resistance and cast as intended verifiability in remote eVoting

  • Finogina, Tamara
  • Herranz Sotoca, Javier
  • Larraia, Enrique
The version of record is available online at:10.1007/978-3-030-92548-2_25, We consider the problem of achieving, at the same time, cast-as-intended verifiability and coercion resistance, in remote electronic voting systems where there are no secure channels through which voters can receive secret information/credentials before the voting phase. We discuss why some simple solutions fail to achieve the two desired notions and we propose (a bit) more involved solutions that are satisfactory. Part of the discussion is closely related to the gap “full versus honest-verifier” when defining the zero-knowledge property of cryptographic zero-knowledge systems., Peer Reviewed, Postprint (author's final draft)
Recercat. Dipósit de la Recerca de Catalunya
Publicación Artículo científico (JournalArticle)

A note on extension properties and representations of matroids

  • Bamiloshin, Micahel
  • Farràs Ventura, Oriol
  • Padró Laimon, Carles
We discuss several extension properties of matroids and polymatroids and their application as necessary conditions for the existence of different matroid representations, namely linear, folded linear, algebraic, and entropic representations. Iterations of those extension properties are checked for matroids on eight and nine elements by means of computer-aided explorations, finding in that way several new examples of non-linearly representable matroids. A special emphasis is made on sparse paving matroids on nine points containing the tic-tac-toe configuration. We present a new, more clear description of that family and we analyze extension properties on those matroids and their duals., Michael Bamiloshin received funding from the European Union’s Horizon 2020 research and innovation programme under the Marie SkłodowskaCurie grant agreement No. 713679 and from the Universitat Rovira i Virgili. Oriol Farràs is supported by grant 2021 SGR 00115 from the Government of Catalonia and by the project HERMES, funded by INCIBE and by the European Union NextGeneration EU/PRTR. Carles Padró is supported by the Spanish Government through grant PID2019-109379RB-I00. Additionally, the authors are supported by the project ACITHEC PID2021-124928NB-I00, funded by MCIN/AEI/10.13039/ 501100011033/FEDER, EU., Peer Reviewed, Postprint (published version)
Recercat. Dipósit de la Recerca de Catalunya
Publicación Artículo científico (JournalArticle)

Frameproof codes, separable codes and B2 codes: bounds and constructions

  • Fernández Muñoz, Marcel
  • Livieratos, John
  • Martín Mollevi, Sebastià
In this paper, constructions of frameproof codes, separable codes, and B2 codes are obtained. For each family of codes, the Lovász Local Lemmais used to establish lower bounds for the codes. The obtained bounds match all best known bounds in the literature. Our strategy allows us to present constructions of the aforementioned codes, by using the variable framework for the Lovász Local Lemma., Open Access funding provided thanks to the CRUE-CSIC agreement with Springer Nature. The work of Marcel Fernández has been supported by TCO-RISEBLOCK (PID2019-110224RB-I00) MINECO. The work of Sebastiá Martín has been supported by Ministerio de Ciencia e Innovación, PID2019-109379RB-I00., Peer Reviewed, Postprint (published version)
Recercat. Dipósit de la Recerca de Catalunya
Publicación Artículo científico (JournalArticle)

Bipartite secret sharing and staircases

  • Csirmaz, Laszlo
  • Matús, Frantisek
  • Padró Laimon, Carles
© 2024 Elsevier. This manuscript version is made available under the CC-BY-NC-ND 4.0 license http://creativecommons.org/licenses/by-nc-nd/4.0/, Bipartite secret sharing schemes have a bipartite access structure in which the set of participants is divided into two parts and all participants in the same part play an equivalent role. Such a bipartite scheme can be described by a staircase: the collection of its minimal points. The complexity of a scheme is the maximal share size relative to the secret size; and the ¿-complexity of an access structure is the best lower bound provided by the entropy method. An access structure is ¿-ideal if it has ¿-complexity 1. Motivated by the abundance of open problems in this area, the main results can be summarized as follows. First, a new characterization of ¿-ideal multipartite access structures is given which offers a straightforward and simple approach to describe ideal bipartite and tripartite access structures. Second, the ¿-complexity is determined for a range of bipartite access structures, including those determined by two points, staircases with equal widths and heights, and staircases with all heights 1. Third, matching linear schemes are presented for some non-ideal cases, including staircases where all heights are 1 and all widths are equal. Finally, finding the Shannon complexity of a bipartite access structure can be considered as a discrete submodular optimization problem. An interesting and intriguing continuous version is defined which might give further insight to the large-scale behavior of these optimization problems., The work of the first author was partially supported by the ERC Advanced Grant ERMiD. The work of third author was supported by the Spanish Government (MICINN) under Project PID2019-109379RB-I00., Peer Reviewed, Postprint (author's final draft)
Recercat. Dipósit de la Recerca de Catalunya
Publicación Contribución de congreso (ConferenceOutput)

Shorter lattice-based zero-knowledge proofs for the correctness of a shuffle

  • Herranz Sotoca, Javier
  • Martínez Pinilla, Ramiro
  • Sánchez Torrón, Manuel
In an electronic voting procedure, mixing networks are used to ensure anonymity of the casted votes. Each node of the network re-encrypts the input list of ciphertexts and randomly permutes it in a process named shuffle, and must prove (in zero-knowledge) that the process was applied honestly. To maintain security of such a process in a post-quantum scenario, new proofs are based on different mathematical assumptions, such as lattice-based problems. Nonetheless, the best lattice-based protocols to ensure verifiable shuffling have linear communication complexity on N, the number of shuffled ciphertexts. In this paper we propose the first sub-linear (on N) post-quantum zero-knowledge argument for the correctness of a shuffle, for which we have mainly used two ideas: arithmetic circuit satisfiability results from Baum et al. (CRYPTO'2018) and Beneš networks to model a permutation of N elements. The achieved communication complexity of our protocol with respect to N is O(v(N)log^2(N)), but we will also highlight its dependency on other important parameters of the underlying lattice ingredients., The work is partially supported by the Spanish Ministerio de Ciencia e Innovaci´on (MICINN), under Project PID2019-109379RB-I00 and by the European Union PROMETHEUS project (Horizon 2020 Research and Innovation Program, grant 780701). Authors thank Tjerand Silde for pointing out an incorrect set of parameters (Section 4.1) that we had proposed in a previous version of the manuscript., Postprint (author's final draft)