Non-malleable Multiple Public-Key Encryption
Summary :
We study non-malleability of multiple public-key encryption (ME) schemes. The main difference of ME from the threshold public-key encryption schemes is that there is no dealer to share a secret among users; each user can independently choose their own public-keys; and a sender can encrypt a message under ad-hoc multiple public keys of his choice. In this paper we tackle non-malleability of ME. We note that the prior works only consider confidentiality of messages and treat the case that all public keys are chosen by honest users. In the multiple public-key setting, however, some application naturally requires non-malleability of ciphertexts under multiple public keys including malicious users'. Therefore, we study the case and have obtained the following results:
·We present three definitions of non-malleability of ME, simulation-based, comparison-based, and indistinguishability-based ones. These definitions can be seen as an analogue of those of non-malleable public-key encryption (PKE) schemes. Interestingly, our definitions are all equivalent even for the “invalid-allowing” relations. We note that the counterparts of PKE are not equivalent for the relations.
·The previous strongest security notion for ME, “indistinguishability against strong chosen-ciphertext attacks (sMCCA)” [1], does not imply our notion of non-malleability against chosen-plaintext attacks.
·Non-malleability of ME guarantees that the single message indistinguishability-based notion is equivalent to the multiple-message simulation-based notion, which provides designers a fundamental benefit.
·We define new, stronger decryption robustness for ME. A non-malleable ME scheme is meaningful in practice if it also has the decryption robustness.
·We present a constant ciphertext-size ME scheme (meaning that the length of a ciphertext is independent of the number of public-keys) that is secure in our strongest security notion of non-malleability. Indeed, the ciphertext overhead (i.e., the length of a ciphertext minus that of a plaintext) is the combined length of two group elements plus one hash value, regardless of the number of public keys. Then, the length of the partial decryption of one user consists of only two group elements, regardless of the length of the plaintext.
- Publication
- IEICE TRANSACTIONS on Fundamentals Vol.E97-A No.6 pp.1318-1334
- Publication Date
- 2014/06/01
- Publicized
- Online ISSN
- 1745-1337
- DOI
- 10.1587/transfun.E97.A.1318
- Type of Manuscript
- Special Section PAPER (Special Section on Discrete Mathematics and Its Applications)
- Category
Authors
Atsushi FUJIOKA
Kanagawa University
Eiichiro FUJISAKI
NTT Corporation
Keita XAGAWA
NTT Corporation
Keyword
Latest Issue
Copyrights notice of machine-translated contents
The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.
Cite this
Copy
Atsushi FUJIOKA, Eiichiro FUJISAKI, Keita XAGAWA, "Non-malleable Multiple Public-Key Encryption" in IEICE TRANSACTIONS on Fundamentals,
vol. E97-A, no. 6, pp. 1318-1334, June 2014, doi: 10.1587/transfun.E97.A.1318.
Abstract: We study non-malleability of multiple public-key encryption (ME) schemes. The main difference of ME from the threshold public-key encryption schemes is that there is no dealer to share a secret among users; each user can independently choose their own public-keys; and a sender can encrypt a message under ad-hoc multiple public keys of his choice. In this paper we tackle non-malleability of ME. We note that the prior works only consider confidentiality of messages and treat the case that all public keys are chosen by honest users. In the multiple public-key setting, however, some application naturally requires non-malleability of ciphertexts under multiple public keys including malicious users'. Therefore, we study the case and have obtained the following results:
·We present three definitions of non-malleability of ME, simulation-based, comparison-based, and indistinguishability-based ones. These definitions can be seen as an analogue of those of non-malleable public-key encryption (PKE) schemes. Interestingly, our definitions are all equivalent even for the “invalid-allowing” relations. We note that the counterparts of PKE are not equivalent for the relations.
·The previous strongest security notion for ME, “indistinguishability against strong chosen-ciphertext attacks (sMCCA)” [1], does not imply our notion of non-malleability against chosen-plaintext attacks.
·Non-malleability of ME guarantees that the single message indistinguishability-based notion is equivalent to the multiple-message simulation-based notion, which provides designers a fundamental benefit.
·We define new, stronger decryption robustness for ME. A non-malleable ME scheme is meaningful in practice if it also has the decryption robustness.
·We present a constant ciphertext-size ME scheme (meaning that the length of a ciphertext is independent of the number of public-keys) that is secure in our strongest security notion of non-malleability. Indeed, the ciphertext overhead (i.e., the length of a ciphertext minus that of a plaintext) is the combined length of two group elements plus one hash value, regardless of the number of public keys. Then, the length of the partial decryption of one user consists of only two group elements, regardless of the length of the plaintext.
URL: https://global.ieice.org/en_transactions/fundamentals/10.1587/transfun.E97.A.1318/_p
Copy
@ARTICLE{e97-a_6_1318,
author={Atsushi FUJIOKA, Eiichiro FUJISAKI, Keita XAGAWA, },
journal={IEICE TRANSACTIONS on Fundamentals},
title={Non-malleable Multiple Public-Key Encryption},
year={2014},
volume={E97-A},
number={6},
pages={1318-1334},
abstract={We study non-malleability of multiple public-key encryption (ME) schemes. The main difference of ME from the threshold public-key encryption schemes is that there is no dealer to share a secret among users; each user can independently choose their own public-keys; and a sender can encrypt a message under ad-hoc multiple public keys of his choice. In this paper we tackle non-malleability of ME. We note that the prior works only consider confidentiality of messages and treat the case that all public keys are chosen by honest users. In the multiple public-key setting, however, some application naturally requires non-malleability of ciphertexts under multiple public keys including malicious users'. Therefore, we study the case and have obtained the following results:
·We present three definitions of non-malleability of ME, simulation-based, comparison-based, and indistinguishability-based ones. These definitions can be seen as an analogue of those of non-malleable public-key encryption (PKE) schemes. Interestingly, our definitions are all equivalent even for the “invalid-allowing” relations. We note that the counterparts of PKE are not equivalent for the relations.
·The previous strongest security notion for ME, “indistinguishability against strong chosen-ciphertext attacks (sMCCA)” [1], does not imply our notion of non-malleability against chosen-plaintext attacks.
·Non-malleability of ME guarantees that the single message indistinguishability-based notion is equivalent to the multiple-message simulation-based notion, which provides designers a fundamental benefit.
·We define new, stronger decryption robustness for ME. A non-malleable ME scheme is meaningful in practice if it also has the decryption robustness.
·We present a constant ciphertext-size ME scheme (meaning that the length of a ciphertext is independent of the number of public-keys) that is secure in our strongest security notion of non-malleability. Indeed, the ciphertext overhead (i.e., the length of a ciphertext minus that of a plaintext) is the combined length of two group elements plus one hash value, regardless of the number of public keys. Then, the length of the partial decryption of one user consists of only two group elements, regardless of the length of the plaintext.},
keywords={},
doi={10.1587/transfun.E97.A.1318},
ISSN={1745-1337},
month={June},}
Copy
TY - JOUR
TI - Non-malleable Multiple Public-Key Encryption
T2 - IEICE TRANSACTIONS on Fundamentals
SP - 1318
EP - 1334
AU - Atsushi FUJIOKA
AU - Eiichiro FUJISAKI
AU - Keita XAGAWA
PY - 2014
DO - 10.1587/transfun.E97.A.1318
JO - IEICE TRANSACTIONS on Fundamentals
SN - 1745-1337
VL - E97-A
IS - 6
JA - IEICE TRANSACTIONS on Fundamentals
Y1 - June 2014
AB - We study non-malleability of multiple public-key encryption (ME) schemes. The main difference of ME from the threshold public-key encryption schemes is that there is no dealer to share a secret among users; each user can independently choose their own public-keys; and a sender can encrypt a message under ad-hoc multiple public keys of his choice. In this paper we tackle non-malleability of ME. We note that the prior works only consider confidentiality of messages and treat the case that all public keys are chosen by honest users. In the multiple public-key setting, however, some application naturally requires non-malleability of ciphertexts under multiple public keys including malicious users'. Therefore, we study the case and have obtained the following results:
·We present three definitions of non-malleability of ME, simulation-based, comparison-based, and indistinguishability-based ones. These definitions can be seen as an analogue of those of non-malleable public-key encryption (PKE) schemes. Interestingly, our definitions are all equivalent even for the “invalid-allowing” relations. We note that the counterparts of PKE are not equivalent for the relations.
·The previous strongest security notion for ME, “indistinguishability against strong chosen-ciphertext attacks (sMCCA)” [1], does not imply our notion of non-malleability against chosen-plaintext attacks.
·Non-malleability of ME guarantees that the single message indistinguishability-based notion is equivalent to the multiple-message simulation-based notion, which provides designers a fundamental benefit.
·We define new, stronger decryption robustness for ME. A non-malleable ME scheme is meaningful in practice if it also has the decryption robustness.
·We present a constant ciphertext-size ME scheme (meaning that the length of a ciphertext is independent of the number of public-keys) that is secure in our strongest security notion of non-malleability. Indeed, the ciphertext overhead (i.e., the length of a ciphertext minus that of a plaintext) is the combined length of two group elements plus one hash value, regardless of the number of public keys. Then, the length of the partial decryption of one user consists of only two group elements, regardless of the length of the plaintext.
ER -
English
