CryptoDB
Roman Langrehr
Publications
Year
Venue
Title
2021
TCC
Towards Tight Adaptive Security of Non-Interactive Key Exchange
📺
Abstract
We investigate the quality of security reductions for non-interactive key
exchange (NIKE) schemes. Unlike for many other cryptographic building blocks
(like public-key encryption, signatures, or zero-knowledge proofs), all known
NIKE security reductions to date are non-tight, i.e., lose a factor of at least
the number of users in the system. In that sense, NIKE forms a particularly
elusive target for tight security reductions.
The main technical obstacle in achieving tightly secure NIKE schemes are
adaptive corruptions. Hence, in this work, we explore security notions and
schemes that lie between selective security and fully adaptive security.
Concretely:
- We exhibit a tradeoff between key size and reduction loss.
We show that a tighter reduction can be bought by larger public and secret NIKE
keys. Concretely, we present a simple NIKE scheme with a reduction loss of
O(N^2 log(\nu)/\nu^2), and public and secret keys of O(\nu) group
elements, where N denotes the overall number of users in the system, and
\nu is a freely adjustable scheme parameter.
Our scheme achieves full adaptive security even against multiple "test
queries" (i.e., adversarial challenges), but requires keys of size O(N) to
achieve (almost) tight security under the matrix Diffie-Hellman assumption.
Still, already this simple scheme circumvents existing lower bounds.
- We show that this tradeoff is inherent.
We contrast the security of our simple scheme with a lower bound for all NIKE
schemes in which shared keys can be expressed as an ``inner product in the
exponent''. This result covers the original Diffie-Hellman NIKE scheme, as well
as a large class of its variants, and in particular our simple scheme. Our
lower bound gives a tradeoff between the ``dimension'' of any such scheme
(which directly corresponds to key sizes in existing schemes), and the
reduction quality. For \nu = O(N), this shows our simple scheme and reduction
optimal (up to a logarithmic factor).
- We exhibit a tradeoff between security and key size for tight reductions.
We show that it is possible to circumvent the inherent tradeoff above by
relaxing the desired security notion. Concretely, we consider the natural
notion of semi-adaptive security, where the adversary has to commit to a single
test query after seeing all public keys. As a feasibility result, we bring
forward the first scheme that enjoys compact public keys and tight
semi-adaptive security under the conjunction of the matrix Diffie-Hellman and
learning with errors assumptions.
We believe that our results shed a new light on the role of adaptivity in NIKE
security, and also illustrate the special role of NIKE when it comes to tight
security reductions.
2020
PKC
Hierarchical Identity-Based Encryption with Tight Multi-challenge Security
📺
Abstract
We construct the first hierarchical identity-based encryption (HIBE) scheme with tight adaptive security in the multi-challenge setting, where adversaries are allowed to ask for ciphertexts for multiple adaptively chosen identities. Technically, we develop a novel technique that can tightly introduce randomness into user secret keys for hierarchical identities in the multi-challenge setting, which cannot be easily achieved by the existing techniques for tightly multi-challenge secure IBE. In contrast to the previous constructions, the security of our scheme is independent of the number of user secret key queries and that of challenge ciphertext queries. We prove the tight security of our scheme based on the Matrix Decisional Diffie-Hellman Assumption, which is an abstraction of standard and simple decisional Diffie-Hellman assumptions, such as the k -Linear and SXDH assumptions. Finally, we also extend our ideas to achieve tight chosen-ciphertext security and anonymity, respectively. These security notions for HIBE have not been tightly achieved in the multi-challenge setting before.
2020
ASIACRYPT
Unbounded HIBE with Tight Security
📺
Abstract
We construct the first unbounded hierarchical identity-based encryption (HIBE) scheme with tight security reductions based on standard assumptions. Our main technical contribution is a novel proof strategy that allows us to tightly randomize user secret keys for identities with arbitrary hierarchy depths using low entropy hidden in a small and hierarchy-independent master public key.
The notion of unbounded HIBE is proposed by Lewko and Waters (Eurocrypt 2011). In contrast to most HIBE schemes, an unbounded scheme does not require any maximum depth to be specified in the setup phase, and user secret keys or ciphertexts can be generated for identities of arbitrary depths with hierarchy-independent system parameters.
While all the previous unbounded HIBE schemes have security loss that grows at least linearly in the number of user secret key queries, the security loss of our scheme is only dependent on the security parameter, even in the multi-challenge setting, where an adversary can ask for multiple challenge ciphertexts. We prove the adaptive security of our scheme based on the Matrix Decisional Diffie-Hellman assumption in prime-order pairing groups, which generalizes a family of standard Diffie-Hellman assumptions such as k-Linear.
2020
JOFC
Tightly Secure Hierarchical Identity-Based Encryption
Abstract
We construct the first tightly secure hierarchical identity-based encryption (HIBE) scheme based on standard assumptions, which solves an open problem from Blazy, Kiltz, and Pan (CRYPTO 2014). At the core of our constructions is a novel randomization technique that enables us to randomize user secret keys for identities with flexible length. The security reductions of previous HIBEs lose at least a factor of Q, which is the number of user secret key queries. Different to that, the security loss of our schemes is only dependent on the security parameter. Our schemes are adaptively secure based on the Matrix Diffie-Hellman assumption, which is a generalization of standard Diffie-Hellman assumptions such as k-Linear. We have two tightly secure constructions, one with constant ciphertext size, and the other with tighter security at the cost of linear ciphertext size. Among other things, our schemes imply the first tightly secure identity-based signature scheme by a variant of the Naor transformation.
2019
PKC
Tightly Secure Hierarchical Identity-Based Encryption
Abstract
We construct the first tightly secure hierarchical identity-based encryption (HIBE) scheme based on standard assumptions, which solves an open problem from Blazy, Kiltz, and Pan (CRYPTO 2014). At the core of our constructions is a novel randomization technique that enables us to randomize user secret keys for identities with flexible length.The security reductions of previous HIBEs lose at least a factor of $$ Q $$, which is the number of user secret key queries. Different to that, the security loss of our schemes is only dependent on the security parameter. Our schemes are adaptively secure based on the Matrix Diffie-Hellman assumption, which is a generalization of standard Diffie-Hellman assumptions such as $$k$$-Linear. We have two tightly secure constructions, one with constant ciphertext size, and the other with tighter security at the cost of linear ciphertext size. Among other things, our schemes imply the first tightly secure identity-based signature scheme by a variant of the Naor transformation.
Coauthors
- Julia Hesse (1)
- Dennis Hofheinz (1)
- Lisa Kohl (1)
- Jiaxin Pan (4)