Computing Reviews
Today's Issue Hot Topics Search Browse Recommended My Account Log In
Review Help
Search
Black-box construction of a more than non-malleable CCA1 encryption scheme from plaintext awareness
Myers S., Sergi M., shelat a. Journal of Computer Security21 (5):721-748,2013.Type:Article
Date Reviewed: Oct 6 2014

Ways to construct cryptographic schemes to protect against malicious attackers have received a great deal of attention in the area of formally provable security, in both academia and industry. It is very difficult to define new formal security models and constructs for the corresponding secure schemes. The research method and technical route proposed in the paper provide a good reference that deserves to be studied further.

Myers et al. contribute to the provable security field. First, they pay attention to the open problem of whether a non-malleable chosen-ciphertext attack (NM-CCA1) encryption scheme can be constructed from a chosen-ciphertext (CCA1) encryption scheme. Particularly, the authors show that an NM-CCA1 encryption scheme can be achieved from a subset of CCA1 encryption schemes, which are also plaintext aware under multiple keys and weak simulatability. Since it was uncertain whether a CCA1 scheme could be used to construct an NM-CCA1 scheme before the publication of this paper, the work seems to be innovative. In fact, plaintext awareness is a very strong property. Any cryptosystem that is chosen plaintext attack (CPA) and plaintext aware is actually secure against a CCA1 attack. Moreover, the authors prove that the weak simulatability requirement implies CPA security, and hence all results follow from any scheme that is weakly simulatable and plaintext aware. So, the first contribution lies in the first black-box construction of a non-malleable CCA1 encryption scheme in the standard model from a weaker encryption primitive against a CCA1 attack.

Second, cNM-CCA1, as a generalization of NM-CCA1, is first defined in this paper, in which an NM-CCA1 adversary is allowed to ask c >=1 number of parallel queries after receiving the challenge ciphertext. More importantly, we can see that cNM-CCA1 is a stronger security notion than NM-CCA1, but does not satisfy CCA2 security, which is an intermediate security notion that helps us to understand the relationship between CCA1 and CCA2. Since the NM-CCA1 can be regarded as the special case of cNM-CCA1 when c=1, the authors strengthened the definition and implementation of cNM-CCA1.

In order to attain the above goals, the main technique involves the nested encryption construction, which includes nuclear inner-layer encryption along with multiple-key outer-layer encryptions. The independent outer-layer encryptions make it more difficult for adversaries to succeed in attack games. Based on the idea, the authors introduce a one-time signature in the construction of cNM-CCA1. From my perspective, the final encryption is formed through being signed by a one-time signature key that should also be an important factor in achieving the non-malleable property. Due to the application of the nested construction, another technical point is how to prove that a weaker security notion (such as sPAl) implies a stronger notion (such as sPAl+). It is necessary to make use of the weak simulatability in order to overcome the technique’s difficulty. The background for understanding the whole paper is highly demanding, especially in the multiple-level theoretic structure. In my opinion, the difference among NM-CCA1, cNM-CCA1, and CCA1 still needs to be stated clearly.

In conclusion, the authors answered some open questions related to the relationship between different security definitions in the area of formally provable security. Particularly, the paper addresses in detail how to construct an NM-CCA1 encryption scheme from CCA1, which will advance the development of provable security theory.

Reviewer:  Zheng Gong Review #: CR142792 (1501-0073)
Bookmark and Share
 
Public Key Cryptosystems (E.3 ... )
 
Would you recommend this review?
yes
no
Other reviews under "Public Key Cryptosystems": Date
Direct demonstration of the power to break public-key cryptosystems
Koyama K.  Advances in cryptology (, Sydney, Australia, Jan 8-11, 1990)211990. Type: Proceedings
Sep 1 1991
Public-key cryptography
Salomaa A., Springer-Verlag New York, Inc., New York, NY, 1990. Type: Book (9783540528319)
Feb 1 1992
Computation of discrete logarithms in prime fields
LaMacchia B., Odlyzko A. Designs, Codes and Cryptography 1(1): 47-62, 1991. Type: Article
Apr 1 1992
more...

E-Mail This Printer-Friendly
Send Your Comments
Contact Us
Reproduction in whole or in part without permission is prohibited.   Copyright 1999-2024 ThinkLoud®
Terms of Use
| Privacy Policy