Cryptology ePrint Archive: Report 2017/040

Practical Non-Malleable Codes from $\ell$-more Extractable Hash Functions

Aggelos Kiayias and Feng-Hao Liu and Yiannis Tselekounis

Abstract: In this work, we significantly improve the efficiency of non-malleable codes in the split state model, by constructing a code with codeword length $|s|+O(k)$, where $|s|$ is the length of the message, and $k$ is the security parameter. This is a substantial improvement over previous constructions, both asymptotically and concretely.

Our construction relies on a new primitive which we define and study, called $\ell$-more extractable hash functions. This notion, which may be of independent interest, is strictly stronger than the previous notion of extractable hash by Goldwasser et al. (Eprint '11) and Bitansky et al. (ITCS '12, Eprint '14), yet we can instantiate it under the same assumption used for the previous extractable hash function (a variant of the Knowledge of Exponent Assumption).

Category / Keywords: Non-malleable codes, hash functions, split-state model

Original Publication (with minor differences): ACM Conference on Computer and Communications Security 2016

Date: received 17 Jan 2017, last revised 19 Jan 2017

Contact author: tselekounis at sians org

Available format(s): PDF | BibTeX Citation

Version: 20170119:163948 (All versions of this report)

Short URL: ia.cr/2017/040

Discussion forum: Show discussion | Start new discussion