Daniel Slamanig
email: d.slamanig@cuas.at

Stefan Rass
email: stefan.rass@syssec.at

Generalizations and Extensions of Redactable Signatures with Applications to Electronic Healthcare

Redactable signatures allow for altering signed documents, retaining the validity of the signature without interaction with the original signer. In their plain form, such schemes are designed for documents having an unspecific structure, i.e. documents are simply considered as binary strings. In this work, we generalize the concept of redactable signatures towards documents that inherently provide a structure and investigate the security of our construction. Furthermore, we present extensions to our scheme, adding features not commonly provided by other redactable signature schemes. Additionally, various applications in healthcare are discussed, supporting the applicability and usability of our construction.

Introduction

A standard digital signature links an identity to a document and thereby provides an authentication mechanism, as well as integrity assurance. Consequently, no alteration of a signed document is possible once the signature has been attached. However, there are scenarios where it would be valuable to have the possibility to replace or remove (specified) parts of a message after signature creation such that the original signature stays valid. Such signatures are called redactable (we remark that the naming is not consistent throughout the literature). An example application is the anonymization (removal of identifying information) of medical documents or general XML-documents.

Redactable signature schemes were independently introduced by Steinfeld et al. [START_REF] Steinfeld | Content Extraction Signatures[END_REF] and Johnson et al. [START_REF] Johnson | Homomorphic Signature Schemes[END_REF] in 2001 and 2002 respectively. Loosely spoken, such signature schemes are constructed from standard signature schemes using the hash-then-sign paradigm by virtue of modifying the construction of the hash value. Merkle-trees [START_REF] Merkle | A Certified Digital Signature[END_REF] are a convenient tool for that matter: if a message is hashed via a Merkle-tree, then a message part at a leaf of that tree can be redacted by replacing it with an empty-symbol in the message, along with the hash-value of the (now missing) message part. For signature verification, the remaining hash-tree can be constructed as usual, thus creating a signature with redaction capabilities. One such scheme is described in section 4. Contribution: The contributions of this paper are manifold: while standard redactable signatures are applicable to documents providing no specific structure, i.e. which are simply interpreted as binary strings, and organized as leafs of binary trees, we generalize the whole concept towards documents providing an inherent structure. We present efficient constructions with provable security and present various extensions, adding valuable features to the given construction.

Applications in Electronic Healthcare

Although there are several different applications of signature schemes supporting redaction, we will focus on their application in electronic healthcare (eHealth) here and thus briefly motivate the field and their potential benefits.

In recent years eHealth and ubiquitous healthcare have gained significant attention in the scientific community as well as among practitioners, since these concepts hold great potential to improve medical treatment processes. In order to guarantee an adequate quality of data, it is important that authenticity and integrity of involved data can be checked at any time. Hence, digital signatures seem to be an invaluable tool for that matter. Redacting parts of documents after signing while preserving the signature validity can be valuable, when information of a medical document needs to be removed (e.g. the document is anonymized). This spares the need to contact the original signer to re-create the signature and enables more time-efficient medical processes with guaranteed signature validity. More importantly, source-authenticity of the original data source is ensured. Achieving k-Anonymity: Person related health data are in general very sensitive information and consequently must be protected appropriately. Especially, when using these data for secondary use, which includes medical research, clinical studies and second opinions, the protection of the privacy of patients is obligatory. Hence, it is necessary to prepare data such that the patients cannot be identified uniquely anymore, before passing it to another party for secondary use. This process of preparation focuses primarily on attributes that directly identify the patients and secondarily on attributes that indirectly identify the patients. Redactable signatures allow for removing certain identifying attributes in order to anonymize a document whilst retaining its authenticity. Suppose that a combination of non-identifying attributes uniquely identifies an individual (a study [START_REF] Golle | Revisiting the Uniqueness of Simple Demographics in the US Population[END_REF] from the year 2000 estimated that 63% of the population of the United States can be uniquely identified based only on gender, date of birth, and 5-digit zip code). Assume that upon removing a subset of those attributes (suppression), identification becomes ambiguous, meaning that these attributes can equally well be related to k different individuals. The same effect could be achieved by replacing the attribute values by more general ones (such as telling only the first 2 digits of a ZIP-code for instance) This process is called generalization (see [START_REF] Ciriani | Theory of Privacy and Anonymity[END_REF] for details). Either way, we get k-anonymity of the individual, as introduced in [START_REF] Samarati | Protecting Respondents' Identities in Microdata Release[END_REF][START_REF] Sweeney | k-Anonymity: a Model for Protecting Privacy[END_REF]. Removing or replacing attributes to achieve k-anonymity is a natural application of redactable signatures. We revisit this in section 6. Privacy Preserving and Unbiased Second Opinions: Redacting certain parts of an authentic (signed) medical document may as well be desirable if second opinions for some medical problem are sought. Either a medical expert or the patient could call for anonymity of the patient (privacy), or could redact certain parts of the medical document to make sure that the other expert remains unbiased by otherwise visible information, e.g. the diagnosis, while having authentic access to relevant information, e.g. anamnesis, lab-results, etc.

Related Work

Signature Schemes: Sanitizable signatures [START_REF] Brzuska | Security of Sanitizable Signatures Revisited[END_REF][START_REF] Ateniese | Sanitizable Signatures[END_REF] permit a designated party (sanitizer ) to remove or replace desginated parts of a document. The signer can exactly mark parts as (not) redactable. However, the signer cannot specify how this redaction may look like, i.e. the redactor can replace a redactable part with an arbitrary string. The redaction capability is achieved by computing chameleon hashes (trapdoor commitments) for all the parts of a message that can be redacted. Only the sanitizer, in possession of the trapdoor information, is able to compute collisions for the chameleon hashes and hence can change the respective parts of the message arbitrarily. Nevertheless, for a verifier it is not noticeable whether the original message has been modified. The concept of sanitizable signatures was further extended to trapdoor sanitizable signatures in [START_REF] Canard | Trapdoor Sanitizable Signatures and Their Application to Content Protection[END_REF], which allow to give the power of sanitization to possibly several entities. Recently, there have also been proposed some extensions that restrict the choice of replaced strings [START_REF] Klonowski | Extended Sanitizable Signatures[END_REF], which seems to be very important and is also discussed in this paper in the context of redactable signatures.

In content extraction signatures [START_REF] Steinfeld | Content Extraction Signatures[END_REF], which, besides other constructions, use a hash-tree based scheme similar to redactable signatures, everybody can remove substrings. Furthermore, the parts that can be removed can be specified by means of a policy named content extraction access structure. This policy, which specifies the set of indices of redactable document parts, is signed along with the message and needs to be evaluated by the signature verification algorithm. If any redaction has taken place that is not specified in the policy, the signature validation algorithm rejects the signature.

A straightforward approach to redactable signatures is by splitting the document into pieces, each of which is signed separately. This makes removing a part simple but computationally expensive and not very flexible. An efficient construction is possible by using the pairing-based signature of [START_REF] Boneh | Aggregate and Verifiably Encrypted Signatures from Bilinear Maps[END_REF], which saves bandwidth by aggregating all single signatures into one signature. However, all signatures corresponding to message parts that can be redacted need to be available to the redactor in addition. Using this construction, it is possible to remove blocks from the document and to remove the corresponding signatures from the aggregated signature without the verifier being able to realize whether the message has been redacted or not (invisible redaction) [START_REF] Miyazaki | Digitally Signed Document Sanitizing Scheme Based on Bilinear Maps[END_REF]. This concept was recently extended to also provide non-invisible redaction [START_REF] Izu | Yet Another Sanitizable Signature from Bilinear Maps[END_REF], which can also be achieved for the aforementioned construction by including indexes into the single message parts. Another scheme, based on aggregating single signatures using batch RSA signatures, was introduced in [START_REF] Steinfeld | Content Extraction Signatures[END_REF] (prior to the aforementioned schemes). Although, their scheme also requires a number of RSA signatures that is linear in the number of message blocks, once a redaction has taken place, solely a single RSA signature (as the product of single signatures) needs to be transmitted to the verifier.

Furthermore, [START_REF] Haber | Efficient Signature Schemes Supporting Redaction, Pseudonymization, and Data Deidentification[END_REF] have recently extended the approach of [START_REF] Johnson | Homomorphic Signature Schemes[END_REF], such that a signer can specify which parts of a document are allowed to be redacted. Their approach is similar to the one of [START_REF] Steinfeld | Content Extraction Signatures[END_REF]. Another approach by [START_REF] Chang | Short Redactable Signatures Using Random Trees[END_REF] extends the treebased construction of [START_REF] Johnson | Homomorphic Signature Schemes[END_REF] such that the length of the redacted strings can be hidden. Finally, [START_REF] Nojima | A Storage Efficient Redactable Signature in the Standard Model[END_REF] have proposed a redactable signature scheme that does not rely on random oracles and is provably secure in the standard model. Medical Applications: Ateniese et al. [START_REF] Ateniese | Sanitizable Signatures[END_REF] mention alongside that sanitizable signatures can accommodate different level of data de-identification, supporting the "minimum necessary" disclosure standard of HIPAA Privacy Rule, but do not consider further details. The authors of [START_REF] Bauer | Redactable Signatures on Data with Dependencies and their Application to Personal Health Records[END_REF] have recently proposed a concept to apply redactable signatures in context of Personal Health Records (PHRs) to realize minimum disclosure of personal information and to achieve cryptographic enforcement of dependencies between parts containing personal information. Another recent work developed independently from ours by Haber et al. [START_REF] Haber | Efficient Signature Schemes Supporting Redaction, Pseudonymization, and Data Deidentification[END_REF] can be considered as closest to the ideas presented in this paper. They present redactable signatures that can be used for pseudonymization and de-identification of data, although they mainly focus on relational, i.e. 2-dimensional, data tables. In contrast, our work focuses on applying the aforementioned and additional mechanisms on structured documents.

Redactable Signatures

As mentioned in the introduction, redactable signatures permit removing parts of a signed document whilst retaining the validity of the signature. Technically, this amounts to an efficient update of the signature that requires no interaction with the original signer. Our proposed scheme will build upon the scheme of Johnson et al. [START_REF] Johnson | Homomorphic Signature Schemes[END_REF], which we will briefly describe. We assume the reader to be familiar with the concept of a (binary) Merkle-tree, as this is used extensively in the following. The second core ingredient for our construction are pseudorandom generators (PRGs) based on GGM-trees [START_REF] Goldreich | How to Construct Random Functions[END_REF].

Johnson-Molnar-Song-Wagner Redactable Signature Scheme: To construct a redactable signature for a document D, the authors of [START_REF] Johnson | Homomorphic Signature Schemes[END_REF] divide the

document into N = |D| n blocks of size n, so that D = D[1], . . . , D[N ].
Next, they build a complete binary tree with N leafs, having the message blocks assigned to them in the correct order. Consequently, one is able to build the hash of the root node h R of the tree by hashing up the tree from the bottom (i.e. simply construct a Merkle-tree) and sign h R by using a conventional signature scheme, i.e. set σ = S SK (h R ).

To remove the i-th block, which can be seen as a replacement with the empty symbol ⊥, one may pass the document

D ′ = D[1], . . . , D[i -1], ⊥, D[i + 1], . . . , D[N ] to a verifier, along with the hash value h D[i] = H(D[i]) of the re- moved message block (leaf) D[i].
The missing message block causes no problem in reconstructing the Merkle-tree, because its hash-value is still available. The updated signature is simply σ ′ = (σ, h D[i] ), where σ is the original signature. One problem instantly arises if the block size is too small to prevent brute-force determination of the missing part D[i]. Therefore, a GGM-tree with its shape identical to the Merkle-tree is used to generate randomizers that are attached to each intermediate value (or message block) prior to hashing it. Technically, one generates a randomizer r vi for every node v i of the tree by means of a GGM-tree, starting with a randomly chosen seed r v R at the root node v R . Instead of solely hashing the values (message parts denoted as x), as within the Merkle-tree, the subsequent rules (1) are applied.

φ(p) =      H(φ(c l )||φ(c r )) if p has two children, H(φ(c l )) if p has one child, H(r p ||x) if p is a leaf. (1)
Intuitively, the values of the leafs are hashed along with a randomizer, which allows to hide the values of removed parts of the document. Technically, this can also be seen as a commitment to a message part, such that the commitment hides the message part as long as the randomizer is unknown, i.e. the hiding of redacted message parts is based on the hiding property of the used commitment scheme. It must be mentioned, that one may also use other commitment schemes. However, commitments based on hash functions [START_REF] Halevi | Practical and Provably-Secure Commitment Schemes from Collision-Free Hashing[END_REF] are usually much more efficient.

In order to be able to build the Merkle-tree to verify the signature for document D, besides the standard signature, the updated signature needs to additionally include the seed of the GGM-tree, i.e. σ RS = (σ, r v R ). The signature verification is straightforward by constructing the GGM-tree by means of the seed r v R , building the Merkle-tree from the document and verifying the standard signature σ of the hash of the root node. In order to redact block i from D, one deletes the block from D as already mentioned above and updates the signature to be σ

′ RS = (σ, h D[i] , A v D[i]
) and additionally includes the indices of the redacted parts (which is omitted here). Thereby, the signature contains the randomized hash of the leaf, which does not reveal any information on the removed part and the authentication path A v D[i] that contains the set of randomizers, which is necessary to reconstruct the remaining part of the GGM-tree. But, the computation of the randomizer r v D[i] for the removed part D[i] is impossible, as long as the used PRG is secure. For notational convenience, we will subsequently denote the set of hash values (commitments) that result from redacted document parts as C and the set of randomizers (in the respective authentication paths) as R. In the example discussed before, our updated signature will be

σ ′ RS = (σ, C, R), where C = {h D[i] } and R = A v D[i] .
Redactable signatures [START_REF] Johnson | Homomorphic Signature Schemes[END_REF] organize the content of an (unstructured) document as leafs of a complete binary tree. For XML documents, however, one can beneficially (cf. section 6) exploit the XML-induced N -ary tree structure to avoid cumbersome assignments to a binary tree not resembling the natural structure of the document. For instance, one can construct subtrees from the respective XML-attributes and values.

Construction

Generalized redactable signatures are obtained by replacing the binary tree construction with a general tree construction. While a Merkle-tree can be defined using general trees rather than binary trees (see equation ( 2)), the generalization is less obvious for the GGM-tree. This one, in particular the proof of security regarding the outputs, hinges on the binary tree construction.

Our construction that enjoys provable security (since the security is implied by the standard GGM-tree construction) can be described as follows: Suppose we have a tree T , and let v denote an inner node with label r v and N > 2 children. For every child c, we seek to derive a randomizer r c (to be used in equation ( 2)) from v's label r v , such that the children's labels (randomizer) do not provide any information about each other. For the leaves of a (binary) GGM-tree, this has been proven (see [START_REF] Goldreich | How to Construct Random Functions[END_REF]). The idea is to simply construct an auxiliary GGM-tree with root v, and (at least) N leafs resembling the children of v. The so-constructed randomizers r for the children of v will enjoy the desired properties, because the leafs of GGM-trees do. Such an auxiliary GGM-tree can be constructed for each inner node of the (general) tree T . The arising additional costs can be considered negligible, since many standard GGM-tree implementations are extremely efficient.

Taking the construction in section 4 as a template, we will devise our scheme for generalized redactable signatures on arbitrary documents D being represented as an N -ary tree. Thereby, we assume that we have already applied a transformation to a document D and for simplicity we will denote a document and its parts as D = D[1], . . . , D[n], whereas we assume that this is a representation of a N -ary tree. The assignment φ for the labels of the nodes of the modified Merkle-tree is adapted to (2), with randomizers r p created using the generalized GGM-tree construction outlined above. Note, that now also inner nodes hold parts of messages (denoted as x). Note that C(m, r) represents a commitment to message m using randomizer r, e.g. using hash functions [START_REF] Halevi | Practical and Provably-Secure Commitment Schemes from Collision-Free Hashing[END_REF].

φ(p) =      H(x||φ(c 0 )|| . . . ||φ(c k ))
if p = root and has k+1 children, C((x, φ(c 0 ), . . . , φ(c k )), r p ) if p = root and has k+1 children, C(x, r p ) if p is a leaf.

(2)

Basically, the computation of the commitments of leave nodes is identical to the Merkle-tree construction and the remaining computations are adapted to N -ary trees. A generalized redactable signature consists of the signed root value φ(p) where p is root and the seed r v R of the root node. More precisely, the signature σ ′ = (σ, C, R), where σ is the signature for φ(p), C = ∅ and R = {r v R }. When redacting a message part, we preceded as in section 4 and if the redacted node is an inner node, the randomizers of all child nodes need to be included.

Security of Generalized Redactable Signatures

Essentially, the security of generalized redactable signatures has to satisfy two properties, namely unforgeability and hiding. Hiding refers to the adversary's inability to reconstruct redacted parts of the document. Unforgeability is more involved and requires some definitions [START_REF] Johnson | Homomorphic Signature Schemes[END_REF][START_REF] Haber | Efficient Signature Schemes Supporting Redaction, Pseudonymization, and Data Deidentification[END_REF]: given a document

D = D[1], . . . , D[n] composed of n blocks, a redacted document is D ′ = D ′ [1], . . . , D ′ [n] with D ′ [i] ∈ {D[i],
⊥} for all i = 1, 2, . . . , n. The more blocks are redacted, the less related the document becomes to its original parent. This is formally modeled through a partial order relation:

Definition 1 Let D = D[1], . . . , D[n] and D ′ = D ′ [1], . . . , D ′ [n]
be two (possibly) redacted versions of a document D. We define a partial order ≺ on redacted documents such that D ≺ D ′ holds if and only if the following properties are satisfied for all 1 ≤ i ≤ n:

1. if D[i] = ⊥, then D ′ [i] = ⊥. 2. if D[i] = ⊥, then either D ′ [i] = D[i] or D ′ [i] = ⊥.
Roughly speaking, unforgeability prevents the adversary from finding a signature for a document D such that D ′ ≺ D for a given and signed document D ′ . In contrast to security definitions of standard signature schemes [START_REF] Goldwasser | A Digital Signature Scheme Secure Against Adaptive Chosen-Message Attacks[END_REF], we are not focusing on existential unforgeability against chosen message attacks (eUF-CMA). Recall that in the game based proof for eUF-CMA security, an adversary can issue signature queries for adaptively chosen messages of his choice, and finally needs to output a valid signature for a message that has not been issued to the sign oracle during the game. But we will base the security on a game capturing the aforementioned unforgeability and hiding properties at the same time and furthermore relate the signature forgery to a redacted document of the adversary's choice. Nevertheless, is should be noted that we require the standard signature scheme used to sign the root of the modified Merkle-tree to provide eUF-CMA security. Thereby, our game is based on the security model of [START_REF] Haber | Efficient Signature Schemes Supporting Redaction, Pseudonymization, and Data Deidentification[END_REF]. Basically, an adversary who manages to win this game with non-negligible probability, will be able to breach the security of some of the used cryptographic primitives with non-negligible probability. Our definition of secure generalized redactable signature schemes follows the same ideas and is as well based on a game in the aforementioned sense.

Definition 2 A generalized redactable signature scheme is said to be secure, if no probabilistic polynomial-time adversary has a non-negligible advantage against the challenger in game 5.2.

Game 5.2

The following oracles are available to the adversary:

1. commit: A commit query is defined as issuing a document D to the oracle, which chooses a random seed r v R , derives randomizers for all nodes of the N -ary tree (assume that the tree has n nodes), computes the commitments h vi , 1 ≤ i ≤ n, for all nodes and returns the tuple (r 1 , . . . , r n , h v1 , . . . , h vn ). 2. sign: A sign query is defined as issuing the hash value of the root node h v R to the oracle, which uses the private-key SK of a eUF-CMA secure digital signature scheme, computes a signature σ = S SK (h v R ) and returns σ. 3. redact: A redact query is defined as issuing a generalized redactable signature σ GRS , a document D and a set of indices (which defines the document parts to be redacted) to the oracle, which computes the redaction and returns the redacted document D ′ along with an adapted generalized redactable signature σ ′ GRS . The adversary plays the following game for breaking the signature scheme: Setup: The challenger takes a security parameter, chooses a secure digital signature scheme, generates a key-pair (SK, P K) for this scheme, chooses a cryptographic hash function H as well as a commitment scheme C for the tree computation and chooses a PRG G to generate the randomizers, gives (P K, H, C, G) and the signature scheme description to the adversary and keeps SK secret. Phase 1: The adversary issues queries q 1 , . . . , q m , where q i ∈ {commit, sign, redact} and these queries may be asked adaptively, that is, each query q i may depend on the replies to q 1 , . . . , q i-1 . Challenge: The adversary may want to attack the hiding property (figure out redacted parts of the document) by providing two documents D 0 and D 1 of equal length along with a list of parts to be redacted to the challenger, which differ in exactly one document part, i.e. for exactly one i it holds that D 0

[i] = D 1 [i].
The challenger chooses a random bit b, produces a generalized redactable signature for D b and redacts the document (the i'th document part must be redacted). Phase 2: The adversary issues additional queries q m+1 , . . . , q n where query q i ∈ {commit, sign, redact} and these queries may be asked adaptively. Thereby, the adversary is not allowed to ask any sign or redact queries for any D b ≺ D. Guess: The adversary outputs a guess for either attacking the hiding or the unforgeability property. Hiding: The adversary outputs a bit b ′ and wins the game if b = b ′ holds. The adversary's advantage is defined as

|Pr[b = b ′ ] -1 2 |. Unforgeability:
The adversary outputs a generalized redactable signature σ ′ = (σ, C, R) for a document D, whereas no sign or redact query has been issued to any document D ′ such that D ≺ D ′ or D b ≺ D ′ . The adversary's advantage is defined as the probability that the verification of the signature succeeds when the two aforementioned conditions hold.

Theorem 1 (proof appears in appendix A). If the signature schemes provides eUF-CMA security, H is a collision-resistant cryptographic hash function, C a secure commitment scheme and G a secure PRG, then the generalized redactable signature scheme is a secure one.

In this section we present extensions to realize controlled replacement and finegrained redaction. Redactable signatures in the sense above allow for "deleting" parts of the document by replacing them with the empty symbol ⊥. However, it might be interesting for the signer to specify a set of permitted replacements for certain parts of the document. An authentic (signed) questionnaire would be an example of such a scenario. Sanitizable signatures permit replacements of designated parts by designated redactors, who are free to substitute any string they like. Recently, [START_REF] Klonowski | Extended Sanitizable Signatures[END_REF] introduced controlled replacements. These limit the redactors substitution options to a set S that can be specified by the verifier. The idea is to replace the empty symbol ⊥ by an element x ∈ S along with a compact representation of the set S of permissible substitutions. Bloom-Filters [START_REF] Bloom | Space/Time Trade-offs in Hash Coding with Allowable Errors[END_REF] or accumulators [START_REF] Benaloh | One-Way Accumulators: A Decentralized Alternative to Digital Sinatures (Extended Abstract)[END_REF] are appropriate for that matter. Testing for a given substitution is easy by querying the Bloom-Filter or the accumulator (notice that a small probability for getting a false-positive answer is inevitable in case of Bloom-filters). Both approaches are deterministic and as such allow for bruteforce identification of the set S, if it is sufficiently small.

We sketch two remedies for this drawback: randomized accumulators and generalization hierarchies. The secure RSA-based accumulator, specified in [START_REF] Chang | Short Redactable Signatures Using Random Trees[END_REF], employs hash-functions. Replacing those hash-values by message-authentication codes with secret random keys, creates a randomized accumulator from a standard (deterministic) accumulator. Simply replace the hash-function H(s) by a randomized commitment for s based on hash functions, i.e. by H(s, r s ), where r s is a randomizer that is specific for s. Providing this randomizer in addition permits querying whether s is contained in the accumulator, but prevents bruteforce searching for other elements s ′ , because their specific randomizers (keys) r s ′ remain unknown. A randomizer r s for s can be derived using GGM-trees.

Generalization hierarchies are particularly suited for k-anonymity and generalization sets. As an example, consider an attribute ZIP= 22047 and its associated generalization set S = {22047, 2204 * , 220 * * , 22 * * * }. The ZIP-code shall only be replacable by elements of S. Simply change this block into the root of a subtree with leafs being the members of S. For the example, the child nodes would have labels 22, 0, 4 and 7. Redactions work in the obvious way.

Conclusion

In this paper we have presented a generalization of redactable signature schemes and several extensions. In contrast to standard redactable signatures, our scheme takes advantage of the inherent structure of structured documents like XMLdocuments. This is on the one hand a more natural way to access this problem and on the other hand beneficial for extensions like generalization hierarchies. Furthermore, the generalization induces only little additional computational overhead, which we attempt to confirm upon implementations. We believe that this concept is a valuable tool in the context of electronic healthcare, since it combines redaction capability with verification of the authenticity of remaining data while improving the efficiency of medical treatment processes. Future research includes further development of the proposed extensions, along with respective implementations (including an analysis of how much the XML structure affects the scheme's efficiency). A performance study to evaluate the quantitative benefit in terms of storage space and computational effort is part of ongoing work.

A Proof of Theorem 1

For the proof of Theorem 1 we use collision-resistant hash functions H, a secure commitment scheme C, a secure PRF G and a eUF-CMA secure digital signature scheme. We omit the formal definitions here, but note that for collision-resistant hash functions the probability of finding two messages m = m ′ with H(m) = H(m ′ ) is negligible and, for a secure commitment scheme only with negligible probability, one will be able to figure out m from C(m, r) and to open C(m, r) to some m ′ = m.

Basically, the proof follows the reduction to contradiction paradigm, i.e. we construct an adversary B that uses the adversary in game 5.2 (called A) whereas B plays the role of the challenger of A (using A's output as his own) and can break one of the used cryptographic primitives with non-negligible advantage.

Proof (sketch): Subsequently, we sketch how B acts when using adversary A: Setup: B's challenger runs the setup, gives (P K, H, C, G) as well as the description of the signature scheme to B. B gives all the information to A (note that A and B do not know SK). Phase 1: A is run and issues queries q 1 , . . . , q m as in game 5.2, but issues his queries q i ∈ {commit, sign, redact} to B. Except for queries of type sign, B acts as defined in section 5.2. However, since B does not know SK he forwards these types of queries to his challenger. Challenge: A may want to attack the hiding property and outputs two equal length documents D 0 and D 1 , which differ in exactly one document part, i.e. for exactly one i it holds that D 0 [i] = D 1 [i], along with a list of parts to be redacted. Now, B will use the advantage of A's guess (in the guess phase) to break the hiding property of the commitment scheme C. He proceeds as follows: He takes D 0 and D 1 as the two messages for breaking the hiding property of C and gives them along with i to his challenger. The challenger chooses at random a bit b and computes a commitment h

D b [i] for D b [i] (note that if D b [i]
is an inner node, the challenger needs to compute the hash of the root of this subtree by means of a commit query). B uses h D b [i] and computes the Merkle-tree using the remaining document (note that the remaining parts of D 0 and D 1 are identical). Now B has embedded his challenge (to attack C) into A's challenge and issues a sign query on the root hash to his challenger. Hence, he obtains a generalized redactable signature, redacts at least the i'th subdocument and gives the result back to A. Phase 2: A issues queries q m+1 , . . . , q n as in phase 1 to B (with the same restrictions as defined in section 5.2). Guess: A outputs a guess for either attacking the hiding or the unforgeability property and B uses this guess for breaking one of the primitives (signature scheme, hash function, commitment scheme, PRG). Hiding: Adversary A outputs a guess b which is used by B. Clearly, if A wins, then B is able to break the hiding property of the commitment scheme C. Consequently, if A's advantage in winning is non-negligible, B will break the commitment scheme with non-negligible probability, which contradicts our assumption. Unforgeability: Adversary A outputs a generalized redactable signature (as defined in game 5.2). Now we need to investigate all possible cases: Let us assume that this signature is not equal to any of the signatures returned by A during his game, i.e. A has broken the unforgeability property. But, now B could construct the Merkle-tree for the corresponding document and the root hash will be h v R = H(x||φ(c 0 )|| . . . ||φ(c k )) which is a hash of a possible label x of the root node and a concatenation of the values of the k + 1 children (as commitments to their subtrees). But the signature constitutes a signature of exactly these values, which can be used by B to break the existential unforgeability property of the respective signature scheme. The remaining case is a signature that is identical to a signature which was output by A during one of the phases. Firstly, either the two Merkle-trees constructed for the respective documents differ in their roots, then B has found a signature forgery for the digital signature scheme. Otherwise, the two trees differ anywhere below the root node and B has found a collision for the hash function H. Secondly, B investigates the construction of auxiliary GGM-tree (note that the security of this construction is implied by that of the standard GGM-tree). If there exists an index j where both documents differ, then he has found two document parts which can be used to break the hiding property of C. Finally, we need to look at the restriction, whereas we denote the two documents as D and D ′ . We have required that D ≺ D ′ needs to hold. But if A outputs as a guess a signature for a document D that contains some position that has been redacted in D ′ (in one of the two phases) and is present in D, then B can use this to break the hiding property of C or the PRG G underlying the auxiliary GGM-tree construction. The proof is complete.


Bernard Caron Llacan
email: llacan.vjf.cnrs.fr.caron@vjf.cnrs.fr

Comparison, similarity and simulation in Zaar, a Chadic language of Nigeria

Keywords: 1st, 2nd, 3rd person, AOR: Aorist, COP: Copula, CPL: Completive, CTP: Centripetal, DEM: Demonstrative, EMPH: Emphatic, EQ: Equative (copula), FUT: Future, ICPL: Incompletive, IMM: Immediate past, INCH: Inchoative, INDF: Indefinite, IRR: Irrealis, NMLZ: Nominaliser, NP: Noun Phrase, OBJ: Object, OPN: Opener (reported speech), PL: Plural, POS: Possessive, POS: Incompletive, PP: Prepositional Phrase, PRO: Pronoun, PROX: Proximate, PTCL: Particle, QL: Qualitative (copula), QLT: Qualitative (modifier), REL: Relativiser, RES: Resultative, S: Sentence, SBJV: Subjunctive, SG: Singular

Most of the examples quoted are extracted from a one-hour corpus published by the CorpAfroAs project (Mettouchi, Vanhove, & Caubet 2012), and completed by a two-hour corpus transcribed and annotated with the help of Marvellous S. Davan in November 2012 in Nigeria during a fieldtrip funded by IFRA-Nigeria and the EFL LABEX programme "The Typology and Corpus Annotation of Information Structure and Grammatical Relations". Transcription: Zaar is a 3 tone languages with High and Low noted respectively (á) and (à), and Middle left unmarked (a). Contour tones are Rising (ǎ) and Falling (â). In the examples, the first line gives a broad phonemic transcription, with postlexical tone realization and segmental assimilations, and the second line gives a morphological analysis.

I. Introduction

This paper discusses the linguistic expression of similarity, aka 'similative' in Zaar, a Chadic language spoken south of Bauchi State, in Northern Nigeria. As the Zaar similative is related to other functional structures, both morphologically (e.g. equative, simulative), or cognitively (e.g. comparison of superiority, aka 'comparative'), these will also be included in the discussion. After a presentation of Zaar and its typological characteristics, stressing the fact that the predicative words expressing the standard of comparison in Zaar are essentially verbs, not adjectives (Section 2), the paper does a quick morpho-syntactic survey of the general cognitive operation of comparison (Section 3), showing how the equative, similative and simulative structures are based on the preposition ɗan, 'like' whereas the comparative structure centers on the verb mop, 'surpass'. Section 4 studies the comparative, while Section 5 focuses on the preposition ɗan and its morpho-syntactic status in relation with the equative and the similative structures. Section 6 shows how the morphemes ɗan, 'like', the quotative tu, and the particle ku combine to form the simulative marker ɗan (ku)tu. Finally, Section 7 summarises the contribution of Zaar to the study of comparison and similarity.

II. Zaar, a South-Bauchi Chadic language

Zaar, also known as Saya, is spoken by about 150 000 speakers in the South of Bauchi State (Nigeria), in the Tafawa Ɓalewa and Ɓogoro Local Government Areas 1 . Together with 30 or so other related languages first identified by (Shimizu 1978), Zaar forms a sub-branch of West Chadic languages named the South-Bauchi languages 2 . Apart from the dominant languages, i.e. English (official national language) and Hausa (dominant all over Northern half of Nigeria), South Bauchi languages are surrounded by Niger-Congo languages in the West (Izere, Birom); in the East (Jarawan Bantu 3 ); in the South (Tapshin, Fyem, Kwanka) and further South-East (Tarok). Two isolates inside South-Bauchi languages are Bankal in the North and Ɓoi in the South.

Four dialects can be distinguished within Zaar, named after the main villages or towns where they are spoken: Ɓogoro (formerly called the Lusa dialect), Gambar Lere, Marti and Kal. The Kal dialect is very close to what is generally called the Sigidi or Guːs language, so much so that Gu:s can be conflated with the Kal dialect of Zaar (cf. [START_REF] Caron | Guus, aka Sigidi (Chadic, West-B, South-Bauchi): Grammatical notes and vocabulary[END_REF].

Most Zaar people of the younger generation are Hausa-Zaar bilinguals. They are schooled in Hausa in primary school, before learning English. The Zaar are Christians and use a Hausa translation of the Bible. The older generation are not fluent in Hausa, whereas the younger educated elite, who often hold positions in the administration, police and education, switch comfortably between Zaar, Hausa and English.

From a typological point of view, Zaar shares with its Hausa 'big brother' the main characteristics of most Chadic languages: it is a SVO head-first language where TAM is conflated with the exponent of the subject function into a pre-verbal pronominal clitic. Contrary to Hausa, this pre-verbal complex does not include the expression of focus. This same portmanteau morpheme can be omitted in sequential clauses -a phenomenon different from subordination, and appearing in narration to indicate consecutive events -and in Serial Verb Constructions (more on SVC in section 4 on the comparative). Zaar uses prepositions and the genitival modifier follows the noun it modifies. There is no case marking of object and subject. Zaar does not use relative pronouns, but has a relative subordinator ɗan, different from interrogative pronouns, which will be discussed in Section 7. Qualification is expressed either by a limited set of adjectives referring to age, size and colour, or more commonly by verbal predication, and more precisely by quality verbs. This preference for verbal predication of quality is manifest in comparison.

III. A brief overview of comparison in Zaar

The linguistic expression of similarity, or similative, is part of the broader conceptual category of comparison. Comparison presupposes an entity, called the comparee, in relation with some property, state or, more rarely, a dynamic state of affairs. The comparee is the argument of a predicative word -most often an adjectiverepresenting a parameter of comparison applied to it, relative to some standard.

"The comparative degree of some predicate -typically an adjective -marks this predicate as applying to its argument (the comparee) to a higher extent than the standard; e.g. smaller.

[…] A comparison of equality is one that ascribes to the comparee the same value of the parameter of comparison as to the standard." [START_REF] Cuzzolin | Comparison and gradation[END_REF], 1212 ff.) In the comparative degree, some languages mark a difference between the comparison of superiority (more intelligent than) and the comparison of inferiority (less intelligent than). In Zaar, such a contrast does not exist, and the comparison of minority is expressed through the negation of the comparison of equality (not as intelligent as).

As a consequence, we will focus on the comparison of equality (generally called 'equative' in typological studies) and the comparison of superiority, which, likewise, we will call 'comparative' for convenience sake.

3

The name Jar, or Jarawa is misleading since it refers to different populations, speaking different languages: the Jarawan Dutse (Mountain Jars) speak Zarek (Zere, Zarek, Afizere, Ifizere), a Benue-Congo language, and the Jarawan Kogi (Plain Jars), speaking Jààr (Zhar), a Bantu language, commonly called Jarawan Bantu. Finally, the Jerawa are another population, speaking Zele, a Benue-Congo language from the Kainji group [START_REF] Shimizu | A Lexicostatistical Study of Plateau Languages and Jukun[END_REF].

A good starting point for the typological study of comparison is given by English, with a clear morphology expressing the various logical articulators of comparison, such as [START_REF] Haspelmath | Equative and similative constructions in the languages of Europe[END_REF]'s descriptive framework for the study of equatives and similatives, which we will use for this work on Zaar:

(1) EQUATIVE My sister is as intelligent as you.

Comparee Parameter Marker

Parameter Standard Marker

Standard

The same framework can be adopted for the comparative:

( This contrast between scalar and non-scalar comparison has been used in the literature, although in different terms, to explain e.g. the difference between equatives and similatives:

"Semantically, the difference between equatives and similatives is not so much that similatives express approximate similarity, while equatives express true equality, but rather that similatives express identity of manner, whereas equatives express identity of degree or extent, or in other words, similatives express quality while equatives express quantity." (Haspelmath & Buchholz 1998, 313) These five types of comparison are basically expressed as follows in Zaar :

(4) equality inequality scalar equative: ɗan, 'like' comparative : mop, 'exceed' non-scalar identity: nàmbón, 'one' similative : ɗan, 'like' difference: mari, 'different'

As can be seen in table (4), there is a strong resemblance between the equative and the similative, both expressed through the preposition ɗan, 'like', as opposed to the expression of the comparative through the verb mop, 'exceed', while identity and difference are lexicalised through the use of the numeral nambon, 'one' and the adjective mari, 'different' respectively.

The identity of the preposition ɗan, 'like' needs further consideration, taking into account the possible links with three other words and their variants: the adverb ɗan (var. ɗa4 ), 'again'; the relative subordinator ɗan (var. ɗa), 'that'; and the deictic adverb ɗân (var. ɗáni), 'there'.

The tonal, morphological and semantic differences between the deictic adverb ɗân/ɗáni and the similative preposition ɗan, 'like' are too important to consider them to be either variants of the same word or to be otherwise related.

In the same way, although relative markers are often derived from deictic determiners in Chadic languages (Frajzyngier 1996), the falling prosody and the adverbial function of ɗân militate against its relationship with the relative subordinator ɗan. In Section 7, we analyse the relative and temporal clauses as complements of the preposition, and the relative and temporal subordinator ɗan as a grammaticalisation of the similative preposition ɗan, 'like'.

Finally, the cognitive relationship between repetition and identity or similitude argues in favour of a lexical connexion with the adverb ɗan/ɗa 'again':

(5) Máman sumí ɣá dəːlí gón ɗaŋ. However, the grammaticalisation path is not clear from the clause-final adverb ɗan to the homophonous preposition ɗan. The relative scarcity of documentation of related Chadic languages concerning similitude and comparison makes it difficult to get any extra information that would help. The only related lexeme is found in Miya with the verb ɗám(à), 'equal, reach, be as…', contrasting with the verb rà, 'exceed'. [START_REF] Schuh | Miya -English -Hausa Dictionary[END_REF] There exists no such verb in Zaar, which would contrast with mop, 'surpass, exceed' (cf. Section 4). It is tempting to imagine that such a verb *ɗan has existed, and given birth to the preposition ɗan, 'like' and the homophonous adverb ɗan, 'again' before disappearing. Unfortunately, nothing more can be said concerning a possible etymology or grammaticalisation path for all the uses of ɗan.

Before moving on to the following sections for the study of the comparative (Section 4) and the equative/similative (Section 5), let us see how identity and difference are expressed through the adjectives nàmbón, 'one, single' (Ex. 6) and mari, 'different' (Ex.7):

(6)

Tá wáːnì miːtsə nàmbóŋ?

IV. Comparative

The comparative (comparison of superiority) in Zaar is based on the verb mop, 'surpass, exceed',5 a labile verb which can be intransitive, monotransitive or ditransitive. The basic transitive use of the verb is exemplified in (8).

(8) Káɗâː ɬyà ɗûː tə móp karfíwâːn.

B. Similative

In English, the difference between the similative and the equative lies in the absence of parameter marker and the use of like, a standard marker that is different from the equative as. Since the Zaar similative uses the same standard marker as the equative (i.e. ɗan), and the equative does not have a parameter marker either, the same structure is used for the equative and the similative: He fights like a lion.

The only difference lies in the scalar property of the comparative predicate. If it is scalar (e.g. luː, 'be tall'; saɣát, 'be wise'), the structure will be interpreted with an equative meaning. It if is non-scalar (fi maːndə, 'fight'), it will take a similative meaning. See (Section 6) below for more on this opposition between the similative and the equative.

7

There exist 'true' adjectives Zaar (cf. (Ex.13), yír ʤìː, 'black eye'), but they don't appear in comparisons where synonymous quality verbs are used instead, e.g. lar 'be red' is substituted for 'ʒa', 'red'.

C. Morphological status of the parameter marker ɗan

Ɗan is followed in Zaar by different types of constituents, i.e. Noun Phrases, Prepositional Phrases and Clauses. If, as a consequence, it is analysed as changing its lexical category with each context, i.e. as preposition or conjunction, this results in a multiplication of the syntactic functions of ɗan. Instead, using Ockham's razor, and inspired by the discussion of English than by [START_REF] Huddleston | The Cambridge Grammar of the English Language[END_REF], 1103) VI. Semantics of the Equative/Similative structure Depending on the semantic and discursive contexts, the equative/similative structure with ɗan will take various meanings. Phrasal complements will induce equative or similative interpretations (both specific and general), as well as a functive interpretation. Clausal complements will induce similative9 , accord and substitutive meanings.

At phrase level, ɗan appears in exactly the same structure with equatives and similative functions. The difference is due to the semantic nature of the comparative predicator, i.e. the parameter. A scalar parameter will induce an equative interpretation (Ex. 26 & 27); a non-scalar parameter will induce a similative interpretation (Ex. 28). The opposition specific vs. general depends on the specificity of the standard. See (Ex. 26 & 27) for a contrast between specific and general equatives.

A. Specific equative

In the following example, the scalar parameter is the quality verb luː, 'be tall'; and the standard is a referential, individual item against which the comparee is set, i.e. Də nɗa, a person:

(25) Mopshí á lûː ɗan Də nɗa.

Mopʃí á luː ɗan Də nɗa Mopshi 3SG.AOR be tall like Doenɗa

Mopshi is as tall as Doenɗa.

B. General equative

The following example, a stock Zaar insult, is a general equative where the scalar parameter is the quality verb ɓaŋ, 'be bitter'. The non-specific standard producing a general equative is ránga, 'mahogany', which stands for the abstract, highest degree of bitterness (a synonym of wickedness).

( The same similative meaning appears when the standard is expressed by a clause: Here, the clausal complement of the preposition ɗan exhibits some morphosyntactic reduction with the bare verb waː appearing without repeating the Subject-TAM complex á of the matrix clause.

D. Functive

Another function of the structure equative/similative structure is that of role phrase [START_REF] Haspelmath | Equative and similative constructions in the languages of Europe[END_REF], also called functive [START_REF] Creissels | The functive (alias essive) in typological perspective[END_REF], where the NP introduced by ɗan works as a secondary predication expressing 'the role or function in which a participant appears' (Haspelmath & Buchholz 1998, 321-4) As I told you yesterday I want you to finish that job before you leave the town. [2012-11 SIM 12] Their function as manner rather than temporal adjuncts, or frame-setting topics (cf. Section 7 below) derives only from the semantic or informational context.

VII. Grammaticalisation of the equative/similative structure

When followed by a clausal complement, the semantic drift of the preposition can lead on to more grammaticalised meanings, e.g. when used to introduce temporal adjunct clauses, relative clause, and finally, at discourse level, topics.

A. Temporal adjunct

The preposition ɗan, 'like, as' can function with a clausal complement as a temporal adjunct. The resulting meaning is that of approximate simultaneity between the matrix clause and the adjunct clause.

( This temporal transposition of the comparative meaning of ɗan is quite common in other languages of the world, and is observed e.g. in English as, or in French comme, as in the opening verse of Arthur Rimbaud's Le Bateau Ivre:

(34) Comme je descendais des Fleuves impassibles, Je ne me sentis plus guidé par les haleurs: 'As I was floating down unconcerned Rivers, I no longer felt myself steered by the haulers:' (Rimbaud 2009, 162) The discursive function of temporal frame-setting, derived from the semantic interpretation of broad simultaneity, can also be narrowed down to a more precise temporal relationship between two events, such as concomitance, which involves both simultaneity and succession: 'just as S…; after S, then..

B. Topicalisation and frame-setting

Ɗan appears with non-clausal complements in left-dislocated position where the resulting phrase functions as a topic. Ɗan can then be considered as having been grammaticalised into a topic particle, e.g. in (Ex. 36) 10 This is not possible e.g. in French where comme used in temporal clauses requires the use of imperfective TAM's, e.g. Present, Imperfect, and Pluperfect.

where ɗan is used with the topic particles àmá, 'but' and kàm, 'indeed', to introduce the contrasting topic 'Godiya', the name of a young boy taken as an example when discussing the various types of mourning ceremonies:

(36)

Àmá ɗan gòːdiya kàm […] tá wâːnì miːtsəy gyàkgyàk kúrûm. We should look for a place that we will go to. (CONV 01 SP2 028)

Alongside the temporal adjunct structure, this is another extension of the function of the preposition ɗan when it takes a clausal complement. In this case, the resulting prepositional phrase functions as a noun modifier.

It should however be noted that the Zaar relative subordinator ɗan is not a relative pronoun, has no relationship with interrogative pronouns, and does not mark the syntactic function of the modified noun within the relative clause. In (Ex.38) for example, the gap left by the relativised constituent lə̂p, 'place' is filled by the locative anaphoric pronoun =káy. Consequently, although ɗan is used for both equative, similative and relative structures, Zaar is characterised as using a preposition, and should not be included in the languages using a relative-based strategy.

VIII. Simulation

Before the final section which summarises the findings concerning comparison and similarity in Zaar, this section focuses on another use of the morpheme ɗan when combined with the quotative tu and/or another morpheme, ku, producing pretense clauses, or simulatives, with the meaning 'as if…, as though…'. In the complex morpheme ɗan kutu the notion of simulation is associated more precisely with the morpheme ku. Ku is never used as an autonomous morpheme in Zaar, and is associated with no other function than the similative. An equivalent can be found in Mupun, a geographically close language belonging to the Angas Chadic family. In Mupun, there are two preposition expressing non-scalar equality comparison: too, ' From these observations, it can be inferred that there exist two competing strategies to form pretense clauses in Zaar, which can also be combined: one involving the combination of the similative ɗan and the quotative tu, and the other involving the "pure" simulative ku.

The way the simulative is expressed in Zaar reveals strong tendencies at work all over the language: borrowing from Hausa and other neighbouring languages; fusion between original Zaar strategies and borrowed strategies; and finally, cumulative use of all the available strategies: synonymous morphemes can be used individually or piled up in the same structure.

IX. Conclusion

As a conclusion, the main properties of the expression of similarity in Zaar can be summarised as follows.

With reference to the descriptive frame set by [START_REF] Haspelmath | Equative and similative constructions in the languages of Europe[END_REF], i.e. Comparee -Parameter Marker -Parameter -Standard Marker -Standard, the equative in Zaar does not have a parameter marker. Due to the dominantly verbal nature of the expression of quality in Zaar, the comparative predicate which includes the parameter is a quality verb. The comparison of superiority uses two competing strategies: a Serial Verb Construction Strategy and a Ditransitive Strategy, both based on the verb mop, 'surpass, exceed'. Similitude and equality comparison share the same syntactic frame in Zaar, based on the preposition ɗan, 'like'. There is no difference in Zaar between specific and general equatives or similatives. This same equative/similative structure based on the preposition ɗan is used for different functions: role phrases and accord clauses. Surprisingly, in the appropriate context, this similative preposition can take the substitutive meaning 'instead of'. Simulation is expressed in various combinations which can involve the similative ɗan (or its Hausa equivalent kaman), with the quotative tu, and the specialised morpheme ku, probably related to Mupun ko. Finally, the similative structure ɗan + clausal complement, has been extended to take on different grammatical functions that are more loosely connected to the original meaning of similarity: time adjunct ('as, when'); relative clause. When combined with left-dislocation, the structure <ɗan NP> is used as a topic, and the structure <ɗan S> functions as a frame-setting adjunct.

From a typological point of view, the expression of comparison and similarity in Zaar is quite different from what has been characterised as the "Standard Average European" equivalent (Haspelmath & Buchholz 1998, 325-6). The three main differences are (i) the verbal nature of quality in Zaar; (ii) the absence of parameter marker; (iii) the non-relative/interrogative base of the standard marker, which in Zaar is a preposition expressing manner.

Finally, Zaar, a head-initial language, confirms the main typological claim of (Haspelmath & Buchholz 1998, 289): "in head-initial languages the order should be 'parameter -standard marker -standard', and in headfinal languages the order should be 'standard -standard marker -parameter'."

  come return =1PL.OBJ at open space -INDF QLT again We will go back to another [tale] again (SAY BC NARR 01 SP1 001).

  : Parameter = S = Mopshí wâː ngîl, 'Mopshi sang'. Də nda á wâː ɮàr ɗam Mopshí wâː ngîl.

  .'. This occurs very often in the discursive context of a narration, characterised by such TAMs as the Aorist (narrative), or the Remote Past 10 : (35) Ɗaŋ á tûlíːɗi aʃí sáy Zhíː wùl ʃí tu […] say 3PL.OBJ COMP When he [Dog] arrived near them [the monkeys], then Panther told them to… (SAY BC READ 13 NAR Gung-Meer 013-4)

  SBJV drink beer 3SG.SBJV surpass strength 2PL.POS Don't drink more beer than you can stand. [lit. Don't drink beer so that it should exceed your strength]. (SAY BC INT 05 Morals SP1 035).The intransitive use of mop expresses set comparison (comparative of absolute superiority):This verb is used in two different strategies for comparison in Zaar: the Serial Verb Construction Strategy, and the ditransitive strategy.A. Serial Verb Construction StrategyLooking superficially like the equative/similative structure (see Section 5 below), the comparative use of the SVC is exemplified in (10) below: 6 which functions as the comparative predicate, and expresses the parameter. The second verb (mop, 'surpass'), is the minor verb, and functions as the standard marker. It is a transitive verb which takes the standard as a direct object. The resulting structure is shown in the table below, with the translation of 'Mopshi is taller than subject pronoun of the major verb (Parameter) can be repeated before mop, 'surpass' (the second verb, and Standard Marker), e.g. in (Ex.12):The ditransitive strategy is the only one available for parameters expressed by non-verbal predicates. The comparative predicator mop remains as the single main verb, with the standard as the first object, and the parameter as the second object.Jackal is more clever than Lion (lit. Jackal exceeds Lion in being clever).The parameter is omitted when it can be contextually recovered, as in (Ex. 16), a question typically concluding tales describing a competition among a group of friends, and for which there exist two varians in the corpus, with and without the parameter kúːskə nì, 'being evil': Mupun, another Chadic language from the Angas famly spoken south of Zaar, uses the same structures to express comparison, e.g. (Ex.17) for the Serial Verb Construction strategy: noted that the equative in Zaar does not use a parameter marker. Due to the dominantly verbal nature of the expression of quality in Zaar 7 , the comparative predicate which includes the parameter is a quality verb, e.g. lúː, 'be tall'; ʧolák, 'be smooth'; saɣát 'be wise', etc.

	The second complement of the ditransitive strategy is prepositional in Mupun, e.g (Ex.18):
	(18)	damuan met	naloŋ	n-ret
	(12)	Kə ʧí vìː kə móp yeɬí. Damuan surpass Nalong	PREP-beauty
	káɗâ àː kə Damuan is more handsome than Nalon (Frajzyngier 1993, 247) ɬya ɗûː t ə mop karfi =wâːn ʧi vìː k ə mop yeɬí Gjòː ɣəndá wò mop deːdéjoː? gjòː =kəndá wò mop deːdéː o ː which =COP2 3SG.FUT surpass exactly EMPH Which one will be most suitable? (SAY BC CONV 01 SP2 021-2). Âː wò colák mop kə. âː wò ʧolák mop kə ah 3SG.FUT be smooth surpass 2SG.OBJ Doenɗa': (10) (11) Comparee Parameter Standard Marker Standard NP PRO V 1 V 2 NP Mopʃí á lûː mop Də nɗa Mopshi is tall surpass Doenɗa 2SG.AOR eat speech 2SG.AOR surpass bird You are more talkative than a bird. (SAY BC READ 03 Sermon 272) B. Ditransitive strategy (13) Nə gyóː ɣəŋ á môp kámʃi ɗə ɣroː? nə gyôː k ən á mop kâːm -sə -i ɗə kər oː COP1 which COP2 3SG.AOR surpass friend -PL -INDEF madness EMPH Who is more stupid than his friends? (lit. 'who surpasses the friends (in) madness?') (SAY BC READ 08 NAR Men-Naar 38) The resulting structure is as follows: (14) Comparee Standard Marker Standard Parameter NP Pro V NP 1 NP 2 Mopshi surpass Doenɗa sense The same structure can be used with a parameter expressed by a nominalised verb: (15) Diːla mòp Záːki saɣátkə nì òː. Diːla mop Záːki sakát -kə nì oː Jackal surpass Lion be clever -NMLZ EMPH (16) Nə núː ɣəŋ á môp kámʃi (kúːskə nì òː)? nə núː k ən á mop kâːm =wôs kúːs -kə nì oː COP1 who COP2 3SG.AOR surpass friend 3SG.POS be evil NMLZ EMPH Who is more evil than his friends? (SAY BC READ 09 36) (17) naloŋ ret met damuan V. Equative/Similative structure A. Equative The basic structure of the equative is exemplified in (Ex. 19): (19) Tâːs Də nɗa á njîrə ɗan ʃémdi. tâːs də nɗa á nʤirə ɗan ʃémdi hand.POS Doenɗa 3SG.AOR be cold like ice Doenɗa's hand is as cold as ice. This structure can be represented as follows: (20) Comparee Parameter Standard Marker Standard NP Pro V Prep NP tâːs Də nɗa á njîrə ɗan ʃémdi Doenɗa's hand is cold like ice NEG3 2SG.(9) Mopʃí mop Də nɗa gyaːl It should be
		Nalong	pretty surpass	Damuan
		Nalon is prettier than Damuan

Eh, he will look nicer than you.

(CONV 02 SP1 111)

Although it appears in the same position as the preposition ɗan, 'like' of the equative/similative structure, mop is a verb: kə in (Ex.10) is a 2 nd person singular Object Pronoun, belonging to the paradigm of verb complement pronouns, whereas prepositions in Zaar take Independent Pronouns as complements, e.g. ɗan kyáːni, 'like you'. This comparative structure uses a Serial Verb Construction (SVC) strategy, as characterised in (Aikhenvald & Dixon 2006, 1):

"A serial verb construction (SVC) is a sequence of verbs which act together as a single predicate, without any overt marker of coordination, subordination, or syntactic dependency of any other sort. Serial verb constructions describe what is conceptualised as a single event. They are monoclausal; their intonational properties are the same as those of a monoverbal clause, and they have just one tense, aspect, and polarity value."

In this construction, the first verb (ʧolák, 'be smooth') is the major verb, an intransitive quality verb 6 There exist 'true' adjectives Zaar, but they don't appear in comparisons where synonymous quality verbs are used, e.g. lar 'be red' is substituted for 'ʒa', 'red'.

The

  26)Kə báŋ ɗan ránga.

	kə		baŋ	ɗan ránga
	2SG.AOR	be bitter	like mahogany
	You are as wicked as the Devil. (Caron 2005, 9)
	C. Similative
	tòː	k ə		dingá	kítâr	ɗan	ɗúːni	hár	kə	ɬə	-íː
	DM	2PL.AOR	continue	running	like	here	up to	2PL.AOR	go	RES
	ɗan wuːr	-	Vùŋ
	like mountain POS Vung
	then you would start running like here till you go to... like the Vung Mountain (SAY BC INT 03 Calendar
	SP1 358-360)

In (Ex.27) the similative meanings are produced by the two non-scalar parameters, viz. the action verbs kítâr,

'run' and ɬə, 'go to'. (27)

Tôː ɣə dìŋgá kítâr ɗan ɗûːn hár ɣə ɬǐːːː ɗan Wǔːr Vùŋ.

  . Only one example of role phrase was found in the corpus:(29) Nə myáːni ɣəŋ mə mân ɗan ndwáːtsə mə gə m longa tu àː lǎːp. noticeable case of semantic inversion is observed in substitutive clauses: the preposition ɗan and the structure of the substitutive clause is identical to that of the similative. With the proper context, and without changing anything to the structure, the preposition ɗan takes a substitutive meaning ('instead of'). In the following example, the substitutive interpretation is induced by the 2sg.Aorist kə used with the verb ɲáːr, 'thank' instead of the Completive usually associated with this verb: Ɗam mənáː fuː ɣə nàːyáːwón myáː súː àː gámá lǎːnníː ɣəndá àː ɬə .

		nə	myáːni		kən	mə		máni		ɗan	ndwáːtsə
		COP1	1SG.IDP	COP2	1SG.AOR	come	like	old person
		mə	g əm	longa tu	àː	láːp
		1SG.AOR release rabbit COMP 2PL.SBJV follow
		"I am the one who came (disguised) as an old man and released rabbits for you to follow. (SAY BC
		READ 12 NAR Kadi gi kitn 063-5)
		E. Substitutive
	(30)	Context: [you saw something worthless,] you went and took it too, instead of thanking God [for what
		you had already.]
		kə ɬíːɗa ngápkə̂n ɗaŋ kə ɲáːr ʧoɣŋ
		kə	ɬə -íː	ɗa	ngap -kə nì	ɗan kə		ɲáːr ʧokn
		2SG.AOR go RES again catch NMLZ	like 2SG.AOR thank God
		you went and took it too, instead of thanking God (SAY BC READ 05 Song Swari 162)
		F. Accord clause
		gə t	-íː	ɬə n	fi	ɗan	gə t	-íː	fuː	=tə
		woman -RES	go	do	like	woman -DIST	tell	=3S.OBJ
		That woman went and did as that [other] woman had told her. [2012-11 like 21 #19/168]
	(32)
		ɗan mənáː	fuː =kə	nàːyáːwón myáː		súː
		like 1SG.REC tell =2SG.OBJ yesterday	ISG.ICPL want
		àː	gamá laː	-ə n	-ni	-íː
		2SG.SBJV finish work -PROX -INCH -DIST
		kəndá àː		ɬə .
		then 2SG.SBJV go .

A

Accord clauses are not distinct formally from other clausal structures using ɗan as a standard marker, as can be seen in

(Ex. 31 & 32)

below.

(31)

Gə ɗíː ɬə n fi ɗaŋ gə ɗíː fúːtə .

  33)Kətáyáː fî wúr ɣá láːpkə̂n ɗaŋ kə fáːrá ndáɣə̂n á láːpkə nì?

	kətáyáː		fi	wuriː	ká	láːp	-kə nì
	2SG.REM.ICPL		do	how	at	follow	NMLZ
	ɗan kə	faːrá	nda	-kə nì	ká láːp	-kə nì
	like 2SG.AOR begin enter NMLZ at follow NMLZ
	How did you practice your faith when you converted to Christianity (lit. when you started
	following)? (SAY BC INT 05 Morals SP2 47)

  This left-dislocated position is favoured by temporal adjuncts in Zaar as in French (Ex. 34) above. The subordinate clause introduced by ɗan appears then before the matrix and functions as a frame-setting adjunct:

		àmáː ɗan gòːdiya kàm
		but	like Godiya indeed
		tá	waː	-ni	miːtsə -i		gyàkgyàk kúrûm
		3PL.FUT perform INCH burial INDF anyhow only
		But like Godiya on the contrary […] they would only be wailing. (INT 02 SP1 367-73)
	(37)	Ɗam míyàː ŋáːs tə ɣáyíː, kíː yèl láː áyàː fi wuriː?
		ɗan míyàː		ŋáːs	=tə	=káy	-íː
		as	ICPL.IMM.1SG	tease	=3S.OBJ	=ANAPH	-RES
		kíː	yel láː	áyǎː		fi wuriː
		2SG.IMM see work 3SG.ICPL.IMM	do how
		As I was teasing him about it, did you see what happened? (CONV 01 SP2 106)
	C. Relative clause Finally, the preposition ɗan, 'like' has been grammaticalised into the default relative subordinator ɗan, which
	behaves like the English subordinator 'that'.
	(38)	Mə ŋàl lə̂pwón ɗam má ɬə̂ɣáy.
		mə	ŋal	lə̂p	wón ɗan	má	ɬə =káy
		1PL.SBJV look for place some REL2 1PL.FUT go =ANAPH

  The most exhaustive combination is the form ɗan kutu e.g. (Ex. 39): IMM see work 3SG.ICPL.IMM do how as if 3SG.FUT weep Did you see what he was doing? As if he was going to cry. (CONV 01 SP2 107)In the combination ɗan kutu, tu is identified as the introducer of reported speech. This morpheme could be a word originally meaning 'say' (<*t-; cf. Hausa ʧêː), which has disappeared in Zaar where the verb wul/wu is used instead. Tu is the default reported speech opener. It can appear alone, at the beginning of the sentence, without any other verb: Kerenkeshe name some OPN Dagulau name some OPN Vwagani One was named Kerenkeshe, one was named Dagulau, one was named Vagani.(NARR 02 SP1 004)

	(39)	[…] vìː ɗaː mán mbaː astə ɗaŋ kutu mur ɣə ázùmí dóːlêː káwêy
		vìː	ɗa	àː	mán mbaː	as =tə
		mouth then 3SG.ICPL come be white POS =3S.OBJ
		ɗan kutu mur kə	ázùmí dóːlêː	káwêy
		like as if man POS fasting seriously merely
		[…] his mouth had become dry as if he was fasting seriously. (CONV 01 SP2 126)
	Ɗan kutu can be reduced to ɗan tu, e.g. (ex. 40) below:
	(40)	Á fím ɗan tu ma gəngá.
		á		fi =mə	ɗan tu	ma	gəngá
		3SG.SBJ.AOR do =1SG.OBJ like OPN 1SG.FUT vomit
		I feel [lit. 'it does me'] as if I'm going to vomit. (CONV03 SP2 255)
	Ɗan kutu can also be reduced to kutu, eg. (ex. 41) below:
	(41)	Kíː yèl láː áyàː fi wuriː? Kutu wò ŋgwáːr.
		kíː	yel láː	áyǎː		fi wuriː kutu wò	ngwáːr
	2SG.(42) Kə tú gíː nə niː? -Tu nə kúŋ ɬùː.
		kə	tu gíː	n ə	niː	tu	nə	kúŋ ɬûː
		2SG.AOR get DIST COP1 what? OPN COP1 dry meat
		What have you found ? He said it's dry meat. (NARR 03 SP1 202)
	Or it can follow a verb or phrase expressing an act of speech, thought, opinion, etc.:
	(43)	Dón tə wû tu kàːsuwa cáː yuɣə y ɗaŋgəní.
		dón	tə		wul tu	kàːsuwa ʧáː	yúkn -íː	ɗangəní
		because 3PL.AOR say OPN market	3SG.ICPL fill	-RES now
		Because they say that now the market is really big. (CONV 01 SP2 040)
	The quotative tu is also used to introduce a proper noun:
	(44)	Sə̂m gón tu Kèrèŋkéːshe, sə̂m gón tu Dàːgùláw, sə̂m gón tu Vwàːgàní
		sə̂m gón tu	kèrènkéːʃe	sə̂m gón tu	dàːgùláw sə̂m gón tu	vwàːgàní
		name some OPN

  Another source for the notion of simulation can be traced to the association of ɗan, 'like' and tu, the reported speech opener. The combination of comparative and quotative as a strategy to express simulation and other related notions (pretense, hypothesis, or irrealis condition), seems to be a straightforward cognitive operation, as exemplified in (Ex.46) taken from Naija (Nigerian English Pidgin):

							as',
	expressing similarity; and ko, 'as if', expressing simulation:
	(45)	wu le siap mopun *too/ko ngu mopun sə
		3M speak	Mupun as if	person Mupun DEM
		He speaks Mupun as if he were a Mupun person. (Frajzyngier 1993, 283)
	(46)	Lai se na ju bi mi, hau ju f du dis tḭ pas sɛf ?
		lai	se	na		ju	bi	mi
		like	OPN	COP.EQ	2SG	COP.QL	1SG
		hau ju	f	du dis		tin	pas	sɛf
		how 2SG IRR do PROX.SG	thing EMPH PTCL

If you were in my place, how would you have done this very thing? (9JA WAR 12 001)

Nasal phonetic variants are common in Zaar; e.g. the variation of the morpheme kutu/kutun, 'as if'. (cf Section 8).

The verb 'surpass' is the frequent means in African languages from various families to code comparison of superiority.

See (Section 7.1) for this use of ɗan introducing a temporal adjunct.

We have no example of the structure being interpreted as a simile, but there is no reason why it should not.