Fine-Grained Non-Interactive Key-Exchange without Idealized Assumptions, and Lower Bounds

Yuyu Wang; Chuanjie Su; Jiaxin Pan; Chunxiang Xu

Paper 2024/1784

Fine-Grained Non-Interactive Key-Exchange without Idealized Assumptions, and Lower Bounds

Yuyu Wang

, University of Electronic Science and Technology of China

Chuanjie Su

, University of Electronic Science and Technology of China

Jiaxin Pan

, University of Kassel

Chunxiang Xu

, University of Electronic Science and Technology of China

Abstract

In this paper, we study multi-party non-interactive key exchange (NIKE) in the fine-grained setting. More precisely, we propose three multi-party NIKE schemes in three computation models, namely, the bounded parallel-time, bounded time, and bounded storage models. Their security is based on a very mild assumption (e.g., NC1 ⊊ ⊕L/poly) or even without any complexity assumption. This improves the recent work of Afshar, Couteau, Mahmoody, and Sadeghi (EUROCRYPT 2023) that requires idealized assumptions, such as random oracles or generic groups. Additionally, we show that all our constructions satisfy a natural desirable property that we refer to as extendability, and we give generic transformations from extendable multi-party NIKE to multi-party identity-based NIKEs in the fine-grained settings. Furthermore, we generalize the lower bound on users’ storage consumption in the bounded storage model by Dziembowski and Maurer (Eurocrypt 2004) to encompass any multi-party NIKE with extendability. This new lower bound suggests that the users’ storage consumption of our multi-party NIKE in the bounded storage model is optimal.

Metadata

Available format(s): PDF
Category: Public-key cryptography
Publication info: A major revision of an IACR publication in CRYPTO 2024
Keywords: Multi-party non-interactive key exchange fine-grained cryptography identity-based cryptography.
Contact author(s): wangyuyu @ uestc edu cn
chuanjie su @ hotmail com
jiaxin pan @ uni-kassel de
chxxu @ uestc edu cn
History: 2024-11-19: revised; 2024-11-01: received; See all versions
Short URL: https://ia.cr/2024/1784
License: CC BY

BibTeX

@misc{cryptoeprint:2024/1784,
      author = {Yuyu Wang and Chuanjie Su and Jiaxin Pan and Chunxiang Xu},
      title = {Fine-Grained Non-Interactive Key-Exchange without Idealized Assumptions, and Lower Bounds},
      howpublished = {Cryptology {ePrint} Archive, Paper 2024/1784},
      year = {2024},
      url = {https://eprint.iacr.org/2024/1784}
}