436 H. Qiu, K. Kapusta and Z. Lu et al. / Information Sciences 502 (2019) 434–445
Table 1
Major notations used in this paper and their definitions.
Notation Definition
D Input data
D
Set of protected data fragments
K Key used for encryption algorithms
D
i
i-th element fragmented from D
F AON data protection function
Fig. 1. The AON data protection schemes can protect, fragment, and then disperse the data.
list the main challenges for the AON data protection schemes and present the perspectives. In Section 6 we discuss and
provide with research perspectives; then, we conclude our work in Section 7 .
2. Basic concepts and designs for AON data protection
In this section, we introduce the basic concept for the traditional AON data protection schemes. First, we present the
historical categories of AON according to Rivest [37] . Then we illustrate the evolving and development of recent trends of
AON. Also we extend the concept based on the developed techniques in different use cases by introducing the definitions of
lightweight AON and full AON data protection schemes. The notations of the definitions are given in Table 1 .
2.1. Definitions
An AON data protection scheme mainly aims at protecting encrypted data against the exposure of the encryption key. It
creates dependencies inside the ciphertext in a way that its partial decryption is infeasible. Therefore, once the ciphertext is
being fragmented and dispersed, encrypted data contained inside the fragments are protected against the key exposure.
Historical AON processing is composed of two steps: an AONT pre-processing applied before data encryption and a sec-
ond step including the proper encryption. The whole two steps process is denoted in the literature as AON data protection
as shown in Fig. 1 . The majority of recent all-or-nothing schemes operates differently. Also, as shown in Fig. 1 , they are
first encrypting the data and then applying a transform over it to create dependencies [21] in order to avoid the data re-
encryption.
Normally, as shown in Fig. 1 , a fragmentation operation is combined with the AON data protection schemes to further
disperse the fragments to different storage locations for enhancing the protection level. Assume for the fragmentation step,
input data D is transformed into N fragments { D
1
, . . . , D
N
} that are later dispersed over several different physical locations
over i.e. multiple physically separated storage servers inside of a data center or several independent storage providers.
There are two main categories of fragmentation schemes. The first one is to fragment the data D in the process of
protection into a sequence of fragments with equal confidentiality. In this case, for an attacker, there is no priority to acquire
which specific subsets of fragments. Once the correct key is leaked, the data reconstruction is only possible when a threshold
of n ( n ≤ N ) of the fragments have been gathered. The other category of AON data protection is to fragment the data D in
the process of protection into several subsets of fragments with different confidentiality levels. Then different protection
methods will be applied to those subsets of data according to their confidentiality levels. Thus, once the key is leaked,
collecting the subsets of data fragments with high confidentiality levels will be more vital for data reconstruction while the
subsets of data fragments with low confidentiality levels are rather less possible for reconstructing the initial data content.
2.2. Lightweight AON data protection
Traditional encryption algorithms like the standard symmetric encryption algorithms (e.g. AES) work with the assumption
that data are sequences of symbols relatively independent (i.i.d.) or even importance, and that the data must be decrypted
with accuracy. This typically does not apply to most of the personal multimedia data that are images, audio, and videos: the
spatial or temporal redundancies of these multimedia data are not sufficiently exploited by historical encryption methods.