Chen Qian
email: chen.qian@irisa.fr

Mehdi Tibouchi
email: tibouchi.mehdi@lab.ntt.co.jp

Rémi Géraud
email: remi.geraud@ens.fr

Universal Witness Signatures

Keywords: Digital signatures, Delegation, Malleable signatures, Functional signatures, Identity-based cryptography, Obfuscation, SNARKs

à la diffusion de documents scientifiques de niveau recherche, publiés ou non, émanant des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

Introduction

Many signature schemes in the literature have delegatability properties either for keys or for messages.

The first family includes notions like (hierarchical) identity-based [Sha84, GS02, CHYC04, KN08] and attributebased [LAS + 10, MPR11, OT14] signatures, in which a master key authority grants signing rights to users, who may in turn be able to delegate those rights to lower-level signers. It also includes a slightly different class of schemes where the owner of the master secret key can sign all messages in the message space, and can delegate signing rights on restricted families of messages (again, possibly with recursive delegation): functional signatures [BGI14, BMS16] and policy-based signatures [BF14] are examples of such schemes.

The second family of schemes is that of malleable signature schemes, as defined e.g. by Ahn et al. [ABC + 15], Attrapadung et al. [ALP12] and Chase et al. [CKLM14]: in those schemes, it is possible, given a signature on some message, to publicly derive signatures on certainly related messages. Specific examples include content extraction signatures [SBZ02], redactable and sanitizable signatures [JMSW02, ACdT05], some variants of set-homomorphic and network coding signatures [JMSW02, BFKW09] (where users sign sets, resp. vector spaces, and those signatures can be delegated to subsets or subspaces) and more. A different example and one of the original motivations of this work is Naccache's notion of signatures on formulas of propositional logic [Nac10], which makes it possible to derive a signature on a propositional formula Q from a signature on P whenever P ⇒ Q.

Main idea of this work. The goal of this paper is to unify all of the schemes above into a single very general and versatile primitive, which we call universal witness signatures (UWS), and to propose concrete instantiations of that primitive achieving good security and privacy properties.

Our first observation is that delegation of keys and delegation of messages are really two sides of the same coin, which can be unified by regarding a signature on a message m by an identity A as really the same object as a key associated with the sub-identity (A, m) of A. The operation of signing messages simply becomes a special case of key delegation. Then, we can obtain in some sense the most general notion of signature scheme with (unary) delegation by saying that the set of identities is endowed with an essentially arbitrary pre-order relation ≤, and that given a key SK A on an identity A, we are able to derive another key SK B on any identity B such that B ≤ A. Unforgeability is then defined in the obvious way: roughly speaking, after obtaining keys SK Ai on various identities A i (possibly derived from higher-level identities), an adversary is unable to construct a valid key SK B for an identity B that doesn't satisfy B ≤ A i for any i.

The type of delegation functionality achieved by such a scheme is simply determined by the pre-order relation ≤. For example, regular (non-delegatable) signatures are obtained by choosing a set of identities equal to the message space together with a special identity * , such that m ≤ * for any message m, and no other relationship exists. Then, SK * is the secret key in the traditional sense, and it can be used to derive keys SK m playing the role of signatures. If non-trivial relationships exist between the messages m themselves, we get a malleable signature scheme instead. For instance, we get redactable signatures if messages are ordered in such a way that m ≤ m if and only if m is obtained from m by replacing some of the text in m by blanks. And we obtain identity-based signatures with a larger set of identities, still containing a special identity * associated with the master key authority, but also identities id i associated with the various users of the system, and identities (id i , m) for each pair of a user and a message. The order relation is then given by id i ≤ * for all i, and (id i , m) ≤ id i for all i and all messages. If additional nontrivial relationships exist between the id i 's, we essentially get hierarchical identity-based signatures.

We would like to support a really general class of pre-order relations ≤, to support for example the signatures on propositional formulas mentioned earlier, which are malleable signatures on messages (formulas) ordered by logical implication. However, the delegation algorithm that lets us publicly derive SK B from SK A when B ≤ A should certainly be able to efficiently test whether the relation B ≤ A actually holds. This is not possible directly for a relation like logical implication. For general NP relations, however, it does become possible if the delegation algorithm also receives as input a witness w of B ≤ A (for logical implication, for example, it would be a proof that A ⇒ B).

Our contributions. Along the lines sketched above, our first contribution is to define the notion of universal witness signature (UWS) scheme with respect to an arbitrary NP pre-order relation ≤ with a greatest element * . Such a scheme consists of only two algorithms:

Setup(1 λ ): returns a key SK * on the special identity * , as well as some public parameters PP; Delegate(PP, SK A , A, B, w): checks that SK A is a valid key for the identity A and that w is a valid witness of B ≤ A. If so, returns a fresh key SK B for the identity B. Otherwise, returns ⊥.

We do not actually need a separate algorithm for signature verification: to check whether SK A is a valid key on A, we can simply try to delegate A to itself (since ≤ is a pre-order, there is a trivial witness w A≤A for A ≤ A), and test whether the Delegate algorithm returns something or just ⊥. Security for a UWS scheme is defined as the unforgeability notion described in the previous paragraph. As usual, we distinguish between selective security (in which the adversary has to choose in advance the identity on which it will try to forge) and adaptive security. We also identify two other desirable properties of a UWS scheme: the privacy notion of context-hiding UWS, which says that the delegation path used to obtain a given key is computationally hidden, and the notion of succinctness, which says that the size of a key SK A is bounded only in terms of the size of A and the security parameter, independently of the delegation path.

We show that universal witness signatures are sufficient to obtain many earlier schemes appearing the literature, including HIBS, redactable signatures, functional signatures and Naccache's propositional signatures (for which our concrete constructions provide the first complete instantiations, to the best of our knowledge).

And finally, we give several constructions of UWS based on a range of assumptions, and achieving various subsets of our desirable properties. First, we show that one-way functions alone are enough to obtain adaptively secure UWS for arbitrary NP pre-order relations. The approach is similar to the one-way function-based construction of functional signatures [BGI14]. As in the work of Boyle et al., however, the resulting scheme is neither context-hiding nor succinct. Then, we prove that virtual black-box obfuscation [BGI + 12] (for a well-defined program depending on the pre-order relation under consideration) provides a very simple construction of secure, succinct, context-hiding UWS. This construction ticks all of our boxes, but it is of course based on a very strong assumption: in fact, Barak et al. showed that VBB is unachievable for general circuits. There could exist a virtual black-box obfuscator for our specific program of interest (and in fact, candidate constructions of indistinguishability obfuscation conjecturally satisfy that property), but this is rather speculative. We therefore try to achieve similarly strong properties based on somewhat more reasonable assumptions. We give two such constructions: one based on SNARKs [Kil92, BCI + 13, GGPR13] (actually, proof-carrying data [CT10, BCCT13, BCTV14]), which is secure and succinct but achieves a somewhat weaker form of privacy than the context-hiding property; and another based on indistinguishability obfuscation [BGI + 12, GGH + 13, SW14, GMM + 16], which is succinct and context-hiding but which we only prove selectively secure. Both of those constructions suffer from a limitation on delegation depth: it can be an arbitrary polynomial in the security parameter but fixed at Setup time. Moreover, our iO-based construction only applies to order relations rather than general pre-orders.

Universal Witness Signatures

Our notion of universal witness signature generalizes many existing signature schemes with delegation or malleability, such as homomorphic signatures [JMSW02], functional signatures [BGI14] and hierarchical identity-based signatures [CHYC04]. It supports delegation hierarchies defined by arbitrary NP pre-order relations, which, to the best of our knowledge, makes it more general than all previously proposed such schemes. And yet, its syntax is quite simple, consisting of only two algorithms.

Formal definition. Now we give a formal definition of our scheme. Note that the terms identity and message are synonymous in our setting, and can be used interchangeably. Similarly, the signing key for an identity can equivalently be seen as a signature on the corresponding message.

Definition 1 (Universal Witness Signatures). A universal witness signature scheme (UWS for short) for an NP pre-order relation ≤ with a greatest element * consists of two probabilistic polynomial-time algorithms:

-Setup(1 λ ) → (PP, SK * ) : This algorithm takes as input a security parameter λ, produces a master signing key SK * , keeps it secret and outputs public parameters PP.

-Delegate(PP, SK A , A, B, w) → SK B : This function takes as input the public parameters, a signing key for identity A, an identity B, and a witness w. If w is a valid witness of the NP statement B ≤ A and SK A is a valid signing key for identity A, then the algorithm outputs a signing key for identity B, otherwise it outputs ⊥.

We note that there exists a trivial witness for A ≤ A. For simplicity's sake, we also define a third algorithm Verify, which is merely a specialization of Delegate:

-Verify(PP, SK A , A) → {True, False} : This algorithm takes a public parameter, an identity A and a signing key SK A . We have Verify(PP, SK A , A) = False if and and only if Delegate(PP, SK A , A, A, w A≤A ) returns ⊥, where w A≤A is the trivial witness for the reflexive property A ≤ A.

Additional properties of UWS. We now propose three desirable properties for a UWS scheme. Intuitively, we will say that a UWS scheme is secure (i.e. unforgeable) if a polynomially-bounded adversary allowed to make arbitrary delegation queries cannot come up with a valid signing key on an identity A * that isn't reachable by delegation from any of the signing keys she obtained. We will say that the scheme is context-hiding if a signing key does not reveal the delegation path used to derive it. For example, a signing key SK A on A obtained from a long delegation path is indistinguishable from a signing key for the same identity delegated directly from the master key SK * .

Finally, we will say that the scheme is succinct when the size of a signing key is bounded depending only on the size of the associated identity (and not on the length of the delegation path used to derive it).

These properties can be captured formally as follows.

Definition 2 (Correctness). Correctness of an UWS scheme states that for all SK A , if A UWS scheme is selectively secure if and only if for all probabilistic polynomial-time adversaries A, the advantage of A in the previous game is negligible.

UWS.Verify(PP, SK

We also consider the adaptive security of UWS schemes, which is similarly defined, with the notable exception that the adversary does not announce in advance the identity A * on which she will forge, but can choose it adaptively instead (with the condition that it does not satisfy A * ≤ A for any of the identities A associated with revealed signatures).

Definition 4 (Context-hiding). A UWS scheme is context-hiding if, for every tuple (SK 1 , SK 2 , A 1 , A 2 , w 1 , w 2 ) and every identity B such that Delegate(PP, SK 1 , A 1 , B, w 1 ) → SK 1 = ⊥ and Delegate(PP, SK 2 , A 2 , B, w 2 ) → SK 2 = ⊥, the distributions of (PP, B, SK 1 ) and (PP, B, SK 2 ) are statistically close.

Definition 5 (Succinctness). An UWS scheme is succinct if there exists a polynomial p such that the size of any signature SK A is bounded by p(λ, |A|).

3 Applications: From UWS to Other Primitives Our universal witness signature scheme can be considered as a generalization of many existing malleable signature schemes. To showcase this, we use our UWS scheme to instanciate several well-known signature schemes, and some more original ones, namely: functional signatures and propositional signatures. A construction of hierarchical identitybased signatures and redactable signatures is also given in Appendix B. To the best of our knowledge, this is the first time that a construction for propositional signatures appears in the literature.

Functional signatures. Functional signatures, introduced by Boyle et al. [BGI14], are a particularly wide-ranging generalization of identity-based signatures in which the key authority can generate signing keys sk f associated to functions f , such that the owner of sk f can sign exactly those messages that are in the image of f . Moreover, to sign m in the image of f , the owner of sk f needs a witness to this fact, namely a preimage of m under f . In this section, we show how we can easily obtain functional signatures based on universal witness signatures.

Definition 6 (Functional Signature). The functional signature for a message space M and a function family F = {f : D f → M} is a tuple of algorithms (Setup, KeyGen, Sign, Verify) which is specified as follows:

-Setup(1 λ ) → (msk, mvk): the setup algorithm takes a security parameter λ and it returns a master signing key msk and a master verification key mvk. Then it keeps the master signing key secret msk and publishes the master verification key mvk. -KeyGen(msk, f ) → sk f : the key generation algorithm takes a master signing key msk and a function f to specify which one will be allowed to sign the messages, then it outputs a corresponding signing key. -Sign(f, sk f , m) → (f (m), σ f (m) ): the signing algorithm takes a function f and the corresponding signing key sk f as input and produces f (m) and the signature σ f (m) of f (m) -Verify(mvk, σ m , m) → {True, False}: the verification algorithm takes a signature-message pair (m, σ m ) and the master verification key mvk. The algorithm outputs True if σ m is a valid signature of m, otherwise outputs False.

Functional signatures from UWS. Consider the order O F corresponding to the function family F:

-Let M be the message space. The order O F is an order on the set { * } ∪ F ∪ M - * is the greatest identity, bigger than all other messages.

m ≤ f when ∃m ∈ M ∧ m = f (m ) -There does not exist any other non-trivial order

We note ≤ be the previously defined order. Then consider the UWS scheme corresponding to this order. The construction of the functional signature is described in figure Figure 1.

Security of the functional signature scheme. A functional signature scheme is typically expected to verify the following properties:

-Correctness: This property expresses the fact that a properly generated signature is verified to be correct. Formally:

∀f ∈ F, ∀m ∈ D f , (msk, mvk) ← Setup(1 λ ), sk f ← KeyGen(msk, f ), (f (m), σ f (m) ) ← Sign(f, sk f , m), Verify(mvk, σ f (m) , f (m)) = True.
-Unforgeability: The unforgeability of the functional signature scheme is defined by the the following security game between an adversary A and a challenger C:

• C generates a pair of keys (msk, mvk) ← Setup(1 λ ), then publishes the master verification key mvk byt keeps the master signing key msk secret. • C constructs an initially empty associative list H indexed by f ∈ F, a key generation oracle O KeyGen and a signing oracle O Sign as follows: * O KeyGen (f ): If there exists already a value associated to f in the associative list H, then outputs H(f ) directly. Otherwise the oracle uses the KeyGen algorithm to generate the signing key sk f ← KeyGen(msk, f ) associated to f , then adds the function-signing key pair (f, sk f ) to the associative list. * O Sign (f, m): If there exists a value associated to f in the associative list H, then uses the signing algorithm to generate a signature σ f (m) of f (m)

Verify(mvk, σm, m): Setup(1 λ ): return UWS.Verify(PP, SK f (m) , f (m)) (PP, SK * ) ← UWS.Setup(1 λ ) return (SK * , PP) KeyGen(msk, f ): return UWS.Delegate(PP = msk, SK * , * , f, "f ≤ * ) Sign(f, sk f , m): σ f (m) = UWS.Delegate(PP, sk f , f, f (m), m, "f (m) ≤ f ) return f (m), σ f (m)
Fig. 1. Functional signatures from UWS.

• A can query the two oracles O Sign and O KeyGen . A can also make requests of corresponding value in the associative list H. A win against the security game if it can produce a message-signature pair (m, σ) such that : * Verify(mvk, m, σ) = 1 * There does not exist m and f such that m = f (m ) and f was sent as a query to the key generation oracle O KeyGen . * There does not exist a function-message pair (f, m ) was a query to the signing oracle O Sign and m = f (m )

Let A be an adversary against the functional signature constructed using UWS scheme with non-negligible advantage.

Then by the definition it can produce a message-signature pair (m, σ) such that:

1. Verify(mvk, m, σ) = True 2. There does not exist m and f such that m = f (m ) and f was sent as a query to the key generation oracle O KeyGen .

3. The message m was not sent as a query to the signing oracle O Sign .

Condition 1 implies that Verify(PP, σ, m) = True. Condition 2 implies that for all (f, m ) which verifies that f (m ) = m, sk f has never been revealed. Then the third condition implies that σ m has not been revealed. As in the specific order corresponding to the functional signature, the only elements bigger than m are m itself, * , and

{f | ∃m ∈ M.f (m ) = m}.
With the conditions 2 and 3, the signatures of these identities have never been revealed, but A can produce a valid signature for m which break the existential unforgeability of the underlying UWS scheme.

Propositional signatures. In an invited talk at CRYPTO and CHES 2010, Naccache [Nac10] introduced the new notion of propositional signatures, for which he suggested a number of real-world applications such as contract-signing. Propositional signatures are signatures on formulas of propositional calculus, which are homomorphic with respect to logical implication. In other words, given a signature on a propositional formula P , one should be able to publicly derive a signature on any Q such that P ⇒ Q. Since the satisfiablity of propositional formulas cannot be decided efficiently without auxiliary information, the derivation algorithm should also take as input a witness of P ⇒ Q, i.e. a proof of Q assuming P .

To the best of our knowledge, no construction of propositional signatures has been proposed so far. However, it is easy to see that they are, again, easily obtained from UWS.

Security of propositional signatures. Formally, a propositional signature scheme is a triple (G, D, V) of efficient algorithms for key generation: G(1 λ ) → (mvk, σ False ), signature derivation: D(mvk, σ P , P, Q, π) → σ Q , and verification: V(mvk, σ P , P ) → True/False. The signature σ False on the false proposition plays the role of master secret key, due to ex falso quodlibet. Correctness states that if σ P is a valid signature on proposition P (in the sense that V(mvk, σ P , P ) evaluates to True) and π is a valid proof of P ⇒ Q, then D(mvk, σ P , P, Q, π) a valid signature σ Q on Q. Unforgeability says that after obtaining signatures on propositions P i of his choice, an efficient adversary cannot produce a valid signature on a prosition Q such that none of the P i 's implies Q.

Propositional signatures from UWS. Clearly, the UWS scheme associated with the corresponding set of propositional formulas endowed with the NP preorder relation given by logical implication (where witnesses are proofs) exactly gives a propositional signature scheme.

In fact, our definition of security captures for UWS captures a slightly stronger security model, where unforgeability still holds when the adversary can make unrestricted delegation queries on messages he cannot see, so as to control delegation paths.

Construction from One-Way Functions

Firstly, we propose a construction of the UWS scheme based only on the existence of one-way functions. The existence of one-way function is a very weak and basic assumption of cryptography. But this very basic construction does not verify many other properties than adaptive security like succinctness or context-hiding.

In this construction, we use a "certificate of computation" approach: Every signature is provided with a certificate of the delegation path. And an identity A can provide a certificate of the identity B if and only if B ≤ A. For example if for the generation of the signature of the identity A, we have passed the identities * , id 1 , id 2 , . . . , id n , A. Each identity produced a signing-verification key pair (sk idi , vk idi ) using the key generation of a signature scheme, and σ vk id i is a signature of (id i , w idi≤idi-1 , vk idi )4 produced using the signing key sk i-1 The signature of the identity A is represented by

SK A = sk A , (vk A , A, w A≤n , σ vk A ) , vk idn , id n , w idn≤idn-1 , σ vk idn , . . . , . . . , (vk * , * , w * ≤ * , σ vk * )
For simplicity we will note "w is a valid witness of x ≤ y" by "x ≤ w y" in the following sections of this paper and we propose the following construction of our UWS scheme using a classical existential unforgeable signature scheme Sig = (Setup, Sign, Verify).

Setup(1 λ ):

-The setup algorithm first takes two pairs of keys (msk, mvk), (vk * , sk * ) from the signature's parameters generation algorithm.

-Then it generates a signature σ vk * of ( * , w * ≤ * , vk * ) using the signing key msk, this can be considered as a certificate of the verification key vk * delivered by the master authority. -The delegation algorithm first verifies that the certificate c A is valid, by checking that each σ j is a valid signature on (id j , w j , vk j ) with respect to the verification key vk j-1 . It also checks that the witnesses are valid: B ≤ w A ≤ w A id n . . . and that vk A is a correct public key for sk A by signing a random message and verifying it. -If all these verification steps succeed, a fresh key pair (sk B , vk B ) for Sig is generated, together with a signature σ B on (B, w B≤A , vk B ) using the siging key sk A The algorithm then computes an extended certificate c B by prepending (vk B , B, w B , σ B ) to c A , and returns the signature SK B as (sk B , c B ).

This construction is summarized in Figure 2.

Theorem 1. The construction of UWS based on the one-way function is correct.

Proof. If we have Verify(mvk, SK A , A) = True and B ≤ w A, then

SK B = (sk B , c B ) with c B = [(vk B , B, w, σ B ), c A ],
and by construction, we have that (vk B , sk B ) is a valid signature key pair, and σ B is a valid signature of (B, w B≤A , vk B ). By the verification above and hypothesis of SK A is valid, c B is also a valid certificat and Verify(mvk, SK B , B) outputs True.

The proof that this construction is adaptively secure is given in Appendix C.

(sk B , vk B ) ← Sig.Setup(1 λ ) σ vk B ← Sig.Sign(sk A , (B, w B≤A , vk B )) Concatenate (vk B , B, w B≤A , σ vk B ) with c A : c B ← (vk B , B, w B≤A , σ vk B )||c A return SK B = (sk B , c B ))

Succinct Construction from Proof-Carrying Data

The previous construction based on one-way functions is clearly neither context-hiding nor succinct. In this section, we give a construction based on SNARKs, which is adaptively secure and succinct; we also provide arguments suggesting that it should satisfy some form of context-hiding property at least when the SNARK is zero-knowledge. As a downside, we are limited to a polynomial number of delegation steps: the maximum delegation depth must be fixed at setup time, as a polynomial in the security parameter. Our construction use the following theorems proposed by Bitansky et al. [BCCT13].

Theorem 2 (SNARK Recursive Composition Theorem). There exists an efficient transformation RecComp algorithm such that, for every publicly-verifiable SNARK (G SNARK , P SNARK , V SNARK ), the 3-tuple algorithms

(G, P, V) = RecComp(G SNARK , P SNARK , V SNARK )
is a publicly-verifiable P CD system for every constant-depth compliance predicate.

Theorem 3 (PCD Depth-Reduction Theorem). Let H = {H K } k∈N be a collision-resistant hash-function family. There exists an efficient transformation DepthRed H with the following properties:

-Correctness: If (G, P, V) is a P CD system for constant-depth compliance predicates, then (G , P , V ) = DepthRed H (G, P, V) is a path P CD for polynomial-depth compliance predicates. -Verifiability Properties: If (G, P, V) is publicly verifiable then so is (G , P , V ) -Efficiency: There exists a polynomial p such that the (time and space) efficiency of (G , P , V ) is the same as that of (G, P, V) up to the multiplicative factor p(k)

For the construction, we follow the same line of thinking as in Section 4.1. We consider an existential unforgeable signature scheme Sig = (Gen, Sign, Verify), with master signing key msk and master verification key mvk. Let us first define the distributed computation transcript T = (G, linp, data) and the corresponding C-compliance C(z out , linp, z in ) as follows: Let us consider the PCD scheme (G, P, V) corresponding to the distributed computation transcript described as above.

-G = (V,
Then we have all the building blocks for our universal witness signature.

- This construction is summarized in Figure 3.

Theorem 4. The construction of UWS scheme based on the Proof-Carrying Data is correct.

Proof. If SK B is produced by the Delegate algorithm on SK A , and SK A is a valid signature of A, by the correctness of the PCD scheme, we have π B is a valid proof of the fact that z B is consistent with the C-compliance transcript. This assures that the new signature SK B will pass the verification algorithm which means Verify(PP, SK B , B) will outputs True.

We give also proof of the selective security and succinctness of this construction in Appendix D.

Construction from Indistinguishability Obfuscation

The SNARK based construction from the previous section has some limitations: a polynomial bound on delegation depth, and no rigorously proved context-hiding property. A very simple construction without either of these shortcomings (thus achieving all the desired properties of universal witness signatures) can be obtained from virtual black-box obfuscation: we describe that construction in Appendix E. Admittedly, however, virtual black-box obfuscation is an onerous assumption: it is known to be unachievable for general circuits in the standard model [BGI + 12]. In this section, we provide a satisfactory construction using a somewhat more realistic flavor of obfuscation (indistinguishability obfuscation) together with puncturable pseudorandom functions (as is usual for iO-based constructions). Both notions are formally recalled in Appendix A.

Setup(1 λ ):

(msk, mvk) ← Sig.Setup(1 λ ) crs ← G(1 λ ) σ VK * ← Sig.
(z A , π A ) ← SK A (VK A , SK A , w A≤C , σ VK A ) ← z A Assert that π A is valid proof of z A / C-compliance (SK B , VK B ) ← Sig.Gen(1 λ ) σ VK B ← Sig.Sign(SK A , (B, w A≤B , VK B )) z B ← (VK B , SK B , w B≤A , σ VK B ) π B ← V(crs, z A , π A , z B , B) return (z B , π B )
Fig. 3. Construction of UWS from proof-carrying data.

Fig. 4. The CheckSign algorithm.

CheckSign[K](SK

A , A, B, w): if f (F (K, A)) == f (SK A ) ∧ A >w B then return SK B = F (K, B) else if f (F (K, A)) == f (SK A ) ∧ A =w B then return SK B := SK A else return ⊥
Our construction of UWS from punctured PRFs and iO achieves correctness, context-hiding, and succinctness. However, besides the reliance on iO, which is a strong assumption, the maximum delegation level must again be chosen at setup time, and there is a limitation of the type of preorder relations we support. More precisely, our construction applies to order relations (≤ is anti-symmetric) and moreover, any given element has at most polynomially many elements greater than itself. We will use the following three primitives in our construction:

1. Let C = iO(C) be the indistinguishability obfuscation of the circuit C; 2. Let (G, F) be a punctured PRF scheme in which G generates the system parameters and F is the keyed PRF; 3. Let f be an injective length-doubling PRG.

Here is our construction:

-Setup(1 λ ):

• We generate the PRF key K from G(1 λ ) and compute the indistinguishability obfuscation CheckSign of the algorithm CheckSign. • The master signing key (signature of * ) SK * is the PRF value F(K, * ) of * and the public parameter PP is the obfuscated circuit CheckSign . -Delegate(PP, SK A , A, B, w B≤A ):

• CheckSign (SK A , A, B, w B≤A ) which is an indistinguishability obfuscation of the program CheckSign described Figure 4.

Theorem 5. The iO-based construction is correct, succinct, and context-hiding.

Proof. All three properties rely on the underlying indistinguishability obfuscation's properties; we denote this obfuscator iO. By construction, a valid signature SK A of identity A is equivalent to the fact that SK A = F(K, A). Very roughly, it follows that:

-Correctness If SK B is produced by the algorithm Delegate, then SK B = F(K, B). We have Verify(PP, SK B , B) = True. -Succinctness and Context-hiding SK A = F(K, A) is independent of the delegation path, and its output is that of a pseudorandom function. Hence the UWS scheme is succinct and context-hiding.

A security proof and extended proofs of sunccinctness and the context-hiding property are provided in Appendix F.

Conclusion

In this paper, we have introduced a very general notion of delegatable signature scheme: universal witness signatures (UWS). We have formally defined the security properties that UWS should ideally satisfy, and provided four different constructions based on a range of assumptions from the existence of one-way functions to virtual black-box obfuscation, and achieving some or all of these security properties. Those constructions can be used to instantiate a number of other primitives, and provide, in particular, the first instantiations of propositional signatures, a notion with numerous interesting applications. Each of our constructions has some limitations, however. Constructing secure, succinct and context-hiding UWS with unbouded delegation depth based on relatively weak assumptions is left as a challenging open problem. In addition, our work did not tackle the problem of anonymity for UWS-like schemes, and we only considered unary delegation. Those problems are also worth investigating in future work.

A.2 Proof-Carrying Data

Proof Carrying Data (PCD), introduced by Chiesa and Tromer, is a cryptographic mechanism for ensuring that a given property is maintained at every step of a computation, typically in a distributed setting. The property of interest is specified as a compliance predicate, and every modification of the data comes accompanied with a proof that the data, and any operation leading to its current contents, satisfies the compliance predicate.

In this section we give a formal definition of PCD adapted from Bitansky et al. [BCCT13].

Definition 9 (Distributed computation transcript). A distributed computation transcript is a tuple T = (G, linp, data) with G = (V, E) a directed acyclic graph, linp : V → {0, 1} * a label function for vertices and data : E → {0, 1} * a label function for edges. We require that linp(v) = ⊥ for all v which are sources or sinks. The output of T , denoted out(T ), is equal to data(ũ, ṽ) which is the lexicographical first edge such that ṽ is a sink.

Definition 10 (Proof-Carrying transcript). A proof-carrying transcript is a pair (T, π) with T a distributed computation transcript and π : E → {0, 1} * an edge label function.

Definition 11 (Compliance predicate). A compliance predicate C is a polynomial-time computable predicate for nodes of the distributed computation transcript. We denote it C(z out ; linp, z in ), where z in is some input, z out is the (alledged) output, and the node's label is linp.

Given a distributed computation transcript DCT, we say that node n in DCT, with inputs z in and local input linp, is C-compliant if C(z out , linp, z in ) holds for every output z out of n. We say that DCT is C-compliant if every node in the graph is C-compliant. We say that a string z is C-compliant if there exists a C-compliant distributed computation transcript containing an edge labeled z. . A distributed-computation generator is an algorithm S(C, σ, P CT ) which takes a C-compliance, a reference string σ and a computation transcript. Then at every time step, it chooses to do one of the following actions -Add a new unlabeled vertex to the computation transcript. Then the algorithm outputs a tuple ("add unlabeled vertex", x, ⊥), with x the new vertex. -Label an unlabeled vertex. Then it outputs ("label vertex", x, y) with x ∈ V neither a source nor a sink and linp(x) = ⊥, and y is the new label of the vertex. -Add a new labeled edge. Then it outputs ("add labeled edge", x, y) with x ∈ E and y the label of the edge.

We introduce in Algorithm A.1 the ProofGen(C, σ, S, P) procedure, which describes an interactive protocol with C a compliance predicate, σ a reference string, S a distributed-computation generator (not necessarily efficient) and P C a PCD prover w.r.t. C, the PCD prover P C interacts with the distributed-computation generator S such that when S chooses to add a labeled edge P C produces a proof for the C-compliance of the new message and add this new proof as the proof label of the edge.

Using the above ProofGen algorithm, we can give the formal definition of the Proof-Carrying Data scheme.

Definition 13 (Proof-carrying data scheme). A proof-carrying data (PCD) scheme is a triple of algorithms (G, P, V) with G is probabilistic and P and V are deterministic.

A proof-carrying data system for a class of compliance predicates C is a triple of algorithm (G, P, V) that works as follows:

-G(1 λ ) → crs, on input the security parameter λ, outputs a common reference string crs. And there exists a negligible function ε(•) such that (G, P, V) satisfies:

Algorithm A.1: ProofGen(C, σ, S, P)

Result: zo, πo, T 1 Set T and P CT to be "empty transcript" (with T = (G, linp, data) and P CT = (T, proof ) with G = (V, E) = (∅, ∅)); 2 while S doesn't halt and outputs a message-proof pair (zo, πo) do 3 (b, x, y) ← S(C, σ, P CT ); -Completeness: For every compliance predicate C ∈ C and (possibly unbounded) distributed computation generator S,

Pr   T is B-bounded C(T ) = 1 V(σ, z o , π o ) = False σ ← G(1 λ , B) (z o , π o , T ) ← ProofGen(C, σ, S, P)   ≤ ε(λ)
-Proof of Knowledge: For every polynomial-size prover P * there exists a polynomial-size extractor E P * such that for every compliance C ∈ C, every large enough security parameter k ∈ N, every auxiliary input z in ∈ {0, 1} poly(k) , and every time bound B ∈ N.

Pr   V(σ, z out , π) = True ⇒ (out(T ) = z out ∧ C(T ) = 1) σ ← G(1 λ , B) (z out , π) ← P * (σ, z in ) T ← E P * (σ, z in )   ≥ 1 -ε(λ) A.

Punctured Pseudorandom Functions and Obfuscation

Punctured pseudorandom functions (punctured PRFs), first introduced by Boyle et al.

[BGI14], have been extensively used [SW14] with the obfuscators to construct provably secure cryptographic schemes. In our case, we combine punctured PRFs with an indistinguishability obfuscation to get the UWS scheme.

Definition 14 (Punctured Pseudorandom Function). A puncturable family of PRFs is a triple of algorithm (G, P, F) corresponding to generation of initial parameters, getting punctured keys and applying the PRF. These three algorithms have to verify that there exists a pair of computable functions n(•) and m(•), satisfying the following conditions.

-Functionality preserved under puncturing: For every PPT adversary A such that A(1 λ ) outputs a set S ⊆ {0, 1} n(λ) , then for all x ∈ {0, 1} n(λ) where x ∈ S, we have that:

Pr F(K, x) = F(K S , x) : K ← G(1 λ ), K S = P(K, S) = 1
-Pseudorandomness at punctured points: We consider an experiment with a PPT adversary (A, D) in which A(1 λ ) outputs a set S ⊆ {0, 1} n(λ) and a state σ, and the challenger then generates a PRF key K ← G(1 λ ), punctures it on the set S: K S ← P(K, S), and then sends σ, S, K S to the distinguisher D together with either the list of evaluations F(K, x) of the PRF on the elements x of S (where the x's are sorted in lexicographic order, say), or a list of uniformly random strings of the same lengths as those evaluations. The goal of the adversary is to distinguish those two cases, and pseudorandomness at punctured points says that the probability of success is negligible.

Obfuscation of programs is a powerful notion in cryptography, as it enables many attractive protocols [SW14].

As proved by Barak et al. [BGI + 12], the ideal virtual black-box notion can not be achieved for all polynomial size circuits (also it can in principle be achieved for a large class of specific circuits nonetheless). As a result, Barak et al. also introduced weaker notions of obfuscation which do not suffer from the same impossibility result, including in particular indistinguishability obfuscation (iO) which is defined as follows, and for which concrete candidates have been proposed since then-we can in particular mention the seminal construction of Garg et al. [GGH + 13] from multilinear maps.

Definition 15 (Indistinguishability obfuscation). A uniform PPT machine iO is called an indistinguishability obfuscation (iO) for a circuit class {C λ }, if it verifies the two following properties:

1. Functionality Preserving: For all security parameters λ ∈ N, for all C ∈ C λ , for all inputs x, we have that

Pr [C (x) = C(x)|C ← iO(λ, C)] = 1
2. Indistinguishability of obfuscation: For any (not necessarily uniform) PPT distinguisher (Samp, D), there exists a negligible function ε(•) such that the following conditions holds: if for all security parameters λ ∈ N. In that hierarchical version of identity-based signatures, the Private Key Generators are organized as a tree structure. An identity of depth , is represented by an -tuple id = (id 0 , id 1 , . . . id -1 ), and given the signing key SK id associated with id, it is possible to extract signing keys SK id on all identities id of the form id = (id 0 , . . . , id -1 , id , . . . ) (i.e. such that id is a prefix of id ).

Pr ∀x.C 0 (x) = C 1 (x)|(C 0 , C 1 , τ ) ← Samp(1 λ ) ≥ 1 -ε(λ) then | Pr D(σ, iO(τ, C 0 )) = 1 | (C 0 , C 1 , τ ) ← Samp(1 k ) -Pr D(σ, iO(τ, C 1 )) = 1 | (C 0 , C 1 , τ ) ← Samp(1 k ) | ≤ ε(λ) B Additional

Definition 16 (HIBS).

A hierarchical identity-based signature is a tuple of algorithms (Setup, Extract, Sign, Verify) which verifies the following specifications:

-Setup(1 λ ) → (PP, msk): Setup algorithm takes the security parameter λ as input and it outputs public parameters PP, and the master signing key msk, which is a signing key on the depth zero identity () (which is a prefix of all identities). -Extract(PP, SK id , id, id ) → SK id : Given the secret key SK id on identity id, and an identity id such that id is a prefix of id , output a signing key SK id on id . -Sign(PP, SK id , id, m) → σ m : Takes a signing key corresponding to the identity id and a message m. Outputs a signature σ m of the message m. -Verify(PP, σ m , m, id) → {True, False}: Takes the master verification key, a message m, and its signature σ m as input. It outputs True or False.

These algorithms need to verify also the following standard correctness property: if SK is a signing key for identity id and σ ← Sign(SK, id, m), then we have Verify(PP, σ, m, id) = True.

HIBS from UWS. Consider an HIBS scheme with identity space I and message space M. We can define an order relation ≤ on the disjoint union I I × M as follows: id ≤ id if and only if id is a prefix of id ; (id , m) ≤ ID if and only if id is a prefix of id ; and (id , m ) ≤ (id, m) if and only if m = m and id is a prefix of id . Then the HIBS scheme can easily be constructed from any universal witness signature scheme for the order relation ≤ (note also that since ≤ is efficiently computable, witnesses can be omitted). The construction is as described in Figure 5. HIBS. Chow et al. [CHYC04] give the following game to define the security of HIBS. That model captures what they call existential unforgeability under selective identity, adaptive chosen-message-and-identity attacks.

Security of

-The adversary A outputs an identity id * which will be used to challenge the security of the HIBS scheme.

-The challenger C takes a security parameter λ and computes the public parameters PP and the master signing key msk, sending the public parameters PP to the adversary A and keeping the master signing key msk secret. -The adversary A can submit two types of queries:

Extract: in which A receives the signing key SK id on any identity id of his choosing Sign: in which A chooses a message m and an identity id, and receives a valid signature σ on message m under identity id -Finally, A outputs a message m * and a signature σ * , and he wins if and only if V(PP, σ * , m * , id * ) = True.

That security notion is clearly satisfied by our UWS-based construction of HIBS, provided that the UWS scheme is adaptively secure (we in fact achieve the stronger notion of unforgeability under fully adaptive attacks). However, starting from a selectively secure UWS scheme, we may not be able to satisfy the property above, since the UWS definition of selective security would require the adversary to announce both the target identity and the target message of her forgery from the start (since we are effectively forging on (id * , m * )).

B.2 Redactable Signatures

Redactable signatures are a type of homomorphic signature scheme originally defined by Johnson,Molnar,Song and Wagner [JMSW02], that allows to redact part of a signed message while preserving signature validity. They were proposed as a way of guaranteeing the authenticity of documents published as part of public disclosure initiatives while taking security and privacy concerns into account. They have also found uses in medical and legal settings.

Let us consider the alphabet Σ = {0, 1, #}. We define a partial order on Σ with # ≤ Σ 0 and # ≤ Σ 1, no other non-trivial order in the alphabet. Then this order can induce a partial order in the set Σ * by point-wise comparison. Which means x 0 , x 1 , . . . , x n ≤ y 0 , y 1 , . . . , y n if ∀i ∈ {0, . . . , n}.x i ≤ Σ y i .

Definition 17 (Redactable signature scheme). A redactable signature scheme is a tuple of algorithms (G, S, V, D) with (PP, sk) ← G(1 λ ) which verifies the following properties:

-S(PP, sk, m) outputs a signature σ m on m ∈ Σ * .

-D(PP, σ m , m, m ) takes as input the public parameters, a signature σ m on a message m, and another message m ∈ Σ * , and returns a signature σ m on m provided that σ m is valid and m ≤ m. -The verification algorithm V is subject to the obvious correctness constraints (it accepts validly generated and derived signatures).

Setup(1 λ ): Redactable signatures from UWS. We will use our UWS scheme to construct the redactable signature scheme. Let us consider a UWS scheme (Setup, Delegate) with respect to the order ≤ on the set { * } ∪ Σ * , where Σ * is ordered as in the redactable signature scheme, and * is appended as the greatest element. Note that the order ≤ is efficiently computable, so that we do not actually need witnesses. We can construct a redactable signature scheme as descibed in Figure 6.

Security of redactable signatures. A redactable signature is said to be secure (i.e. unforgeable) if an efficient adversary allowed to make signature queries on arbitrary messages m 1 , . . . , m q ∈ Σ * is not able to produce a valid signature on a new mesage m * that does not satisfy m * ≤ m i for any i.

Our construction clearly satisfies that property, provided that the underlying UWS scheme is adaptively secure.

C Adaptive Security of the OWF-Based Construction Theorem 6. If the signature scheme Sig used in Section 4.1 is adaptively and existentially unforgeable then the OWF-based UWS scheme based is also adaptively secure with our definition.

Proof. We will construct an attacker against the adaptively existential unforgeability of the underlying signature scheme A Sig by using an attacker against the existential unforgeability of the UWS scheme A UWS . Suppose that we have an adversary A UWS which wins the existential unforgeable security game against the UWS scheme with an advantage ε. By definition, it can produce SK A which is a valid signature of A. Thus SK A verifies the following properties: -Type 0 forgery: c m is a suffix of c m which is a certificate of m revealed by the requests of the adversary A.

1. SK A = (sk A , [(vk A , A, w A≤idn , σ vk A ), (vk idn , id n , w idn≤idn-1 , σ vk idn ), . . . , (vk id1 , id 1 , w id1≤ * , σ vk1 ), (vk * , * , w * ≤ * , σ vk * )]) 2. For m ← random(1 λ ) and σ m ← Sig.Sign(m, sk A ), Sig.Verify(vk A , m, σ m ) outputs True 3. The identities verifies that A ≤ w A≤idn id n ∧ • • • ∧ * ≤ w * ≤ * * . 4.
-Type 1 forgery: c m is not a suffix of any c m which is a certificate of m revealed by the request of the adversary A.

Definition 18 (Valid certificate). c x is a valid certificate of x if and only if the adversary has required a signature of y and c x is a suffix of c y . We note maxPref(c x ) the longest suffix of c x which is a valid certificate for a certain identity 5 .

5 This is uniquely defined since suffixes are totally ordered. Put all together: Finally as the 2q O Delegate + 1 types of forgeries recover all the possibilities,6 our adversary constructed A Sig can win at least one of them with advantage ε, and the adversary choose randomly between the 2q O Delegate + 1 cases, then the advantage of A Sig against the underlying signature scheme is at least

ε 2q O Delegate +1 , which is still non-negligible if ε is non-negligible.

D Security Proof of the PCD-Based Construction

Suppose that there exists an adversary A PCD with non-negligible advantage against the PCD-based UWS scheme described in Section 4.2. In the selective security game, the adversary first announces the identity id * that will be targeted. Since as a hypothesis, there are only polynomially many identities, the set I = {id | id .id < id ∧id * < id } also has polynomial size. We ask the Delegate OWF oracle to sign all identities in the set I, then we construct a simulator for the UWS PCD oracles.

We construct the following simulator S:

-Delegate PCD (PP, SK A , A, B, w B≤A ): S verifies that SK A is a valid signature. Then use the signatures of the identities in I to generate a valid signature for the identity B. Then store it in an associative list7 . -Reveal PCD (A): This algorithm follows the honest procedure of access to the associative list.

Together with the attacker A PCD , the simulator S can be considered as a prover which provides a valid PCD proof (z id * , π id * ). Then by the proof of knowledge property there exist a extractor E algorithm which can produce a valid distributed computation transcript T ← E(PP) verifing that out(T ) = z id * and C(T ) = True. From this transcript we can construct a valid signature (SK id * , c id * ) for id * in the underlying signature scheme. This will be a valid attack for the underlying signature scheme in the construction of UWS scheme.

Remind that actually our construction is also selective with the a pre-order without anti-symmetric property, because in our construction, when we delegate to an identity whether there already exists a vertex with the same label, we will always create a new vertex. Thus the distributed computation script corresponding to the pre-order is always acyclic.

E Construction from Virtual Black-Box Obfuscation

Obfuscations of programs is a very powerful cryptographic primitive, from which many attractive protocols can be constructed [SW14].

For our construction, we remind that in previous sections we have constructed two different UWS. But these constructions have not been proven completely context-hiding. In this section, we will use the Virtual Black-Box (VBB) obfuscator to construct the first context-hiding UWS scheme.

Note that constructing a VBB obfuscator for all circuits is known to be impossible in the standard model, by a result of Barak et al. [BGI + 12]. Nevertheless, this impossibility result doesn't preclude VBB to be achievable for a given, restricted class of circuits (which is the setting in which we use it here); moreover, some existing candidate obfuscators have been shown to achieve VBB for all circuits in idealized models, such as the generic graded encoding model or the weak multilinear map model. Therefore, we regard the use of VBB obfuscation to establish feasibility results in a clean and easy way as quite reasonable: it yields concrete instantiations that are secure in idealized models, can also provide useful insights towards extending these results to weaker forms of obfuscation (like indistinguishability obfuscation) that do not suffer from the same theoretical limitations.

Definition 19 (Virtual Black-Box Obfuscator). A virtual black-box obfuscator O is a probabilistic algorithm verifying the following three properties:

-Functionality: For every circuit C, the string O(C) describes a circuit that given any inputs outputs the same result as C. -Polynomial Slowdown: There exists a polynomial p such that |O(C)| ≤ p(|C|). We give our construction as follows. Let O be a VBB obfuscator and Sig = (Setup, Sign, Verify) a deterministic existential unforgeable signature scheme. Assume that all identities and witnesses have at most polynomial size with respect to the security parameter. Let us consider the following UWS scheme:

-Setup(1 λ ):

• We generate a pair of signature keys (msk, mvk) ← Sig.Setup(1 λ ). Then compute the VBB obfuscation P = O(P [msk]) of the algorithm P [msk] • The master signing key (signature of * ) SK * is Sig.Sign(msk, * ) and the public parameter is PP = (P , mvk).

-Delegate(PP, SK A , A, B, w B≤A ):

• P (mvk, SK A , A, B, w B≤A ) where P is described in Figure 7, in which msk is a constant. This algorithm is doing directly what we want to do, it checks if SK A is a valid signature of the identity A.

Theorem 7. The VBB-based construction is correct, succinct and context-hiding.

Proof.

-Correctness Using the functionality of VBB obfuscation, we can see that the valid signature SK A is equal to Sig.Sign(msk, A). Thus if B ≤ w A and SK B = Delegate(PP, SK A , A, B, w) then wee have Sig.Verify(mvk, B, SK B ) outputs True, which means Verify(mvk, SK B , B) does not output ⊥. -Succinctness, context-hiding. A valid signature SK A equals to Sig.Sign(msk, A), then the signature is completely independent from the delegation path, thus the UWS scheme is succinct and context-hiding.

The intuition for this construction's security is based on the virtual-black box property of VBB obfuscation. A detailed proof of security is given below.

E.1 Security Proof of the VBB-Based Construction

We simulate the two oracles O Delegate and O Reveal , which will be used by the adversary later on:

-O Delegate (PP, A, B, w B≤A ): If A = * or the value corresponding to the identity A in the associative list is , then it add (B, ) to the associative list. -O Reveal (B): If the value corresponding to the identity B in the associative list is , then it outputs Sig.Sign(msk, B).

We will present the security proof using hybrids:

-Hybrid 0: This hybrid is the real-world adaptive security game for the adversary A. Denote the advantage of A by Adv 0 -Hybrid 1: In this hybrid, we replace PP = (mvk, P ) by PP = mvk. and consider the adversary S P (•) , which is an adversary with the oracle access to the algorithm P . Denote the advantage of S P by Adv 1 .

-

  The certificate c * of the identity * is [(vk * , * , w * ≤ * , σ vk * )]. The signing key (signature) SK * of the identity * in our UWS scheme is (sk * , c * ) and the public parameter PP will be mvk. Delegate(mvk, SK A , A, B, w): -The signing key SK A has the form (sk A , c A ), where the certificate c A is a list [(vk A , A, w A , σ A ), . . . , (vk * , * , w * ≤ * , σ vk * )].

Fig. 2 .

 2 Fig. 2. Construction of UWS from one way functions.

  E): The graph of the distributed computation transcript, with V labeled by the identity and (A, B) ∈ E labeled by the tuple (VK B , SK B , w B≤A , σ VK B ). -linp: The local input of the vertices will be the identity corresponding to this vertex. z out : The data of the edges are the labels of the edges, specifically z out = (VK B , SK B , w B≤A , σ VK B ). -C(z out , linp, z in ): parse z out as (VK B , SK B , w B≤A , σ VK B ), and suppose z in = (VK A , SK A , w A≤C , σ VK A ) with C the predecessor of A. The algorithm C(z out , linp, z in ) outputs True if • Sig.Verify(VK A , (linp(B), w B≤A , VK B ), σ VK A ) = True • B ≤ w B≤A A • For a random message m, we have Sig.Verify(VK B , m, Sig.Sign(SK B , m)) = True.

  Setup(1 λ ) → (PP, SK * ): Let (mvk, msk) ← Sig.Gen(1 λ ), then use the generation algorithm of the proofcarrying data to get PP = crs ← G(1 λ ). Let z * = (mvk, msk, " * ≤ * ", σ VK * ), we compute π * ← P(crs, ⊥, ⊥, z * , * ) and σ VK * ← Sig.Sign(msk, ( * , " * ≤ * ", mvk)). Then output SK * = (z * , π * ) and VK * = mvk.-Delegate(PP, SK A , A, B, w B≤A ) → SK B :•Parse SK A as (z A , π A ) with z A = (VK A , SK A , w A≤C , σ VK A ). • We firstcheck whether π A is valid proof of the fact that z A is consistent with the C-compliance transcript. If the test fails then the algorithm ouputs ⊥ • If the check suceeds, use the underlying signature scheme's generation algorithm to get (SK B , VK B ) ← Sig.Gen(1 λ ), and use the sign algorithm to get σ VK B = Sig.Sign(SK A , (B, w A≤B , VK B )). Let z B = (VK B , SK B , w B≤A , σ VK B ). • Finally use the proof algorithm P to generate a proof of z B : π B ← V(crs, z A , π A , z B , B) which is a proof of the fact that z B is consistent with the C-compliance transcript. The algorithm outputs SK B = (z B , π B ).

  Sign(msk, ( * , " * ≤ * ", VK * )) π * ← P(crs, ⊥, ⊥, z * , * ) z * = (VK * , SK * , " * ≤ * ", σ VK * ) return ((z * , π * ), crs) Delegate(mvk, SK A , A, B, w):

  -P C (crs, π i , z i .z o , linp) → π o for a compliance predicate C ∈ C which takes as input a common reference string crs, inputs z i with corresponding proofs π i , a local input linp, and an output z o . The algorithm produces a proof π o for the fact that z o is consistent with some C-compliance transcript such that C ∈ C. -V C (crs, z o , π o ) → {True, False} for a compliance predicate C ∈ C takes as input a common reference string crs, an output z o with corresponding proof π o , the algorithm returns True if π o is a valid proof of the fact that z o is consistent with some C-compliance transcript, otherwise it returns False.

4 10 E

 10 if b = "add unlabeled vertex" then 5 Set V := V ∪ {x} and linp(x) := ⊥ 6 else if b = "label vertex" then 7 Set linp(x) := y 8 else if b = "add labeled edge" then 9 Parse (v, w) := x with (v, w) ∈ V 2 ; := E ∪ {(v, w)}; PC(σ, data(v, w), linp(v), inputs(v), inproof s(v)) with inputs(v) := (data(u1, v), . . . , data(uc, v)), inproof s(v) := (proof (u1, v), . . . , proof (uc, v)) and (u1, . . . , uc) := parents(v).; 16 proof (v, w) := π

  Primitives from UWS B.1 Hierarchical Identity-Based Signatures Hierarchical identity-based signatures (HIBS) were first introduced by Chow et al. [CHYC04].

  Fig. 5. HIBS from UWS.

Fig. 6 .

 6 Fig. 6. Redactable signatures from UWS.

Fig. 7 .

 7 Fig. 7. The P [msk] algorithm. P [msk](mvk, SK A , A, B, w): if Sig.Verify(mvk, A, SK A ) ∧ A ≥w B then return SK B = Sig.Sign(msk, B) else return SK B = ⊥

  A , A) outputs True and w B≤A is a witness of B ≤ A, then the signing key SK B ← UWS.Delegate(PP, A, B, w B≤A ) is not equal to ⊥, and UWS.Verify(PP, SK B , B) outputs True.Definition 3 (Selective security of UWS schemes). The selective security of an UWS scheme is captured by the advantage of an adversary A in the following security game against a challenger C:1. A chooses a target identity A * . 2. C runs the algorithm Setup(1 λ ) to get SK * and PP. Then it keeps the master signing key SK * secret and sends the public parameter PP to A, together with a tag t SK * referring to SK * . 3. C initializes an associative list H in which the challenger maintains a set of tuples (t, A, SK) where t is a tag for the signing key generated by the challenger, A is an identity, and SK is a signing key for the identity A. The associative initially consists of just the tuple (t SK * , * , SK * ). 4. A can submit two types of queries: Delegate queries: Assume that C generated the signing key SK A on an identity A, and that A received the corresponding tag t SK A . For any identity B for which A knows a witness w B≤A of B ≤ A, A can instruct C to execute Delegate(PP, SK A , A, B, w B≤A ). The challenger will then generate a new unique tag t SK B on the resulting signing key SK B , and add the tuple (t SK B , B, SK B ) to its associative list H, sending back the tag t SK B to A. Reveal queries: Using the corresponding tag, A can ask C to reveal any previously generated signing key SK A provided that the associated identity A does not satisfy A * ≤ A. 5. After polynomially many queries of the type above, A outputs a candidate forgery SK A * , and wins if and only if Verify(PP, SK A * , A * ) = True.

  Delegate(mvk, SKA , A, B, w): sk A , c A ← SK A (vk id i , i, wi, σ vk id i ) ← c A Check certificate and witnesses: Assert Sig.Verify(vkj-1, (idj , wj , vkj ), σj ) for all j Assert B ≤w A ≤w A≤idn idn, . . . , * ≤w * ≤ * * Check public key:

	Setup(1 λ ):
	(msk, mvk) ← Sig.Setup(1 λ )
	(sk * , vk * ) ← Sig.Setup(1 λ ) σ vk * ← Sig.Sign(msk, ( * , w * ≤ * , vk * )) c * ← [(vk * , * , w * ≤ * , σ vk * )] return (mvk, (sk * , c * )	m σm ← Sig.Sign(sk A , m) $ ← -random(1 λ ) Assert Sig.Verify(vk A , m, σm) Generate new key pair and certificate:

  Each signature in the certificate verifies the following conditions: -Sig.Verify(mvk, * ||w * ≤ * ||vk

* , σ vk * ) → True -. . . -Sig.Verify(vk idn-1 , n||w idn≤idn-1 ||vk idn , σ vk idn ) → True -Sig.Verify(vk idn , A||w A≤idn ||vk A , σ vk A ) → True

Suppose that the number of requests of delegation is bounded by a fixed number q and the adversary A can produce SK m = (sk m , c m ) corresponding to m where c m is a certificate of the signature. For example, in the case of SK A , c A = [(vk A , A, w A≤idn , σ vk A ), . . . , (vk * , * , w * ≤ * , σ vk * )]. We define 2 types of forgeries:

We now explain how to realise UWS. The first construction requires only the existence of one-way function, but is neither context-hiding nor succinct. These properties can be obtained at the cost of introducing new assumptions such as the existence of proof-carrying data (for succinctness) or obfuscators (for context-hiding).

This is represented as a message idi||w id i ≤id i-1 ||vk id i .

Note that they are also all needed, to cover both type 0 and type 1 forgers.

Which may be implemented efficiently as a hash table.

A Some Definitions of Required Primitives

In this section, we recall the formal definitions of SNARKs, proof-carrying data, and notions related to obfuscation. All these notions are used in this paper to construct our Universal Witness Signature scheme.

A.1 SNARK Proof Systems

Succinct non-interactive arguments of knowledge, or SNARKs for short, are powerful proof systems that we use in particular to instanciate proof-carrying data constructions. To achieve this we define the SNARK proof system for the universal language on Random-Access Machines.

Definition 7 (Universal relation and Language). The universal relation is the set R U of instance-witness pairs (y, w) = ((M, x, t), w), where |y|, |w| ≤ t and M is a random-access machine, such that M accepts (x, w) after at most t steps. We denote by L U the universal language corresponding to the universal relation R U .

For any constant c > 0, we denote by R c ⊂ R U the subset of R U consisting of pairs (y, w) = (M, x, t), w such that t ≤ |x| c (and hence the running time of M on input (x, w) is polynomially bounded).

We will define a SNARK proof system for NP using those relations R c . Such a proof system is a triple (G, P, V) of three algorihms operating as follows:

G(1 λ ): on input of the security parameter λ, outputs a common reference string crs and verification state τ ; P(crs, y, w): produces a proof π of the statement y = (M, x, t) if w is a valid witness; V(c, τ, y, π): deterministically verifies the proof π, provided that y = (M, x, t) satisfies t ≤ |x| c .

The proof system is a SNARK if it verifies the following properties.

Definition 8 (SNARK for NP). A SNARK for NP is a triple (G, P, V) as above statisfying the following properties.

-Completeness: For all large enough λ, all constants c > 0, and every pair (y, w) = ((M, x, t), w) ∈ R c , we have

-Adaptive proof of knowledge: For every polynomial size prover P * , there exists a polynomial size extractor E P * and a negligible function ε such that for all λ, all constants c > 0 and every auxiliary input string z ∈ {0, 1} poly(λ) , we have

-Full succinctness: There exists a universal polynomial p such that, for all large enough λ, all c > 0 and every instance y = (M, x, t) such that t ≤ |x| c , we have that:

• the generator G(1 λ ) runs in time p(λ);

• the prover P(crs, y, w) runs in time p(λ

• the verifier V(c, τ, y, π) runs in time p(λ + |M | + |x|) (and independent of c); and

• an honestly generated proof π has length |π| ≤ p(λ).

To construct an adversary A Sig , we need simulate the delegation oracle O Delegate and the reveal oracle O Reveal by the functions in the underlying signature scheme.

Let us consider the associative list H initially empty. Let q O be the number of queries to the oracle O. We will proof that the attacker A UWS with non-negligible advantage ε against its own security game can win the security game of the underlying signature scheme with advantage ε 2q O Delegate +1 which is not negligible. We suppose that A UWS outputs SK m = (sk m , c m ) as challenge text against the UWS scheme. We choose an integer i in {0, . . . , 2q O Delegate }} and then proceed as in the case i described below:

Case 0: In this case, we guess that A UWS is a type 1 forgery and maxPref(c m ) is the empty suffix ε. Firstly we construct a simulator which simulates O Delegate and O Reveal .

-O Delegate : We construct the delegation function just as it has been defined.

-O Reveal : Outputs the corresponding value in the associative list.

During the procedure Setup, the simulator follows the same procedure except that for signing m * = * ||w * ≤ * ||vk * we replace the signing algorithm Sig.Sign by the signing oracle O msk using the master signing key msk.

Suppose that there exists an adversary A which produces an attack text SK of type 0 forgery against the UWS OW F scheme. Let (m * = ( * ||w * ≤ * ||vk * ), σ vk * ) be the last element of the certificate of SK . We submit the messagesignature pair (m * , σ vk * ) as a challenge text for underlying signature scheme using the master signing key msk. As (m * , σ vk * ) is not a suffix of any c x revealed by the adversary (by the assumption of this case), so the probability of O sign has evaluated on m * is zero. Thus if our guess is correct, we can win the security game against the underlying signature scheme with a non-negligible probability.

Case i (for i ∈ {1, . . . , q O Delegate }): In these cases, we guess that A UWS is a type 1 forgery, and it outputs (SK A , A) with SK A = (sk A , c A ). In the case i we suppose that in the i-th query's result SK x we have c x = maxPref(c A ).

Then we construct an adversary A Sig for the underlying signature scheme.

-O Delegate : We follow the construction of the delegation function in the UWS scheme for the first i queries. Then when we use the function Delegate(PP, SK x , x, y, w), we replace the signing procedure using sk x by the signing oracle O skx until another different sk x corresponding to x have been generated. -O Reveal : Outputs the corresponding value in the associative list.

Let (m, σ m ) = ((vk, id, w), σ m ) be the element in c A just after maxPref(c A ). The existence of (m, σ m ) is assured by the fact that maxPref(c A ) = c A otherwise it is a type 0 forgery. Then we submit it as challenge text for the underlying signature scheme with signing key sk x . With a negligible probability O skx has signed the message m (even A UWS have required to delegate from x to m, any valid signing key corresponding to the identities smaller than m can never be revealed, otherwise it contradict with the assumption "c x = maxPref(c A )", so we can simply ignore these requests), but as SK A is a valid signature of A. σ m is a valid signature of m w.r.t the signing key sk x which means if our guess is correct then we have constructed an adversary A Sig who can win the security game against the underlying signature scheme.

Case i (for i ∈ {q O Delegate + 1, . . . , 2q O Delegate }): In these cases, we guess that A UWS is a type 0 forgery and it outputs (SK A , A) with SK A = (sk A , c A , c sk A ). In the case i, we suppose that in the (i -q O Delegate )-th query's result SK x we have c x = c A . Then we construct an adversary A Sig for the underlying signature scheme.

-O Delegate : We follow the construction of the delegation function in the UWS scheme for the first i -q O Delegate -1 queries. Then when we use the function Delegate(PP, SK x , x, y, w), we replace the signing procedure using sk x by the signing oracle O skx . -O Reveal : Outputs the corresponding value in the associative list.

Let m be a message randomly generated. We obtain the signature σ m corresponding to the message m using sk x obtained in the SK A . As m is generated randomly, so the signing oracle O skx only has a negligible probability to have signed the message m. So with a non-negligible probability (m, σ m ) is a valid challenge text for the security game against the underlying signature scheme. Thus if our guess of this case is correct then we can construct an adversary against the underlying signature scheme.

Lemma 1. There exists a negligible function ε such that with the security parameter λ:

Proof. By the virtual black-box property which is:

We know that, Adv 0 ≤ Adv 1 + ε(λ).

Lemma 2. There exists a negligible function ε such that with the security parameter λ:

Proof. By the adaptive security of the signature scheme, there exists a negligible function ε(•) such that all adversaries A have at most ε(λ) advantage against the signature scheme.

And from the security game in the hybrid 1, we can see that we can simulate the oracle access to the delegation algorithm by the access of the signing oracle. From a forgery (m, SK m ) of the UWS scheme, we submit it as a forgery of the underlying signature scheme. In the security game, by the definition S P has never required to get a messagesignature pair (m , SK m ) such that m ≤ m . Thus (m, SK m ) is a valid forgery for the underlying signature scheme. By the adaptive security of the signature scheme and the fact that S P is a valid adversary, we have Adv 1 ≤ ε(λ).

Succinctness. The succinctness of the UWS scheme is clear from the construction. A valid signature of the message m in the UWS scheme by the construction in equal to Sig.Sign(msk, m). Thus if the underlying signature scheme is succinct. Then the UWS scheme constructed is succinct.

F Security of the Indistinguishability Obfuscation-Based Construction F.1 Security Proof

We prove the selective security of the constructed signature scheme using the following hybrids.

Hybrid 0 : In this hybrid, we proceed exactly as in the initial selective security game of the UWS scheme. We topologically sort all the identities e 1 , . . . , e greater or equal to m in non-increasing order. In particular, e = m, and the number of such identities is polynomial by assumption.

We also initialize a list L to the empty list, and two associative lists H L and H L with key space L, also initially empty. As we advance through the list of hybrids, the list L will be expanded to contain all identities e i up to a certain index i, and the associative lists will contain bitstrings associated with those identities.

For all i ∈ {1, . . . , }, we define the following four hybrids.

Hybrid i : We add (e i , y i = F(K L , e i )) to the associative list H L and (e i , z i = f (y i )) to the associative list H L , then we include e i in the list L ← L ∪ {e i } and we puncture the PRF key K L at the point e i where K ∅ = K used in the hybrid 0. We also modify the obfuscated circuit as Algorithm F.1: Hybrid i : In this hybrid, we replace y i = H L (e i ) by a random y i in the domain of f , and

Hybrid i : We replace y i by an independent random element y i , without modifying z i .

Hybrid i : We replace z i by an independent random element z i in the codomain of f , without modifying y i .

Final hybrid : In the final hybrid which is after hybrid , we modify the obfuscated algorithm by Algorithm F.2.

Proof. We begin the proof by noticing that in the final hybrid, there is no valid signature of m, so that the probability of the adversary win the security game is 0. Moreover, in all hybrids, the challenger can simulate all valid Reveal queries from the adversary, as he possesses the PRF key K L punctured on the points L, and none of the identities of valid Reveal queries belong to L.

Thus, to complete the proof, it suffices to show that the hybrids are indistinguishable.

Lemma 3. If the adversary A can distinguish hybrid i and the one that precedes it, then A can break the indistinguishability property of the underlying indistinguishability obfuscator.

Proof. The only difference between hybrid i and the one that precedes it is the change of the circuit CheckSign to be obfuscated; namely, the PRF key is punctured at e i , and evaluations of the PRF at that point are replaced by their values (as program constants) prior to puncturing. As a result the circuits corresponding to both hybrids are functionally equivalent, since each modified evaluation is replaced by its correct value in the previous program. It follows that if A can distinguish between the two obfuscated programs, it breaks the indistinguishability property of the underlying indistinguishability obfuscator.

Lemma 4. If the adversary A can distinguish hybrid i and hybrid i with non-negligible probability, then A can break the pseudorandomness of the PRF at punctured points.

Proof. The only difference between the hybrid i and the hybrid i is that we replace H L (e i ) = F(K {e1,...,ei-1} , e i ) by a random value, and we only know K {e1,...,ei} , by the pseudorandomness of the PRF at the punctured point e i , the hybrids i and i are indistinguishable.

Lemma 5. If the adversary A can distinguish hybrid i and hybrid i with non-negligible probability, then A can break the indistinguishability of the underlying indistinguishability obfuscator.

Proof. (of Lemma 5) The only points at which the two circuits differ are of the form (SK ej , e j , e i , w), where e j > w e i and in particular j < i and f (SK ej ) = z j . In particular, z j must belong to the image of f , which happens with negligible probability since f is length-doubling and z j is a random element in the codomain. Thus, with overwhelming probability, the circuits are functionally equivalent. Thus any adversary which can distinguish these two hybrid can break the indistinguishability of the underlying indistinguishability obfuscator.

Lemma 6. If the adversary A can distinguish hybrid i and hybrid i with non-negligible probability, then A can break the pseudorandomness of the underlying PRG f .

Proof. The only thing changed between hybrid i and hybrid i , is that we change the output of the PRG by a random value in the codomain, if an adversary A can distinguish these two hybrids, then A breaks also the pseudorandomness of the underlying PRG function.

Lemma 7. If the adversary A can distinguish the penultimate hybrid and and the final hybrid with non-negligible probability, then A can break the indistinguishability of the underlying indistinguishability obfuscator.

Proof. This proof is very similar to the proof of Lemma 5. The only points at which the two circuits differ are of the form (SK ej , e j , e, w), where e j ∈ L and in particular j ≤ and f (SK ej ) = z j . This means z j must be an image of f , but since f is length-doubling and z j is a random element in the codomain by the modification of the previous hybrids, which can only happen with negligible probability. Thus the two circuits are functionally equivalent with overwhelming probability, and as a result, if the adversary A can distinguish the two hybrids, it can break the indistinguishability of the underlying indistinguishability obfuscator.

F.2 Context-Hiding Property and Succinctness

Apart from the very basic notion of unforgeability, there are many other properties which are interesting such as context-hiding and succinctness. We will show that our construction verifies such properties.

Remind that the value of the signing key SK A for the identity A is equal to F(K, A).

Context-hiding. As defined in the preliminary, no adversary can distinguish between SK 1 B and SK 2 B which were generated respectively by Delegate(PP, SK A1 , A 1 , B, w 1 ) and Delegate(PP, SK A2 , A 2 , B, w 2 ), because SK 1 B = SK 2 B . Actually they have exactly the same value.

Succinctness. As we mentioned before, a valid signature SK A for an identity A is equal to F(K, A). So the length of the signature is bounded by the length of messages in the PRF's range.