International Conference on Practice and Theory in Public Key Cryptography

p. 435-464

DOI: 10.1007/978-3-662-54365-8_18

Presentation's date: 2017-03-30

Abstract:

In this paper we provide new algebraic tools to study the relationship between different Matrix Diffie-Hellman (MDDH) Problems, which are recently introduced as a natural generalization of the so-called Linear Problem. Namely, we provide an algebraic criterion to decide whether there exists a generic black-box reduction, and in many cases, when the answer is positive we also build an explicit reduction with the following properties: it only makes a single oracle call, it is tight and it makes use only of operations in the base group. It is well known that two MDDH problems described by matrices with a different number of rows are separated by an oracle computing certain multilinear map. Thus, we put the focus on MDDH problems of the same size. Then, we show that MDDH problems described with a different number of parameters are also separated (meaning that a successful reduction cannot decrease the amount of randomness used in the problem instance description). When comparing MDDH problems of the same size and number of parameters, we show that they are either equivalent or incomparable. This suggests that a complete classification into equivalence classes could be done in the future. In this paper we give some positive and negative partial results about equivalence, in particular solving the open problem of whether the Linear and the Cascade MDDH problems are reducible to each other. The results given in the paper are limited by some technical restrictions in the shape of the matrices and in the degree of the polynomials defining them. However, these restrictions are also present in most of the work dealing with MDDH Problems. Therefore, our results apply to all known instances of practical interest.

The final publication is available at link.springer.com]]>

Lecture notes in computer science

Vol. 10174, p. 435-464

DOI: 10.1007/978-3-662-54365-8_18

Date of publication: 2017-02

Abstract:

In this paper we provide new algebraic tools to study the relationship between different Matrix Diffie-Hellman (MDDH) Problems, which are recently introduced as a natural generalization of the so-called Linear Problem. Namely, we provide an algebraic criterion to decide whether there exists a generic black-box reduction, and in many cases, when the answer is positive we also build an explicit reduction with the following properties: it only makes a single oracle call, it is tight and it makes use only of operations in the base group. It is well known that two MDDH problems described by matrices with a different number of rows are separated by an oracle computing cer- tain multilinear map. Thus, we put the focus on MDDH problems of the same size. Then, we show that MDDH problems described with a different number of parameters are also separated (meaning that a suc- cessful reduction cannot decrease the amount of randomness used in the problem instance description). When comparing MDDH problems of the same size and number of pa- rameters, we show that they are either equivalent or incomparable. This suggests that a complete classification into equivalence classes could be done in the future. In this paper we give some positive and negative par- tial results about equivalence, in particular solving the open problem of whether the Linear and the Cascade MDDH problems are reducible to each other. The results given in the paper are limited by some technical restrictions in the shape of the matrices and in the degree of the polynomials defining them. However, these restrictions are also present in most of the work dealing with MDDH Problems. Therefore, our results apply to all known instances of practical interest.

The final publication is available at link.springer.com]]>

Journal of cryptology

Vol. 30, num. 1, p. 242-288

DOI: 10.1007/s00145-015-9220-6

Date of publication: 2017-01

Abstract:

We put forward a new algebraic framework to generalize and analyze Die-Hellman like Decisional Assumptions which allows us to argue about security and applications by considering only algebraic properties. Our D`;k-MDDH assumption states that it is hard to decide whether a vector in G` is linearly dependent of the columns of some matrix in G`k sampled according to distribution D`;k. It covers known assumptions such as DDH, 2-Lin (linear assumption), and k-Lin (the k-linear assumption). Using our algebraic viewpoint, we can relate the generic hardness of our assumptions in m-linear groups to the irreducibility of certain polynomials which describe the output of D`;k. We use the hardness results to nd new distributions for which the D`;k-MDDH-Assumption holds generically in m-linear groups. In particular, our new assumptions 2-SCasc and 2-ILin are generically hard in bilinear groups and, compared to 2-Lin, have shorter description size, which is a relevant parameter for eciency in many applications. These results support using our new assumptions as natural replacements for the 2-Lin Assumption which was already used in a large number of applications. To illustrate the conceptual advantages of our algebraic framework, we construct several fundamental primitives based on any MDDH-Assumption. In particular, we can give many instantiations of a primitive in a compact way, including public-key encryption, hash-proof systems, pseudo-random functions, and Groth-Sahai NIZK and NIWI proofs. As an independent contribution we give more ecient NIZK and NIWI proofs for membership in a subgroup of G`. The results imply very signicant eciency improvements for a large number of schemes.

The final publication is available at Springer via http://dx.doi.org/10.1007/s00145-015-9220-6

We put forward a new algebraic framework to generalize and analyze Di e-Hellman like Decisional Assumptions which allows us to argue about security and applications by considering only algebraic properties. Our D`;k-MDDH assumption states that it is hard to decide whether a vector in G` is linearly dependent of the columns of some matrix in G` k sampled according to distribution D`;k. It covers known assumptions such as DDH, 2-Lin (linear assumption), and k-Lin (the k-linear assumption). Using our algebraic viewpoint, we can relate the generic hardness of our assumptions in m-linear groups to the irreducibility of certain polynomials which describe the output of D`;k. We use the hardness results to nd new distributions for which the D`;k-MDDH-Assumption holds generically in m-linear groups. In particular, our new assumptions 2-SCasc and 2-ILin are generically hard in bilinear groups and, compared to 2-Lin, have shorter description size, which is a relevant parameter for e ciency in many applications. These results support using our new assumptions as natural replacements for the 2-Lin Assumption which was already used in a large number of applications. To illustrate the conceptual advantages of our algebraic framework, we construct several fundamental primitives based on any MDDH-Assumption. In particular, we can give many instantiations of a primitive in a compact way, including public-key encryption, hash-proof systems, pseudo-random functions, and Groth-Sahai NIZK and NIWI proofs. As an independent contribution we give more e cient NIZK and NIWI proofs for membership in a subgroup of G`. The results imply very signi cant e ciency improvements for a large number of schemes.]]>

Journal of cryptology

Vol. 30, num. 1, p. 242-288

DOI: 10.1007/s00145-015-9220-6

Date of publication: 2017-01

Abstract:

We put forward a new algebraic framework to generalize and analyze Diffie-Hellman like Decisional Assumptions which allows us to argue about security and applications by considering only algebraic properties. Our D`,k-MDDH assumption states that it is hard to decide whether a vector in ¿ìs linearly dependent of the columns of some matrix in ¿`×k sampled according to distribution D`,k. It covers known assumptions such as DDH, 2-Lin (linear assumption), and k-Lin (the k-linear assumption). Using our algebraic viewpoint, we can relate the generic hardness of our assumptions in m-linear groups to the irreducibility of certain polynomials which describe the output of D`,k. We use the hardness results to find new distributions for which the D`,k-MDDH-Assumption holds generically in m-linear groups. In particular, our new assumptions 2-SCasc and 2-ILin are generically hard in bilinear groups and, compared to 2-Lin, have shorter description size, which is a relevant parameter for efficiency in many applications. These results support using our new assumptions as natural replacements for the 2-Lin Assumption which was already used in a large number of applications. To illustrate the conceptual advantages of our algebraic framework, we construct several fundamental primitives based on any MDDH-Assumption. In particular, we can give many instantiations of a primitive in a compact way, including public-key encryption, hash-proof systems, pseudo-random functions, and Groth-Sahai NIZK and NIWI proofs. As an independent contribution we give more efficient NIZK and NIWI proofs for membership in a subgroup of ¿` . The results imply very significant efficiency improvements for a large number of schemes.]]>

Abstract:

The aim al this project is to obtain new results, improvements and advances in the design and study al the cryptographic primitives that, in a transversal way, take part in many al the applications conforming a secure e-Society. The results we expect to obtain, even being of mathematical/theoretical nature, mus! have an almost immediate impact in the improvement, in terms of both security and efficiency, of sorne of the most common applications in the e-Society. The research work proposed in this project deals with topics like the design of better cryptographic protocols for digital interactions, including encryption, digital signatures, key generation and exchange, atribute-based and identity-based cryptosystems. The improvements are with respect to the efficiency, the security or the extra features of the above mentioned protocols. The results will _have an impact on the current e-voting systems as well as on prívate and secure authentication systems, secure cloud-storage and cloudcomputing, anonymous access control systems or confidential data sharing on social networks. We will also analyze and propose new cryptographic schemes enjoying post-quantum security, to address the challenge of preserving the security of digital communications even the day when fully operative quantum computers will exist. We will particularly focus on the design of cryptographic protocols with postquantum security for electronic voting systems. Another aim of this project is to gel new results in other cryptographic areas like secret sharing schemes or algebraic frameworks to study hard computational problems, which have a more theoretical nature but also have strong implications in the design and security analysis of cryptographic protocols that are used in real lile. To guarantee that our research efforts lace real challenges in the e-Society, another goal of the project is to draw up new collaboration agreements with agents in the system (companies, public administration), analogous to those we already have with companies like Scytl or 14S, in order to provide them with our experience in the resolution of problems related to cryptography, and so that their resolution will have the biggest possible impact in the Spanish society, both present and future. Last but not least, the project will contribute to the academic training of the next generation of experts in cryptography, who will lead the future research in this area, by working either in research centers or in companies that will develop and use secure digital solutions.]]>

Lecture notes in computer science

Vol. 10031, p. 729-758

DOI: 10.1007/978-3-662-53887-6_27

Date of publication: 2016-12

Abstract:

We put forward a new family of computational assumptions, the Kernel Matrix Diffie-Hellman Assumption. Given some matrix A sampled from some distribution D, the kernel assumption says that it is hard to find “in the exponent” a nonzero vector in the kernel of A>. This family is a natural computational analogue of the Matrix Decisional Diffie-Hellman Assumption (MDDH), proposed by Escala et al. As such it allows to extend the advantages of their algebraic framework to computational assumptions. The k-Decisional Linear Assumption is an example of a family of decisional assumptions of strictly increasing hardness when k grows. We show that for any such family of MDDH assumptions, the corresponding Kernel assumptions are also strictly increasingly weaker. This requires ruling out the existence of some black-box reductions between flexible problems (i.e., computational problems with a non unique solution).

The final publication is available at link.springer.com]]>

Annual International Conference on the Theory and Application of Cryptology and Information Security

p. 729-758

DOI: 10.1007/978-3-662-53887-6_27

Presentation's date: 2016-12

Abstract:

We put forward a new family of computational assumptions, the Kernel Matrix Diffie-Hellman Assumption. Given some matrix A sampled from some distribution D, the kernel assumption says that it is hard to find “in the exponent” a nonzero vector in the kernel of A¿ . This family is a natural computational analogue of the Matrix Decisional Diffie-Hellman Assumption (MDDH), proposed by Escala et al. As such it allows to extend the advantages of their algebraic framework to computational assumptions. The k-Decisional Linear Assumption is an example of a family of decisional assumptions of strictly increasing hardness when k grows. We show that for any such family of MDDH assumptions, the corresponding Kernel assumptions are also strictly increasingly weaker. This requires ruling out the existence of some black-box reductions between flexible problems (i.e., computational problems with a non unique solution).

The final publication is available at https://link.springer.com/chapter/10.1007%2F978-3-662-53887-6_27]]>

Date: 2015-04-20

Abstract:

We put forward a new family of computational assumptions, the Kernel Matrix Die- Hellman Assumption. Given some matrix A sampled from some distribution D `;k , the kernel as- sumption says that it is hard to nd \in the exponent" a nonzero vector in the kernel of A > . This family is the natural computational analogue of the Matrix Decisional Die-Hellman Assumption (MDDH), proposed by Escala et al . As such it allows to extend the advantages of their algebraic framework to computational assumptions. The k -Decisional Linear Assumption is an example of a family of decisional assumptions of strictly increasing hardness when k grows. We show that for any such family the corresponding Kernel Assumption family is also a strictly increasingly weaker family of computational assumptions. This requires ruling out the existence of some black-box reductions between exible problems ( i.e. , com- putational problems with a non unique solution)

We put forward a new family of computational assumptions, the Kernel Matrix Di e- Hellman Assumption. Given some matrix A sampled from some distribution D `;k , the kernel as- sumption says that it is hard to nd \in the exponent]]>

Information sciences

Vol. 276, p. 319-331

DOI: 10.1016/j.ins.2013.11.009

Date of publication: 2014-08-20

Abstract:

In this paper we describe a cryptanalysis of a key exchange scheme recently proposed by Alvarez, Tortosa, Vicent and Zamora. The scheme is based on exponentiation of block matrices over a finite field of prime order, and its security is claimed to rely in the hardness of a discrete logarithm problem in a subgroup of GL(n)(Z(p)). However, the proposal's design allows for a clean attack strategy which exploits the fact that exponents are at some point added instead of multiplied as in a standard Diffie-Hellman construction. This strategy is moreover successful for a much more general choice of parameters than that put forward by Alvarez et al. (C) 2013 Elsevier Inc. All rights reserved.]]>

Abstract:

The aim of this project is to contribute to the challenge of enforcing the confidence in the digital technologies, by finding new results, improvements and advances in the design and study of the cryptographic primitives that, in a transversal/generic way, take part in the applications conforming a secure e- Society. The results we aim to obtain, even being of mathematical/theoretical nature, must have an almost immediate impact in the improvement, in terms of both security and efficiency, of some of the most common applications in the e-Society. The research work proposed in this project includes (o contains) subjects like the design of improved cryptographic protocols for digital interactions, including multiparty computation, encryption, digital signature, key exchange and generation and zero-knowledge proofs. These improvements are with respect to the efficiency, the security or the extra features of the above mentioned protocols. The results will have an impact on the current e-voting systems as well as on e-mail, e-commerce systems, private and secure authentication systems, secure cloud-storage and cloud-computing, anonymous access control systems or confidential data sharing on social networks. The project also addresses the study and design of cryptographic primitives extending distributed cryptography beyond the threshold barrier, to other access structures of practical interest. The criteria used here will be efficiency and applicability to attribute based cryptography, e-voting, secure cloud-storage, access control systems and confidential data-sharing. We also aim to analyze the security of existing cryptosystems that resist certain attacks based on quantum computers, and to propose new systems with this property. Finally, another technical goal of this project is to improve the current knowledge of the relationships between the different computationally-hard mathematical problems used in cryptography, and between the different security models. For instance, we plan to search for generic frameworks that help simplifying the security analysis of cryptographic protocols. The theoretical character of this research does not prevent its practical implications, because the mathematical problem on which the security of a protocol is based has direct consequences on the final complexity of the protocol, in particular on efficiency parameters like the size of keys, ciphertexts or digital signatures. Regarding its more informative and formative side, this project will have an impact on several sectors of the society (mainly companies and public administration), which will be offered useful and clear information about the state-of-art in Cryptology, the guarantees it offers, and where and how it can and must be used. We also stress the project impact on the future of research and applications of Cryptology, since the project will contribute to training the next generation of cryptography experts, who will lead the future research in this area, either from research centers or from companies developing or using secure digital solutions.]]>

Date: 2013-06-11

Annual International Cryptology Conference

p. 129-147

DOI: 10.1007/978-3-642-40084-1_8

Abstract:

We put forward a new algebraic framework to generalize and analyze Diffie-Hellman like Decisional Assumptions which allows us to argue about security and applications by considering only algebraic properties. Our D l,k-MDDH assumption states that it is hard to decide whether a vector in Gl is linearly dependent of the columns of some matrix in Glxk sampled according to distribution Dl,k. It covers known assumptions such as DDH, Lin2 (linear assumption), and k-Lin (the k-linear assumption). Using our algebraic viewpoint, we can relate the generic hardness of our assumptions in m-linear groups to the irreducibility of certain polynomials which describe the output of Dl,k. We use the hardness results to find new distributions for which the Dl,k- MDDH-Assumption holds generically in m-linear groups. In particular, our new assumptions 2-SCasc and 2-ILin are generically hard in bilinear groups and, compared to 2-Lin, have shorter description size, which is a relevant parameter for efficiency in many applications. These results support using our new assumptions as natural replacements for the 2-Lin Assumption which was already used in a large number of applications. To illustrate the conceptual advantages of our algebraic framework, we construct several fundamental primitives based on any MDDH-Assumption. In particular, we can give many instantiations of a primitive in a compact way, including public-key encryption, hash-proof systems, pseudo-random functions, and Groth-Sahai NIZK and NIWI proofs. As an independent contribution we give more efficient NIZK and NIWI proofs for membership in a subgroup of Gl, for validity of ciphertexts and for equality of plaintexts. The results imply very significant efficiency improvements for a large number of schemes, most notably Naor-Yung type of constructions.]]>

Annual International Conference on the Theory and Application of Cryptology and Information Security

p. 80-97

DOI: 10.1007/978-3-642-34961-4

Presentation's date: 2012-12-03

Lecture notes in computer science

Vol. 7658, p. 80-97

DOI: 10.1007/978-3-642-34961-4_7

Date of publication: 2012-12

European Symposium on Research in Computer Security

p. 627-642

DOI: 10.1007/978-3-642-33167-1_36

Presentation's date: 2012-09

Communications in computer and information science

Vol. 222, num. 5, p. 203-219

DOI: 10.1007/978-3-642-25206-8_13

Date of publication: 2012

Abstract:

We propose a simple and efficient Subscription Scheme, allowing a set of users to anonymously pay for and request access to different services offered by a number of service providers. Using an e-cash system in such a scenario, the identity of the user would be hid into the e-coin in order to preserve its anonymity. Providing an additional triggering mechanism that opens this identity in case of double spending, also the service provider will be protected against fraud. Note that in traditional e-cash universality of the coin is required, however, in our scenario, the use of the token is completely determined at issuing time (yet this final aim remains hidden to the issuing authority). This allows for our construction, in which moreover fraud detection here implies no loss of anonymity; as we make access tokens independent of the owner in a quite simple and efficient way. On the other hand, if different usages of the same token are allowed, these are fully traceable by the service providers. An application to e-polling protocols is also given.]]>

Public Key Infrastructures, Services and Applications

p. 125-140

DOI: 10.1007/978-3-642-22633-5_9

Presentation's date: 2010-09

Abstract:

A fair contract signing protocol is used to enable two mistrusted parties to exchange two signatures on a given contract, in such a way that either both of them get the other party’s signature, or none of them gets anything. A new signature scheme is presented, which is a variant of Boneh and Boyen’s scheme, and building on it, we propose a new signature fair exchange protocol for which all the properties of being optimistic, setup-free and abuse-free can be proved without random oracles, and it is more efficient than the known schemes with comparable properties.]]>

International Conference on Security and Cryptography

p. 120-131

Presentation's date: 2010-07

Abstract:

In traditional e-cash systems, the tradeoff between anonymity and fraud-detection is solved by hiding the identity of the user into the e-coin, and providing an additional triggering mechanism that opens this identity in case of double spending. Hence, fraud detection implies loss of anonymity. This seems to be a somewhat natural solution when universality of the e-coin is required (i.e., the use of the coin is not determined at the time the coin is generated). However, much simpler protocols may suffice if we only want to prevent that payments for accessing certain services are over-used, even when users' anonymity is perfectly preserved. In this paper we propose a simple and efficient Subscription Scheme, allowing a set of users to anonymously pay for and request access to different services offered by a number of service providers. In our approach, the use of the token is completely determined at issuing time, yet this final aim remains hidden to the issuing authority. Moreover, fraud detection here implies no loss of anonymity; as we make access tokens independent of the owner in a quite simple and efficient way. On the other hand, if different usages of the same token are allowed, these are fully traceable by the service providers.]]>

Abstract:

ECRYPT II is a NoE in the area of cryptology with a duration of 54 months. Cryptology is the science that studies mathematical techniques in order to provide secrecy, authenticity and related properties for digital information including the secure implementations of these techniques. It is an interdisciplinary research area with a high strategic impact for European industry and for the society as a whole. It is a fundamental enabler for secure, dependable and trusted infrastructures. The ECRYPT II research roadmap is motivated by the changing environment and threat models in which cryptology is deployed, by the gradual erosion of the computational difficulty of the mathematical problems on which cryptology is based, and by the requirements of new applications and cryptographic implementations. Its main objective is to ensure a durable integration of European research in both academia and industry and to maintain and strengthen the European excellence in these areas. In order to reach this goal, 11 leading players propose to integrate their research capabilities within three virtual labs focusing on symmetric key algorithms, public key algorithms and protocols, and hardware and software implementation. They will be joined by more than 20 adjoint members to the network who will closely collaborate with the core partners. ECRYPT II plans to build on an expand the integration activities developed within ECRYPT that include joint workshops, exchange of researchers and students, development of common tools and benchmarks and a website and forum which will be a focal point for the network and the wider cryptographic community. Spreading activities will include a training program, a substantial contribution towards standardization, bodies and an active publication policy. The project team has the critical mass and breadth to address the key questions in these areas.]]>

Designs codes and cryptography

Vol. 52, num. 2, p. 129-154

DOI: 10.1007/s10623-009-9272-4

Date of publication: 2009-08

Lecture notes in computer science

Vol. 5381, p. 294-308

DOI: 10.1007/978-3-642-04159-4

Date of publication: 2009

Abstract:

In this paper we propose a new publicly verifiable secret sharing scheme using pairings with close relations to Shoenmakers’ scheme. This scheme is efficient, multiplicatively homomorphic and with unconditional verifiability in the standard model. We formalize the notion of Indistinguishability of Secrets and prove that out scheme achieves it under the Decisional Bilinear Square (DBS) Assumption that is a natural variant of the Decisional Bilinear Diffie Hellman Assumption. Moreover, our scheme tolerates active and adaptive adversaries.]]>

International Workshop on Selected Areas in Cryptography

Presentation's date: 2008-08-15

Applicable algebra in engineering communication and computing

Vol. 19, num. 2, p. 161-173

DOI: 10.1007/s00200-008-0068-y

Date of publication: 2008-04

International Workshop on Selected Areas in Cryptography

p. 275-289

Date of publication: 2006-12-31

Annual International Conference on the Theory and Application of Cryptology and Information Security

Presentation's date: 2006-12-06

Lecture notes in computer science

Vol. 4284, p. 252-266

Date of publication: 2006-12

IX Reunion Española sobre Criptologia y Seguridad de la Informacion

Presentation's date: 2006-09-07

Geometric and Asymptotic Group Theory with Applications

p. 46-

Presentation's date: 2006-09-04

Abstract:

In this talk, we analyze the hardness of the discrete logarithm problem on matrix groups over finite commutative rings and its relation to the traditional discrete logarithm problem, over a finite field. Some considerations about the conjugacy problem in such groups are also done.]]>

International Congress of Mathematicians

Presentation's date: 2006-08-25