BRICS RS-01-41 Damgård & Nielsen: Universally Composable Commitments with Constant Expansion Factor BRICS

Basic Research in Computer Science

Perfect Hiding and Perfect Binding Universally Composable Commitment Schemes with Constant Expansion Factor

Ivan B. Damgård Jesper Buus Nielsen

BRICS Report Series RS-01-41 ISSN 0909-0878 October 2001 Copyright \begin{matrix}c \\ ◯ \end{matrix} 2001, Ivan B. Damgård & Jesper Buus Nielsen.

BRICS, Department of Computer Science University of Aarhus. All rights reserved.

Reproduction of all or part of this work is permitted for educational or research use on condition that this copyright notice is included in any copy.

See back inner page for a list of recent BRICS Report Series publications. Copies may be obtained by contacting:

BRICS Department of Computer Science University of Aarhus Ny Munkegade, building 540 DK–8000 Aarhus C Denmark

Telephone: +45 8942 3360
Telefax: +45 8942 3255
Internet: BRICS@brics.dk

BRICS publications are in general accessible through the World Wide Web and anonymous FTP through these URLs:

http://www.brics.dk
ftp://ftp.brics.dk

This document in subdirectory RS/01/41/

Perfect Hiding and Perfect Binding Universally Composable Commitment Schemes with Constant

Expansion Factor

Ivan Damgård  Jesper B. Nielsen

October, 2001

Abstract

Canetti and Fischlin have recently proposed the security notion universal composability for commitment schemes and provided two examples. This new notion is very strong. It guarantees that security is maintained even when an unbounded number of copies of the scheme are running concurrently, also it guarantees non-malleability, resilience to selective decommitment, and security against adaptive adversaries. Both of their schemes uses Θ(k) bits to commit to one bit and can be based on the existence of trapdoor commitments and non-malleable encryption.

We present new universally composable commitment schemes based on the Paillier cryptosystem and the Okamoto-Uchiyama cryptosystem. The schemes are efficient: to commit to k bits, they use a constant number of modular exponentiations and communicates O(k) bits. Further more the scheme can be instantiated in either perfectly hiding or perfectly binding versions. These are the first schemes to show that constant expansion factor, perfect hiding, and perfect binding can be obtained for universally composable commitments.

We also show how the schemes can be applied to do efficient zeroknowledge proofs of knowledge that are universally composable.

Contents

1 Introduction 4

2 An Intuitive Explanation of some Main Ideas 5

3 Mixed Commitments 7 3.1 Σ-protocols . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8 3.2 Proof of Relation between Mixed Commitments . . . . . . . . . 9 3.3 Security under Lunchtime Opening . . . . . . . . . . . . . . . . 10

4 Universally Composable Commitments 15 4.1 The General Framework . . . . . . . . . . . . . . . . . . . . . . 15 4.2 The Commitment Functionality . . . . . . . . . . . . . . . . . . 17 4.3 The Common Reference String Model . . . . . . . . . . . . . . 18

5 UCC with Constant Expansion Factor 18 5.1 The Commitment Scheme . . . . . . . . . . . . . . . . . . . . . 19 5.2 The Simulator . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20 5.3 Analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22 5.4 Perfect Hiding and Perfect Binding . . . . . . . . . . . . . . . . 25

6 A Special Mixed Commitment Scheme based on the p-Subgroup Assumption 27 6.1 Key Space, Message Space, and Committing . . . . . . . . . . . 27 6.2 Equivocability . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27 6.3 Extraction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28 6.4 The Transformation . . . . . . . . . . . . . . . . . . . . . . . . 28 6.5 Proof of Commitment to 0 (Base Scheme) . . . . . . . . . . . . 28 6.6 Proof of Commitment to 1 (Base Scheme) . . . . . . . . . . . . 29 6.7 Monotone Logical Combination of Non-Erasure Σ-Protocols . . 29 6.8 Proof of Binary Boolean Relations . . . . . . . . . . . . . . . . 30

7 A Special Mixed Commitment Scheme based on the DCRA 31 7.1 Key Space, Message Space, and Committing . . . . . . . . . . . 31 7.2 Equivocability . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32 7.3 Extraction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32 7.4 The Transformation . . . . . . . . . . . . . . . . . . . . . . . . 32 7.5 Proof of Multiplicative Relation . . . . . . . . . . . . . . . . . . 32 7.6 Proof of Identity and Proof of Additive Relation . . . . . . . . 36 7.7 Proof of Binary Boolean Relations . . . . . . . . . . . . . . . . 37 8 Efficient Universally Composable Zero-Knowledge Proofs 37

8.1 Exploiting the Multi-Bit Commitment Property . . . . . . . . . 37 8.2 Exploiting Efficient Proofs of Relations . . . . . . . . . . . . . . 41

1 Introduction

The notion of commitment is one of the most fundamental primitives in both theory and practice of modern cryptography. In a commitment scheme, a committer chooses an element m from some finite set M, and releases some information about m through a commit protocol to a receiver. Later, the committer may release more information to the receiver to open his commitment, so that the receiver learns m. Loosely speaking, the basic properties we want are first that the commitment scheme is hiding: a cheating receiver cannot learn m from the commitment protocol, and second that it is binding: a cheating committer cannot change his mind about m, the verifier can check in the opening that the value opened was what the committer had in mind originally. Each of the two properties can be satisfied unconditionally or relative to a complexity assumption.

A very large number of commitment schemes are known based on various notions of security and various complexity assumptions. Although commitment schemes can be implemented as a game between more than two players, we will concentrate here on the two-player case with standard digital communication. This immediately implies that we cannot build schemes where both the binding and the hiding properties are satisfied unconditionally.

In [CF01] Canetti and Fischlin proposed a new security measure for commitment schemes called universally composable commitments. This is a very strong notion: it guarantees that security is maintained even when an unbounded number of copies of the scheme are running concurrently in an asynchronous way. It also guarantees non-malleability and resilience to selective decommitment, and finally it maintains security even if an adversary can decide adaptively to corrupt some of the players and make them cheat. The new security notion is based on the framework for universally composable security in [Can01]. In this framework one specifies desired functionalities by specifying an idealized version of them. An idealized commitment scheme is modeled by assuming a trusted party to which both the committer and the receiver have a secure channel. To commit to m, the committer simply sends m to the trusted party who notifies the receiver that a commitment has been made. To open, the committer asks the trusted party to reveal m to the receiver. Security of a commitment scheme now means that the view of an adversary attacking the scheme can be simulated given access to just the idealized functionality.

It is clearly important for practical applications to have solutions where only the two main players need to be active. However, in [CF01] it is shown that universal composability is so strong a notion that no universally composable commitment scheme for only two players exist. However, if one assumes that a common reference string with a prescribed distribution is available to the players, then two-player solutions do exist and two examples are given in [CF01]. Note that common reference strings are often available in practice, for instance if a public key infrastructure is given.

The commitment scheme(s) from [CF01] uses Ω(k) bits to commit to one bit, where k is a security parameter, and it guarantees only computational hiding and binding. In fact, as detailed later, one might even get the impression from the construction that perfect hiding, respectively binding cannot be achieved. Here, by perfect, we mean that an unbounded receiver gets zero information about m, respectively an unbounded committer can change his mind about m with probability zero.

Our contribution is a new construction of universally composable commitment schemes, which uses O(k) bits of communication to commit to k bits. The scheme can be set up such that it is perfectly binding, or perfectly hiding, without loosing efficiency^{1}. The construction is based on a new primitive which we call a mixed commitment scheme. We give two efficient implementations of mixed commitments, one based on the Paillier cryptosystem and one based on the Okamoto-Uchiyama cryptosystem. Our commitment protocol has three moves, but the two first messages can be computed independently of the message committed to and thus the latency of a commitment is still one round as in [CF01].

As a final contribution we show that if a mixed commitment scheme comes with protocols in a standard 3-move form for proving in zero-knowledge relations among committed values, the resulting UCC commitment scheme inherits these protocols, such that usage of these is also universally composable. For our concrete example schemes, this results in efficient protocols for proving binary Boolean relations among committed values and also (for the version based on Paillier encryption) additive and multiplicative relations modulo N among committed values. We discuss how this can be used to construct efficient universally composable zero-knowledge proofs of knowledge for NP, improving the complexity of a corresponding protocol from [CF01].

2 An Intuitive Explanation of some Main Ideas

In the simplest type of commitment scheme, both committing and opening are non-interactive, so that committing just consists of running an algorithm commit_{K}, keyed by a public key K, taking as input the message m to be committed to and a uniformly random string r. The committer computes c ← commit_{K}(m, r), and sends c to the receiver. To open, the committer sends m and r to the receiver, who checks that c = commit_{K}(m, r). For this type of scheme, hiding means that given just c the receiver does not learn m and binding means that the committer cannot change his mind by computing m′, r′, where c = commit(m′, r′) and m′ ≠ m.

1[CF01] also contains a scheme which is statistically binding and computationally hiding, the scheme however requires a new setup of the common reference string per commitment and is thus mostly interesting because it demonstrates that statistically binding can be obtained at all.

In a trapdoor scheme however, to each public key K a piece of trapdoor information t_{K} is associated which, if known, allows the committer to change his mind. Note that the existence of such trapdoor information implies that the scheme can never be unconditionally binding. Most trapdoor schemes even have the property that from t_{K}, one can compute commitments that can be opened in any way desired. Such trapdoor schemes are called equivocable.

One may also construct schemes where a different type of trapdoor information d_{K} exists, such that given d_{K}, one can efficiently compute m from commit(m, r). Such schemes are called extractable and clearly cannot be unconditionally hiding.

As mentioned, the scheme in [CF01] guarantees only computational binding and computational hiding. Actually this is important to the construction: recall that to prove security, we must simulate an adversary’s view of the real scheme with access to the idealized model only. Now, if the committer is corrupted by the adversary and sends a commitment c, the simulator must find out which message was committed to, and send it to the trusted party in the ideal model. The universally composable framework makes very strict demands to the simulation implying that rewinding techniques cannot be used for extracting the message. A solution is to use an extractable scheme, have the public key K in the reference string, and set things up such that the simulator knows the trapdoor d_{k}. A similar consideration leads to the conclusion that if instead the receiver is corrupt, the scheme must be equivocable with trapdoor known to the simulator, because the simulator must generate a commitment on behalf of the honest committer before finding out from the trusted party which value was actually committed to. So to build universally composable commitments it seems we must have a scheme that is simultaneously extractable and equivocable — although such a scheme can of course only be computationally secure. This is precisely what Canetti’s and Fischlin’s ingenious construction provides.

In this paper, we propose a different technique for universally composable commitments based on what we call a mixed commitment scheme. A mixed commitment scheme is basically a commitment scheme which on some of the keys is perfectly hiding and equivocable, we call these keys the E-keys, and on some of the keys is perfectly binding and extractable, we call these keys the X-keys. Clearly, no key can be both an X- and an E-key, so if we were to put the entire key in the common reference string, either extractability or equivocability would fail and the simulation could not work. We remedy this by putting only a part of the key, the so-called system key, in the reference string. The rest of the key is set up once per commitment using a two-move protocol.

This allows the simulator to force the key used for each commitment to be an E-key or an X-key depending on whether equivocability or extractability is needed. In other words, our observation is that successful simulation does not really require a scheme that is globally extractable and simulatable at the same time, it is enough if the simulator can decide between extractability and equivocability on a per commitment basis.

Our basic construction is neither perfectly binding nor perfectly hiding because the set-up of keys is randomized and is not guaranteed to lead to any particular type of key. However, one may add to the reference string an extra key that is guaranteed to be either an X- or an E-key. Using this in combination with the basic scheme, one can obtain either perfect hiding or perfect binding.

3 Mixed Commitments

We now give a more formal description of mixed commitment schemes. The most important difference to the intuitive discussion above is that the system key N comes with a trapdoor t_{N} that allows efficient extraction for all X-keys. The E-keys, however, each come with their own trapdoor for equivocability.

Definition 1 By a mixed commitment scheme we mean a commitment scheme commit_{K} with some global system key N, which determines the message space M_{N} and the key space K_{N} of the commitments. The key space contains two sets, the E-keys and the X-keys, for which the following holds:

Key generation One can efficiently generate a system key N along with the so-called X-trapdoor t_{N}. One can, given the system key N, efficiently generate random commitment keys and random X-keys. Given the system key, one can efficiently generate an E-key K along with the so-called E-trapdoor t_{K}.

Key indistinguishability Random E-keys and random X-keys are both computationally indistinguishable from random keys as long as the X-trapdoor is not known.

Equivocability Given E-key K and E-trapdoor t_{K} one can generate fake commitments c, distributed exactly as real commitments, which can later be open arbitrarily, i.e. given a message m one can compute uniformly random r for which c = commit_{K}(m, r).

Extraction Given a commitment c = commit_{K}(m, r), where K is an Xkey, one can given the X-trapdoor t_{N} efficiently compute m, where m is uniquely determined by the perfect binding.

Note that the indistinguishability of random E-keys, random X-keys, and random keys implies that as long as the X-trapdoor is not known the scheme is computationally hiding for all keys and as long as the neither the X-trapdoor nor the E-trapdoor is known the scheme is computationally binding for all keys.

For the construction in the next section we will need a few special requirements on the mixed commitment scheme.

First of all we will assume that the message space M_{N} and the key space K_{N} are finite groups in which we can compute efficiently. We will denote the group operation by +. There are no special requirements on the group structure; If e.g. the key space is the set of all bit-strings of some fixed length l, the group operation could be the xor operation on strings or addition modulo 2^{l}. Second we need that the number of E-keys over the total number of keys is negligible and that the number of X-keys over the total number of keys is negligible close to 1. Note that this leaves only a negligible fraction which is neither X-keys nor E-keys. We call a mixed commitment scheme with these properties a special mixed commitment scheme.

The last requirement is that the scheme is on a particular form. We ensure this be a transformation. The keys for the transformed scheme will be of the form (K_{1}, K_{2}). We let the E-keys be the pairs of E-keys and let the X-keys be the pairs of X-keys. Note that this leaves a negligible fraction of the keys which is neither E-keys nor X-keys. The message space will be the same. Given a message m we commit as (commit_{K_{1}}(\overline{m}_{1}), commit_{K_{2}}(\overline{m}_{2})), where \overline{m}_{1} and \overline{m}_{2} are uniformly random values for which m = \overline{m}_{1} + \overline{m}_{2}. Note that if both keys are X-keys, then \overline{m}_{1} and \overline{m}_{2} and thus m can be computed by extraction. It is trivial to check that all other properties of a special mixed commitment scheme are also maintained under this transformation.

3.1 Σ-protocols

For the mixed commitment schemes we exhibit later, there are efficient protocols for proving in zero-knowledge relations among committed values. Depending on the mixed commitment scheme used, a number of relations between committed values could be considered, e.g equality, additive, or multiplicative relations between committed values. As we shall see, it is possible to have the derived universally composable commitment schemes inherit these protocols while maintaining universal composability. In order for this to work, we need the protocols to have a special form:

A non-erasure Σ-protocol for relation R is a protocol for two parties, called the prover P and the verifier V. The prover gets as input (x, w) ∈ R, the verifier gets as input x, and the goal is for the prover to convince the verifier that he knows w such that (x, w) ∈ R, without revealing information about w.

We require that it is done using a protocol of the following form. The prover first computes a message a ← A(x, w, r_{a}), where r_{a} is a uniformly random string, and sends a to V. Then V returns a random challenge e of length l. The prover then computes a responds to the challenge z ← Z(x, w, r_{a}, e), and sends z to the verifier. The verifier then runs a program B on (x, a, e, z) which outputs b ∈ {0, 1} indicating where to believe that the prover knows a valid witness w or not.

Besides the protocol being of this special three-move form we furthermore require that the following requirements hold, in order for the protocol to be called a non-erasure Σ-protocol for R.

Completeness If (x, w) ∈ R, then the verifier always accepts (b = 1).

Special Honest Verifier Zero-Knowledge There exists a PPT algorithm, the honest verifier simulator hvs, which given instance x (where there exists w such that (x, w) ∈ R) and any challenge e ∈ {0, 1}^{l} generates (a, z) ← hvs(x, e, r), where r is a uniformly random string, such that (x, a, e, z) is distributed identically to a successful conversation, where e occurs as challenge.

State Construction Given (x, w, a, e, z, r), where (a, z) = hvs(x, e, r) and (x, w) ∈ R it should be possible to compute uniformly random r_{a} for which a = A(x, w, r_{a}) and z = Z(x, w, r_{a}, e).

Special Soundness There exists a PPT algorithm extract, which given x, (a, e, z), and (a, e′, z′), where e ≠ e′, B(x, a, e, z) = 1, and B(x, a, e′, z′) = 1, outputs w ← extract(x, a, e, z, e′, z′) such that (x, w) ∈ R.

In [Dam00] it is shown how to use Σ-protocols in a concurrent setting. This is done by letting the first message be a commitment to a and then letting the third message be (a, r, z), where (a, r) is an opening of the commitment and z is computed as usual. If the commitment scheme used is a trapdoor commitment scheme this will allow for simulation using the honest verifier simulator. In an adaptive non-erasure setting, where an adversary can corrupt parties during the execution, it is also necessary with the State Construction property as the adversary is entitled to see the internal state of a corrupted party. In the following we call r_{a} the internal state of the Σ-protocol.

3.2 Proof of Relation between Mixed Commitments

In order to use non-erasure Σ-protocols in our context, it is convenient to specialize the above definition somewhat. We therefore now review the notion of a Σ-protocol in the context of mixed commitment schemes.

Let M_{N} be the message space for system key N and let R^{M} ⊂ M_{N}^{a} be a a-ary relation over M. We denote a commitment by (K_{1}, c_{1}, K_{2}, c_{2}), where K_{1}, K_{2} ∈ K_{N} and c_{1} and c_{2} are commitments in the base scheme under K_{1} respectively K_{2}. From a relation on M_{N}^{a} we can define a binary relation on commitments, where

(((K_{1}, c_{1}, K_{2}, c_{2}), …, (K_{2a−1}, c_{2a−1}, K_{2a}, d_{2a})), (m_{1}, r_{1}, …, m_{2a}, r_{2a})) ∈ R

iff

(⋀_{i=1}^{2a} c_{i} = commit_{K_{i}}(m_{i}, r_{i})) ∧ (m_{1} + m_{2}, …, m_{2a−1} + m_{2a}) ∈ R^{M} .

The instance is x = (K_{1}, c_{1}, K_{2}, c_{2}, …, K_{2a}, c_{2a}) and the witness is w = (m_{1}, r_{1}, m_{2}, r_{2}, …, m_{2a}, r_{2a}).

Because of the particular context in which we will be using the proofs, it is enough that the special honest verifier zero-knowledge and the state construction holds for E-keys and fake commitments, and that the special soundness holds for X-keys. More precisely, we assume that

1. In the honest verifier simulator and the state construction

(a) All the keys K_{1}, K_{2}, …, K_{2a} are E-keys and the E-trapdoors of the keys K_{b}, K_{2+b}, …, K_{2(a−1)+b} are known, where b is either 1 and 2 and is not known before the simulation.

(b) The commitments c_{b}, c_{2+b}, …, c_{2(a−1)+b} are fake commitments (under the above keys) and the random bits used to construct them are known and the commitments c_{2−b}, c_{4−b}, …, c_{2a−b} are commitments to random values and their openings are known.

(c) The witnesses given in the state construction are consistent with the above information. One can think of the input to the state construction as a real opening of the fake commitments c_{b}, c_{2+b}, …, c_{2(a−1)+b}, where for the given opening (m_{1}+m_{2}, …, m_{2a−1}+m_{2a}) ∈ R^{M}. The job of the state construction is then to come up with an internal state consistent with these openings.

2. In the special soundness, given two accepting conversations one must compute either a valid witness or a proof that one of the involved keys is not an X-key. The proof must point to the key which is not an X-key.

3.3 Security under Lunchtime Opening

In the following constructions, we will need to use a mixed commitment scheme in a coin-flip protocol for generating random keys, and also for committing to the first message in Σ-protocols. In order for this to work, we need that the scheme satisfies the following: an adversary who sees a number of fake commitments under E-keys and is allowed adaptively to specify how they should be opened, is nevertheless unable to produce such an arbitrary opening himself. It is advantageous to prove this as a lemma at the current abstraction level.

So let A be a PPT algorithm and consider the following game, which we call the lunchtime opening game. First we generate a system key N and hand N to A. Let E denote a subset of M_{N} for which \frac{|E|}{|M_{N} |} is negligible. Then during the game A can issue the following types of requests.

Generate Key If A requests a key generation we generate a random E-key K = (K_{1}, K_{2}) along with the E-trapdoor t_{K_{b}} of either K_{1} or K_{2} and hand K to A. The same b is used for all keys.

Generate Commitment If A requests a commitment generation for a key K = (K_{1}, K_{2}) earlier generated in a Generate Key request, we generate a random fake commitment c = (c_{1}, c_{2}) under K = (K_{1}, K_{2}) using t_{K_{b}} and hand c to A. The fake commitment is generated by committing honestly to a random message under K_{2−b}, c_{2−b} = commit_{K_{2−b}}(m_{2−b}, r_{2−b}), and faking under K_{b}.

Open c If A requests to open a commitment c to message m, where c was generated in a Generate Commitment request and has not earlier been requested opened, then we let m_{b} = m − m_{2−b} and generate uniformly random bits r_{b} for which c_{b} = commit_{K}(m_{b}, r_{b}) and hand (m_{1}, m_{2}, r_{1}, r_{2}) to A.

Prove Relation R((K_{1}, c_{1}), …, (K_{a}, c_{a})) using K If A requests receiving a proof of R((K_{1}, c_{1}), …, (K_{a}, c_{a})) using key K = (K_{1}, K_{2}), where K was generated due to a Generate Key request and c_{1}, …, c_{a} was generated due to Generate Commitment requests, then using a non-erasure Σprotocol for the relation we do as follows: Generate a fake commitment c using t_{K_{b}} and send it to A. Receive a challenge from A and using the honest verifier simulator compute (a, z) and using t_{K_{b}} compute uniformly random r for which c = commit_{K}(a, r). Then send (a, r, z) to A.

It must be possible to open any unopened commitment among (c_{1}, …, c_{a}) in a way consistent with the relation R and A must never request opened any unopened commitment in a way inconsistent with the relation R.

If A later has requested all of c_{1}, …, c_{a} opened, then by the above restriction the openings are a witness for the relation and using the state construction property we can compute the internal state r_{a} of the Σprotocol and hand it to A.^{2}

Test on c using K If A requests a test on commitment c and key K, where c can either be a commitment generated for K due to a Generate Commitment request or by A alone, we hand A as challenge a uniformly random element m_{1} from M_{N}. Then A returns m_{2}, r_{2}. If c = commit_{K}(m_{2}, r_{2}) and m_{1} + m_{2} ∈ E, then A scores one point.

Test on R((K_{1}, c_{1}), …, (K_{a}, c_{a})) using K On a proof of relation test A proves the relation as in the proof of relation test (with the roles changed). We require that K was generated due to a Generate Key request and that each of the K_{i} was either generated due to a Generate Key request or is an X-key.

If A succeeds in the proof and can ever come up with openings c_{j} = commit_{K_{j}}(m_{j}, r_{j}) of the E-commitments such that R(m_{1}, …, m_{a}) does not hold, where the value m_{i} for the X-commitments are defined by extraction, then he scores one point.

We allow the interactions between A and the game to be scheduled arbitrarily by A, meaning that e.g. two proofs of relation can be run concurrently. However, we enforce a two phase structure on the game by requiring that after the first test request is issued by A, only test requests can be issued in the following. Further more, after the first test request is issued, all proof of relation requests that are not ended yet is terminated, meaning that if A returns the challenge after the first test request, the challenge will not be answered. Note that this means that after the first test request, the game does not need the trapdoors t_{K_{b}} anymore. This is essential in proving the following lemma.

Lemma 1 Any special mixed commitment scheme has the property that the expected score of any PPT algorithm A in the lunchtime opening game against the scheme is negligible.

Proof: Assume for the sake of contradiction that there exists some PPT algorithm A which has an expected score which is significant^{3}. Now consider the following experiment. We run the game with A as specified above with two modifications.

First of all, each time A sends m_{2}, r_{2}, where c = commit_{K}(m_{2}, r_{2}) in a Test on c using K, save the state of A and rewind it to the point, where m_{1} was send. Then repeat the following until A returns m′_{2}, r′_{2}, where c = commit_{K}(m′_{2}, r′_{2}):

2Note that the honest verifier simulator and the state construction were used in a context meeting the relaxations we put on the protocols in the previous section.

3We are using significant to denote ’not negligible’.

Generate a new random m′_{1} and give it to A. Then run A until either A returns m′_{2}, r′_{2} or A stops. When the challenge has been answered correctly again, continue the game at the saved state.

Further more, each time A answers a challenge correctly in a proof of relation test save the state of A and rewind to the point where that challenge was send. Then repeat the following until a challenge for that particular proof of relation test is answered correctly again: Generate a new random challenge and give it to A and run A until either the challenge is answered correctly again or A stops. When the challenge has been answered correctly again continue the game at the saved state.

We will argue that the expected running time of this experiment is polynomial in k. The experiment is of the form that each time certain challenges are answered correctly by A we replay until a challenge is answered correctly again. It is enough to prove that the expected running time of each of these replays is polynomial. For this purpose let E denote the event that challenge l is answered correctly and let Pr[E|s] denote the probability that challenge l is answered correctly given that the experiment is in state s at the time the challenge is given. Let Pr[s|E] denote the probability that the experiment was in state s at the time challenge l was given conditioned on the event that the challenge was answered correctly. Let T (s) be the expected running time of the game given that it is in state s at the time challenge l is given, let T_{1}(s) denote the expected running time of the game from challenge l is given to the end of the game given that the challenge is not answered correctly and let T_{2}(s) denote the running time from challenge l is given until it is answered correctly (given that it is answered correctly). Then T (s) ≥ (1 − Pr[E|s])T_{1}(s) + Pr[E|s]T_{2}(s) and the time spend in loop l is

Pr[E] ∑_{s} Pr[s|E] (∑_{i=1}^{∞}(1 − Pr[E|s])^{i−1} Pr[E|s]((i − 1)T_{1}(s) + T_{2}(s)))

= Pr[E] ∑_{s} \frac{Pr[s|E] Pr[E|s]}{(1 − Pr[E|s])} ∑_{i=1}^{∞}(iT_{1}(s) + (T_{2}(s) − T_{1}(s)))(1 − Pr[E|s])^{i}

= Pr[E] ∑_{s} Pr[s|E] (\frac{T_{1}(s)}{Pr[E|s]} + (T_{2}(s) − T_{1}(s)))
= Pr[E] ∑_{s} \frac{Pr[s|E]}{Pr[E|s]} ((1 − Pr[E|s])T_{1}(s) + Pr[E|s]T_{2}(s))
≤ ∑_{s} Pr[s]T (s) = T ,

which is polynomial.

By the linearity of expectation there must be an opening challenge l where the challenge is answered correctly and m_{1} + m_{2} ∈ E with significant probability or there must be a successful proof of relation test for which A returns a contradictory opening with significant probability. We will argue that this means that the experiment generates a double opening with significant probability.

Consider the first case. Let p be a polynomial for which the probability that m_{1} + m_{2} ∈ E is larger than p^{−1}(k) for infinitely many k and consider a value of k for which this is the case. Assume that the challenge is answered correctly and m_{1}+m_{2} ∈ E. Let \overline{E} = m_{2}⊕E. Since \frac{|\overline{E}|}{|M|} = \frac{|E|}{|M|} is negligible and the expected number of iterations in the loop is less than p(k) we have that when a challenge m′_{1} is answered correctly again Pr[m′_{1} ∉ \overline{E}] = 1 − ϵ, where ϵ is negligible. Further more Pr[m′_{1} ⊕ m′_{2} ∈ E] ≥ p^{−1}(k). Thus Pr[m′_{1} ⊕ m′_{2} ∈ E ∧ m′_{1} ∉ \overline{E}] ≥ (1 − ϵ) + p^{−1}(k) − 1 = p^{−1}(k) − ϵ. Since m′_{1} ⊕ m′_{2} ∈ E ∧ m′_{1} ∉ \overline{E} implies that m_{2} ≠ m′_{2} we thus have a significant probability of obtaining a double opening.

In the second case we have that since the proof was successful we ran a loop after the proof until a challenge e′ was answered successfully again. We can assume without lose of generality that the two challenges answered in the loop are different. If the commitment to a is opened differently in the two cases we are done. Assume therefore that it is opened to the same value a. This means that we have (a, e, e′, z, z′), where (a, e, z) and (a, e′, z′) are both accepting conversations. This allows us to either extract witnesses or get (K, P), where K is not an X-key and P is a proof that K is not an X-key.^{4} If no witness is obtained, let b′ ∈ {1, 2} indicate whether K is a left or a right key and give up the experiment and output (b′, K, P). If a witness is obtained, the witness contains an opening of each of the commitments to values in the relation. Thus one of the openings of the E-commitments must be different than the contradictory ones provided by A.

Assume that the game is never given up and consider the following experiment. We are given as input a system key N and an E-key K. Assume without loose of generality that we know the index l of a key for which A produces a double opening with a significant probability. We are going to embed K in the l’th key requested by A. To do this we pick a random bit b and let K_{b} = K and generate K_{1−b} as a random E-key with known E-trapdoor. For all other key we learn both of the trapdoors.

We then do the above experiment with A using (K_{0}, K_{1}) as the l’th key. With a significant probability this produces a double opening for the key (K_{0}, K_{1}), which contains a double opening for K_{0} or K_{1}. Since all values handed to A are independent of b, including those handed to A during the rewinding (because of the two phase structure of the game), this means that with at least half the probability of generating a double opening for (K_{0}, K_{1}) it will produce a double opening according to the key K_{b}, a contradiction to the computational binding.

4See the relaxation of the extraction in the previous section.

This means that the game must be given up with significant probability. Since the values send to A is independent of b the probability that b = b′ is \frac{1}{2}. Now consider the following experiment. We run the game as usual except that the sub keys K_{1−b} for which the trapdoor is not used is replaced by random X-keys. By the indistinguishability of E-keys and X-keys the game is still given up with significant probability, but as a proof of K not being an X-key is output along with K it must now be the case that the probability that b′ = b is 1 when the game is given up. This essentially makes the game a distinguisher of E-keys and X-keys, a contradiction. The reduction is left to the reader. □

In the next sections we will build universally composable commitments from mixed commitments. To the reader who likes to have a concrete example of a mixed commitment scheme in mind during the reading, we recommend reading Section 7.

4 Universally Composable Commitments

4.1 The General Framework

In the framework from [Can01] the security of a protocol is defined in three steps. First the real-life execution of the protocol is defined. Here the protocol π is modeled by n interactive Turing Machines P_{1}, …, P_{n} called the parties of the protocols. Also present in the execution is an adversary A and an environment Z modeling the environment in which A is attacking the protocol. The environment gives inputs to honest parties, receives outputs from honest parties, and can communication with A at arbitrary points in the execution. Both A and Z are PPT interactive Turing Machines. Second an ideal evaluation is defined. In the ideal evaluation an ideal functionality F is present to which all the parties have a secure communication line. The ideal functionality is an interactive Turing Machine defining the desired input-output behavior of the protocol. Also present is an ideal adversary S, the environment Z, and n so-called dummy parties P̃_{1}, …, P̃_{n} — all PPT interactive Turing Machines. The only job of the dummy parties is to take inputs from the environment and send them to the ideal functionality and take messages from the ideal functionality and output them to the environment. This basically makes the ideal process a trivially secure protocol with the same input-output behavior as the ideal functionality. The security of the protocol is then defined by requiring that the protocol emulates the ideal process.

The framework also defines the hybrid models, where the execution proceeds as in the real-life execution, but where the parties in addition have access to an ideal functionality. An important property of the framework is that these ideal functionalities can securely be replaced with sub-protocols securely realizing the ideal functionality. The real-life model including access to an ideal functionality F is called the F-hybrid model.

Below we add a few more details. For a more elaborate treatment of the general framework, see [Can01].

The framework as we will be using it models asynchronous authenticated communication over point-to-point channels, erasure free computation, and an active adaptive adversary. In the real-life execution all parties are assumed to share an open point-to-point channel. In the ideal evaluation all parties are assumed to have a secure channel to the ideal functionality. These assumptions are modeled by the way the execution proceeds. The environment Z is the driver of the execution. It can either provide a honest party, P_{i} or P̃_{i}, with an input or send a message to the adversary. If a party is given an input, that party is then activated. The party can then, in the real-life execution, send a message to another party or give an output to the environment. In the ideal evaluation an activated party just copies its input to the ideal functionality and the ideal functionality is then activated, sending messages to the parties and the adversary according to it program. After the party and/or the ideal functionality stops, the environment is activated again. If the adversary, A or S, is activated it can do several things. It can corrupt a honest party, send a message on behalf of a corrupt party, deliver any message send from one party to another, or communicate with the environment. On corrupting a party the adversary sees the entire communication history of that party including the random bits used in the execution. After the corruption the adversary sends and receives messages on behalf of the corrupted party. The adversary controls the scheduling of the message delivery. In the real-life execution the adversary A can see the contents of all message and may decide which messages should be delivered and when — it can however not change or add messages to a channel. In the ideal evaluation the adversary S cannot see the contents of the messages as the channels are assumed to be secure. It can only see that a message has been send and can then decide when the message should be delivered, if ever. If the adversary delivers a message to some party, then this party is activated and the environment resumes control when the party stops. At the beginning of the protocol all parties, the adversary, and the environment is given as input the security parameter k and random bits. Furthermore the environment is given an auxiliary input z. At some point the environment stops activating parties and outputs some bit. This bit is taken to be the output of the execution. We use REAL_{π,A,Z}(k, z) to denote the random variable describing the real-life execution and use IDEAL_{F,S,Z}(k, z) to denote the random variable describing the ideal evaluation.

We are now ready to state the definition of securely realizing an ideal functionality. For this purpose let REAL_{π,A,Z} denote the distribution ensemble {REAL_{π,A,Z}(k, z)}_{k∈N,z∈{0,1}^{∗}} and let IDEAL_{F,S,Z}(k, z) denote the distribution ensemble {IDEAL_{F,S,Z}(k, z)}_{k∈N,z∈{0,1}^{∗}}. We recall the definition of computationally indistinguishable distribution ensembles over {0, 1}.

Definition 2 (indistinquishable ensembles) We say distribution ensembles X = {X(k, z)}_{k∈N,z∈{0,1}^{∗}} and Y = {Y (k, z)}_{k∈N,z∈{0,1}^{∗}} over {0, 1} are indistinguishable (written X ≈^{c} Y) if for any c ∈ N there exists k_{0} ∈ N such that | Pr[X(k, z) = 1] − Pr[Y (k, z) = 1]| < k^{−c} for all k > k_{0} and all z.

Definition 3 ([Can01]) We say that π securely realizes F if for all real-life adversaries A there exists an ideal-evaluation adversary S such that for all environments Z we have that IDEAL_{F,S,Z} ≈^{c} REAL_{π,A,Z}.

An important fact about the above security notion is that it is maintained even if an unbounded number of copies of the protocol (and other protocols) are carried out concurrently — see [Can01] for a formal statement and proof. In proving the composition theorem it is used essentially that the environment and the adversary can communicate at any point in an execution. The price for this strong security notion, which is called universally composability in [Can01], is that rewinding cannot be used in the simulation.

4.2 The Commitment Functionality

We now specify the task that we want to implement as an ideal functionality. We look at a slightly different version of the commitment functionality than the one in [CF01]. The functionality in [CF01] is only for committing to one bit. Here we generalize. The domain of our commitments will be the domain of the special mixed commitment used in the implementation. Therefore the ideal functionality must specify the domain by giving a system key N. An important point related to this is that the X-trapdoor of N is revealed to the adversary in the ideal evaluation. This is to model the fact that the job of the commitment functionality is to hide the contents the commitments, not to hide the X-trapdoor of N; the value N so to say only has the job of specifying the domain of the commitment scheme. An implementation is therefore entitled to reveal the X-trapdoor of the N used to specify the domain of the commitment scheme — as long as commitments hides the values committed to. That the implementation which we are going to give actually keeps the X-trapdoor of N hidden relies only on the fact that this X-trapdoor is actually a trapdoor of the computational assumption on which the security of the implementation is based. The ideal functionality for homomorphic commitments is named F_{HCOM} and is as follows.

0. Generate a uniformly random system key N along with the X-trapdoor t_{N}. Send N to all parties and send (N, t_{N}) to the ideal adversary S.

1. Upon receiving (commit, sid, cid, P_{i}, P_{j}, m) from P̃_{i}, where m is in the domain of system key N, record (cid, P_{i}, P_{j}, m) and send the message (receipt, sid, cid, P_{i}, P_{j}) to P̃_{j} and S. Ignore subsequent (commit, sid, cid, …) messages.

2. Upon receiving (prove, sid, cid, P_{i}, P_{j}, R, cid_{1}, …, cid_{a}) from P̃_{i}, where (cid_{1}, P_{i}, P_{j}, m_{1}), …, (cid_{a}, P_{i}, P_{j}, m_{a}) has been recorded, R is an a-ary relation, and (m_{1}, m_{2}, …, m_{a}) ∈ R, send the message (prove, sid, cid, P_{i}, P_{j}, R, cid_{1}, …, cid_{a}) to P̃_{j} and S.

3. Upon receiving a message (open, sid, cid, P_{i}, P_{j}) from P̃_{i}, where (cid, P_{i}, P_{j}, m) has been recorded, send the message (open, sid, cid, P_{i}, P_{j}, m) to P̃_{j} and S.

It should be noted that a version of the functionality where N and t_{N} are not specified by the ideal functionality could be used. We could then let the domain of the commitments be a domain contained in the domain of all the system keys.

4.3 The Common Reference String Model

As mentioned in the introduction we cannot hope to construct two-party UCC in the plain real-life model. We need a that a common reference string (CRS) with a prescribed distribution is available to the players. In [CF01] the CRS is modeled by the F_{CRS}-hybrid model, where the ideal functionality F_{CRS}^{D}, parameterized by distribution ensemble D = {D(k)}_{k∈N}, proceeds as follows.

1. When initialized, choose a value d from the distribution D(k).

2. When activated on input (value, sid), send d back to the activating party and the adversary.

This functionality is a slightly modified version of the one from [CF01]. The difference is that we send d to the adversary. This only makes a difference if all parties are honest, but in that case it makes an important difference. The implication of this formulation is that a protocol implementing the F_{CRS} functionality (e.g. by a multi-party protocol) does not have to guarantee privacy.

5 UCC with Constant Expansion Factor

We now describe how to construct universally composable commitments from special mixed commitments.

5.1 The Commitment Scheme

Given a special mixed commitment scheme com we construct the following protocol UCC_{com}.

The CRS The CRS is (N, \overline{K}_{1}, …, \overline{K}_{n}), where N is a random system key and \overline{K}_{1}, …, \overline{K}_{n} are n random E-keys for the system key N, \overline{K}_{i} for P_{i}.

Committing

C.1 On input (commit, sid, cid, P_{i}, P_{j}, m) party P_{i} generates a random commitment key K_{1} for system key N and commits to it as c_{1} = commit_{\overline{K}_{i}}(K_{1}, r_{1}), and sends (com_{1}, sid, cid, c) to P_{j}.^{5}

R.1 The party P_{j} replies with (com_{2}, sid, cid, K_{2}) for random commit-

ment key K_{2}. C.2 On a message (com_{2}, sid, cid, K_{2}) from P_{j} the party P_{i} computes

K = K_{1} + K_{2} and c_{2} = commit_{K}(m, r_{2}) for random r_{2}. Then P_{i} records (sid, cid, P_{j}, K, m, r_{2}) and sends the message (com_{3}, sid, cid, K_{1}, r_{1}, c_{2}) to P_{j}.

R.2 On a message (com_{3}, sid, cid, K_{1}, r_{1}, c_{2}) from P_{i}, where c_{1} = commit_{\overline{K}_{i}}(K_{1}, r_{1}), the party P_{j} computes K = K_{1} + K_{2}, records (sid, cid, P_{j}, K, c_{2}), and outputs (receipt, sid, cid, P_{i}, P_{j}).

Opening

C.3 On input (open, sid, cid, P_{i}, P_{j}), P_{i} sends (open, sid, cid, m, r_{2}) to

P_{j}. R.3 On message (open, sid, cid, m, r_{2}) from P_{i} party P_{j} checks if c_{2} =

commit_{K}(m, r_{2}). If so party P_{j} outputs (open, sid, cid, P_{i}, P_{j}, m).

Proving Relation

C.4 On input (prove, sid, cid, P_{i}, P_{j}, R, cid_{1}, …, cid_{a}), where (sid, cid_{1}, P_{j}, K_{1}, m_{1}, r_{1}), …, (sid, cid_{a}, P_{j}, K_{a}, m_{a}, r_{a}) are recorded commitments, compute a from the recorded witnesses and compute c_{3} = commit_{\overline{K}_{i}}(a, r_{3}) for random r_{3} and send (prv_{1}, sid, cid, R, cid_{1}, …, cid_{a}, c_{3}) to P_{j}.

R.4 Generate a random challenge e and send (prv_{2}, sid, cid, P_{j}, e) to P_{i}. C.5 Compute the answer z and send (prv_{3}, sid, cid, a, r_{3}, z) to P_{j}. R.5 Check that c_{3} = commit_{\overline{K}_{i}}(a, r_{3}) and that (a, e, z) is an accepting

conversation. If so output (prove, sid, cid, P_{i}, P_{j}, R, cid_{1}, …, cid_{a}).

5We assume that the key space is a subset of the message space. If this is not the case the message space can be extended to a large enough M_{N}^{l} by committing to l values in the original scheme.

5.2 The Simulator

Let A be an adversary attacking UCC_{com} in the F_{com}-hybrid model. We construct a simulator S such that no environment Z can distinguish between A attacking UCC_{com} in the CRS-hybrid model and S attacking the ideal process for F_{HCOM}.

The CRS The CRS is (N, \overline{K}_{1}, …, \overline{K}_{n}), where N is the system key obtained (along with its X-trapdoor) from the ideal functionality F_{HCOM} and \overline{K}_{1}, …, \overline{K}_{n} are n random E-keys for the system key N. The keys are set up such that S knows the E-trapdoors of \overline{K}_{1}, …, \overline{K}_{n}.

Relaying All message from Z to S are relayed to A and all message from A intended for the environment are relayed to Z.

Committing On input (receipt, sid, cid, P_{i}, P_{j}) from the ideal functionality, where P_{i} is honest, we know that Z has given P̃_{i} input (commit, sid, cid, P_{i}, P_{j}, m) for some m ∈ Z_{n^{s}}. We have to simulate P_{i}’s behavior on the input (commit, sid, cid, P_{i}, P_{j}, m) without knowing m. We do this as follows.

C.1 Using the E-trapdoor of \overline{K}_{i} generate a fake commitment c_{1} and proceed as in the protocol. If P_{i} is corrupted before the next step, then corrupt P_{i} in the ideal evaluation. Then generate random K_{1} and compute r_{1} such that c_{1} = commit_{\overline{K}_{i}}(K_{1}, r_{1}).

C.2 On a message (com_{2}, sid, cid, K_{2}) from P_{j} generate a random E-key K for system key N with known E-trapdoor and let K_{1} = K − K_{2}. Then compute r_{1} such that c_{1} = commit_{\overline{K}_{i}}(K_{1}, r_{1}). Finally generate a fake commitment c_{2} using the E-trapdoor of K and send (com_{3}, sid, cid, K_{1}, r_{1}, c_{2}) to P_{j}. If P_{i} is corrupted by A after this step and before Step C.3, then corrupt P_{i} in the ideal evaluation and learn m. Then construct consistent random bits by generating r_{2} such that c_{2} = commit_{K}(m, r_{2}).

Opening (C.3) On input (open, sid, cid, P_{i}, P_{j}, m) from the ideal functionality, where P_{i} is honest, we know that Z has given P̃_{i} input (open, sid, cid, P_{i}, P_{j}). To simulate this construct r_{2} as specified in step C.2 and send (open, sid, cid, m, r_{2}) to P_{j}.

Receiving a commitment This is how to simulate a honest receiver P_{j} receiving a commitment.

R.1 Generate K_{2} as in the protocol.

R.2 On receiving the message (com_{3}, sid, cid, K_{1}, r_{1}, c_{2}) from P_{i}, where c_{1} = commit_{\overline{K}_{i}}(K_{1}, r_{1}), we have to make P̃_{j} output the value (receipt, sid, cid, P_{i}, P_{j}) in the ideal evaluation.

(a) If the com_{3}-message was send by S, then it was send because S received a (receipt, sid, cid, P_{i}, P_{j}) message from the ideal functionality and thus P̃_{j} has also been send a (receipt, sid, cid, P_{i}, P_{j}) message from the ideal functionality, so simply deliver the receipt to P̃_{j} which makes it output the receipt.

(b) If the com_{3}-message was send by A and K is an X-key, then use the X-trapdoor of N to decrypt c_{2} and let m′ denote the obtained value. If K is an E-key, then let m′ = 0. Then input (commit, sid, cid, P_{i}, P_{j}, m′) to the ideal functionality on behalf of P̃_{i}. Then deliver the receipt to P̃_{j} which makes it output the receipt.

Receiving an opening (R.3)

This is how to simulate a honest receiver P_{j} receiving an opening. On receiving a message (open, sid, cid, m′, r′_{2}) from P_{i} check whether c_{2} = commit_{K}(m′, r′_{2}). If so we must make P̃_{j} output (open, sid, cid, P_{i}, P_{j}, m′) in the ideal evaluation.

(a) If the open-message was send by S, then (open, sid, cid, P_{i}, P_{j}, m′) has already been send to P̃_{j} by the ideal functionality, so simply deliver that message and activate P̃_{j} to make it output the message.

(b) If the open-message was send by the adversary, then P̃_{i} is corrupt and we can input (open, sid, cid, P_{i}, P_{j}) on behalf of P̃_{i} to the ideal functionality. As response S receives a message (open, sid, cid, P_{i}, P_{j}, m) from the ideal functionality. If m = m′, then deliver the open-message send to P̃_{j} which makes it output the message.

(c) If in Case (b) m ≠ m′, then give up the simulation.

Proving Relation

C.4 On input (prove, sid, cid, P_{i}, P_{j}, R, cid_{1}, …, cid_{a}) from the ideal functionality we know that the ideal functionality has recorded (sid, cid_{1}, P_{i}, P_{j}, m_{1}), …, (sid, cid_{a}, P_{i}, P_{j}, m_{a}), where (m_{1}, …, m_{a}) ∈ R. Since we do not know the messages m_{1}, …, m_{a}, we send a fake commitment c_{3} under key \overline{K}_{i}. If P_{i} is corrupted before Step C.5, then corrupt P̃_{i} in the ideal evaluation and learn the messages m_{1}, m_{2}, …, m_{a} and generate a as in the protocol and compute r_{3} such that c_{2} = commit_{\overline{K}_{i}}(a, r_{3}).

C.5 Receive a challenge e. Then compute (a, z) using the honest verifier simulator and compute r_{3} such that c_{3} = commit_{\overline{K}_{i}}(a, r_{3}). Then send (a, z, r_{3}). If P_{i} is corrupted later, then corrupt P̃_{i} in the ideal evaluation and learn the message m_{1}, m_{2}, …, m_{a} and use the state construction property of the Σ-protocol to construct an internal state consistent with the conversation (a, e, z).

Receiving a Proof of Relation

R.4 Send a random challenge e.

R.5 Check as in the protocol. If the proof is accepted, then we need to make P̃_{j} output (prove, sid, cid, P_{i}, P_{j}, R, cid_{1}, …, cid_{a}). If the proof was initiated by the simulator on receiving the value (prove, sid, cid, P_{i}, P_{j}, R, cid_{1}, …, cid_{a}), then P̃_{i} has received (prove, sid, cid, P_{i}, P_{j}, R, cid_{1}, …, cid_{a}) as input from Z and delivered it to the ideal functionality, which has send the message (prove, sid, cid, P_{i}, P_{j}, R, cid_{1}, …, cid_{a}) to P̃_{j} and S. We then simply deliver (prove, sid, cid, P_{i}, P_{j}, R, cid_{1}, …, cid_{a}) to P̃_{j}, which makes P̃_{j} output the desired value. If the proof was initiated by the adversary, then P̃_{i} is corrupt and we can input (prove, sid, cid, P_{i}, P_{j}, R, cid_{1}, …, cid_{a}) to the ideal functionality on behalf of it. If the ideal functionality has recorded (cid_{1}, P_{i}, P_{j}, m_{1}), …, (cid_{a}, P_{i}, P_{j}, m_{a}), where (m_{1}, m_{2}, …, m_{a}) ∈ R, then it sends (prove, sid, cid, P_{i}, P_{j}, R, cid_{1}, …, cid_{a}) to P̃_{j} and S. If S receives this message deliver the one send to P̃_{j} as above. If S does not receive this message, then give up the simulation.

5.3 Analysis

Let REAL(A, Z) denote the distribution of an execution of the protocol and let IDEAL(S, Z) denote the distribution of the simulation. In order to prove that REAL(A, Z) ≈^{c} IDEAL(S, Z) we are going to define two hybrid distributions HYB_{1}(A, Z) and HYB_{2}(A, Z) and prove the following relations: REAL(A, Z) ≈^{c} HYB_{1}(A, Z) ≈^{c} HYB_{2}(A, Z) ≈^{c} IDEAL(S, Z).

To produce HYB_{1}(A, Z) we execute the protocol with adversary A and environment Z with one difference: When generating the keys \overline{K}_{1}, …, \overline{K}_{n} we learn the E-trapdoors and then generate the values K_{1} in step C.2 as in the simulator, i.e. generate them as K_{1} = K − K_{2} for random E-key K and then do a fake opening of c_{1} to make a consistent state. Further more we do the proofs of relations as in the simulator.

To produce HYB_{2}(A, Z) we execute the simulator, but without the knowledge of the X-trapdoor of N. As we cannot do the decryption in R.2.b, we then always use m = 0. Then in R.3.b instead of delivering (open, sid, cid, P_{i}, P_{j}, 0) to P̃_{j}, we patch the simulation and deliver (open, sid, cid, P_{i}, P_{j}, m′′), where m′′ is computed as follows. If the com_{3}-message was send by the simulator, then since P_{i} is now corrupt it was corrupted after Step C.2 and S has constructed an opening c_{2} = commit_{K}(m, r_{2}) as specified in Step C.2. We then take m′′ = m. If the com_{3}-message was send by A, then we take m′′ = m′, where m′ is the value send by A in the opening. Further more, each time S is about to give up the simulation in Step R.5, we patch the simulation and deliver (prove, sid, cid, P_{i}, P_{j}, R, cid_{1}, …, cid_{a}) anyway.

5.3.1 REAL(A, Z) vs. HYB_{1}(A, Z)

The difference between REAL(A, Z) and HYB_{1}(A, Z) is that in HYB_{1}(A, Z) the keys K used by honest parties in Step C.2 are random E-keys and not random keys. However random E-keys and random keys are assumed to be indistinguishable and thus this difference should not be detectable by the adversary. To prove this rigorously consider the following distinguisher.

The distinguisher is given as input keys K which are either all random keys or random E-keys. It then generates the keys \overline{K}_{1}, …, \overline{K}_{n} with known E-trapdoors. Then using these trapdoors it runs a real execution except that for honest parties the value of K in step C.2 is replaced by a random key from the distinguisher game and K_{1} and r_{1} are computed as in HYB_{1}(A, Z). Further more, the proofs of relations are done as in the simulator.

Then note that if the keys K from the distinguisher game are all random keys, then all values are distributed exactly as in a real execution. If on the other hand the keys K are random E-keys, then all values are distributed exactly as in HYB_{1}(A, Z). This proves that REAL(A, Z) and HYB_{1}(A, Z) are computationally indistinguishable.

5.3.2 HYB_{1}(A, Z) vs. HYB_{2}(A, Z)

The only difference between HYB_{1}(A, Z) and HYB_{2}(A, Z) is the following. In HYB_{1}(A, Z) the (open, sid, cid, P_{i}, P_{j}, m) value output by honest P_{j} when receiving correct opening message (open, sid, cid, m′, r′_{2}) in R.3 always has m = m′. In HYB_{2}(A, Z) this is also the case if the com_{3}-message was send by S. However, if the com_{3}-message was send by the adversary, then the m output is the one for which an opening c_{2} = commit_{K}(m, r_{2}) was computed in Step C.2 when P_{i} was corrupted. Note however, that if m ≠ m′, then S knows its own opening c_{2} = commit_{K}(m, r_{2}) and the new opening c_{2} = commit_{K}(m′, r′_{2}) send by the adversary. Since the X-key of N is not used when producing HYB_{1}(A, Z) and HYB_{2}(A, Z) one can easily prove that m ≠ m′ therefore only occurs with negligible probability using Lemma 1. This reduction is an easier case of the one done in the next section and we leave the details to the reader.

5.3.3 HYB_{2}(A, Z) vs. IDEAL(S, Z)

There are two differences between HYB_{2}(A, Z) and IDEAL(S, Z). First of all in IDEAL(S, Z) the simulator S might give up in R.5, whereas in HYB_{2}(A, Z) the simulation is patched. To prove that this difference is negligible it is enough to prove that the simulator gives up in IDEAL(S, Z) only with negligible probability. For the second difference, in HYB_{2}(A, Z), when a honest P_{j} receives a correct opening message (open, sid, cid, m′, r′_{2}) in R.3 and when the com_{3}-message was send by A, then the (open, sid, cid, P_{i}, P_{j}, m) value output has m = m′, where m′ is the value send by A in the opening. In IDEAL(S, Z) the value of m is the one computed in Step R.2.b. To prove that this difference is negligible it is enough to prove that these two values are different only with negligible probability. Observe that to be different it must be the case that the key K used is an E-key as X-keys are perfect binding. All in all, it is therefore enough to prove that when the com_{3}-message is send by A, then the key K is an X-key except with negligible probability and that the simulation is only given up in R.5 with negligible probability.

For sake of contradiction assume that an E-key is used with probability p_{1} and that the probability that no E-key is used, but the simulation is given up in R.5 is p_{2}, where p_{1} + p_{2} is significant. Then consider the following lunchtime opening game, where we set the set E to be the set of E-keys. We get a random system key N. Then request a key generation and get E-key \overline{K}. Then uniformly pick one of the parties P_{s} and use the key received as the key \overline{K}_{s} for P_{s}. For the remaining parties we generate keys and learn the corresponding E-trapdoors. We then generate HYB_{2}(A, Z) with the following differences: First of all we request a trapdoor commitment for \overline{K}_{s} from the game each time we would have used the E-trapdoor of \overline{K}_{s} in Step C.1 and we ask for an opening each time such is needed in Step C.1 or C.2. Second, the proofs of relation are done with the game for key \overline{K}_{s}. Finally, the random E-key K generated in C.2 is generated by requesting a key generation in the game and the fake commitment under K in C.2 is generated by requesting a commitment generation, and when a fake opening is needed for K in C.2 or C.3 we ask for this opening in the game. Finally all the proofs of relations (C.4 and C.5) are done by having the adversary doing them with the game.

If P_{s} is ever corrupted we go to the test phase in the lunchtime opening game and each time a com_{1}-message is received from the now corrupt P_{s} we give the commitment c from the message to the lunchtime opening game and receive as a challenge a uniformly random K_{2} and send K_{2} to P_{s}, and if c is ever opened, then if the value K_{1} opened to is such that K_{1} + K_{2} is an E-key, we score one point in the game. Also, all the proofs of relation done by the adversary (R.4 and R.5) are done with the game as proof of relation tests (this requires that the keys in the test are either generated due to key generation requests or are X-key, which is proven to be the case except with negligible probability in the following paragraph). Each time the simulation is given up in R.5, then if an opening is known for all the commitments and these openings are in the relation, then give them to the game and score one point.

That p_{1} is negligible follows directly from the assumption that the score in the lunchtime opening game is negligible. We prove that p_{2} is negligible. Assume for the sake of contradiction that p_{2} is significant. This means that with a significant probability the simulation is given up and an opening is known for all E-commitments in the relation given up on. This is so as for the E-commitments generated by S, S generated an opening, and a commitment generated by the adversary is never an E-commitment. Further more the value of the openings of the E-commitments together with the values extractable^{6} from the X-commitments are exactly those recorded in the ideal simulator, and since the simulation is given up we thus conclude that the openings are not in the relation. Since we only give up if the proof of relation succeeded we can hand the contradictory openings of the E-commitments to the game and scored one point. This implies that the expected score is significant in contradiction to Lemma 1.

We have proven the following theorem.

Theorem 1 If com is a special mixed commitment scheme, then the protocol UCC_{com} securely realizes F_{HCOM} in the CRS-hybrid model.

5.4 Perfect Hiding and Perfect Binding

The scheme described above has neither perfect binding nor perfect hiding. Here we construct a version of the commitment scheme with both perfect hiding and perfect binding. The individual commitments are obviously not simultaneously perfect hiding and perfect binding, but it can be chosen at the time of commitment whether a commitment should be perfect binding or perfect hiding and proofs of relations can include both types of commitments. We sketch the scheme and the proof of its security. The details are left to the reader.

In the extended scheme we add to the CRS a random E-key K_{E} and a random X-key K_{X} (both for system key N). Then to do a perfect binding commitment to m the committer will in Step C.2 compute c_{2} = commit_{K}(m, r_{2}) as before, but will in addition compute c_{3} = commit_{K_{X}} (m, r_{3}). To open the commitment the committer will then have to send both a correct opening (m, r_{2}) of c_{2} and a correct opening (m, r_{3}) of c_{3}. This is perfect binding as the X-key commitment is perfect binding.

6Observe that we need not actually extract the values, as the lunchtime opening game only requires to see openings of the E-commitments. This is an important detail as we do not know the X-trapdoor.

To do a perfect hiding commitment the committer computes a uniformly random message \overline{m} and commits with c_{2} = commit_{K}(\overline{m} + m, r_{2}) and c_{3} = commit_{K_{E}}(\overline{m}, r_{3}). To open to m the committer must then send a correct opening (m_{2}, r_{2}) of c_{2} and a correct opening (m_{3}, r_{3}) of c_{3} for which m_{2} = m_{3} + m. This is perfect hiding because c_{3} hides \overline{m} perfectly and \overline{m} + m thus hides m perfectly.

To do the simulation simply let the simulator make the excusable mistake of letting K_{E} be a random X-key and letting K_{X} be a random E-key. This mistake will allow to simulate and cannot be detected by the assumption that both E-keys and X-keys are indistinguishable from random keys, the switch can be handled between REAL(A, Z) and HYB_{1}(A, Z). In the perfect binding version both K and K_{X} will then be E-keys when the simulator does a commitment, which allows to fake. When the adversary does a commitment K will (except with negligible probability p_{1}) be an X-key and the simulator can extract m from commit_{K}(m). In the perfect hiding version both K and K_{E} will (except with negligible probability p_{1}) be X-keys when the adversary does a commitment, which allows to extract. When the simulator commits, K will be an E-key, which allows to fake an opening by faking commit_{K}(m).

In the version with perfect binding the proofs of relation can be used directly for the modified version by doing the proof on the commit_{K}(m) values. In the version with perfect hiding there is no general transformation that will carry proofs of relations over to the modified system. If however there is a proof of additive relation, then one can publish commit_{K}(m) and prove that the sum of the values committed to by commit_{K}(m) and commit_{K_{E}}(\overline{m}) is committed to by commit_{K}(\overline{m} + m), and then use the commitment commit_{K}(m) when doing the proofs of relation.

To see that this is secure assume that the adversary succeeds in proving a relation which is not meet by the values input to the ideal functionality by the simulator. We can safely exclude the case where an E-key has been generated by the adversary as it occurs with negligible probability p_{1}. This means that the simulator knows the opening of all the commit_{K}(m) commitments and the opening of the commit_{K_{E}}(\overline{m}) and commit_{K}(m + \overline{m}) commitments for the perfect hiding commitments, and that the value of these openings were those used to compute the input to the ideal functionality. This means that either 1) the adversary has proven a relation for the commit_{K}(m) commitments and the simulator knows contradictory openings or 2) the adversary has proven an additive relation among commit_{K}(m), commit_{K_{E}}(\overline{m}), and commit_{K}(\overline{m} + m) and the simulator knows a contradictory opening. In both cases the simulator scores one point in the lunchtime opening game and both cases must thus occur with negligible probability.

6 A Special Mixed Commitment Scheme based on the p-Subgroup Assumption

In this section we provide our first construction of a special mixed commitment. It is build on the encryption scheme from [OU98].

6.1 Key Space, Message Space, and Committing

Let p and q be random k-bit primes, where p ≠ q and gcd(p − 1, q) = gcd(q − 1, p) = 1. Let n = pq and let N = pn. The system key will be (N, g), where g = (1 + n)^{m_{g}}r_{g}^{p} mod N for random r_{g} ∈ Z_{N}^{∗}. The X-trapdoor will be (p, q). The key space will be Z_{N}^{∗} and the message space will be {0, 1}^{k−1}, both have the necessary group structure. The E-keys will be P = {r^{p} mod N|r ∈ Z_{N}^{∗}} and the X-keys will be Z_{N}^{∗} \ P. The density of both E-keys and X-keys are obviously as required.

To sample an E-key simply let K = r^{N} mod N for random r ∈ Z_{N}^{∗}. It is clear that P is a subgroup of Z_{N}^{∗} of size ϕ(n) = (p − 1)(q − 1). Since r ↦ r^{p} mod N is a homomorphism from Z_{N}^{∗} to P it is p to 1, and since gcd(p − 1, q) = gcd(q − 1, q) = 1, the map r ↦ r^{pq} mod N is an automorphism on P. Therefore the map r ↦ r^{N} = (r^{p})^{pq} is p to 1 in Z_{N}^{∗}. Thus r^{N} mod N is a random E-key for random r ∈ Z_{N}^{∗}.

To sample a random X-key let m be a random element from Z_{p}^{∗}, let r be a random element for Z_{N}^{∗}, and let K = g^{m}r^{N} mod N. It is easy to see that (1 + n)^{i} ≡ 1 + in (mod N). Thus (n + 1) has order p in Z_{N}^{∗} and Z_{N}^{∗}/P = {(1 + n)^{i}P |i ∈ Z_{p}^{∗}}. Thus g^{m}r^{N} = (1 + n)^{m_{g}m}(r_{g}^{mp}r^{N}) is a random element from Z_{N}^{∗} \ P.

The key spaces are indistinguishable relative to the p-subgroup assumption, that uniformly random elements from P are indistinguishable from uniformly random elements from Z_{N}^{∗}. For details, see [OU98].

We commit as c = commit_{K}(m, r) = K^{m}r^{N} mod N.

6.2 Equivocability

Assume that K is an E-key K = r_{K}^{N} mod N. Then c = (r_{K}^{m}r)^{N}. Assume that we are given any message \overline{m} ∈ Z_{N^{s}} and let \overline{r} = r_{K}^{m−\overline{m}}r mod N.

Then commit_{K}(\overline{m}, \overline{r}) ≡ K\overline{m}\overline{r}^{N} ≡ K^{m}r^{N} (mod N). Further more it is easy to see that if c = commit_{K}(\overline{m}, r̃), then r̃ = \overline{r}. This proves that r_{K} gives equivocability.

6.3 Extraction

Let K = (n + 1)^{m_{g}m_{K}}(r_{g}^{m_{K}}r_{K})^{N} mod N be an X-key, i.e. m_{K} ∈ Z_{p}^{∗}. Assume that c can be opened to m ∈ {0, 1}^{k−1}. I.e. there exists r ∈ Z_{N}^{∗} such that c ≡ K^{m}r^{N} ≡ (n + 1)^{m_{g}m_{K}m}(r_{g}^{m_{K}m}r_{K}^{m}r)^{N} (mod N). Let λ = lcm(p − 1, q − 1) and let

d = c^{λ} mod N
= (n + 1)^{λm_{g}m_{K}m}((r_{g}^{m_{K}m}r_{K}^{m}r)^{pλ(p−1,q−1)})^{pq} mod N
= 1 + (λm_{g}m_{K}m)n mod N .

Since λm_{g}m_{K} ∈ Z_{p}^{∗} we can efficiently compute α, β ∈ N such that

α(d − 1) mod N = (1 + βp)mn mod N
= mn mod N
= mn

and from this number we can compute m. This proves that (p, q) allows extraction.

6.4 The Transformation

The transformed scheme has keys which are pairs of keys and commits as (C_{1}, C_{2}) = (K_{1}^{m_{1}}r_{1}^{N} mod N, K_{2}^{m_{2}}r_{2}^{N} mod N), where r_{1}, r_{2} are random in Z_{N}^{∗}, m_{1} is random in {0, 1}^{k−1}, and m = m_{1} ⊕ m_{2}, where ⊕ denotes bit-wise xor.

In the following we are going to provide proofs of relations for the transformed scheme with message space {0, 1}.

6.5 Proof of Commitment to 0 (Base Scheme)

To prove that a commitment C in the base scheme commits to 0 (i.e. C ∈ P) one has to prove knowledge of r such that C = r^{N} mod N. Here is a protocol for doing that.

1. The prover is given r ∈ Z_{N}^{∗}, computes D = s^{N} mod N for random s ∈ Z_{N}^{∗}, and sends D to the verifier.

2. The verifier sends random e < 2^{k−1}.

3. The prover sends t = sr^{e} mod N.

4. The verifier checks that t^{N} ≡ DC^{e} (mod N).

The correctness is obvious. For the special soundness note that if two different challenges e_{1}, e_{2} are answered correctly, we have

t_{1}^{N} ≡ DC^{e_{1}} (mod N), t_{2}^{N} ≡ DC^{e_{2}} (mod N) ,

which allows us to compute r ∈ Z_{N}^{∗} such that

C = r^{N} mod N .

For the special honest verifier zero-knowledge, given a challenge e pick t ∈ Z_{N}^{∗} at random and let D = t^{N}C^{−e} mod N. When given r such that C = r^{N} mod N in the state construction, let s = tr^{−1} mod N. Then s is uniform in Z_{N}^{∗} and s^{N} ≡ t^{N}(r^{N})^{−1} ≡ D (mod N) as desired.

6.6 Proof of Commitment to 1 (Base Scheme)

To prove that a commitment C commits to 1 under the key K (i.e. C ∈ KP) simply prove that C/K ∈ P using the above proof.

6.7 Monotone Logical Combination of Non-Erasure Σ-Proto-cols

Using techniques from [CDS94] we can now combine the proofs of committing to 0 and the proof of committing to 1 using monotone logical circuits to obtain proof of relations between the transformed commitments. We review the construction for disjunction here and verify that it preserves the non-erasure property.

Assume that we are given non-erasure Σ-protocols for relations R_{0} and R_{1} and that we want a non-erasure Σ-protocol for the relation ((x_{0}, x_{1}), (b, w)) ∈ R ⇔ (x_{b}, w) ∈ R_{b}.

1. The input of the prover is (x_{0}, x_{1}, b, w), where b ∈ {0, 1} and (x_{b}, w) ∈ R_{b}. Compute a random challenge e_{1−b} < 2^{k−1} and using the honest verifier simulator compute a_{1−b}, z_{1−b} such that (x_{1−b}, a_{1−b}, e_{1−b}, z_{1−b}) is an accepting conversation. Then using (x_{b}, w) compute the first message a_{b} in the protocol for R_{b} and send (a_{0}, a_{1}) to the verifier.

2. The verifier sends random e < 2^{k−1}.

3. The prover sets e_{b} = e − e_{1−b} mod 2^{k−1} and computes z_{b} such that (x_{b}, a_{b}, e_{b}, z_{b}) is an accepting conversation, and sends (e_{0}, e_{1}, z_{0}, z_{1}) to the verifier.

4. The verifier checks that e_{0} + e_{1} = e mod 2^{k−1} and (x_{0}, a_{0}, e_{0}, z_{0}) and (x_{1}, a_{1}, e_{1}, z_{1}) are accepting conversations.

The correctness is obvious. For the special soundness assume that two challenges e, e′ are answered correctly, with e = e_{0} + e_{1} mod 2^{k−1} and e′ = e′_{0} + e′_{1} mod 2^{k−1}. This means that either e_{0} ≠ e′_{0} or e_{1} ≠ e′_{1}, which allows to extract a witness.

For the special honest verifier zero-knowledge assume that we are given challenge e. Then pick e_{0} and e_{1} as random values for which e = e_{0} + e_{1} mod 2^{k−1} and using the honest verifier simulator compute accepting conversations (x_{0}, a_{0}, e_{0}, z_{0}) and (x_{1}, a_{1}, e_{1}, z_{1}). When given (b, w) in the state construction e_{1−b} is uniformly random and e_{b} = e − e_{1−b} mod 2^{k−1} and (a_{1−b}, z_{1−b}) was generated using the honest verifier simulator as required. To construct an internal state consistent with (a_{b}, z_{b}) being generated as in the protocol with challenge e_{b}, use the state construction property of R_{b}.

6.8 Proof of Binary Boolean Relations

We show how to combine the proof of committing to 0 and the proof of committing to 1 using a monotone logical circuit to obtain proofs of binary Boolean relations by using the conjunctive relation as an example. We are given commitments (C_{1}, C_{2}), (C_{3}, C_{4}), (C_{5}, C_{6}), where

C_{1} = K_{1}^{m_{1}}r_{1}^{N^{s}} mod N^{s+1}, C_{2} = K_{2}^{m_{2}}r_{2}^{N^{s}} mod N^{s+1}
C_{3} = K_{3}^{m_{3}}r_{3}^{N^{s}} mod N^{s+1}, C_{4} = K_{4}^{m_{4}}r_{4}^{N^{s}} mod N^{s+1}
C_{5} = K_{5}^{m_{5}}r_{5}^{N^{s}} mod N^{s+1}, C_{6} = K_{6}^{m_{6}}r_{6}^{N^{s}} mod N^{s+1}
(m_{1} ⊕ m_{2}) ∧ (m_{3} ⊕ m_{4}) = (m_{5} ⊕ m_{6}) .

To prove knowledge, simply prove

[(m_{1} ∈ P ∧ m_{2} ∈ P ∨ m_{1} ∈ K_{1}P ∧ m_{2} ∈ K_{2}P)

∨

(m_{3} ∈ P ∧ m_{4} ∈ P ∨ m_{3} ∈ K_{3}P ∧ m_{4} ∈ K_{4}P]

∧

(m_{5} ∈ P ∧ m_{6} ∈ P ∨ m_{5} ∈ K_{5}P ∧ m_{6} ∈ K_{6}P) ⋁

(m_{1} ∈ P ∧ m_{2} ∈ K_{2}P ∨ m_{1} ∈ K_{1}P ∧ m_{2} ∈ P)

∧

(m_{3} ∈ P ∧ m_{4} ∈ K_{4}P ∨ m_{3} ∈ K_{3}P ∧ m_{4} ∈ P)

∧

(m_{5} ∈ P ∧ m_{6} ∈ K_{6}P ∨ m_{5} ∈ K_{5}P ∧ m_{6} ∈ P) .

As a final remark on verifying Boolean relations, note that if (C_{1}, C_{2}) is a commitment to m, then (K_{1}C_{1}^{−1}, C_{2}) is a commitment to 1 − m, so this implements Boolean negation assuming m is a 0/1 value. This, together with the monotone logical combinations of proofs we have seen above is clearly enough to verify any relation defined by a binary Boolean function f, i.e., we obtain a proof that committed values m_{1}, m_{2}, m_{3} are 0/1 values and satisfy f(m_{1}, m_{2}) = m_{3}. Summarizing, we have:

Theorem 2 Relative to the p-subgroup assumption, the above is a special mixed commitment scheme. When restricted to message space {0, 1} the scheme has proofs of relations between committed values for all relations of the form m_{3} = f(m_{1}, m_{2}), where f is a binary Boolean function.

7 A Special Mixed Commitment Scheme based on the DCRA

In this section we describe another special mixed commitment scheme. It is based on the decisional composite residuosity assumption (DCRA) introduced in [Pai99]. The scheme has a constant expansion factor and allows efficient proofs of additive and multiplicative relations.

7.1 Key Space, Message Space, and Committing

Let N = pq be an RSA modulus and let s ≥ 0 be some fixed constant. Consider the map ψ : Z_{N^{s}}×Z_{N}^{∗} → Z_{N^{s+1}}^{∗} given by (m, r) ↦ (N+1)^{m}r^{N^{s}} mod N^{s+1}. In [DJN01] it is proven that ψ is an isomorphism, where ψ(m_{1}, r_{1})^{e}ψ(m_{2}, r_{2}) mod N^{s+1} = ψ(em_{1} + m_{2} mod N^{s}, r_{1}^{e}r_{2} mod N), and that it can be efficiently inverted given the factorization of N. Further more it is proven that if the DCRA holds, then elements of the form ψ(0, r) cannot be distinguished from elements of the form ψ(m, r), where r is uniformly random from Z_{N}^{∗} and m is any fixed element m ∈ Z_{N^{s}}. We will use this to construct a special mixed commitment scheme.

The system key will be a random RSA-modulus N = pq, where p and q are k-bit primes, and some fixed s and the X-trapdoor will be (p, q). The key space will be Z_{N^{s+1}}^{∗} and the message space will be Z_{N^{s}}, both have the necessary group structure. The E-keys will be elements of the form ψ(0, r) and the E-trapdoor will be r. The X-keys will be the elements of the form ψ(m, r), where m ∈ Z_{N^{s}}^{∗}. The density in the key space of both the E-keys and the X-keys are obviously as required and the keys can be sampled as required. Further more random E-keys, random X-keys, and random keys are computationally indistinguishable by the DCRA as discussed above.

Given a key K ∈ Z_{N^{s+1}}^{∗} and a message m ∈ Z_{N^{s}}, let r be a uniformly random element from Z_{N}^{∗} and commit as c = commit_{K}(m, r) = K^{m}r^{N^{s}} mod N^{s+1}.

7.2 Equivocability

Assume that K is an E-key K = ψ(0, r_{K}). Then c = ψ(0, r_{K})^{m}ψ(0, r) = ψ(0, r_{K}^{m}r mod N). Assume that we are given any message \overline{m} ∈ Z_{N^{s}} and let \overline{r} = r_{K}^{m−\overline{m}}r mod N. Then commit_{K}(\overline{m}, \overline{r}) = ψ(0, r\overline{m} ; K\overline{r} mod N) = ψ(0, r_{K}^{m}r mod N) = c. Further more commit_{K}(\overline{m}, r̃) = c implies that r̃ = \overline{r}. This proves that r_{K} gives equivocability.

7.3 Extraction

Assume that K is an X-key K = ψ(m_{K}, r_{K}). Assume that c can be opened to m, i.e. there exists r such that c = ψ(m_{K}, r_{K})^{m}ψ(0, r) = ψ(mm_{K} mod N^{s}, r_{K}^{m}r mod N). Given the X-trapdoor (p, q) we can by [DJN01] invert ψ on K and c and compute m_{K} and mm_{K} mod N^{s}. Since m_{K} ∈ Z_{N^{s}}^{∗} this allows us to compute m. This proves that (p, q) allows extraction.

7.4 The Transformation

The transformed scheme has keys (K_{1}, K_{2}), which are pairs of keys, and commits as

commit_{K_{1},K_{2}}(m, (r_{1}, r_{2}, m_{1})) = (K_{1}^{m_{1}}r_{1}^{N^{s}} mod N^{s+1}, K_{2}^{m_{2}}r_{2}^{N^{s}} mod N^{s+1})

where r_{1}, r_{2} are random in Z_{N}^{∗}, m_{1} is random in Z_{N^{s}}, and m_{2} = m − m_{1} mod N^{s}.

7.5 Proof of Multiplicative Relation

We are given commitments (C_{1}, C_{2}), (C_{3}, C_{4}), (C_{5}, C_{6}), where

C_{1} = K_{1}^{m_{1}}r_{1}^{N^{s}} mod N^{s+1}, C_{2} = K_{2}^{m_{2}}r_{2}^{N^{s}} mod N^{s+1}
C_{3} = K_{3}^{m_{3}}r_{3}^{N^{s}} mod N^{s+1}, C_{4} = K_{4}^{m_{4}}r_{4}^{N^{s}} mod N^{s+1}
C_{5} = K_{5}^{m_{5}}r_{5}^{N^{s}} mod N^{s+1}, C_{6} = K_{6}^{m_{6}}r_{6}^{N^{s}} mod N^{s+1}
(m_{1} + m_{2})(m_{3} + m_{4}) ≡ (m_{5} + m_{6}) (mod N^{s}) .

To prove knowledge we send

C_{7} = K_{5}^{m_{3}}r_{7}^{N^{s}} mod N^{s+1}, C_{8} = K_{6}^{m_{4}}r_{8}^{N^{s}} mod N^{s+1}
\overline{C}_{1} = K_{1}^{\overline{m}_{1}} \overline{r}_{1}^{N^{s}} mod N^{s+1}, \overline{C}_{2} = K_{2}^{\overline{m}_{2}} \overline{r}_{2}^{N^{s}} mod N^{s+1}
\overline{C}_{3} = K_{5}^{\overline{m}_{3}} \overline{r}_{3}^{N^{s}} mod N^{s+1}, \overline{C}_{4} = K_{6}^{\overline{m}_{4}} \overline{r}_{4}^{N^{s}} mod N^{s+1}
\overline{C}_{7} = K_{5}^{\overline{m}_{3}} \overline{r}_{7}^{N^{s}} mod N^{s+1}, \overline{C}_{8} = K_{6}^{\overline{m}_{4}} \overline{r}_{8}^{N^{s}} mod N^{s+1}
\overline{C}_{5} = K_{5}^{m_{3}(\overline{m}_{1}+\overline{m}_{2})+\overline{m}}\overline{r}_{5}^{N^{s}} mod N^{s+1}
\overline{C}_{6} = K_{6}^{m_{4}(\overline{m}_{1}+\overline{m}_{2})−\overline{m}}\overline{r}_{6}^{N^{s}} mod N^{s+1} ,

where the values r_{7}, r_{8}, \overline{m}_{i}, \overline{r}_{i}, \overline{m} are chosen at random in the respective domains. After receiving e < 2^{k−1} we let l = \frac{m_{6}+m_{5}−(m_{1}+m_{2})(m_{3}+m_{4})}{N^{s}} and send the following values (except m̃_{1}, m̃_{2}, m̃_{3}, m̃_{4}, m̃):

m̃_{1} = em_{1} + \overline{m}_{1}, m̃_{1}^{(r)} = m̃_{1} mod N^{s}, r̃_{1} = K_{1}^{m̃_{1} div N^{s}}r_{1}^{e}\overline{r}_{1} mod N

m̃_{2} = em_{2} + \overline{m}_{2}, m̃_{2}^{(r)} = m̃_{2} mod N^{s}, r̃_{2} = K_{2}^{m̃_{2} div N^{s}}r_{2}^{e}\overline{r}_{2} mod N

m̃_{3} = em_{3} + \overline{m}_{3}, m̃_{3}^{(r)} = m̃_{3} mod N^{s}
r̃_{3} = K_{3}^{m̃_{3} div N^{s}}r_{3}^{e}\overline{r}_{3} mod N, r̃_{7} = K_{5}^{m̃_{3} div N^{s}}r_{7}^{e}\overline{r}_{7} mod N
m̃_{4} = em_{4} + \overline{m}_{4}, m̃_{4}^{(r)} = m̃_{4} mod N^{s}
r̃_{4} = K_{4}^{m̃_{4} div N^{s}}r_{4}^{e}\overline{r}_{4} mod N, r̃_{8} = K_{6}^{m̃_{4} div N^{s}}r_{8}^{e}\overline{r}_{8} mod N

m̃ = em_{5} + m_{3}(\overline{m}_{1} + \overline{m}_{2} − m̃_{1} − m̃_{2}) + \overline{m}, m̃^{(r)} = m̃ mod N^{s}

r̃_{5} = K_{5}^{m̃ div N^{s}} \overline{r}_{5}r_{5}^{e}r_{7}^{−(m̃_{1}+m̃_{2})} mod N

r̃_{6} = K_{6}^{−(m̃ div N^{s})+[el+(m_{3}+m_{4})((m̃_{1} div N^{s})+(m̃_{2} div N^{s}))]}\overline{r}_{6}r_{6}^{e}r_{8}^{−(m̃_{1}+m̃_{2})} mod N .

The verifier checks that

C_{1}^{e}\overline{C}_{1} ≡ K_{1}^{m̃_{1}^{(r)}}r̃_{1}^{N^{s}}, C_{2}^{e}\overline{C}_{2} ≡ K_{2}^{m̃_{2}^{(r)}}r̃_{2}^{N^{s}} (mod N^{s+1})
C_{3}^{e}\overline{C}_{3} ≡ K_{3}^{m̃_{3}^{(r)}}r̃_{3}^{N^{s}}, C_{4}^{e}\overline{C}_{4} ≡ K_{4}^{m̃_{4}^{(r)}}r̃_{4}^{N^{s}} (mod N^{s+1})
C_{7}^{e}\overline{C}_{7} ≡ K_{5}^{m̃_{3}^{(r)}}r̃_{7}^{N^{s}}, C_{8}^{e}\overline{C}_{8} ≡ K_{6}^{m̃_{4}^{(r)}}r̃_{8}^{N^{s}} (mod N^{s+1})
C_{5}^{e}\overline{C}_{5} ≡ C_{7}^{m̃_{1}^{(r)}+m̃_{2}^{(r)}}K_{5}^{m̃^{(r)}}r̃_{5}^{N^{s}} (mod N^{s})
C_{6}^{e}\overline{C}_{6} ≡ C_{8}^{m̃_{1}^{(r)}+m̃_{2}^{(r)}}K_{6}^{−m̃^{(r)}}r̃_{6}^{N^{s}} (mod N^{s}) .

7.5.1 Correctness

We check the last equivalence. The other equivalences are checked using simpler computations. To check the equivalence it is enough to prove that

C_{6}^{e}\overline{C}_{6}K_{6}^{m̃^{(r)}}r̃_{6}^{−N^{s}}C_{8}^{−(m̃_{1}^{(r)}+m̃_{2}^{(r)})} ≡

K_{6}^{em_{6}}r_{6}^{e}^{N^{s}}K_{6}^{m_{4}(\overline{m}_{1}+\overline{m}_{2})−\overline{m}}\overline{r}_{6}^{N^{s}}K_{6}^{m̃^{(r)}}r̃_{6}^{−N^{s}}K_{6}^{−m_{4}(m̃_{1}^{(r)}+m̃_{2}^{(r)})}(r_{8}^{m̃_{1}^{(r)}+m̃_{2}^{(r)}})^{−N^{s}} ≡

1 (mod N^{s+1}) .

By collecting terms in the exponent of K_{6}, this follows from the following computation

m_{4}(\overline{m}_{1} + \overline{m}_{2}) + em_{6} − \overline{m} − m_{4}(m̃_{1}^{(r)} + m̃_{2}^{(r)})
+ N^{s}(m̃ div N^{s} − [el + (m_{3} + m_{4})((m̃_{1} div N^{s})
+ (m̃_{2} div N^{s}))]) + m̃^{(r)}
≡m_{4}(\overline{m}_{1} + \overline{m}_{2}) + em_{6} − \overline{m} + m̃ − m_{4}(m̃_{1}^{(r)} + m̃_{2}^{(r)})
− N^{s}[el + (m_{3} + m_{4})((m̃_{1} div N^{s}) + (m̃_{2} div N^{s}))]
≡m_{4}(\overline{m}_{1} + \overline{m}_{2}) + e(m_{6} + m_{5})
+ m_{3}(\overline{m}_{1} + \overline{m}_{2} − m̃_{1} − m̃_{2}) − m_{4}(m̃_{1}^{(r)} + m̃_{2}^{(r)})
− N^{s}el − (m_{3} + m_{4})(N^{s}(m̃_{1} div N^{s}) + N^{s}(m̃_{2} div N^{s}))
≡m_{4}(\overline{m}_{1} + \overline{m}_{2}) + e(m_{6} + m_{5}) + m_{3}(\overline{m}_{1} + \overline{m}_{2})
− N^{s}el − (m_{3} + m_{4})(m̃_{1} + m̃_{2})
≡(m_{3} + m_{4})(−em_{1} + −em_{2}) + e(m_{6} + m_{5}) − N^{s}el
≡e[−(m_{3} + m_{4})(m_{1} + m_{2}) + (m_{6} + m_{5}) − lN^{s}] ≡ 0 (mod N^{s}) .

7.5.2 Special Soundness

Assume that two different challenges ẽ, \underline{e} are answered correctly. This gives us

Cẽ ; 1\overline{C}_{1} ≡ Km̃_{1} ; 1r̃_{1}^{N^{s}}, C\underline{e} ; 1\overline{C}_{1} ≡ K_{1}^{\underline{m}_{1}} \underline{r}_{1}^{N^{s}}

and thus

C_{1}^{ẽ−\underline{e}} ≡ K_{1}^{m̃_{1}−\underline{m}_{1}}(r̃_{1}\underline{r}_{1}^{−1})^{N^{s}} .

Since ẽ − \underline{e} < p, q we can using the extended Euclid’s algorithm compute α and β s.t.

1 = αN^{s} + β(ẽ − \underline{e}) .

Now let

m_{1} = β(m̃_{1} − \underline{m}_{1}) mod N^{s}, u_{1} = β(m̃_{1} − \underline{m}_{1}) div N^{s}
r_{1} = (r̃_{1}\underline{r}_{1}^{−1})^{β}C_{1}^{α}K_{1}^{u_{1}} mod N .

Then it is easy to see that C_{1} = K_{1}^{m_{1}}r_{1}^{N^{s}} mod N^{s+1}. In the same way we can write

C_{1} = K_{1}^{m_{1}}r_{1}^{N^{s}} mod N^{s+1}, C_{2} = K_{2}^{m_{2}}r_{2}^{N^{s}} mod N^{s+1}
C_{3} = K_{3}^{m_{3}}r_{3}^{N^{s}} mod N^{s+1}, C_{4} = K_{4}^{m_{4}}r_{4}^{N^{s}} mod N^{s+1}
C_{7} = K_{5}^{m_{3}}r_{7}^{N^{s}} mod N^{s+1}, C_{8} = K_{6}^{m_{4}}r_{8}^{N^{s}} mod N^{s+1}
C_{5} = K_{5}^{m_{5}}r_{5}^{N^{s}} mod B^{s+1}, C_{6} = K_{6}^{m_{6}}r_{6}^{N^{s}} mod B^{s+1}

where

m_{1} = β(m̃_{1} − \underline{m}_{1}) mod N^{s}, m_{2} = β(m̃_{2} − \underline{m}_{2}) mod N^{s}
m_{3} = β(m̃_{3} − \underline{m}_{3}) mod N^{s}, m_{4} = β(m̃_{4} − \underline{m}_{4}) mod N^{s}
m_{5} = β(m_{3}((m̃_{1} + m̃_{2}) − (\underline{m}_{1} + \underline{m}_{2}) + m̃ − \underline{m})) mod N^{s}
m_{6} = β(m_{4}((m̃_{1} + m̃_{2}) − (\underline{m}_{1} + \underline{m}_{2}) + \underline{m} − m̃)) mod N^{s} .

This is exactly what we want as

\begin{aligned}m_{6} + m_{5} & ≡ (m_{3} + m_{4})(β(m̃_{1} − \underline{m}_{1}) + β(m̃_{2} − \underline{m}_{2})) \\ & ≡ (m_{3} + m_{4})(m_{1} + m_{3}) (mod N^{s}) . \end{aligned}

7.5.3 Special Honest Verifier Zero-Knowledge We can assume without lose of generality that we know m_{3} and that we know t_{6} such that K_{6} = t_{6}^{N^{s}} mod N^{s+1}. Now pick r_{7}, v_{8}, m̃_{1}^{(r)}, r̃_{1}, m̃_{2}^{(r)}, r̃_{2}, m̃_{3}^{(r)}, r̃_{3}, m̃_{4}^{(r)}, r̃_{4}, r̃_{7}, r̃_{8}, m̃^{(r)}, r̃_{5}, r̃_{6} at random, and then let

C_{7} = K_{5}^{m_{3}}r_{7}^{N^{s}}, C_{8} = v_{8}^{N^{s}}

\overline{C}_{1} = K_{1}^{m̃_{1}^{(r)}}r̃_{1}^{N^{s}}C_{1}^{−e}, \overline{C}_{2} = K_{2}^{m̃_{2}^{(r)}}r̃_{2}^{N^{s}}C_{2}^{−e}
\overline{C}_{3} = K_{3}^{m̃_{3}^{(r)}}r̃_{3}^{N^{s}}C_{3}^{−e}, \overline{C}_{4} = K_{4}^{m̃_{4}^{(r)}}r̃_{4}^{N^{s}}C_{4}^{−e}
\overline{C}_{7} = K_{5}^{m̃_{3}^{(r)}}r̃_{7}^{N^{s}}C_{7}^{−e}, \overline{C}_{8} = K_{6}^{m̃_{4}^{(r)}}r̃_{8}^{N^{s}}C_{8}^{−e}
\overline{C}_{5} = C_{7}^{m̃_{1}^{(r)}+m̃_{2}^{(r)}}K_{5}^{m̃^{(r)}}r̃_{5}^{N^{s}}C_{5}^{−e}, \overline{C}_{6} = C_{8}^{m̃_{1}^{(r)}+m̃_{2}^{(r)}}K_{6}^{−m̃^{(r)}}r̃_{6}^{N^{s}}C_{6}^{−e}

7.5.4 State Construction After the special honest verifier simulation we are given

C_{1} = K_{1}^{m_{1}}r_{1}^{N^{s}}, C_{2} = K_{2}^{m_{2}}r_{2}^{N^{s}}

C_{3} = K_{1}^{m_{3}}r_{3}^{N^{s}}, C_{4} = K_{2}^{m_{4}}r_{4}^{N^{s}}
C_{5} = K_{1}^{m_{5}}r_{5}^{N^{s}}, C_{6} = K_{2}^{m_{6}}r_{6}^{N^{s}}

where

(m_{1} + m_{2})(m_{3} + m_{4}) ≡ (m_{5} + m_{6}) (mod N^{s}) .

Let l = \frac{m_{6}+m_{5}−(m_{1}+m_{2})(m_{3}+m_{4})}{N^{s}} and let r_{8} = v_{8}t_{6}^{−m_{4}} mod N such that C_{7} = K_{5}^{m_{3}}r_{7}^{N^{s}}, C_{8} = K_{6}^{m_{4}}r_{8}^{N^{s}} .

Then let

\overline{m}_{1} = m̃_{1}^{(r)} − em_{1} mod N^{s}, m̃_{1} = em_{1} + \overline{m}_{1}
\overline{r}_{1} = r̃_{1}r_{1}^{−e}K_{1}^{−(m̃_{1} div N^{s})} mod N
\overline{m}_{2} = m̃_{2}^{(r)} − em_{2} mod N^{s}, m̃_{2} = em_{2} + \overline{m}_{2}
\overline{r}_{2} = r̃_{2}r_{2}^{−e}K_{2}^{−(m̃_{2} div N^{s})} mod N
\overline{m}_{3} = m̃_{3}^{(r)} − em_{3} mod N^{s}, m̃_{3} = em_{3} + \overline{m}_{3}
\overline{r}_{3} = r̃_{3}r_{3}^{−e}K_{3}^{−(m̃_{3} div N^{s})} mod N
\overline{m}_{4} = m̃_{4}^{(r)} − em_{4} mod N^{s}, m̃_{4} = em_{4} + \overline{m}_{4}
\overline{r}_{4} = r̃_{4}r_{4}^{−e}K_{4}^{−(m̃_{4} div N^{s})} mod N
\overline{r}_{7} = r̃_{7}r_{7}^{−e}K_{5}^{−(m̃_{3} div N^{s})}
\overline{r}_{8} = r̃_{8}r_{8}^{−e}K_{6}^{−(m̃_{4} div N^{s})}
\overline{m} = m̃^{(r)} − em_{5} − m_{3}(\overline{m}_{1} + \overline{m}_{2} − m̃_{1} − m̃_{2}) mod N^{s}
m̃ = em_{5} + m_{3}(\overline{m}_{1} + \overline{m}_{2} − m̃_{1} − m̃_{2}) + \overline{m}
\overline{r}_{5} = r̃_{5}r_{5}^{−e}r_{7}^{m̃_{1}+m̃_{2}}K_{5}^{−(m̃ div N^{s})}
\overline{r}_{6} = r̃_{6}r_{6}^{−e}r_{8}^{m̃_{1}+m̃_{2}}K_{6}^{(m̃ div N^{s})−[el+(m_{3}+m_{4})((m̃_{1} div N^{s})+(m̃_{2} div N^{s}))]} .

It is straightforward to verify that these values all have the required distribution.

7.6 Proof of Identity and Proof of Additive Relation

A proof of identity between committed values can be extracted from the above proof of multiplicative relation, by setting m_{3} = 1 and m_{4} = 0. The proof can be somewhat simplified by eliminating the unnecessary values \overline{C}_{3}, \overline{C}_{4}, C_{7}, C_{8}.

A proof of additive relation between commitments using the same key, (K_{1}^{m_{1}}r_{1}^{N^{s}}, K_{2}^{m_{2}}r_{2}^{N^{s}}), (K_{1}^{m_{3}}r_{3}^{N^{s}}, K_{2}^{m_{4}}r_{4}^{N^{s}}), and (K_{1}^{m_{5}}r_{1}^{N^{s}}, K_{2}^{m_{6}}r_{2}^{N^{s}}), where (m_{1}+ m_{2})+(m_{3} +m_{4}) = m_{5} +m_{6}, can be constructed by proving that the base commitments C_{1} = K_{1}^{m_{1}+m_{3}−m_{5}}(r_{1}r_{3}r_{5}^{−1})^{N^{s}} and C_{2} = K_{2}^{m_{6}−m_{2}−m_{4}}(r_{6}r_{2}^{−1}r_{4}^{−1})^{N^{s}} commit to the same value. Arbitrary commitments can be brought on this restricted form by recommitting in some common key and then using the proof of identity to check that this was done correctly. A proof that C_{1} and C_{2} commit to the same value can be constructed in line with the proof of identity of the transformed scheme.

7.7 Proof of Binary Boolean Relations

The proof that two committed values are identical implies a proof that a committed value equals a public constant, and hence, using the same techniques as in Section 6.7, a proof that a committed value equals 0 or 1. It is well known that multiplication and addition in any ring can be used to simulate Boolean operations efficiently, when the input is constrained to 0/1 values, so we obtain therefore immediately proofs for any relation defined by a binary Boolean function f, i.e., a proof that committed values m_{1}, m_{2}, m_{3} are 0/1 values and satisfy f(m_{1}, m_{2}) = m_{3}.

Theorem 3 Relative to the DCRA, the above commitment scheme is a special mixed commitment scheme with proofs of relations between committed values for identity, additive relation, multiplicative relation ( mod N^{s}), and for Boolean relations defined by any binary Boolean function.

8 Efficient Universally Composable Zero-Knowledge Proofs

In [CF01] Canetti and Fischlin showed how universally composable commitments can be used to construct simple Zero-Knowledge (ZK) protocols which are universally composable. This is a strong security property, which implies concurrent and non-malleable ZK proof of knowledge.

The functionality F_{ZK}^{R} for universally composable zero-knowledge (for binary relation R) is as follows.

1. Wait to receive a value (verifier, id, P_{i}, P_{j}, x) from some party P_{i}. Once such a value is received, send (verifier, id, P_{i}, P_{j}, x) to S, and ignore all subsequent (verifier, …) values.

2. Upon receipt of a value (prover, id, P_{j}, P_{i}, x′, w) from P_{j}, let v = 1 if x = x′ and R(x, w) holds, and v = 0 otherwise. Send (id, v) to P_{i} and S, and halt.

In [CF01] a protocol for Hamiltonian-Cycle (HC) is given and proven to securely realize F_{ZK}^{HC}.

8.1 Exploiting the Multi-Bit Commitment Property

First we show how the fact that we can commit to k bits using O(k) bits of communication can be used to reduce the communication complexity of known solutions.

Before describing this optimization we demonstrate the technique from [CF01] to get a similar protocol for satisfiability of Boolean circuits (SAT).

Parts of the following treatment will be very close in structure and text to the one in [CF01], but we include it for completeness.

A Boolean circuit C consists of l inputs and m binary gates. (For notational reason we only consider binary gates.) The binary gates are named G_{l+1}, …, G_{l+m}. The binary gate G_{i} is a tuple (i_{1}, i_{2}, G_{i,0,0}, G_{i,0,1}, G_{i,1,0}, G_{i,1,1}), where i_{1}, i_{2} < i and G_{i,0,0}, G_{i,0,1}, G_{i,1,0}, G_{i,1,1} ∈ {0, 1}. An evaluation eval(C, x) = (G_{1}(x), …, G_{l+m}(x)) ∈ {0, 1}^{l+m} of C on input x ∈ {0, 1}^{l} is given by G_{i}(x) = x_{i} for i = 1, …, l, G_{i}(x) = G_{i,G_{i_{1}}(x),G_{i_{2}}(x)} for i = l + 1, …, l + m. We let C(x) denote G_{l+m}(x).

A scrambler is a value S ∈ {0, 1}^{l+m}, where S_{l+m} = 0. An S-scrambling of circuit C is a circuit S(C), where for i = l + 1, …, l + m the gate G′_{i} is given by G′_{i} = (i_{1}, i_{2}, G′_{i,0,0}, G′_{i,0,1}G′_{i,1,0}G′_{i,1,1}), where G_{i,b_{1},b_{2}} = G_{i,b_{1}⊕S_{i_{1}},b_{2}⊕S_{i_{2}}} ⊕ S_{i}. An S-scrambling of input x is S(x) = (x_{1} ⊕ S_{1}, …, x_{l} ⊕ S_{l}). Note that eval(S(G), S(x)) = eval(G, x) ⊕ S.

The protocol, which we name SAT, proceeds as follows.

1. Given input (Prover, id, P, V, C, x), where C is a circuit and x is an input for the circuit the prover proceeds as follows. If C(x) = 0, then P sends a message reject to V. Otherwise, P proceeds as follows for j = 1, …, t.

(a) Pick a uniformly random scrambler S^{j} and compute x^{j} = S^{j}(x) and C^{j} = S^{j}(C).

(b) Using F_{com} commit to the bits of the scrambler.

(c) Using F_{com} commit to x^{j} and under commitment id (j, i, b_{1}, b_{2}) commit to G_{i,b_{1},b_{2}}^{j} for i = l+1, …, l+m, b_{1} ∈ {0, 1}, and b_{2} ∈ {0, 1}.

2. Given input (Verifier, id, V, P, C), the verifier waits to receive either reject from P, or receipts from F_{com}. If reject is received, then V outputs (id, 0) and halts. Otherwise, once all the receipts are received V randomly chooses t bits c_{1}, …, c_{t} and sends these to P.

3. Upon receiving c_{1}, …, c_{t} from V, P proceeds as follows for j = 1, …, t.

(a) If c_{j} = 0, then reveal S^{j} and C^{j}.

(b) If c_{j} = 1, then reveal x^{j} and for each gate G_{i}^{j} = (i_{1}, i_{2}, G_{i,0,0}^{j}, G_{i,0,1}^{j}, G_{i,1,0}^{j}, G_{i,1,1}^{j}) open the commitment with id (j, i, G_{i_{1}}^{j}(x^{j}), G_{i_{1}}^{j}(x^{j})).

4. Upon receiving the appropriate (Open, …) messages from F_{com} the verifier V verifies the following for all j = 1, …, t. If c_{j} = 0, then it holds that C^{j} = S^{j}(C). If c_{j} = 1, then it holds that the revealed x^{j}, v_{l+1}, …, v_{l+m} are consistent with a acceptance, i.e. if gate i_{1} was open to v_{1} and gate i_{2} was open to v_{2}, then for gate i the commitment with id (j, i, v_{1}, v_{2}) was opened, and further more gate l + m was opened to 1.

Theorem 4 The protocol SAT securely realizes F_{ZK}^{SAT} in the F_{com}-hybrid model.

Proof (sketch): Let A be an adversary attacking SAT in the F_{com}-hybrid model. We construct a simulator S such that no environment Z can distinguish between A attacking SAT in the F_{com}-hybrid model and S attacking the ideal process for F_{ZK}^{SAT}.

The simulator S runs a simulated copy of A. Messages from Z are relayed to A and messages from A to its environment are relayed to Z. Other types of messages are handled as follows.

1. If A, controlling a corrupted party P, starts an interaction as a prover with an uncorrupted party V, then S records the values that A sends to F_{com}, sends challenges c_{1}, …, c_{t} as in the protocol, and records A’s responses. Now S simulates V ’s decision and if V accepts, then S tries to find a witness x and hands it to the ideal functionality. If such a witness cannot be found the simulator aborts.

To find the witness S finds a j, where c_{j} = 1 and C^{j} = S^{j}(C). It is proven below that the probability of not finding such j is less than 2^{−t/2}. Let x^{j} and v_{l+1}, …, v_{l+m} be the values revealed by A and let x be given by x_{i} = x_{i}^{j} ⊕ S_{i}^{j}. Then eval(C, x) = (x_{1}^{j}, …, x_{l}^{j}, v_{l+1}, …, v_{l+m}) ⊕ S^{j}. To see this observe that for i = 1, …, l we have that G_{i}(x) = x_{i} = x_{i}^{j} ⊕ S_{i}^{j} and for i = l + 1, …, l + m we inductively have that G_{i}(x) = G_{i,G_{i_{1}}(x),G_{i_{2}}(x)} = G_{i,v_{i_{1}}⊕S_{i_{1}}^{j},v_{i_{2}}⊕S_{i_{2}}^{j}} = G_{i,v_{i_{1}},v_{i_{2}}} ⊕ S_{i}^{j} = v_{i} ⊕ S_{i}^{j}. Especially

we have that C(x) = v_{l+m} ⊕ S_{l+m}^{j} = 1 ⊕ 0 = 1 and thus x is a witness.

2. If an uncorrupted party P starts an interaction with a corrupted party V, then S learns from the ideal functionality F_{ZK}^{SAT} whether V should accept or reject, and simulates the view of A accordingly. Note that S has no problem carrying out the simulation since it simulates for A an interaction with F_{com} where F_{com} is played by S. Thus, S is not bound by the “commitments” and can “open” them in whichever way it pleases.

3. If two uncorrupted parties P and V interact, then S simulates for A the appropriate protocol messages. This is very similar to the case of corrupted verifier, since the protocol is a Σ-protocol.

4. Party corruptions are dealt with in a straightforward way. Since the protocol is a Σ-protocol, corrupting the verifier provides the adversary with no extra information. When the prover is corrupted S corrupts the prover in the ideal process, obtains x, and generates an internal state of the prover that matches the protocol stage. Generating such a state is not problematic since S is not bound by any “commitments”, and it can freely choose the remaining values to match the (simulated) conversation up to the point of corruption.

Given that S does not abort in Step 1, the validity of the simulation is straightforward. We prove that the probability that a proof is accepted and there does not exist j, where c_{j} = 1 and C^{j} = S^{j}(C), is less than 2^{−t/2}.

Assume that the expected number of indices j where C^{j} = S^{j}(C) is at least t/2. Then the probability that c_{j} = 0 for all these indices is less than 2^{−t/2} and thus the probability that there does not exist j, where c_{j} = 1 and C^{j} = S^{j}(C), is less than 2^{−t/2}. Assume on the contrary that the expected number of indices j, where C^{j} = S^{j}(C), is less than t/2. Then with probability less than 2^{−t/2} we have c_{j} = 1 on all the indices where C^{j} ≠ S^{j}(C) and thus the probability of acceptance is less than 2^{−t/2}. □

We now show how to use our new universally composable commitments to make the protocol more efficient.

For each value of j the protocol commits to 2l + 5m − 1 bits. Of these, the 2l + m − 1 bits of x^{j} and S^{j} are always either revealed or not. We can therefore efficiently commit to them using the multi-bit commitments.

We cannot however not commit to the remaining 4m commitments using multi-bit commitments. The reason for this is that if c_{j} = 0 all the bits should be revealed and if c_{j} = 1, then only a subset S of them should be revealed, and more importantly, revealing the subset S in case c_{j} = 0 would effectively reveal x.

In [KMO89] Kilian, Micali, and Ostrovski presented a general technique for transforming a multi-bit commitment scheme into a multi-bit commitment scheme with the property that individual bits can be open independently. Unfortunately their technique adds one round of interaction. However, we do not need the full generality of their result. This allows us to modify the technique to avoid the extra round of interaction. Let m ∈ {0, 1}^{4m} denote the bits to be committed to and let S ∈ {0, 1}^{4m} denote the subset {i|S_{i} = 1} of the entries of m which should be revealed if c_{j} = 1. Then m should be revealed if c_{j} = 0 and (S, m∧S) should be revealed if c_{j} = 1. Then do the commitment by generating a uniformly random pad m′ ∈ {0, 1}^{4m} and committing to the four values m′, m ⊕ m′, S, and m′ ∧ S individually using multi-bit commitments. The verifier then challenges uniformly with d_{j} ∈ {0, 1, 2}. If d_{j} = 0, then reveal m and m ⊕ m′. If d_{j} = 1, then reveal m ⊕ m′, S and m′ ∧ S and thereby m ∧ S = (m ⊕ m′) ∧ S ⊕ (m′ ∧ S). If d_{j} = 2, then reveal m′, S, and m′ ∧ S and let the verifier check the consistency of these values.

The extension of the above analysis to consider the modified protocol is straightforward. In Step 1 find a j, where d_{j} = 1 and C^{j} = S^{j}(C) and the committed values are consistent. Then proceed as before. It is easy to see that the probability that such a j does not exist is less than 2^{−t/3}.

It is clear that we can achieve the same error probability as in the original protocol by increasing t by a constant factor of 3/2. Furthermore, the number of bits committed to for each scrambling is the same up to a constant factor. Therefore, if we implement the modified protocol using our commitment scheme, we get communication complexity O((l + m + k)t), where k is the security parameter of the commitment scheme and t is the number of iterations in the zero-knowledge proof. This follows because we can commit to O(l + m) bits by sending O(l + m + k) bits. This can be compared to the O((l + m)kt) bits we would need for SAT using the commitments from [CF01]; this is an improvement by a factor θ(\frac{(l+m)k}{(l+m)+k}).

8.2 Exploiting Efficient Proofs of Relations

Here we show how we can use the homomorphic properties and/or efficient proofs of relations on committed values to reduce the communication complexity and the round complexity in a different way. This is done by “evaluating” the circuit using the proofs of relations.

1. Given input (Prover, id, P, V, C, x), where C is a circuit and x is an input for the circuit, the prover proceeds as follows. If C(x) = 0, then P sends a message reject to V. Otherwise, compute eval(G, x) = (v_{1}, …, v_{l+m}) and using F_{HCOM} commit to the bits of eval(G, x), except v_{l+m}.

Then for each gate G_{i} = (i_{1}, i_{2}, G_{i,0,0}, G_{i,1,0}, G_{i,0,1}, G_{i,1,1}), i = l+1, …, l+ m − 1, P proves (using F_{HCOM}) that the commitments to v_{i}, v_{i_{1}}, and v_{i_{2}} are in the binary Boolean relation specified by (G_{i,0,0}, G_{i,1,0}, G_{i,0,1}, G_{i,1,1}). And for G_{l+m} = (i_{1}, i_{2}, G_{l+m,0,0}, G_{l+m,1,0}, G_{l+m,0,1}, G_{l+m,1,1}), proves that v_{i_{1}} and v_{i_{2}} are in the relation G_{l+m,v_{i_{1}},v_{i_{2}}} = 1. This can be done by committing to 1 (using F_{HCOM}) and then doing a proof on the commitments.

2. Given input (Verifier, id, V, P, C), the verifier waits to receive either reject from P, or receipts and proofs from F_{HCOM}. If reject is received, then V outputs (id, 0) and halts. Otherwise, once all the appropriate receipts and proofs are received V outputs (id, 1).

The following theorem is straightforward.

Theorem 5 The protocol SAT_{2} securely realizes F_{ZK}^{SAT} in the F_{HCOM}-hybrid model.

This protocol has no messages of its own. All interaction is done through F_{HCOM}. The security notion guarantees that the security is preserved under any scheduling of the messages of the underlying F_{HCOM} protocol. This especially allows us to run the overall zero-knowledge proof as a Σ-protocol by bundling the messages when our implementation of the commitment protocol is used. This protocol requires O(l + m) commitments to single bits, each of which require O(k) bits of communication. Then we need to do O(l + m) proofs of relations, each of which require O(k +t) bits of communication using our implementation and assuming that we want an overall error probability of 2^{−Ω(t)}. This amounts to O((l + m)(k + t)) bits of communication, and is an improvement over the O((l + m)kt) bits for the original protocol, namely by a factor O(\frac{kt}{k+t}).

This is incomparable to the optimization using multi-bit commitments. But note that in the theory of zero-knowledge protocols, sometimes one only considers the case where all parameters are linear in the size m of the common input. In this case, both optimizations improve from O(m^{3}) to O(m^{2}) bits.

References

[Can01] Ran Canetti. Universally composable security: A new paradigm for cryptographic protocols. In 42th Annual Symposium on Foundations of Computer Science. IEEE, 2001.

[CDS94] R. Cramer, I. B. Damgård, and B. Schoenmakers. Proofs of partial knowledge and simplified design of witness hiding protocols. In Yvo Desmedt, editor, Advances in Cryptology - Crypto ’94, pages 174–187, Berlin, 1994. Springer-Verlag. Lecture Notes in Computer Science Volume 839.

[CF01] Ran Canetti and Marc Fischlin. Universally composable commitments. In J. Kilian, editor, Advances in Cryptology - Crypto 2001, pages 19–40, Berlin, 2001. Springer-Verlag. Lecture Notes in Computer Science Volume 2139.

[Dam00] Ivan Damgård. Efficient concurrent zero-knowledge in the auxiliary string model. In Bart Preneel, editor, Advances in Cryptology - EuroCrypt 2000, pages 418–430, Berlin, 2000. Springer-Verlag. Lecture Notes in Computer Science Volume 1807.

[DJ01] Ivan Damgård and Mads Jurik. A generalisation, a simplification and some applications of Paillier’s probabilistic public-key system. In Kwangjo Kim, editor, Public Key Cryptography, 4th International Workshop on Practice and Theory in Public Key Cryptography, pages 110–136, Berlin, 2001. Springer. Lecture Notes in Computer Science Volume 1992.

[DJN01] Ivan B. Damgård, Mads J. Jurik, and Jesper B. Nielsen. A generalization, a simplification and some applications of Paillier’s probabilistic public-key system. Manuscript, obtainable from authors. Submitted to journal. Preliminary version occurs in [DJ01], 2001.

[KMO89] Joe Kilian, Silvio Micali, and Rafail Ostrovsky. Minimum resource zero-knowledge proofs (extended abstract). In 30th Annual Symposium on Foundations of Computer Science, pages 474–479, Research Triangle Park, North Carolina, 30 October–1 November 1989. IEEE.

[OU98] Tatsuaki Okamoto and Shigenori Uchiyama. A new public-key cryptosystem as secure as factoring. In K. Nyberg, editor, Advances in Cryptology - EuroCrypt ’98, pages 308–318, Berlin, 1998. Springer-Verlag. Lecture Notes in Computer Science Volume 1403.

[Pai99] P. Paillier. Public-key cryptosystems based on composite degree residue classes. In Jacques Stern, editor, Advances in Cryptology - EuroCrypt ’99, pages 223–238, Berlin, 1999. Springer-Verlag. Lecture Notes in Computer Science Volume 1592.

Recent BRICS Report Series Publications

RS-01-41 Ivan B. Damgård and Jesper Buus Nielsen. Perfect Hiding and Perfect Binding Universally Composable Commitment Schemes with Constant Expansion Factor. October 2001. 43 pp.

RS-01-40 Daniel Damian and Olivier Danvy. CPS Transformation of Flow Information, Part II: Administrative Reductions. October 2001. 9 pp.

RS-01-39 Olivier Danvy and Mayer Goldberg. There and Back Again. October 2001. 14 pp.

RS-01-38 Zoltán Ésik. Free De Morgan Bisemigroups and Bisemilattices. October 2001. 13 pp.

RS-01-37 Ronald Cramer and Victor Shoup. Universal Hash Proofs and a Paradigm for Adaptive Chosen Ciphertext Secure Public-Key Encryption. October 2001. 34 pp.

RS-01-36 Gerth Stølting Brodal, Rolf Fagerberg, and Riko Jacob. Cache Oblivious Search Trees via Binary Trees of Small Height. October 2001.

RS-01-35 Mayer Goldberg. A General Schema for Constructing One-Point Bases in the Lambda Calculus. September 2001. 6 pp.

RS-01-34 Flemming Friche Rodler and Rasmus Pagh. Fast Random Access to Wavelet Compressed Volumetric Data Using Hashing. August 2001. 31 pp.

RS-01-33 Rasmus Pagh and Flemming Friche Rodler. Lossy Dictionaries. August 2001. 14 pp. Short version appears in Meyer auf der Heide, editor, 9th Annual European Symposiumon on Algorithms, ESA ’01 Proceedings, LNCS 2161, 2001, pages 300– 311.

RS-01-32 Rasmus Pagh and Flemming Friche Rodler. Cuckoo Hashing. August 2001. 21 pp. Short version appears in Meyer auf der Heide, editor, 9th Annual European Symposiumon on Algorithms, ESA ’01 Proceedings, LNCS 2161, 2001, pages 121–