Abstract
Digital signature schemes are a foundational building block enabling integrity and non-repudiation. We propose a graph signature scheme and corresponding proofs that allow a prover (1) to obtain a signature on a committed graph and (2) to subsequently prove to a verifier knowledge of such a graph signature. The graph signature scheme and proofs are a building block for certification systems that need to establish graph properties in zero-knowledge, as encountered in cloud security assurance or provenance. We extend the Camenisch-Lysyanskaya (CL) signature scheme to graphs and enable efficient zero-knowledge proofs of knowledge on graph signatures, notably supporting complex statements on graph elements. Our method is based on honest-verifier \({\varSigma }\)-proofs and the strong RSA assumption. In addition, we explore the capabilities of graph signatures by establishing a proof system on graph 3-colorability (G3C). As G3C is NP-complete, we conclude that there exist Camenisch-Lysyanskaya proof systems for statements of NP languages.
Access provided by Autonomous University of Puebla. Download conference paper PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
1 Introduction
Digital signature schemes are foundational cryptographic primitives; they are useful in themselves to ensure integrity and non-repudiation and as building block of other systems. From their first construction by Rivest, Shamir and Adleman [1], digital signatures have been on bit-strings or group elements, on a committed sequence of bit-strings [2] or structure-preserved group elements [3]. In this work, we establish a signature scheme and corresponding proof system for committed graphs.
The basis for this work is the Camenisch-Lysyanskaya proof system: a collection of distributed algorithms that allow an issuer, a prover and a verifier to prove knowledge of committed values, issue a Camenisch-Lysyanskaya (CL) signature [2, 4] on committed values, and prove knowledge of such a signature in zero-knowledge. It uses honest-verifier \({\varSigma }\)-proofs (Schnorr proofs [5]) and has the advantage that it keeps all attributes in the exponent. It thereby allows us to access attributes with known discrete-logarithm-based zero-knowledge proofs of knowledge [5–10]. The attributes that could be signed are, however, limited by the message space of the CL-signature scheme: a sequence of small bit-strings.
We study how to extend the Camenisch-Lysyanskaya proof system to establish signatures on committed graphs and, by extension, on committed statements from NP languages. Zero-knowledge proofs of certified or committed graphs and complex statements thereon have significant applications beyond classical graph proof techniques [11, 12] or the more recent proposal of transitive signatures [13]. The key difference to earlier work is that the graph encoding is universal, enables direct access to graph elements, and allows a prover to be flexible in the statements proven after the graph is certified. Such graph proofs are instrumental in foundational techniques, such as the zero-knowledge proof of knowledge of certified Petri nets as well as in various application scenarios, such as for the certification of audited cloud topologies, for which we proposed a dedicated framework for topology proofs [14].
First, we establish a new encoding of undirected graphs into the message space of CL-Signatures. The encoding supports vertex- or edge-labeled graphs and is universal in the sense that it supports efficient proofs over arbitrary graph elements and their relations.
Second, we extend the Camenisch-Lysyanskaya proof system to graphs by integrating the graph encoding into integer commitments and the CL-Signature bootstrapping process. This allows prover and issuer to sign committed graphs with sub-graphs contributed by both parties and to prove knowledge of graph signatures in honest-verifier \({\varSigma }\)-proofs. The obtained graph proof system in itself enables efficient zero-knowledge proofs of interesting graph properties, such as partitions, connectivity and isolation [14]. Graph proofs with a level of indirection between the authority on the graph (the issuer) and the verifier, established by a graph signature and with access to a wide range of graph properties, have not been covered by existing zero-knowledge graph proofs, such as [11, 12, 15], or transitive signatures [13]. While the former graph proofs are powerful constructions allowing for NP statements, e.g., graph 3-colorability or directed Hamiltonian cycle, their encoding does not cater for proving relations over graph elements in zero-knowledge. The latter is focused on the transitive closure along graph edges.
Third, we establish a proof system for graph 3-colorability (G3C) that allows us to obtain CL-Signatures on committed instances of 3-colorable graphs and to prove knowledge thereof to a verifier in zero-knowledge. Given that graph 3-colorability is NP-complete, we can lift the Camenisch-Lysyanskaya proof system to NP statements. Based on the 3-colorability proof system in a special RSA group and under the Strong RSA assumption, we show that there exists a Camenisch-Lysyanskaya proof system for any NP language, that is, the proof is capable of issuing CL-Signatures on committed statements from the NP language and to prove knowledge of such signatures in honest-verifier \({\varSigma }\)-proofs. Whereas the G3C-reduction does not offer efficient constructions for graph proofs, it shows the expressiveness of graph signatures.
In effect, this work extends the reach of the Camenisch-Lysyanskaya proof system to signatures and proofs on structures of entire systems. To our knowledge, it is the first work to enable signatures on committed graphs. Notably, the graph elements are present in the exponents and, thereby, accessible to known discrete-logarithm-based zero-knowledge proofs on a wide range graph properties in honest-verifier proofs.
1.1 Outline
In Sect. 2, we discuss the preliminaries of our graph proof construction: Camenisch-Lysyanskaya signatures and Camenisch-Groß encoding. Based on the Camenisch-Groß encoding, we establish a canonical encoding for vertex- and edge-labeled graphs in Sect. 3. Section 4 establishes how integer commitments and CL-Signature are extended with the graph encoding. In Sect. 5 we show how graph 3-colorability can be expressed in the graph proof system as proof of the encoding’s theoretical reach. Section 7 considers earlier work on zero-knowledge proofs and signatures on graphs, while Sect. 8 draws conclusions on this work.
2 Preliminaries
2.1 Assumptions
Special RSA Modulus. A special RSA modulus has the form \(N = pq\), where \(p=2p'+1\) and \(q=2q'+1\) are safe primes, the corresponding group is called special RSA group. Strong RSA Assumption [1, 7]. Given an RSA modulus N and a random element \(g \in \mathbb {Z}_N^*\), it is hard to compute \(h \in \mathbb {Z}_N^*\) and integer \(e > 1\) such that \(h^e \equiv g\) mod N. The modulus N is of a special form pq, where \(p=2p'+1\) and \(q=2q'+1\) are safe primes. Quadratic Residues. The set \({\mathrm {QR}}_{N}\) is the set of Quadratic Residues of a special RSA group with modulus N.
2.2 Integer Commitments
Damgård and Fujisaki [6] showed for the Pedersen commitment scheme [16] that if it operates in a special RSA group and the committer is not privy to the factorization of the modulus, then the commitment scheme can be used to commit to integers of arbitrary size. The commitment scheme is information-theoretically hiding and computationally binding. The security parameter is \(\ell \). The public parameters are a group G with special RSA modulus N, and generators \((g_0,\ldots ,g_{m})\) of the cyclic subgroup \({\mathrm {QR}}_{N}\). In order to commit to the values , pick a random \(R \in \{0,1\}^\ell \) and set \(C = g_0^R\prod _{i=1}^{l}g_i^{v_i}\).
2.3 Known Discrete-Logarithm-Based, Zero-Knowledge Proofs
In the common parameters model, we use several previously known results for proving statements about discrete logarithms, such as (1) proof of knowledge of a discrete logarithm modulo a prime [5] or a composite [6, 7], (2) proof of knowledge of equality of representation modulo two (possibly different) composite [8] moduli, (3) proof that a commitment opens to the product of two other committed values [8, 17], (4) proof that a committed value lies in a given integer interval [8, 9], and also (5) proof of the disjunction or conjunction of any two of the previous [18]. These protocols modulo a composite are secure under the strong RSA assumption and modulo a prime under the discrete logarithm assumption.
Proofs as described above can be expressed in the notation introduced by Camenisch and Stadler [19]. For instance,
denotes a “zero-knowledge Proof of Knowledge of integers \(\alpha \), \(\beta \), and \(\delta \) such that \(y=g^{\alpha }h^{\beta }\) and \(\tilde{y}=\tilde{g}^{\alpha }\tilde{h}^{\delta }\) holds, where \(u \le \alpha \le v\),” where \(y,g,h,\tilde{y},\tilde{g},\) and \(\tilde{h}\) are elements of some groups \(G=\langle {g}\rangle =\langle {h}\rangle \) and \(\tilde{G}=\langle \tilde{g} \rangle =\langle \tilde{h} \rangle \). The convention is that Greek letters denote quantities of which knowledge is being proven, while all other values are known to the verifier. We apply the Fiat-Shamir heuristic [20] to turn such proofs of knowledge into signatures on some message m; denoted as, e.g., \( SPK \{(\alpha ):y=g^{\alpha }\}(m)\). Given a protocol in this notation, it is straightforward to derive an actual protocol implementing the proof.
2.4 Camenisch-Lysyanskaya Signatures
Let us introduce Camenisch-Lysyanskaya (CL) signatures in a Strong RSA setting [2]. Let \(\ell _\mathcal {M} \), \(\ell _e\), \(\ell _N\), \(\ell _r\) and L be system parameters; \(\ell _r\) is a security parameter, \(\ell _\mathcal {M} \) the message length, \(\ell _e\) the length of the Strong RSA problem instance prime exponent, \(\ell _N\) the size of the special RSA modulus. The scheme operates with a \(\ell _N\)-bit special RSA modulus. Choose, uniformly at random, \(R_0,\ldots ,R_{L-1},S,Z \in {\mathrm {QR}}_{N}\). The public key \({\mathsf {pk}}(\mathsf {I} \!)\) is \((N,R_0,\ldots ,R_{L-1},S,Z)\), the private key \({\mathsf {sk}}(\mathsf {I} \!)\) the factorization of the special RSA modulus. The message space is the set \(\{(m_0,\ldots ,m_{L-1}) : m_i \in \pm \{0,1\}^{\ell _\mathcal {M}}\}.\)
Signing hidden messages. On input \(m_0,\ldots ,m_{L-1}\), choose a random prime number e of length \(\ell _e > \ell _\mathcal {M} + 2\), and a random number v of length \(\ell _v = \ell _N + \ell _\mathcal {M} + \ell _r\). To sign hidden messages, user \(\mathsf {U} \) commits to values V in an integer commitment C and proves knowledge of the representation of the commitment. The issuer\(\mathsf {I} \) verifies the structure of C and signs the commitment:
The user completes the signature as follows: \(\sigma = (e,A,v) = (e,A,(v'+R))\).
To verify that the tuple (e, A, v) is a signature on message \((m_0,\ldots ,m_{L-1}) \), check that the following statements hold: \(Z \equiv A^e R_0^{m_0}\ldots R_{L-1}^{m_{L-1}}S^v \pmod {N}\), \(m_i \in \pm \{0,1\}^{\ell _\mathcal {M}}\), and \(2^{\ell _e}> e > 2^{\ell _e-1}\) holds.
Theorem 1
[2] The signature scheme is secure against adaptive chosen message attacks under the strong RSA assumption.
Proving Knowledge of a Signature. The prover randomizes A: Given a signature (A, e, v), the tuple \((A' := A S^{-r} \hbox {mod }{N},e,v' := v+er)\) is also a valid signature as well. Now, provided that \(A \in \langle S \rangle \) and that r is chosen uniformly at random from \(\{0,1\}^{\ell _N + \ell _\varnothing }\), the value \(A'\) is distributed statistically close to uniform over . Thus, the user could compute a fresh \(A'\) each time, reveal it, and then run the protocol
2.5 Set Membership from CL-Signatures
Set membership proofs can be constructed from CL-Signatures following a method proposed by Camenisch, Chaabouni and shelat [21]. For a set \(\mathcal {S} = \{m_0, \ldots , m_i,\ldots , m_l\}\), the issuer signs all set members \(m_i\) in CL-Signatures \(\sigma _i = (A, e, v)\) and publishes the set of message-signature pairs \(\{(m_i, \sigma _i)\}\) with integrity. To prove set membership of a value committed in C, the prover shows knowledge of the blinded signature \(\sigma _i'\) corresponding to the message \(m_i\) and equality of exponents with C. We explain this technique in detail in the extended version of this paper and denote a set membership proof \(\mu [C] \in \mathcal {S} \), which reads \(\mu \) encoded in commitment C is member of set \(\mathcal {S} \).
2.6 Camenisch-Groß Encoding
The Camenisch-Groß (CG) Encoding [22] establishes structure on the CL message space by encoding multiple binary and finite-set values into a single message, and we will use a similar paradigm to encode graphs efficiently. We explain the key principles briefly and give more details in the extended version of this paper.
The core principle of the CG-Encoding is to represent binary and finite-set attribute values as prime numbers. It uses divisibility and coprimality to show whether an attribute value is present in or absent from a credential. The attribute values certified in a credential, say \(e_i\), \(e_j\), and \(e_l\), are represented in a single message of the CL-Signature, by signing the product of their prime representative \(E= e_i \cdot e_j \cdot e_l\) in an Integer attribute. The association between the value and the prime number of the encoding is certified by the credential issuer.
Divisibility/AND-Proof. To prove that a disclosed prime representative \(e_i\) is present in E, we prove that \(e_i\) divides the committed product E, we show that we know a secret \(\mu '\) that completes the product:
Coprimality/NOT-Proof. We show that one or multiple prime representatives are not present in a credential, we show coprimality. To prove that two values E and F are coprime, i.e., \(\mathsf {gcd}(E, F) = 1\), we prove there exist integers a and b such that Bézout’s Identity equals 1, where a and b for this equation do not exist, if \(\mathsf {gcd}(E, F) > 1\).
OR-Proof. To show that a credential contains an attribute e that is contained in an OR-list, we show there exists an integer a such that \(a e = \prod _i^{\ell } {e_i}\); if e is not in the list, then there is no such integer a as e does not divide the product. We use the notation \(\alpha \subseteq {\varXi }\) for an OR-proof that \(\alpha \) contains one or more values of \({\varXi }\).
3 Graph Encoding
We consider graphs over finite vertex sets, with undirected edges or directed arcs, and finite sets of vertex and edge labels. Vertices and edges may be associated with multiple labels. We leave the encoding of directed arcs to the extended version of this paper.
For each vertex i in \(\mathcal {V} \), we introduce a vertex identifier, a prime \(e_i\), which represents this vertex in credential and proofs. The symbol \(\bot \), associated with identifier \(e_{\bot }\) represents that a vertex is not present. All vertex identifiers are pair-wise different. We call the set of all vertex identifiers \({\varXi }_\mathcal {V} \), their product \(\chi _\mathcal {V} = {\varPi }{\varXi }_\mathcal {V} \). For each label k in the label sets \(\mathcal {L} _\mathcal {V} \) and in \(\mathcal {L} _\mathcal {E} \), we introduce a prime representative \(e_k\). All label representatives are pair-wise different. We call the set of all label representatives \({\varXi }_\mathcal {L} \), their product \(\chi _\mathcal {L} = {\varPi }{\varXi }_\mathcal {L} \). Vertex identifiers and label representatives are disjoint:
Random Base Association. We encode vertices and edges into the exponents of integer commitments and CL-Signatures and make them therefore accessible to proofs of linear equations over exponents. We randomize the base association to vertices and edges: For a vertex index set \(\mathcal {V} \)= 0,...,i,\( n \)-1 with vertex identifiers \(e_i\), we choose a uniformly random permutation \(\pi _\mathcal {V} \) of set \(\mathcal {V} \) to determine the base \(R_{\pi (i) }\) to encode vertex i. Edge bases \(R_{\pi (i,j) }\) are chosen analogously with a random permutation \(\pi _{\mathcal {E}}\).
Encoding Vertices. To encode a vertex and its associated labels into a graph commitment or CL-Signature, we encode the product of the vertex identifier \(e_i \in {\varXi }_\mathcal {V} \) and the prime representatives \(e_k \in {\varXi }_\mathcal {L} \) for \(k \in f_\mathcal {V} (i) \) of the labels into a single of the signature message. The product of prime representatives is encoded as exponent of dedicated vertex bases \(R \in G_\mathcal {V} \).
Encoding Edges. To get a compact encoding and efficient proofs thereon, the encoding needs to maintain the graph structure and to allow us to access it to proof higher-level properties, such as connectivity and isolation. The proposal we make in this paper after evaluating multiple approaches is to use divisibility and coprimality similar to the CG-Encoding to afford us these efficient operations over the graph structure, while offering a compact encoding of edges.
Recall that each vertex is certified with an vertex identifier from \({\varXi }_\mathcal {V} \), e.g., \(e_i\) or \(e_j\). For each edge \((i, j) \in \mathcal {E} \), we include an edge attribute as exponent of a random edge base \(R_{\pi (i,j)} \in G_\mathcal {E} \), containing the product of the vertex identifiers and the associated label representatives \(e_k \in {\varXi }_\mathcal {L} \) for \(k \in f_\mathcal {E} (i, j) \) of the edge:
whereas we usually consider simple graphs, specialties such as multigraphs, loops (i, i) encoded as \(e_i^2\) or half-edges encoded as \((e_j, e_\bot )\) can be included.
Definition 1
(Well-formed Graph). We call a graph encoding well-formed iff 1. the encoding only contains prime representatives \(e \in {\varXi }_\mathcal {V} \cup {\varXi }_\mathcal {L} \) in the exponents of designated vertex and edge bases \(R \in G_\mathcal {V} \cup G_\mathcal {E} \), 2. each vertex base \(R \in G_\mathcal {V} \) contains exactly one vertex identifier \(e_i \in {\varXi }_\mathcal {V} \), pair-wise different from other vertex identifiers and zero or more label representatives \(e_k \in {\varXi }_\mathcal {L} \), and 3. each edge base \(R \in G_\mathcal {E} \) contains exactly two vertex identifiers \(e_i, e_i \in {\varXi }_\mathcal {V} \) and zero or more label representatives \(e_k \in {\varXi }_\mathcal {L} \).
Theorem 2
(Unambiguous Encoding and Decoding). A well-formed graph encoding on the integers is unambiguous modulo the base association. [Proof 9.1]
4 Signatures on Committed Graphs
CL-signatures are signatures on committed messages, where messages can be contributed by issuer and user. This translates to a user committing to a hidden partial graph \(\mathcal {G} _\mathsf {U} \), which is then completed by the issuer \(\mathcal {G} _\mathsf {I} \!\), as outline in the interface in Table 1. We establish the secrecy notion of the construction first, explain the proof of representation second, and the issuing third.
As a point of reference, we give the structure of the graph signatures first. We have bases \(R_{\pi (i) } \in G_\mathcal {V} \), which store attributes encoding vertices, and bases \(R_{\pi (i,j) } \in G_\mathcal {E} \), which store attributes encoding edges. Observe that which base stores which vertex or edge is randomized by permutations \(\pi _\mathcal {V} \) and \(\pi _\mathcal {E} \).
4.1 Secrecy Notion
In a known-graph proof, the structure of the graph \(\mathcal {G} = (\mathcal {V}, \mathcal {E})\) is an auxiliary input to the verifier. Such a proof occurs if the prover needs to prove knowledge of a (NP-hard) property of the entire graph, e.g., a proper coloring in graph 3-colorability (cf. Sect. 2.4).
A hidden-graph proof keeps the structure of the graph \(\mathcal {G} =(\mathcal {V}, \mathcal {E})\) secret. For instance, there are graph proofs in which a local property is proven and the graph structure itself kept secret, e.g., when proving that disclosed vertices of the graph are connected by a hidden path.
The number of bases from \(\mathcal {G} _\mathcal {V} \) and \(\mathcal {G} _\mathcal {E} \) in a CL-Signature reveals an upper-bound on the number of vertices \( n \) and edges \( m \) of the signed graph. A suitable padding can be introduced by encoding nil-vertices \(e_{\bot }\) and nil-edges \((e_{\bot }, e_{\bot })\).
Proving properties over multiple attributes reveals which bases were involved in the proof. Characteristic patterns over said bases may interfere with the CL-Signature’s multi-use unlinkability. For instance, if the prover shows that vertices i and j are connected by an edge (i, j) along with properties on the vertices themselves, the verifier will learn that the bases for the vertex identifiers \(e_i\) and \(e_j\) are related to the base for the encoding of edge (i, j). To overcome this linking, the prover can obtain a collection of CL-Signatures on the same graph, each with a randomized association between bases and vertices/edges, that is, using different random permutations \(\pi _\mathcal {V} \) and \(\pi _\mathcal {E} \). When proving a property over the graph the prover chooses a CL-Signature from the collection uniformly at random and proves possession over that instance.
4.2 Proof of Representation
For a full proof of representation, we need to establish that the encoded graph in a graph commitment or CL-Signature is indeed well-formed (Definition 1). Given a graph commitment C the prover and verifier engage in the following proof of representation (the proof for a CL credential work analogously). We show that vertex bases contain a bi-partition of one and only one vertex identifier \(e_i \in {\varXi }_\mathcal {V} \) and a set of labels \(e_l \in {\varXi }_\mathcal {L} \). Edge bases contain a bi-partition of a product of exactly two vertex identifiers \((e_i \cdot e_j)\) and a set of labels \(e_l \in {\varXi }_\mathcal {L} \). To prove that the representation contains exactly one vertex identifier for a vertex base and two vertex identifiers for an edge base, we establish a set membership proof.
1. Commitments. The prover computes Integer commitments on the exponents of all vertex and edge bases. For each vertex i and for each edge (i, j), the prover computes commitments on vertex attribute and identifier (all \(\hbox {mod }{N}\)):
2. Proof of knowledge. We build up the proof of possession and well-formedness step by step, where it is understood the proofs will be done in one compound proof of knowledge with referential integrity between the secret exponents. Let us consider a proof fragment for vertices i, j and an edge (i, j) committed in a graph commitment C (the same proof structure is used for CL-Signatures).
2.1 Proof of representation. We prove that commitment C decomposes into commitments \(C_i,C_j\), one for each vertex i, j and one commitment \(C_{(i,j)}\) for each edge (i, j):
2.2 Vertex composition. Second, we need to show properties of the vertex composition, that the encoding for each vertex i contains exactly one vertex identifier \(e_i \in {\varXi }_\mathcal {V} \) and zero or multiple label representatives \(e_k \in {\varXi }_\mathcal {L} \). We show this structure with help of the commitments \(\breve{C}_i\) and set membership and prime-encoding OR proofs. This proof is executed for all vertices.
2.3 Edge composition. Third, we prove the structure of each edge (i, j) over the commitments \(C_{(i,j)}\), showing that each commitment contains exactly two vertex identifiers \(e_i,e_j \in {\varXi }_\mathcal {V} \) as well as zero or more label representative \(e_k \in {\varXi }_\mathcal {L} \):
2.4 Pair-wise difference. We prove pair-wise difference of vertices by showing that the vertex representatives are pair-wise co-prime over the commitments \(\breve{C}_i\) and \(\breve{C}_j\).
Theorem 3
(Proof of Well-formedness). The compound proof of knowledge establishes the well-formedness of an encoded graph according to Definition 1. [Proof 10]
4.3 Joint Graph Issuing
To jointly issue a graph CL-signature, a user commits to a hidden partial graph and the issuer adds further elements to the graph (cf. Sect. 2.4)
In the setup, the issuer establishes a user vertex space and issuer vertex space, i.e., a bi-partition on vertex and edge bases, \(G_\mathcal {V} \) and \(G_\mathcal {E} \) and on vertex identifiers \({\varXi }_\mathcal {V} \). Thus, user and issuer can encode partial graphs without interfering with each other.
In the joint graph issuing, user and issuer designate and disclose connection points (vertex identifiers) that allow the user and the issuer to connect their sub-graphs deliberately. The user constructs a graph representation by choosing two uniformly random permutation \(\pi _\mathcal {V} \) and \(\pi _\mathcal {E} \) for the base association on the user bases and commits to his sub-graph in a graph commitment. The user interacts with the issuer in a proof of representation of his committed sub-graph. The issuer verifies this proof, chooses uniformly random permutations for his graph elements and encodes them into his base range. The issuer creates the pre-signature of the CL-Signature scheme on the entire graph, proving that the added sub-graph is well-formed. The user completes the CL-Signature with his own randomness.
Theorem 4
(Security of Graph Signatures). The graph signature scheme maintains confidentiality and integrity of the encoded graphs and offers existential unforgeability against adaptive chosen message attacks under the strong RSA assumption. [Proof 9.1]
5 Graph 3-Colorability and NP Statements
5.1 Graph 3-Colorability
We adapt the following definition from Goldreich, Micali and Wigderson [11].
Definition 2
(Graph 3-Colorability). A graph \(\mathcal {G} =(\mathcal {V}, \mathcal {E})\) is said to be 3-colorable if there exists a vertex label mapping \(f_\mathcal {V} : \mathcal {V} \rightarrow \{\mathsf {R},\mathsf {G},\mathsf {B}\}\) called proper coloring such that every two adjacent vertices are assigned different color labels. This means that for each edge \((i,j) \in \mathcal {E} f_\mathcal {V} (i) \ne f_\mathcal {V} (j) \). The language graph 3-colorability, denoted G3C, consists of the set of undirected graphs that are 3-colorable. Graph 3-Colorability is known to be NP-complete. [23]
We adapt the graph 3-colorability problem to show in honest-verifier zero-knowledge that the prover knows an CL signature on an instance of a proper coloring of a given graph \(\mathcal {G} \).
Without loss of generality, we assume that graph \(\mathcal {G} \) is simple and connected. The three color labels \(\mathcal {L} = \{\mathsf {R},\mathsf {G},\mathsf {B}\}\) are encoded with three primes \({\varXi }_\mathcal {L} = \{e_\mathsf {R}, e_\mathsf {G}, e_\mathsf {B}\}\). The graph is encoded with vertex identifiers \({\varXi }_\mathcal {V} \) and these vertex labels. In addition to the conditions for a well-formed graph (Definition 1), we require that each vertex base contains exactly one label representative from \({\varXi }_\mathcal {L} \), which we show with a set membership proof on the secret vertex label.
The prover shows knowledge of a proper graph coloring by showing that the product of vertex identifiers and label representatives for each pair of adjacent vertices (i, j) are coprime.
Common inputs. Graph \(\mathcal {G} \), public-key of the CL-issuer.
Prover input. CL-Signature on proper coloring for G3C.
1. Credential randomization and commitments. The prover computes randomizations for the graph signature as well as for all occurrences of set membership proofs. The prover computes Integer commitments on the exponents of all vertex and edge bases. For each vertex i, the prover computes two commitments on the vertex attribute and the vertex identifier:
For each edge (i, j), the prover computes the commitment:
2. Proof of knowledge. The prover sends the commitments to the verifier. Then, prover and verifier engage in the following proof of possession over the graph signature and vertices i and j and all edges (i, j). We build upon the proof of representation and well-formedness presented in Sect. 4.2 with the following differences: Instead of proving that a vertex contains zero or multiple labels, we prove that the vertex contains exactly one label. Further, the proof is simplified because the edges do not contain labels. While we explain the proofs step by step, it is understood that the proofs are executed as compound proof of knowledge with referential integrity between the secret exponents.
2.1 Possession of CL-Signature. First, we prove of possession of the graph signature and representation of the commitments. Clause 1 proves possession of the CL-Signature on the graph. The clauses 2 and 3 prove the representation on the integer commitments on signed attributes for vertices j, j and edges (i, j), and, thereby, make the attributes accessible for the analysis of the exponents.
2.2 Well-formedness. Second, we establish that the vertex attributes are well-formed: Clause 4 establishes the relation between \(C_i\) and \(\breve{C}_i\) and, thereby, shows that a vertex attribute is bi-partitioned onto a vertex identifier and a label representative part. Clause 5 establishes that they contain exactly one vertex identifier and label representative of the certified sets \({\varXi }_\mathcal {V} \) and \({\varXi }_\mathcal {L} \).
Clause 5 is different from a proof of well-formedness as introduced in Sect. 4.2, as it enforces that vertex i contains exactly one label.
2.3 Proper coloring. Third, clauses 7 and 8 complete the statement by establishing that there is a proper coloring for the adjacent vertices i and j: Clause 7 shows that commitment \(C_{(i,j)}\) is on an edge (i, j). Finally, Clause 8 establishes that the attributes for vertex i and j are coprime, by proving that Bézout’s Identity equals 1. It follows that the labels of both vertices must be different.
3. Verification. The verifier outputs accept if the proof of knowledge checks out; reject otherwise.
Lemma 1
(Knowledge of a CL-Signature of G3C). The prover convinces the verifier in zero-knowledge that the prover knows a proper graph 3-coloring for known graph \(\mathcal {G} \). [Proof 10.1]
Lemma 2
The proof has an asymptotic computation complexity of \(O( n + m )\) exponentiations and a communication complexity of \(O( n + m )\) group elements and is thereby a polynomial time proof. [Proof 10.1]
5.2 Proofs Systems for Languages in NP
Having established a proof for certified graph 3-colorability, we can use the fact that G3C is NP-complete to establish that such Camenisch-Lysyanskaya proof systems exist for statements from other NP languages.
Definition 3
We call a Camenisch-Lysyanskaya proof system a set of PPT machines Prover \(\mathsf {P} \), Verifier \(\mathsf {V} \)and Issuer \(\mathsf {I} \)that engage in the following protocols:
Proof of Representation \(\mathsf {P} \!\rightarrow \mathsf {I} \!:\) Proof of representation on committed values V.
Issuing \(\mathsf {I} \!\rightarrow \mathsf {P} \!:\) Issuing of CL-Signature \(\sigma \) on hidden committed values V.
Proof of Possession \(\mathsf {P} \!\rightarrow \mathsf {V} \!:\) Proof of possession of CL-Signature \(\sigma \).
The issuer \(\mathsf {I} \)can act in the role of the verifier \(\mathsf {V} \)and thereby allow the bootstrapping of further CL-Signatures from the hidden values of existing CL-Signatures.
Compared to a zero-knowledge proof system for an NP language, this construction offers a level of indirection: The issuer acts as auditor with authority to decide whether the statement of an NP language is fulfilled in a certain environment, and its signature binds this statement to that environment. The instance of the NP language can either be provided by the issuer or provided by the prover and verified by the issuer.
The proof follows the same strategy as one of the initial results that all languages in NP have zero-knowledge proof systems, by Goldreich, Micali and Widgerson [11]: Given a CL proof system for G3C, we use the existing poly-time NP reductions to transform any NP language statement into an instance of G3C. This instance is then encoded as a graph in a CL-Signature and knowledge of the signature proven to a verifier. Lemma 1 shows that this is a zero-knowledge proof of knowledge of a proper coloring.
Theorem 5
Statements of languages in NP can efficiently be proven in a Camenisch-Lysyanskaya proof system based in honest-verifier zero-knowledge. [Proof 10.2]
6 Efficiency Analysis
We display the efficiency analysis for the proof predicates in Table 2, where vertex and edge composition proofs show the overhead over the basic proof of possession (cf. topology proofs [14]). We measure computational complexity in multi-base exponentiations. The communication complexity is dominated by the transmitted group elements from , which is equal to the number of multi-base exponentiations (one for each Integer and Schnorr proof commitment). The most expensive proof is the complete graph representation established in the issuing, where the set membership proofs (4 MExps) and the OR-based subset proofs (6 MExps) constitute significant overhead. The square-complexity is introduced by the final disjointness proof to establish that the graph is indeed well-formed. In the down-stream proofs, the verifier trusts the issuer to only certify well-formed graphs, which allows us to reduce complexity by only the computing the proof of possession and the statement proven.
The modular exponentiations for message bases \(R_i\) are with small exponents of size of \(\ell _\mathcal {M} \ll \ell _N\), where the parameter \(\ell _\mathcal {M} \) can be chosen similarly small as in Direct Anonymous Attestation (DAA) [24].
In addition, the \({\varSigma }\)-proofs employed in this work benefit from batch-proof techniques, such as [25]. The graph proofs are likely to be transformed to signature proofs of knowledge with the Fiat-Shamir heuristic [20] and can thereby be computed offline.
We have evaluated the system experimentally in [14], in computations using components of the Identity Mixer Library [26] with modulus length \(\ell _n = 2048\) bits and default system parameters (\(\ell _v\), etc.). The performance analysis is executed on 64-bit Java JDK 1.7.13 on a Windows 7 SP 1 Thinkpad X220 Tablet, on Intel CPU i5-2520 with 2.5 GHz, 8 GB RAM, where all computations are performed on a single processor core only, a very conservative setup. Figure 1 contains the results of a prototypical implementation of computations of the graph signature scheme, on representative computations of commitments and a proof of knowledge thereof. Based on uniform random bit-strings of the prescribed length and number (as in the actual Schnorr proof witnesses), we compute: \(C := R_0^{m_0}\cdots R_\ell ^{m_\ell } S^{v} \hbox {mod }{N}\),
The simulation uses random graphs with specified number of vertices \( n \) and a derived number of edges \( m := 2 n \) as major independent variable (on the x-axis), the dependent variable is computation time in milliseconds (in log-scale on the y-axis).
7 Related Work
Establishing zero-knowledge proofs on graphs and their properties is a classic area of research. Such proofs were instrumental in showing that there exist zero-knowledge proof systems for all NP languages. We discuss their graph modeling: Goldreich, Micali and Wigderson [11] offered such a construction with \(O( m ^2)\) rounds and \(O( n )\) messages each. Based on the existence of a non-uniformly secure encryption function, they explored graph isomorphism and non-isomorphism as well as graph 3-colorability (G3C). Blum’s proof [12] shows directed Hamiltonian cycles (DHC) in graphs. Both proofs use a metaphor of locked boxes to formulate the proof. Goldreich et al.’s G3C proof encodes the colors of adjacent vertices in boxes. Blum’s proof of Hamiltonian cycles encodes the graph’s adjacency matrix randomly in \(n+\left( {\begin{array}{c}n\\ 2\end{array}}\right) \) such boxes, giving the verifier the choice to either verify the correct graph representation or the knowledge of the Hamiltonian cycle. Blum offers an alternative construction for G3C with a similar methodology, encoding the graph representation and the coloring of each vertex in separate yet related boxes and operating on an adjacency matrix lifted to the labeling. Goldreich and Kahan [15] offered a constant-round construction based on the existence of collections of claw-free functions, also using G3C as NP-problem. We observe that these constructions are specific to the statement to be proven and do not cater for a level of indirection through a signature scheme.
A related notion to full graph signatures is transitive signature schemes, e.g., as proposed by Micali and Rivest [13]. They are concerned with the transitive closure of signatures on graph elements, where vertices and edges are signed individually; however, they do not offer zero-knowledge proofs of knowledge on graph properties.
8 Conclusion
We have introduced a practical construction of signatures on committed graphs and zero-knowledge proofs over their structure. The scheme is special in that it enables proofs over the entire graph structure, including statements such as isolation (two vertices are not connected by any sequence of edges). The construction derives its security from the properties of the Camenisch-Lysyanskaya (CL) signature scheme under the Strong RSA assumption. The interactive proofs are honest-verifier zero-knowledge if executed with multiple rounds with small challenges. While we have established a framework for graph topology proofs separately [14], this work focuses on the foundations of graph encoding in CL-signatures itself. We show its theoretical expressiveness by proving that the scheme is capable of signing committed NP statements and proving properties thereof, via reduction to graph 3-colorability. The presented scheme is efficient and practical because once the issuer has established graph well-formedness in \(O(n^2)\), the prover can resort to proofs over the graph structure in linear time. The used \({\varSigma }\)-proofs can be handled efficiently with batch processing techniques [25]. As future work, we aim at establishing a differential graph signature scheme, which can be employed for large-scale graph topologies as found in virtualized infrastructures.
References
Rivest, R.L., Shamir, A., Adleman, L.: A method for obtaining digital signatures and public-key cryptosystems. Commun. ACM 21(2), 120–126 (1978)
Camenisch, J.L., Lysyanskaya, A.: A signature scheme with efficient protocols. In: Cimato, S., Galdi, C., Persiano, G. (eds.) SCN 2002. LNCS, vol. 2576, pp. 268–289. Springer, Heidelberg (2003)
Abe, M., Fuchsbauer, G., Groth, J., Haralambiev, K., Ohkubo, M.: Structure-preserving signatures and commitments to group elements. In: Rabin, T. (ed.) CRYPTO 2010. LNCS, vol. 6223, pp. 209–236. Springer, Heidelberg (2010)
Camenisch, J.L., Lysyanskaya, A.: An efficient system for non-transferable anonymous credentials with optional anonymity revocation. In: Pfitzmann, B. (ed.) EUROCRYPT 2001. LNCS, vol. 2045, p. 93. Springer, Heidelberg (2001)
Schnorr, C.P.: Efficient signature generation for smart cards. J. Cryptology 4(3), 239–252 (1991)
Damgård, I., Fujisaki, E.: An integer commitment scheme based on groups with hidden order (2001). http://eprint.iacr.org/2001
Fujisaki, E., Okamoto, T.: Statistical zero knowledge protocols to prove modular polynomial relations. In: Kaliski Jr., B.S. (ed.) CRYPTO 1997. LNCS, vol. 1294, pp. 16–30. Springer, Heidelberg (1997)
Camenisch, J.L., Michels, M.: Proving in Zero-Knowledge that a Number Is the Product of Two Safe Primes. In: Stern, J. (ed.) EUROCRYPT 1999. LNCS, vol. 1592, p. 107. Springer, Heidelberg (1999)
Boudot, F.: Efficient proofs that a committed number lies in an interval. In: Preneel, B. (ed.) EUROCRYPT 2000. LNCS, vol. 1807, pp. 431–444. Springer, Heidelberg (2000)
Chan, A.H., Frankel, Y., Tsiounis, Y.: Easy come - easy go divisible cash. In: Nyberg, K. (ed.) EUROCRYPT 1998. LNCS, vol. 1403, pp. 561–575. Springer, Heidelberg (1998)
Goldreich, O., Micali, S., Wigderson, A.: Proofs that yield nothing but their validity or all languages in np have zero-knowledge proof systems. J. ACM (JACM) 38(3), 690–728 (1991)
Blum, M.: How to prove a theorem so no one else can claim it. In: Proceedings of the International Congress of Mathematicians. vol.e 1, p. 2 (1986) 2
Micali, S., Rivest, R.L.: Transitive signature schemes. In: Preneel, B. (ed.) CT-RSA 2002. LNCS, vol. 2271, pp. 236–243. Springer, Heidelberg (2002)
Anonymized for review: anonymized for review. In: conference proceedings to appear, November 2014
Goldreich, O., Kahan, A.: How to construct constant-round zero-knowledge proof systems for NP. J. Cryptology 9(3), 167–190 (1996)
Pedersen, T.P.: Non-interactive and information-theoretic secure verifiable secret sharing. In: Feigenbaum, J. (ed.) CRYPTO 1991. LNCS, vol. 576, pp. 129–140. Springer, Heidelberg (1992)
Brands, S.: Rapid demonstration of linear relations connected by boolean operators. In: Fumy, W. (ed.) EUROCRYPT 1997. LNCS, vol. 1233, pp. 318–333. Springer, Heidelberg (1997)
Cramer, R., Damgård, I.B., Schoenmakers, B.: Proof of partial knowledge and simplified design of witness hiding protocols. In: Desmedt, Y.G. (ed.) CRYPTO 1994. LNCS, vol. 839, pp. 174–187. Springer, Heidelberg (1994)
Camenisch, J.L., Stadler, M.A.: Efficient group signature schemes for large groups. In: Kaliski Jr., B.S. (ed.) CRYPTO 1997. LNCS, vol. 1294, pp. 410–424. Springer, Heidelberg (1997)
Fiat, A., Shamir, A.: How to prove yourself: practical solutions to identification and signature problems. In: Odlyzko, A.M. (ed.) CRYPTO 1986. LNCS, vol. 263, pp. 186–194. Springer, Heidelberg (1987)
Camenisch, J.L., Chaabouni, R., Shelat, A.: Efficient protocols for set membership and range proofs. In: Pieprzyk, J. (ed.) ASIACRYPT 2008. LNCS, vol. 5350, pp. 234–252. Springer, Heidelberg (2008)
Camenisch, J., Groß, T.: Efficient attributes for anonymous credentials. ACM Trans. Inf. Syst. Secur. (TISSEC) 15(1), 4 (2012)
Garey, M.R., Johnson, D.S., Stockmeyer, L.: Some simplified np-complete problems. In: Proceedings of the Sixth Annual ACM Symposium on Theory of Computing. pp. 47–63. ACM (1974)
Brickell, E., Camenisch, J., Chen, L.: Direct anonymous attestation. In: Proceedings of 11th ACM Conference on Computer and Communications Security. ACM Press, pp. 225–234 (2004)
Peng, K., Boyd, C., Dawson, E.: Batch zero-knowledge proof and verification and its applications. ACM Trans. Inf. Sys. Secur. (TISSEC) 10(2), 6 (2007)
IBM: Specification of the Identity Mixer cryptographic library, v. 2.3.40. Specification, IBM Research, January 2013 http://prime.inf.tu-dresden.de/idemix/
Cook, S.A.: The complexity of theorem-proving procedures. In: Proceedings of the third annual ACM symposium on Theory of computing, pp. 151–158. ACM (1971)
Acknowledgments
This research is supported by the EU FP7 FutureID project (http://futureid.eu) under GA \(n^o\) 318424 and the EU Horizon 2020 project PrismaCloud (https://prismacloud.eu) under GA \(n^o\) 644962. The author is grateful for the discussions with Jens Groth and Jan Camenisch as well as for the feedback of the anonymous reviewers considering this work.
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Appendices
9 Proofs
1.1 9.1 Well-Formed Encoding and Security
Proof
(Unambiguous encoding and decoding: Theorem 2 ). We show that there is a bijection between encoding and graph.
Graph \(\rightarrow \) Encoding: For each graph there exits a unique encoding modulo base association. For all vertices \(i \in \mathcal {V} \) choose the vertex identifier \(e_i \in {\varXi }_\mathcal {V} \), for the labels \(k \in f_\mathcal {V} (i) \) choose the prime representative \(e_k \in {\varXi }_\mathcal {L} \) and compute their product. As said factors are prime, it follows from the fundamental theorem of arithmetic that the \(e_i {\varPi }_{k \in f_\mathcal {V} (i)} e_k\) represents a unique integer. Given that the user is not privy to the discrete logarithm between one base and another (guaranteed by the CL-Signature setup), the bases unambiguously separate the exponents. Thus, apart from the random permutation of the base association, the encoding is unambiguous.
Encoding \(\rightarrow \) Graph: With knowledge of the elements of \({\varXi }_\mathcal {V} \) and \({\varXi }_\mathcal {L} \), an encoded product can be decoded efficiently and unambiguously into the elements of the graph. That the parties are not privy to the discrete logarithm between base and another guarantees attribute separation. The base designates unambiguously whether a vertex or an edge is encoded. Given that all representatives of the encoding are prime, the product can be decomposed into a unique factorization by the fundamental theorem of arithmetic. Each representative unambiguously represents either a vertex identifier in \({\varXi }_\mathcal {V} \) or a label in \({\varXi }_\mathcal {L} \), as both sets are disjoint. \(\quad \square \)
Proof
(Security of graph signatures: Theorem 4 ). The security of the scheme is directly derived from the unambiguous embedding into Integer commitments and Camenisch-Lysyanskaya signatures and their security properties. Theorem 2 establishes that the graph encoding encodes graphs unambiguously into the CL-message space. The graph structure is encoded in the exponents of the Integer commitment and CL-signature schemes. Confidentiality is derived from the information-theoretical hiding property of the Integer commitment scheme and the hiding properties of CL-signatures on committed messages. Under the condition that the adversary is not privy to the group-order of the commitment and the CL signature scheme, we obtain that integrity for both schemes holds over the integers and thereby the graph encoding (cf. [6]). We obtain existential unforgeability against chosen message attacks directly from the CL-signature scheme in Theorem 1 [2].
10 Well-Formedness Proof
The following proof is representative for the argument structure of the proofs for different predicates; others use the same tools.
Proof
(Wellformedness proofs, Theorem 3 ). The Schnorr proofs used in the construction are honest-verifier zero-knowledge if executed repeatedly with small challenges, otherwise witness-indistinguishable. It is standard to extract from a successful prover knowledge on the secrets ranging over \(\forall i,j\):
such that all equations of the CS-notation hold for some t, where t must be \(\pm 1\) as modulus N is a product of two safe primes [6]. As CL-signatures are existentially unforgeable [2], we obtain that the messages \(\mu _i\) and \(\mu _{(i,j)}\) are indeed signed, and that the membership proofs for \(\varepsilon _i\) establish that \(\varepsilon _i \in {\varXi }_\mathcal {V} \), i.e., are certified vertex identifiers (the CL multi-show unlinkability ensures that the verifier learns no other information about \(\varepsilon _i\)). The CG-OR proofs [22] yield that \(\gamma _i\) and \(\gamma _{(i,j)}\) must encode valid vertex label identifiers (but yield no further information on the labels). Therefore, we have fixes the roots \(\mu _i, \mu _{(i,j)}\) and the leaves \(\varepsilon _i, \gamma _i, \gamma _{(i,j)}\) of the proof tree in the CL-notation.
It remains to show what can be derived from the equations that connect the roots to the leaves in the vertex and edge composition statements and from the pairwise difference. The technique used is a standard decomposition of certified messages in Integer commitments to make their components accessible to discrete-logarithm based proofs of knowledge; if the same secret is referenced we have an equality proof, if not there is no further information learned about the relation of the secrets. For the vertices, the equation \(C_i \equiv \pm \breve{C}_i^{\gamma _i} S^{\rho _{i}'}\) (4) establishes that \(\mu _i = \varepsilon _i\gamma _i\), given that the prover does not know a multiple of the group order, \(\breve{C}_i\) separates out \(\varepsilon _i\) connected to the membership proof. For edges, the equation \(C_{(i,j)} \equiv \pm \breve{C}_{(i,j)}^{\gamma _{(i,j)}} S^{\rho _{(i,j)}'} \)(7) establishes that \(\mu _{(i,j)} = \mu _{(i,j)}'\gamma _{(i,j)}\), where \(\breve{C}_{(i,j)}\) is shown to contain a product \(\dot{\varepsilon }_i \dot{\varepsilon }_j\) in equation (3), which are in turn shown to be valid vertex identifiers (8). By that all variables are bound and the connection between the roots and the leaves established.
Finally, we claim pair-wise difference on vertices from the equation
Unless the prover knows a multiple of the group order or the discrete logarithm \(\log _R S\), the following equation must hold over the integers:
It is well-known that \(\alpha _{i,j}\) and \(\beta _{i,j}\) only exist if \(\varepsilon _i\) and \(\varepsilon _j\) are coprime, which gives us the pair-wise difference claimed.
1.1 10.1 Graph 3-Colorability (G3C)
Proof
(Graph 3-Colorability: Lemma 1 ).
1. Proof of Knowledge. It is standard to show that there exists a knowledge extractor for all exponents of the proof such that the equality of exponents equations are fulfilled.
We obtain from Clause 1 that the prover knows the representation of a CL-Signature of the given structure. From the existential unforgeability of CL-Signatures, we see that the issuer must have signed the secret attributes \(\mu _i\), \(\mu _j\) and \(\mu _{(i,j)}\). Proving equality of exponents with corresponding integer commitments is standard, by which the arguments over the commitments, such as \(C_i\), \(\breve{C}_i\) and \(C_{(i,j)}\) transfer to the structure of the signed messages.
The Clause 4 shows that a message \(\mu _i\) consists of two factors known to the prover: \(\mu _i = \varepsilon _i \gamma _i\). The following Clause 5 employs a set membership proof to show that \(\varepsilon _i \in {\varXi }_\mathcal {V} \) and that \(\gamma _i \in {\varXi }_\mathcal {L} \). We use that the set membership from Sect. 2.5 guarantees that \(\varepsilon _i\) and \(\gamma _i\) are exactly one member of the set to conclude that a message \(\mu _i\) contains exactly one vertex identifier and one label identifier. Thus, \(\mu _i\) is well-formed. Similarly, Clause 7 establishes the structure \(\mu _{(i,j)} = \varepsilon _i \varepsilon \) for the edge (i, j), showing it to be well-formed. Because the prover is not privy to the group order, these statements hold over the integers, by the results of Damgård and Fujisaki [6]. Therefore, with the proof of representation including pair-wise difference, we conclude that the signed graph is well-formed.
Clause 8 shows that the labeling \(f_\mathcal {V} \) of the signed graph is a proper coloring. Again, we employ Damgård and Fujisaki’s [6] result that equations hold over the integers. We have that for each edge (i, j), the corresponding signed messages have the following structure:
We show that the secret labels \(\gamma _i\) and \(\gamma _j\) are different by showing that \(\mu _i\) and \(\mu _j\) are coprime, where we use Bézout’s Identity:
The equality of exponent proof of Clause 8 achieves this as follows
From this equation we can conclude that \(\mathsf {gcd}(\mu _i, \mu _j) = 1\) and that, therefore, \(\gamma _i \ne \gamma _j\), which implies that \(f_\mathcal {V} (i) \ne f_\mathcal {V} (j) \) and that the CL signature indeed contains a proper coloring. \(\Box \)
2. Zero-Knowledge. We claim that proof does not disclose anything else than the statement made that the prover knows a CL-Signature of a proper coloring on known graph \(\mathcal {G} \).
The \({\varSigma }\)-proofs here are zero-knowledge in an honest verifier setting if performed with multiple rounds and small challenges. It is standard to construct a simulator for all \({\varSigma }\)-proofs of representation for the CL-Signature and the commitments as well as for their conjunction [18, 19], showing that the verifier does not learn anything else than the relations on exponents shown.
It remains to be shown what the relations disclose. We will argue on the statements made on the secret messages \(\gamma _i\), which contain the color. Clause 4 establishes that \(\gamma _i\) is part of commitment \(C_i\), but does not disclose further information than the equality of exponents.
Clause 5 proves that \(\gamma _i\) is a member of the set \({\varXi }_\mathcal {L} = \{ e_\mathsf {R}, e_\mathsf {G}, e_\mathsf {B} \}\). This statement itself is part of the known problem definition of G3C. The set membership proof is a proof of representation for an anonymized CL-Signature and a standard proof of equality of exponents, and thereby, does not disclose further information.
Finally, Clause 8 references \(\mu _i = \epsilon _i \gamma _i\) to prove that \(\gamma _i\) and \(\gamma _j\) of an adjacent edge are coprime. As the vertex identifiers are pair-wise different by definition and as all representatives are primes, this only establishes that \(\gamma _i \ne \gamma _j\) as required by the G3C problem, but nothing else.\(\quad \square \)
Proof
(Polynomial Proof of G3C: Lemma 2 ).
Precomputation: The prover computes \(2 n +1\) signature randomizations with one exponentiation each and \(2 n + m \) integer commitments with 2 exponentiations each. The pre-computation phase uses \(6 n +2 m +1\) exponentiations, transmits \(4 n + m +1\) group elements, and thereby has a computation complexity of \(O( n + m )\) and a communication complexity of \(O( n + m )\).
Proof of Knowledge: The Schnorr proofs in the proof of knowledge are zero-knowledge if executed with small challenges over multiple rounds and can be connected with techniques from Cramer et al. [18]. The round complexity of the overall protocol is dependent on the proof mode (cf. Brands [17]).
Clause 1 is executed once yielding a Schnorr proof with \( n + m +2\) exponentiations for the prover. The clauses 2 are executed once for each vertex, such as i and j, Therefore we have \( n \) Schnorr proofs with 2 exponentiations each for the prover. The clauses 3 are executed once for each edge (i, j), making \( m \) Schnorr proofs with 2 exponentiations each for the prover. The clauses 4 are executed once for each vertex, such as i or j. We have \(2 n \) Schnorr proofs with 2 exponentiations each for the prover. The set membership proofs of Clauses 5 are executed once for each vertex and its label. Each set membership proof is a proof of representation of a designated CL-Signature for the set member, amounting to 3 exponentiations for the prover. In total, we have \(2 n \) such proofs of possessions, all done with a single Schnorr proof proving equality of exponents with the corresponding commitment. Clause 7 proves the edge structure and is executed once per edge, yielding \( m \) Schnorr proofs with 2 exponentiations each for the prover. Finally, the proper graph coloring in Clause 8 is shows once for each edge (i, j) amounting to \( m \) Schnorr proofs with 3 exponentiations for the prover.
The proof of knowledge of graph coloring thereby requires \(5 n \) + \(3 m +1 = O( n + m )\) Schnorr proofs with a computational complexity for the prover of \(13 n +8 m +2 = O( n + m )\) exponentiations. The total computational complexity is therefore \(O( n + m )\), the communication complexity is \(O( n + m )\) group elements. The G3C proof is done in polynomial time. The round complexity depends on the proof mode, where variants with multiple rounds (number of rounds depending on the error probability), with four rounds and initial commitments of the verifier on challenges, and three rounds in a \({\varSigma }\)-proof (not zero-knowledge) are possible.\(\quad \square \)
1.2 10.2 CL Proof Systems for NP-Statements
Proof
(Sketch NP-Statements: Theorem 5 ). Let a NP language \(\mathfrak {L} \) be given. Let \(\tau \) be a polynomial-time computable and invertible reduction from \(\mathfrak {L} \) to Graph 3-Colorability (G3C): \(\tau \) can be constructed by composing a polynomial-time reduction of \(\mathfrak {L} \) to 3SAT by Cook’s proof [27] and a polynomial-time reduction from 3SAT to G3C. We have that \(x \in \mathfrak {L} \) iff \(\tau (x)\) is 3-colorable.
On common input x, both prover and verifier compute graph \(G \leftarrow \tau (x)\). In Goldreich, Micali and Widgerson’s work, the proof proceeds to use any interactive zero-knowledge proof system to prove that G is 3-colorable and thereby show that \(x \in \mathfrak {L} \). Our proof continues from this point to show that there exists a Camenisch-Lysyanskaya proof system.
On obtaining \(\mathcal {G} = \tau (x)\), the prover constructs a graph commitment C on \(\mathcal {G} \) as defined in Sect. 3, including a labeling \(f_\mathcal {V} \) of a proper coloring of \(\mathcal {G} \). The known-graph proof transmits \(\mathcal {G} \) itself, yet keeps the proper coloring confidential as default.
Proof of Representation \(\mathsf {P} \!\rightarrow \mathsf {I} \!:\) The prover interacts with an CL-Signature issuer, proving representation and well-formedness of the commitment C in a known-graph proof, disclosing information to satisfy the verification requirements of the issuer. As \(\tau (x)\) is invertible, this proof of representation of G and the proper coloring serves as proof of representation for x and \(x \in \mathfrak {L} \).
Issuing \(\mathsf {I} \!\rightarrow \mathsf {P} \!:\) Upon acceptance of the proof, the issuer signs the committed graph \(\mathcal {G} \) in a CL-Signature \(\sigma \). Given the invertibility of \(\tau \), this signature holds for x as well. sigma is a CL-Signature on \(\tau (x)\) and the proper coloring of \(\tau (x)\) iff \(x \in \mathfrak {L} \).
Proof of Possession \(\mathsf {P} \!\rightarrow \mathsf {V} \!:\) The prover interacts with the verifier to proof knowledge of the CL-Signature \(\sigma \) on a proper coloring on \(\mathcal {G} \) and thereby shows graph 3-colorability of \(\tau (x)\), which holds iff \(x \in \mathfrak {L} \). Thereby, the proof of possession of \(\sigma \) translates to a proof of possession of the statement \(x \in \mathfrak {L} \). The proof is zero-knowledge if executed with small challenges over multiple rounds.\(\quad \square \)
Rights and permissions
Copyright information
© 2015 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Groß, T. (2015). Signatures and Efficient Proofs on Committed Graphs and NP-Statements. In: Böhme, R., Okamoto, T. (eds) Financial Cryptography and Data Security. FC 2015. Lecture Notes in Computer Science(), vol 8975. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-662-47854-7_18
Download citation
DOI: https://doi.org/10.1007/978-3-662-47854-7_18
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-662-47853-0
Online ISBN: 978-3-662-47854-7
eBook Packages: Computer ScienceComputer Science (R0)