The Experts below are selected from a list of 41214 Experts worldwide ranked by ideXlab platform

David Pointcheval - One of the best experts on this subject based on the ideXlab platform.

  • On the Tightness of Forward-Secure Signature Reductions
    Journal of Cryptology, 2018
    Co-Authors: Michel Abdalla, Fabrice Benhamouda, David Pointcheval
    Abstract:

    In this paper, we revisit the Security of factoring-based signature schemes built via the Fiat–Shamir transform and show that they can admit tighter reductions to certain decisional complexity assumptions such as the quadratic-residuosity, the high-residuosity, and the $$\phi $$ϕ-hiding assumptions. We do so by proving that the underlying identification schemes used in these schemes are a particular case of the lossy identification notion introduced by Abdalla et al. at Eurocrypt 2012. Next, we show how to extend these results to the forward-Security Setting based on ideas from the Itkis–Reyzin forward-secure signature scheme. Unlike the original Itkis–Reyzin scheme, our construction can be instantiated under different decisional complexity assumptions and has a much tighter Security reduction. Moreover, we also show that the tighter Security reductions provided by our proof methodology can result in concrete efficiency gains in practice, both in the standard and forward-Security Setting, as long as the use of stronger Security assumptions is deemed acceptable. Finally, we investigate the design of forward-secure signature schemes whose Security reductions are fully tight.

  • On the Tightness of Forward-Secure Signature Reductions
    2017
    Co-Authors: Michel Abdalla, Fabrice Benhamouda, David Pointcheval
    Abstract:

    In this paper, we revisit the Security of factoring-based signature schemes built via the Fiat-Shamir transform and show that they can admit tighter reductions to certain decisional complexity assumptions such as the quadratic-residuosity, the high-residuosity, and the ϕ ϕ -hiding assumptions. We do so by proving that the underlying identification schemes used in these schemes are a particular case of the lossy identification notion recently introduced by Abdalla et al. at Eurocrypt 2012. Next, we show how to extend these results to the forward-Security Setting based on ideas from the Itkis-Reyzin forward-secure signature scheme. Unlike the original Itkis-Reyzin scheme, our construction can be instantiated under different decisional complexity assumptions and has a much tighter Security reduction. Moreover, we also show that the tighter Security reductions provided by our proof methodology can result in concrete efficiency gains in practice, both in the standard and forward-Security Setting, as long as the use of stronger Security assumptions is deemed acceptable. Finally, we investigate the design of forward-secure signature schemes whose Security reductions are fully tight.

  • tighter reductions for forward secure signature schemes
    Public Key Cryptography, 2013
    Co-Authors: Michel Abdalla, Fabrice Ben Hamouda, David Pointcheval
    Abstract:

    In this paper, we revisit the Security of factoring-based signature schemes built via the Fiat-Shamir transform and show that they can admit tighter reductions to certain decisional complexity assumptions such as the quadratic-residuosity, the high-residuosity, and the φ-hiding assumptions. We do so by proving that the underlying identification schemes used in these schemes are a particular case of the lossy identification notion recently introduced by Abdalla et al. at Eurocrypt 2012. Next, we show how to extend these results to the forward-Security Setting based on ideas from the Itkis-Reyzin forward-secure signature scheme. Unlike the original Itkis-Reyzin scheme, our construction can be instantiated under different decisional complexity assumptions and has a much tighter Security reduction. Finally, we show that the tighter Security reductions provided by our proof methodology can result in concrete efficiency gains in practice, both in the standard and forward-Security Setting, as long as the use of stronger Security assumptions is deemed acceptable. All of our results hold in the random oracle model.

  • Public Key Cryptography - Tighter Reductions for Forward-Secure Signature Schemes
    Public-Key Cryptography – PKC 2013, 2013
    Co-Authors: Michel Abdalla, Fabrice Ben Hamouda, David Pointcheval
    Abstract:

    In this paper, we revisit the Security of factoring-based signature schemes built via the Fiat-Shamir transform and show that they can admit tighter reductions to certain decisional complexity assumptions such as the quadratic-residuosity, the high-residuosity, and the φ-hiding assumptions. We do so by proving that the underlying identification schemes used in these schemes are a particular case of the lossy identification notion recently introduced by Abdalla et al. at Eurocrypt 2012. Next, we show how to extend these results to the forward-Security Setting based on ideas from the Itkis-Reyzin forward-secure signature scheme. Unlike the original Itkis-Reyzin scheme, our construction can be instantiated under different decisional complexity assumptions and has a much tighter Security reduction. Finally, we show that the tighter Security reductions provided by our proof methodology can result in concrete efficiency gains in practice, both in the standard and forward-Security Setting, as long as the use of stronger Security assumptions is deemed acceptable. All of our results hold in the random oracle model.

Somindu C. Ramanna - One of the best experts on this subject based on the ideXlab platform.

  • Non-Zero Inner Product Encryption with Short Ciphertexts and Private Keys
    2016
    Co-Authors: Jie Chen, Benoît Libert, Somindu C. Ramanna
    Abstract:

    We describe two constructions of non-zero inner product encryption (NIPE) systems in the public index Setting, both having ciphertexts and secret keys of constant size. Both schemes are obtained by tweaking the Boneh-Gentry-Waters broadcast encryption system (Crypto 2005) and are proved selectively secure without random oracles under previously considered assumptions in groups with a bilinear map. Our first realization builds on prime-order bilinear groups and is proved secure under the Decisional Bilinear Diffie-Hellman Exponent assumption, which is parameterized by the length n of vectors over which the inner product is defined. By moving to composite order bilinear groups, we are able to obtain Security under static subgroup decision assumptions following the Déj a Q framework of Chase and Meiklejohn (Eurocrypt 2014) and its extension by Wee (TCC 2016). Our schemes are the first NIPE systems to achieve such parameters, even in the selective Security Setting. Moreover, they are the first proposals to feature optimally short private keys, which only consist of one group element. Our prime-order-group realization is also the first one with a deterministic key generation mechanism.

  • Non-zero Inner Product Encryption with Short Ciphertexts and Private Keys
    Security and Cryptography for Networks, 2016
    Co-Authors: Jie Chen, Benoît Libert, Somindu C. Ramanna
    Abstract:

    We describe two constructions of non-zero inner product encryption (NIPE) systems in the public index Setting, both having ciphertexts and secret keys of constant size. Both schemes are obtained by tweaking the Boneh-Gentry-Waters broadcast encryption system (Crypto 2005) and are proved selectively secure under previously considered assumptions in groups with a bilinear map. Our first realization builds on prime-order bilinear groups and is proved secure under the Decisional Bilinear Diffie-Hellman Exponent assumption, which is parameterized by the length n of vectors over which the inner product is defined. By moving to composite order bilinear groups, we are able to obtain Security under static subgroup decision assumptions following the Déjà Q framework of Chase and Meiklejohn (Eurocrypt 2014) and its extension by Wee (TCC 2016). Our schemes are the first NIPE systems to achieve such parameters, even in the selective Security Setting. Moreover, they are the first proposals to feature optimally short private keys, which only consist of one group element. Our prime-order-group realization is also the first one with a deterministic key generation mechanism.

Michel Abdalla - One of the best experts on this subject based on the ideXlab platform.

  • On the Tightness of Forward-Secure Signature Reductions
    Journal of Cryptology, 2018
    Co-Authors: Michel Abdalla, Fabrice Benhamouda, David Pointcheval
    Abstract:

    In this paper, we revisit the Security of factoring-based signature schemes built via the Fiat–Shamir transform and show that they can admit tighter reductions to certain decisional complexity assumptions such as the quadratic-residuosity, the high-residuosity, and the $$\phi $$ϕ-hiding assumptions. We do so by proving that the underlying identification schemes used in these schemes are a particular case of the lossy identification notion introduced by Abdalla et al. at Eurocrypt 2012. Next, we show how to extend these results to the forward-Security Setting based on ideas from the Itkis–Reyzin forward-secure signature scheme. Unlike the original Itkis–Reyzin scheme, our construction can be instantiated under different decisional complexity assumptions and has a much tighter Security reduction. Moreover, we also show that the tighter Security reductions provided by our proof methodology can result in concrete efficiency gains in practice, both in the standard and forward-Security Setting, as long as the use of stronger Security assumptions is deemed acceptable. Finally, we investigate the design of forward-secure signature schemes whose Security reductions are fully tight.

  • On the Tightness of Forward-Secure Signature Reductions
    2017
    Co-Authors: Michel Abdalla, Fabrice Benhamouda, David Pointcheval
    Abstract:

    In this paper, we revisit the Security of factoring-based signature schemes built via the Fiat-Shamir transform and show that they can admit tighter reductions to certain decisional complexity assumptions such as the quadratic-residuosity, the high-residuosity, and the ϕ ϕ -hiding assumptions. We do so by proving that the underlying identification schemes used in these schemes are a particular case of the lossy identification notion recently introduced by Abdalla et al. at Eurocrypt 2012. Next, we show how to extend these results to the forward-Security Setting based on ideas from the Itkis-Reyzin forward-secure signature scheme. Unlike the original Itkis-Reyzin scheme, our construction can be instantiated under different decisional complexity assumptions and has a much tighter Security reduction. Moreover, we also show that the tighter Security reductions provided by our proof methodology can result in concrete efficiency gains in practice, both in the standard and forward-Security Setting, as long as the use of stronger Security assumptions is deemed acceptable. Finally, we investigate the design of forward-secure signature schemes whose Security reductions are fully tight.

  • Algebraic XOR-RKA-Secure Pseudorandom Functions from Post-Zeroizing Multilinear Maps
    2017
    Co-Authors: Michel Abdalla, Fabrice Benhamouda, Alain Passelègue
    Abstract:

    Due to the vast number of successful related-key attacks against existing block-ciphers, related-key Security has become a common design goal for such primitives. In these attacks, the adversary is not only capable of seeing the output of a function on inputs of its choice, but also on related keys. At Crypto 2010, Bellare and Cash proposed the first construction of a pseudorandom function that could provably withstand such attacks based on standard assumptions. Their construction, as well as several others that appeared more recently, have in common the fact that they only consider linear or polynomial functions of the secret key over complex groups. In reality, however, most related-key attacks have a simpler form, such as the XOR of the key with a known value. To address this problem, we propose the first construction of RKA secure pseudorandom function for XOR relations. Our construction relies on multilinear maps and, hence, can only be seen as a feasibility result. Nevertheless, we remark that it can be instantiated under two of the existing multilinear-map candidates since it does not reveal any encodings of zero. To achieve this goal, we rely on several techniques that were used in the context of program obfuscation, but we also introduce new ones to address challenges that are specific to the related-key-Security Setting.

  • tighter reductions for forward secure signature schemes
    Public Key Cryptography, 2013
    Co-Authors: Michel Abdalla, Fabrice Ben Hamouda, David Pointcheval
    Abstract:

    In this paper, we revisit the Security of factoring-based signature schemes built via the Fiat-Shamir transform and show that they can admit tighter reductions to certain decisional complexity assumptions such as the quadratic-residuosity, the high-residuosity, and the φ-hiding assumptions. We do so by proving that the underlying identification schemes used in these schemes are a particular case of the lossy identification notion recently introduced by Abdalla et al. at Eurocrypt 2012. Next, we show how to extend these results to the forward-Security Setting based on ideas from the Itkis-Reyzin forward-secure signature scheme. Unlike the original Itkis-Reyzin scheme, our construction can be instantiated under different decisional complexity assumptions and has a much tighter Security reduction. Finally, we show that the tighter Security reductions provided by our proof methodology can result in concrete efficiency gains in practice, both in the standard and forward-Security Setting, as long as the use of stronger Security assumptions is deemed acceptable. All of our results hold in the random oracle model.

  • Public Key Cryptography - Tighter Reductions for Forward-Secure Signature Schemes
    Public-Key Cryptography – PKC 2013, 2013
    Co-Authors: Michel Abdalla, Fabrice Ben Hamouda, David Pointcheval
    Abstract:

    In this paper, we revisit the Security of factoring-based signature schemes built via the Fiat-Shamir transform and show that they can admit tighter reductions to certain decisional complexity assumptions such as the quadratic-residuosity, the high-residuosity, and the φ-hiding assumptions. We do so by proving that the underlying identification schemes used in these schemes are a particular case of the lossy identification notion recently introduced by Abdalla et al. at Eurocrypt 2012. Next, we show how to extend these results to the forward-Security Setting based on ideas from the Itkis-Reyzin forward-secure signature scheme. Unlike the original Itkis-Reyzin scheme, our construction can be instantiated under different decisional complexity assumptions and has a much tighter Security reduction. Finally, we show that the tighter Security reductions provided by our proof methodology can result in concrete efficiency gains in practice, both in the standard and forward-Security Setting, as long as the use of stronger Security assumptions is deemed acceptable. All of our results hold in the random oracle model.

Jie Chen - One of the best experts on this subject based on the ideXlab platform.

  • Non-Zero Inner Product Encryption with Short Ciphertexts and Private Keys
    2016
    Co-Authors: Jie Chen, Benoît Libert, Somindu C. Ramanna
    Abstract:

    We describe two constructions of non-zero inner product encryption (NIPE) systems in the public index Setting, both having ciphertexts and secret keys of constant size. Both schemes are obtained by tweaking the Boneh-Gentry-Waters broadcast encryption system (Crypto 2005) and are proved selectively secure without random oracles under previously considered assumptions in groups with a bilinear map. Our first realization builds on prime-order bilinear groups and is proved secure under the Decisional Bilinear Diffie-Hellman Exponent assumption, which is parameterized by the length n of vectors over which the inner product is defined. By moving to composite order bilinear groups, we are able to obtain Security under static subgroup decision assumptions following the Déj a Q framework of Chase and Meiklejohn (Eurocrypt 2014) and its extension by Wee (TCC 2016). Our schemes are the first NIPE systems to achieve such parameters, even in the selective Security Setting. Moreover, they are the first proposals to feature optimally short private keys, which only consist of one group element. Our prime-order-group realization is also the first one with a deterministic key generation mechanism.

  • Non-zero Inner Product Encryption with Short Ciphertexts and Private Keys
    Security and Cryptography for Networks, 2016
    Co-Authors: Jie Chen, Benoît Libert, Somindu C. Ramanna
    Abstract:

    We describe two constructions of non-zero inner product encryption (NIPE) systems in the public index Setting, both having ciphertexts and secret keys of constant size. Both schemes are obtained by tweaking the Boneh-Gentry-Waters broadcast encryption system (Crypto 2005) and are proved selectively secure under previously considered assumptions in groups with a bilinear map. Our first realization builds on prime-order bilinear groups and is proved secure under the Decisional Bilinear Diffie-Hellman Exponent assumption, which is parameterized by the length n of vectors over which the inner product is defined. By moving to composite order bilinear groups, we are able to obtain Security under static subgroup decision assumptions following the Déjà Q framework of Chase and Meiklejohn (Eurocrypt 2014) and its extension by Wee (TCC 2016). Our schemes are the first NIPE systems to achieve such parameters, even in the selective Security Setting. Moreover, they are the first proposals to feature optimally short private keys, which only consist of one group element. Our prime-order-group realization is also the first one with a deterministic key generation mechanism.

Elmar Tischhauser - One of the best experts on this subject based on the ideXlab platform.

  • key alternating ciphers in a provable Setting encryption using a small number of public permutations
    Theory and Application of Cryptographic Techniques, 2012
    Co-Authors: Andrey Bogdanov, Lars R Knudsen, Gregor Leander, Francoisxavier Standaert, John P Steinberger, Elmar Tischhauser
    Abstract:

    This paper considers--for the first time--the concept of key-alternating ciphers in a provable Security Setting. Key-alternating ciphers can be seen as a generalization of a construction proposed by Even and Mansour in 1991. This construction builds a block cipher PX from an n-bit permutation P and two n-bit keys k0 and k1, Setting PX{k0,k1} (x) = k1 ⊕ P(x ⊕ k0). Here we consider a (natural) extension of the Even-Mansour construction with t permutations P1,…,Pt and t+1 keys, k0,…, kt. We demonstrate in a formal model that such a cipher is secure in the sense that an attacker needs to make at least 22n/3 queries to the underlying permutations to be able to distinguish the construction from random. We argue further that the bound is tight for t=2 but there is a gap in the bounds for t>2, which is left as an open and interesting problem. Additionally, in terms of statistical attacks, we show that the distribution of Fourier coefficients for the cipher over all keys is close to ideal. Lastly, we define a practical instance of the construction with t=2 using AES referred to as AES2. Any attack on AES2 with complexity below 285 will have to make use of AES with a fixed known key in a non-black box manner. However, we conjecture its Security is 2128.

  • key alternating ciphers in a provable Setting encryption using a small number of public permutations extended abstract
    International Cryptology Conference, 2012
    Co-Authors: Andrey Bogdanov, Lars R Knudsen, Gregor Leander, Francoisxavier Standaert, John P Steinberger, Elmar Tischhauser
    Abstract:

    This paper considers—for the first time—the concept of key- alternating ciphers in a provable Security Setting. Key-alternating ciphers can be seen as a generalization of a construction proposed by Even and Mansour in 1991. This construction builds a block cipher PX from an n-bit permutation P and two n-bit keys k0 and k1, Setting PXk0,k1 (x )= k1 ⊕ P (x ⊕ k0). Here we consider a (natural) extension of the Even- Mansour construction with t permutations P1,...,Pt and t +1 keys, k0,...,kt. We demonstrate in a formal model that such a cipher is secure in the sense that an attacker needs to make at least 2 2n/3 queries to the underlying permutations to be able to distinguish the construction from random. We argue further that the bound is tight for t = 2 but there is a gap in the bounds for t> 2, which is left as an open and interesting problem. Additionally, in terms of statistical attacks, we show that the distribution of Fourier coefficients for the cipher over all keys is close to ideal. Lastly, we define a practical instance of the construction with t =2 using AES referred to as AES 2 . Any attack on AES 2 with complexity