Publicly auditable conditional blind signatures

Abstract

This work formalizes Publicly Auditable Conditional Blind Signatures (PACBS), a new cryptographic primitive that allows the verifiable issuance of blind signatures, the validity of which is contingent upon a predicate and decided by a designated verifier. In particular, when a user requests the signing of a message, blinded to protect her privacy, the signer embeds data in the signature that makes it valid if and only if a condition holds. A verifier, identified by a private key, can check the signature and learn the value of the predicate. Auditability mechanisms in the form of non-interactive zero-knowledge proofs are provided, so that a cheating signer cannot issue arbitrary signatures and a cheating verifier cannot ignore the embedded condition. The security properties of this new primitive are defined using cryptographic games. A proof-of-concept construction, based on the Okamoto–Schnorr blind signatures infused with a plaintext equivalence test is presented and its security is analyzed.

Keywords

Blind signatures designated verifier signatures plaintext equivalence coercion-resistant electronic voting

1. Introduction

Alice wants to vote remotely in an electronic election conducted by Simon, an election authority. Chuck, a coercer, wants to dictate a voting behavior on her, by impersonating her or by making her vote randomly or by forcing her to abstain. Can Alice fool Chuck, and evade his attack without any consequences?

This question was answered affirmatively by Juels, Catalano, and Jakobsson (JCJ) who presented a framework for creating coercion-resistant e-voting protocols in [23]. Their main idea was that Alice registers an anonymous credential with Simon, before voting begins. When she casts her ballot, she must attach it to her vote. If she is not being coerced she presents the valid credential (i.e. the one that she had registered). If she is being coerced she presents a new, fake, but indistinguishable one. When counting the votes, Simon must discard the ballots that contain unregistered credentials and count only those that contain valid ones. This must be done without leaking the vote contents to Simon or whether it was counted to Chuck, while allowing Alice to verify that her vote was taken into account. Note that if Chuck cannot be convinced that a vote was indeed counted, then the framework protects both against an active coercer and also provides receipt-freeness, i.e. protection against a corrupted user who wants to sell her vote and must present a receipt to convince the buyer.

Motivated by this scenario, one could build a generic cryptographic token from these requirements, by starting from a digital signature and augmenting it with the following properties:

Blindness: The signer cannot access the message (e.g. to protect vote secrecy from the election authorities). Ideally, blindness should be perfect.

Conditionality: The signature ‘carries’ the result of some data processing performed by the signer – e.g. if the voter is eligible or if she is coerced or, in general, if a user can access a service. In order to avoid ‘leaking’ this authorization status by the mere existence of the signature, the token could be given both to eligible and ineligible users. In the former case it should be valid and invalid in the latter.

Designated-verifier: While the signature itself will be available to everyone, its semantics should only be revealed to a specific entity (e.g. the tallying authorities). As a result, it must not be publicly verifiable, but its validity should be available only to a designated entity.

Public Auditability: The case of a malicious signer and designated verifier must also be taken into account. The token should be accompanied with auditable evidence that forces them to follow the protocol. This evidence should not leak the validity of the signature.

At first glance, the combination of a designated verifier and public auditability seems contradictory. But this ‘paradox’ is exactly what is required to solve the e-voting coercion-resistance problem. If the signature, which indicates that a vote should be counted, were publicly verifiable, then the coercer would know if the voter followed his instructions. So, in this setting, only the tallier should be the one to verify the signature and count the vote. However, this would mean that the resulting scheme would not possess universal verifiability, as a corrupted tallier could arbitrarily choose which votes to count and which not. In order to avoid this situation, the designated verifier must produce evidence to prove that he followed the verification protocol. So while the public cannot know if a signature is valid or not, they can be sure that the computations of an untrusted verifier were not arbitrary. The voter herself, on the other hand, would also, in private, be aware of the conditional data (e.g. if she used the correct credential or not) and therefore have confidence that her vote was counted.

1.1. Contribution

In this work, two cryptographic primitives are presented to satisfy this diverse set of properties. The first, Conditional Blind Signatures (CBS) 1

¹
Initially proposed in [38].

satisfies blindness, conditionality, and verification by a designated entity. The second, Publicly Auditable Conditional Blind Signatures (PACBS) 2

A construction was introduced in [18].

additionally satisfies public auditability.

In both schemes, instead of creating a digital signature by solely applying a function parameterized with a secret key to a message, a predicate is also applied. In this sense, the validity of the signature is conditional, which means that it depends on the predicate being true. Both schemes are perfectly blind so that the message is protected against a computationally unbounded adversary and strongly designated to a verifier.

In CBS, both the signer and the verifier are trusted. As a result, the predicate is modeled as a private input bit b to the signer. This formalization means that the signer performs some private computations and, based on their results, determines if a valid signature should be issued. On the other hand, PACBS protect from a malicious signer or a malicious verifier that may disregard the predicate and the data on which it is computed. As a result, the data on which the predicate depends must be publicly available and audit functions for signature creation and verification are defined. Evidence, in the form of non-interactive zero-knowledge proofs, is produced along with the signature. So, anyone can check if the predicate was correctly computed relative to the public data, embedded into the signature, and verified.

Security models that formally reflect the desired properties are also defined. To this end, blindness and unforgeability – the standard properties of blind signatures – are complemented with a new property, conditional verifiability, that combines the designated-verifier with the conditionality of the signature and states that nobody except the signer and the designated verifier can know if it is valid or not. PACBS, also require public auditability which is formalized as well.

As a proof of concept, constructions for both primitives are also provided based on the Okamoto–Schnorr blind signatures [28]. Finally, their security analysis is presented based on well-studied cryptographic assumptions.

PACBS were mainly created to satisfy the strict requirements of coercion-resistant electronic voting. However, abstracting away from this usage scenario, the fact that CBS and PACBS connect the generation and verification of digital signatures with external data can make them a generic cryptographic primitive to provide certified unlinkability, i.e. used to implement tokens that protect user privacy, while also regulating the usage of a service. Their potential applications are explored in Section 7.

1.2. Related work

CBS and PACBS combine concepts that permeate many well known cryptographic primitives, such as group [10], ring [32] and designated confirmer signatures (DCS) [7]. Moreover, ideas from cryptographic primitives such as partially blind signatures [1], plaintext equivalence tests (PETs) [21], designated verifier proofs (DVP) [22] and conditional disclosure of secrets (CDS) [16] are utilized.

To begin with, PETs [21] were proposed by Juels and Jakobsson as a way for a group of parties to convince a set of participants that two ciphertexts indeed encrypt the same plaintext. This works by utilizing the homomorphic properties of the underlying cryptosystem to divide the ciphertexts and decrypt a blinded version of the quotient. If the ciphertexts hide the same plaintext, the result is 1. Otherwise, the result is a random group element.

Next, the idea of a designated verifier found in [7] and [22] was applied. These schemes replace the public verifiability of digital signatures and proofs of knowledge with (implicit or explicit) validation only by a particular entity. For instance, DCS solve the signer unavailability problem of undeniable signatures [8], by introducing another party to the protocol that can confirm a signature in case the signer is unavailable. In designated verifier proofs (DVP) [22] the verifier is identified by the inclusion of his public key in the proof. As a result, he can create simulations that no third party can distinguish. So, in effect, the validity of a proof rests on the validity of a statement or on the knowledge of the secret verification key. Consequently, the designated verifier can produce valid-looking proofs, thus fooling any third party. In the same manner, designated verifier signatures (DVS) aim to increase the privacy of the user, by limiting the parties that can be convinced for the authenticity of a digital signature only to a single entity. This designated verifier can again simulate signatures using his secret key. In strong designated verifier signatures this secret key must be used during verification. The original threat model for DVP and DVS in [22] and subsequent works [26,27], state that an adversary who obtains the secret verification key, becomes in essence the designated verifier. Consequently, in DVS, signatures simulated by the verifier, are not considered forgeries. In fact, they serve an important design goal of the scheme; to increase the privacy of the user, by limiting who can perform authenticity checks on the signature.

Finally, it must be noted that the use of a group/ring signature scheme with a designated verifier is equivalent to the signer sending a message to the verifier, by using the signature as a private channel. For instance, if the group members are treated as possible responses to the message to be signed, a designated group signature is equivalent to sending a particular response to the verifier. This resembles conditional disclosure of secrets [16], which was proposed as a way for a client to obtain a secret held by a server if and only if the input of the client satisfies a certain condition. The client may hold a secret key and encrypt the input using the corresponding public key that is known to the server.

This work, combines all these usage scenarios. The verifier for PACBS can be a third party which is ‘designated’ during the signature creation process or simply the signer at a later time, something that sets it apart from similar schemes such as CDS. The existence of such a verifier is essential to achieve coercion-resistance in electronic voting, as a publicly verifiable signature could indicate to the coercer that a particular vote was counted. This was one of the explicit goals of DVP already stated in [22], but considered only from the point of view of the voter. Moreover, inspired by the use of PETs in JCJ [23] and the common unblinded input of partially blind signatures [1], the value of the predicate is similarly embedded in the signature generated by PACBS. The possible values of the signature can be considered as virtual group members, as first proposed by [29]. The most important difference of PACBS with all these related proposals is that the user messages are blinded, so that the signer, can never have access to their contents, and the auditability of the actions of the signer and the verifier.

Conditional Blind Signatures (CBS) were introduced in [38]. Their drawback is that the validity predicate is represented by a simple bit, external to the signature, which means that it can be maliciously ignored both by corrupted signers and corrupted verifiers. Furthermore, CBS provide no evidence, making them suitable only in trusted environments, since signing and verification are opaque. PACBS, this paper’s main contribution, extend CBS to fix both of these problems.

On the application front, the JCJ framework was adapted to use blind signatures, for increased voter privacy, in [17]. In follow-up work, [18], a concrete implementation was provided, where the basic mechanisms of PACBS were introduced, in a bottom-up manner. However, their construction was examined solely in the context of a voting scheme and not as a standalone primitive. Thus, they lacked generality and, importantly, they were not accompanied by a security model. This meant that no formal proof of security could be given. This work conceptually defines PACBS in a general way, fixing those drawbacks. It also considers other uses, in addition to coercion-resistance in remote e-voting.

2. Preliminaries

2.1. Notation

The security parameter is denoted as λ. A negligible function is denoted as $negl$ . The algorithms that are executed by the users, the signers, and the adversaries are denoted as $U, S, A$ respectively, while their (secret) input follows in parentheses. A protocol Π that requires interaction between two algorithms $A, B$ with secret input $α, β$ respectively and public input γ with output O is denoted as $O \leftarrow Π ⟨ A (α), B (β), γ ⟩$ . Assignment is $: =$ and the output of an algorithm or a protocol using ←. To indicate the selection of an element uniformly at random $\leftarrow_{$}$ is used. An equality check is indicated by =, which returns $0, 1$ instead of $False, True$ . Algorithms are assumed to have an internal state that is preserved between successive invocations in cryptographic games. For simplicity, this internal state is omitted during the exposition. When an algorithm is used in a particular mode of operation, this mode is the first argument (e.g. $A (guess)$ ). Empty values or values omitted for brevity are denoted by ·. We denote the set ${1, \dots, n}$ with $[n]$ . Our constructions work in the random oracle model, which means that the outputs of hash functions can be considered to be selected uniformly at random. We denote encrypted elements by using boldface.

2.2. Security assumptions

The security of the proposed schemes depends on the Computational Diffie Hellman (CDH) and the Decisional Diffie Hellman (DDH) assumptions. Informally, the CDH assumption states that given a group $G$ , a generator g and two group elements $g^{a}, g^{b}$ , the value $g^{a b}$ cannot be efficiently computed. The DDH assumption states that triples of group elements $(g^{a}, g^{b}, g^{a b})$ and $(g^{a}, g^{b}, g^{c})$ , where $a, b, c$ are random elements of ${1, \dots, | G |}$ , cannot be efficiently distinguished. More formally, following [5], let G be a group family and g a generator of a particular member $G$ of G.

Definition 1 (Computational Diffie Hellman Assumption).

A CDH algorithm A is a probabilistic polynomial time algorithm satisfying $Pr [A (g, g^{a}, g^{b}) = g^{a b}] > \frac{1}{λ^{k}}$ for some fixed $k > 0$ and sufficiently large λ, where the probability is taken over the selection of $G$ , $a, b$ and the random bits of A. The group family satisfies the CDH assumption if there is no CDH algorithm for it.

Definition 2 (Decisional Diffie Hellman Assumption).

A DDH algorithm A is a probabilistic polynomial time algorithm satisfying $| Pr [A (g, g^{a}, g^{b}, g^{a b}) = 1] - Pr [A (g, g^{a}, g^{b}, g^{c}) = 1] | > \frac{1}{λ^{k}}$ for some fixed $k > 0$ and sufficiently large λ, where the probability is taken over the selection of $G$ , $a, b, c$ and the random bits of A. The group family satisfies the DDH assumption if there is no DDH algorithm for it.

There are many groups where the Decisional Diffie Hellman Assumption is believed to hold [5]. One such group is the q order subgroup of quadratic residues in $Z_{p}^{*}$ where $q, p = 2 q + 1$ are primes.

2.3. Cryptographic primitives

2.3.1. Blind signatures

CBS and PACBS are extensions of the blind signature concept proposed by David Chaum [6], which allows a signer to sign messages without having access to their contents. The user first blinds the message and the signer signs it in this blinded form. The user subsequently unblinds the signature, and retrieves a valid signature for the plain message, which can be used as a normal signature. The motivating application, behind this primitive is anonymous centralized electronic cash. A bank blindly signs tokens created by the user to vouch for her capacity to spend a coin of particular value. Blinding protects user privacy, as it stops the bank from linking signing requests with signature verifications.

The security properties stem from this usage scenario. Blindness or unlinkability states that the signer cannot retrieve the signed message or associate signatures with protocol executions. Unforgeability, a standard property of digital signatures, states that a (malicious) user cannot create valid signatures without the possession of the signing key. However, as noted in [30], in blind signatures this is the actual use case: The user creates the signature, herself, from an ‘intermediate’ representation provided by the signer. Thus, the standard unforgeability definitions cannot be applied. Instead, unforgeability is defined as the inability of a forger to create more signatures than the number of interactions with the bank.

This interpretation of unforgeability has been formalized in [31] with the notion of $(l, l + 1)$ -Forgery, where for any integer l the forger $A$ must produce $l + 1$ valid signatures after at most l interactions with the signer $S$ . One-More Forgery is a $(l, l + 1)$ -Forgery, where l is polynomially bounded, while Strong One-More Forgery is a $(l, l + 1)$ -Forgery, where l is polylogarithmically bounded.

The security of blind signatures has been studied in the random oracle model [30]. These results were later refined in [31] and revisited in [36]. A complexity-based approach was presented in [24], however, the schemes analyzed are deemed largely theoretical.

The CBS and PACBS instantiations presented in this paper, are direct extensions of the Okamoto–Schnorr (OS) blind signature scheme [28], which is presented in Fig. 1.

Fig. 1.

Okamoto–Schnorr Blind Signatures.

2.3.2. Proofs of knowledge

In order to make PACBS publicly auditable, non-interactive zero-knowledge (NIZK) proofs of knowledge (PoK) are used. In particular, the classic NIZK proofs of discrete logarithm knowledge [34] and equality [9] are employed, which can be made non-interactive with the Fiat–Shamir heuristic [13]. Such a proof, as in [9] for instance, is denoted by the functionality $NIZK$ in the following way: $NIZK {(g_{1}, g_{2}, a, b), (x) : a = g_{1}^{x} \land b = g_{2}^{x}}$ , where x is the witness and $(g_{1}, g_{2}, a, b)$ are public data. Composition of PoKs is also employed, as described in [12].

2.3.3. Plaintext equivalence test

The signature verification in the PACBS construction employs techniques inspired by the PET primitive, used in [21] to convince a distributed set of entities who share a decryption key that two ciphertexts hide the same plaintext. It works by first having the participants blind the ciphertexts and then employing the homomorphic properties of the underlying cryptosystem to compute a function on them, so that a joint decryption of the result will reveal if the two initial ciphertexts encrypted the same message or not.

3. Conditional blind signatures

We begin with the simpler of our two primitives, Conditional Blind Signatures (CBS). In CBS, a user requests a signature and a trusted signer provides it. The purpose of the signature is to authorize the usage of a service. However, the access patterns, which would leak if all the provided signatures were publicly verifiable, must be hidden. Therefore, both valid and invalid signatures can be requested. To model the signing process in an authorization-agnostic manner, a bit b is used as a private input of the signer. In particular, the signature is valid if and only if $b = 1$ , and is privately verified by a designated verifier, who ultimately grants usage of the service. The adversary in CBS, is an eavesdropper that must be prevented from discovering if a particular signature is valid or invalid. Even the user requesting the signature should not be able to convince a third party of its validity. No auditable evidence is produced from signing or verifying as both the signer and the verifier are considered honest. Thus, CBS are conceptually simple. For this reason, they can also be used as a stepping stone for the more complex PACBS presented in Section 5.

3.1. Definitions

Definition 3.
A conditional blind signature (CBS) scheme is a triple ( $CBS.Gen$ , $CBS.Sign$ , $CBS.Vrfy$ ) such that:
$(({sk}_{S}, {pk}_{S}), ({sk}_{V}, {pk}_{V}), prms) \leftarrow CBS.Gen (1^{λ})$

$σ_{b} \leftarrow CBS.Sign ⟨ S ({sk}_{S}, b), U (m), (prms, pk) ⟩$

${0, 1} \leftarrow CBS.Vrfy (prms, pk, {sk}_{V}, m, σ_{b})$

$CBS.Gen$ is an algorithm that outputs two pairs of keys, $({sk}_{S}, {pk}_{S})$ for signing and $({sk}_{V}, {pk}_{V})$ for verification, the message space $M$ and the signature space $S$ , described by a set of parameters (e.g. group generators) collectively denoted as $prms$ . For convenience, both public keys are grouped together and denoted as $pk = ({pk}_{S}, {pk}_{V})$ .

$CBS.Sign$ is a protocol executed between the signer and the user. The secret input of the signer is the signing key ${sk}_{S}$ and the bit b, while the secret input of the user is the message m to be signed. The public input consists of the group parameters and the public keys. The protocol output for the user is a signature $σ_{b}$ of m.

$CBS.Vrfy$ is an algorithm which outputs a single bit representing the validity of the signature. A valid signature is one for which $CBS.Vrfy (\cdot) = 1$ . Correctness must hold, that is $CBS.Vrfy (\cdot, m, σ_{b})$ outputs 1 if and only if $σ_{b}$ is the output of the execution of the protocol $CBS.Sign$ on message m and the secret bit of $S$ is $b = 1$ , except with negligible probability.
3.2. Security properties

The security of CBS is captured by Blindness, Unforgeability and Conditional Verifiability. These properties are defined by extending the respective games for plain blind signatures [36] to accommodate for the secret conditionality bit and the designated verifier.

3.2.1. Blindness

The blindness property is formally expressed using the game presented in Algorithm 1, which states that a malicious signer cannot tell which of the two messages $m_{0}, m_{1}$ was signed first, except with negligible probability. The signatures on which the adversary is challenged are forced to be valid ( $b = 1$ ).

Algorithm 1:

${CBS-BlindExp}_{A, Π}$

Definition 4.

A conditional blind signature scheme Π is perfectly blind if for every (unbounded) $A$ : $Pr [{CBS-BlindExp}_{A, Π} (λ) = 1] = \frac{1}{2}$

3.2.2. Unforgeability

The unforgeability property is captured using the notion of One-More Forgery of [31], which states that, if l is an integer, polynomial in the security parameter λ, an attacker can produce $l + 1$ valid signatures, after at most l successful interactions with the signer. The Strong One-More Forgery [31] is a variation of the above case, where l is polylogarithmically bound to the security parameter. More formally, in the game $CBS-OneMoreForge$ , $A$ can obtain both valid ( $b = 1$ ) and invalid ( $b = 0$ ) signatures after k successful interactions.

Algorithm 2:

${CBS-OneMoreForge}_{A, Π}$

Definition 5.

A conditional blind signature scheme Π is one-more unforgeable if for every PPT $A$ there is a negligible function of λ where: $Pr [{CBS-OneMoreForge}_{A, Π} (λ) = 1] ⩽ negl (λ)$

In order for the verification of the signatures (and thus the checking of the forgeries) to be trustworthy, the verifier (identified by the possession of ${sk}_{V}$ ) should be trusted. Consequently, in Algorithm 2, the adversary does not receive ${sk}_{V}$ . In effect, this makes forgery a concern only against outsiders, i.e. everybody except the real signer and the designated verifier. This is consistent with the security model for designated verifier signatures [26,27], where signature simulations by the designated verifier are not treated as forgeries, but as aids towards the protocol’s goals. In fact, in the applications of CBS, such simulations are utilized in order to make the scheme more versatile (cf. Section 4.2, Section 7.2).

3.2.3. Conditional verifiability

For CBS an extra property is described, called Conditional Verifiability, which states that an adversary $A$ cannot guess the validity of a signature without the secret verification key.

$A$ is assumed to be an external entity, i.e. neither the signer nor the verifier. This is justified as the signer must already know the value of b to create the signature, and the verifier learns the value of b by executing the verification functionality. So, if $A$ corrupted $S$ he would know that the received signature is valid and would entirely bypass conditional verifiability. In the motivating example of coercion-resistant electronic elections, a corrupted signer would imply that the coercer would know if the voter was using a fake or genuine credential to cast her ballot. So, what the game $CBS-CondVerExp$ , presented in Algorithm 3, expresses is that no third-party except the signer and the verifier can learn the conditional bit associated with the signature. In other words, our model intuitively resembles the IND-CPA property of public-key encryption, as it is meant to ‘hide’ the conditional bit of the signatures from third-parties.

In $CBS-CondVerExp$ , the adversary can adaptively obtain a polynomially restricted number of valid or invalid signatures (denoted by · in the input of $S$ ) by submitting messages of his choice to the signer through the $CBS.Sign$ protocol. Then the adversary submits the challenge and is presented with a signature whose validity is decided by a random coin flipped by the challenger. The adversary can then continue to submit signing requests. In the end, he must guess the coin toss.

Algorithm 3:

${CBS-CondVerExp}_{A, Π}$

Definition 6.

A conditional blind signature scheme Π is conditionally verifiable if for every PPT $A$ there is a negligible function of λ such that $Pr [{CBS-CondVerExp}_{A, Π} (λ) = 1] ⩽ \frac{1}{2} + negl (λ)$ .

No verification oracle is provided to the adversary and he can only make signing requests. This is better suited to the intended usage of the primitive, where publicly revealing the validity of the signature would also reveal the value of the secret bit. In real-world applications, when a scheme that utilizes CBS needs to reveal the validity of a signature, it can do so by employing anonymization or obfuscation techniques, thus rendering the knowledge of the validity result useless. An example of how this can be achieved is provided in Section 7.2.

4. Okamoto–Schnorr CBS construction

A construction of the CBS primitive can be based on the Okamoto–Schnorr blind signatures [28].

The parameter generation procedure, depicted in Algorithm 4, creates a group $G$ with prime order q ( $2^{λ - 1} ⩽ q < 2^{λ}$ ) and generators $g_{1}, g_{2}$ , where the DDH assumption holds. The existence of a random oracle $H : M \times G \to Z_{q}$ is assumed. The secret signing key comprises the values $s_{1}, s_{2} \in Z_{q}$ with corresponding public signing key v. The secret verification key is $s \in Z_{q}$ with public counterpart k.

Algorithm 4:

$OS-CBS.Gen (1^{λ})$

The signing protocol is presented in Fig. 2. It proceeds through four phases as in [28]. The signer commits to an element x. The user blinds the message along with the commitment and the signer produces the blind signature. Finally, the user unblinds the signature. In summary, in the case of valid signatures, the OS-CBS instantiation, is a direct adaptation of the Okamoto–Schnorr blind signatures from Fig. 1, with the only difference being the ‘lifting’ of $β_{1}$ and $σ_{1}$ respectively. Invalid signatures, consist of randomly sampled values.

Fig. 2.

The protocol $OS-CBS.Sign ⟨ S ((s_{1}, s_{2}), b), U (m), prms, pk ⟩$ .

In the verification stage (Algorithm 5), the verifier checks the hash of the message and the commitment using the secret key $s \in Z_{q}$ . If the signer’s secret bit is 1, then the signature will be valid, otherwise the verification equation will not hold. Thus, the verifier implicitly learns the secret bit of the signer.

Algorithm 5:

$OS-CBS.Vrfy (prms, pk, {sk}_{V}, m, σ)$

4.1. Security analysis

4.1.1. Correctness

Correctness follows from straightforward computations on the equation checked in Algorithm 5. Indeed: $\begin{array}{l} σ_{1} \cdot {g_{2}}^{σ_{2} \cdot s} \cdot v^{e^{*} \cdot s} \\ = k^{y_{1}} k^{u_{1}} \cdot g_{2}^{(y_{2} + u_{2}) \cdot s} \cdot {(g_{1}^{- s_{1}} g_{2}^{- s_{2}})}^{(e + d) s} \\ = k^{r_{1} + e s_{1} + u_{1}} \cdot g_{2}^{(r_{2} + e s_{2} + u_{2}) \cdot s} \cdot {(g_{1}^{- s_{1}} g_{2}^{- s_{2}})}^{(e + d) s} \\ = {g_{1}}^{(r_{1} + e s_{1} + u_{1}) \cdot s} \cdot g_{2}^{(r_{2} + e s_{2} + u_{2}) \cdot s} \cdot {(g_{1}^{- e s_{1}} g_{2}^{- e s_{2}})}^{s} {(g_{1}^{- d s_{1}} g_{2}^{- d s_{2}})}^{s} \\ = {g_{1}}^{(r_{1} + u_{1}) \cdot s} \cdot g_{2}^{(r_{2} + u_{2}) \cdot s} \cdot {(g_{1}^{- d s_{1}} g_{2}^{- d s_{2}})}^{s} \\ = {({g_{1}}^{r_{1}} {g_{2}}^{r_{2}} \cdot {g_{1}}^{u_{1}} {g_{2}}^{u_{2}} \cdot (g_{1}^{- d s_{1}} g_{2}^{- d s_{2}}))}^{s} \\ = {(x \cdot {g_{1}}^{u_{1}} {g_{2}}^{u_{2}} \cdot v^{d})}^{s} = {x^{*}}^{s} \end{array}$

4.1.2. Blindness

For the blindness property the arguments of the original Okamoto–Schnorr scheme in [28] and [1] hold. More specifically, the commitment is blinded in exactly the same way in both schemes and the second parts of the signatures are identical in both cases. In addition, the message hash is hidden using the value d exactly as in [28]. The first part of the signature is ‘lifted’, but the mapping from $y_{1}$ to $k^{y_{1}}$ is one to one and onto.

Theorem 1.
The Okamoto–Schnorr CBS scheme satisfies perfect blindness.
Proof.
Let $S^{}$ be the unbounded adversary in the blindness game in Algorithm 1 and $vie w_{i} = (x_{i}, e_{i}, β_{i})$ for $i \in {0, 1}$ be the view 3
³
For simplicity, both components of the blind signature as are collectively referred as $β_{i}$ i.e. $β_{i} = (β_{i 1}, β_{i 2})$ . The same applies to $σ_{i}$ as well.

of $S^{}$ . There exists a unique tuple $(u_{1}, u_{2}, d)$ that maps $vie w_{i}$ to signature $σ_{j}$ for both cases of $i, j \in {0, 1}$ . $\begin{array}{l} u_{1} = {log}_{k} (σ_{j 1} \cdot β_{i 1}^{- 1}) \Rightarrow g_{1}^{u_{1} s} = σ_{j 1} \cdot β_{i 1}^{- 1}, \\ u_{2} = σ_{j 2} - β_{i 2}, \\ d = e_{j}^{} - e_{i} \end{array}$ This tuple causes both signatures to be valid: $\begin{array}{l} x_{j}^{^{s}} & = {(x_{i} g_{1}^{u_{1}} g_{2}^{u_{2}} v^{d})}^{s} = g_{1}^{s r_{1}} g_{2}^{s r_{2}} g_{1}^{s u_{1}} g_{2}^{s u_{2}} v^{s d} \\ = g_{1}^{s r_{1}} g_{2}^{s r_{2}} (σ_{j 1} β_{i 1}^{- 1}) g_{2}^{s (σ_{j 2} - β_{i 2})} v^{s (e_{j}^{} - e_{i})} \\ = (σ_{j 1} g_{2}^{σ_{j 2} s} v^{s e_{j}^{}}) \cdot g_{1}^{s r_{1}} g_{2}^{s r_{2}} β_{i 1}^{- 1} g_{2}^{- s β_{i 2}} v^{- s e_{i}} \\ = (σ_{j 1} g_{2}^{σ_{j 2} s} v^{s e_{j}^{}}) \cdot g_{1}^{s r_{1}} g_{2}^{s r_{2}} g_{1}^{- s (r_{1} + e_{i} s_{1})} g_{2}^{- s (r_{2} + e_{i} s_{2})} g_{1}^{s_{1} s e_{i}} g_{2}^{s_{2} s e_{i}} \\ = (σ_{j 1} g_{2}^{σ_{j 2} s} v^{s e_{j}^{}}) \end{array}$ As a result, in the blindness game in Algorithm 1, the view of $A$ and the signatures are statistically independent for both cases of the coin flip. So the probability that an unbounded adversary succeeds in linking two protocol executions to the corresponding messages and signature pairs is exactly $1 / 2$ . □

4.1.3. Unforgeability

The scheme is also secure against the strong version of the One-More Forgery definition [31]. Note that an adversary can create invalid signatures by randomly choosing $y_{2} \in Z_{q}$ and a random element of $G$ . As a result, in the security proof, an interaction with the signer for an invalid signature does not provide any advantage, so it can be assumed that the adversary only interacts with the signer to obtain valid signatures. Theorem 2 shows that the scheme is secure under the strong one-more forgery definition.

Theorem 2.
Suppose there exists a PPT adversary $A$ that wins the CBS-OneMoreForge experiment, for l polylogarithmic in the security parameter λ, with non-negligible probability. Then there exists a PPT algorithm $B$ that solves the Computational Diffie Hellman problem with non-negligible probability.
Proof.
Let $A$ be a PPT adversary that wins the game in Algorithm 2 with non-negligible probability. This means that it can produce $l + 1$ valid signatures of the form $(x^{}, e^{}, σ_{1}, σ_{2})$ 4
⁴
To be exact the signatures should be denoted as ${(x^{}, e^{}, σ_{1}, σ_{2})}_{i = 1}^{l + 1}$ , but for simplicity the indices are omitted.

after l interactions with the signer $S$ and the random oracle $H$ . The transcript of each interaction of $A$ with $S$ is the blind signature tuple $(x, e, β_{1}, β_{2})$ . The transcript of each interaction of $A$ with $H$ is the tuple $(m, x^{}, e^{})$ .

A PPT adversary $B$ will be constructed, that impersonates $S$ to make $A$ produce valid signatures $σ = (x^{}, e^{}, σ_{1}, σ_{2})$ and $\tilde{σ} = (x^{}, \tilde{e^{}}, \tilde{σ_{1}}, \tilde{σ_{2}})$ with the same initial message $x^{}$ and $y_{2} - s_{2} e \neq \tilde{y_{2}} - s_{2} \tilde{e}$ . These two valid signatures will allow $B$ to break the CDH Assumption.

Fig. 3.
Breaking the CDH assumption by forging OS-CBS.

The construction is presented at a high level in Fig. 3. In more detail, $B$ receives a triple of public group elements $g_{1}, g_{2}, k$ where $k = g_{1}^{s}$ with unknown $s \in Z_{q}$ and $g_{2} = g_{1}^{a}$ for some unknown $a \in Z_{q}$ . To break the CDH Assumption $B$ must compute $g_{1}^{a s} = g_{2}^{s}$ . To set up the OS-CBS forgery, $B$ selects $s_{1}, s_{2} \in Z_{q}$ and computes the public signing key $v = g_{1}^{- s_{1}} g_{2}^{- s_{2}}$ and sets the public verification key as k. $B$ replays $A$ until it outputs the two valid signatures $σ_{1}, \tilde{σ_{1}}$ with the same initial message $x^{}$ .

Since the verification equation in Algorithm 5 holds for valid signatures: $\begin{array}{l} {(x^{})}^{s} = σ_{1} \cdot g_{2}^{σ_{2} s} \cdot v^{e^{} s} and {(x^{})}^{s} = \tilde{σ_{1}} \cdot g_{2}^{\tilde{σ_{2}} s} \cdot v^{\tilde{e^{}} s} \end{array}$ As $x^{}$ is the same in both cases: $\begin{array}{l} σ_{1} \cdot g_{2}^{σ_{2} s} \cdot v^{e^{} s} = \tilde{σ_{1}} \cdot g_{2}^{\tilde{σ_{2}} s} \cdot v^{\tilde{e^{}} s} \Rightarrow σ_{1} \cdot {\tilde{σ_{1}}}^{- 1} = g_{2}^{(\tilde{σ_{2}} - σ_{2}) s} \cdot v^{(\tilde{e^{}} - e^{}) s} \end{array}$ All values except s are known to $B$ . For simplicity set:
$τ = σ_{1} \cdot {\tilde{σ_{1}}}^{- 1}$

$ρ = \tilde{σ_{2}} - σ_{2}$

$ϕ = \tilde{e^{}} - e^{}$
Next, the public signing key v is analyzed: $\begin{array}{l} τ = g_{2}^{ρ s} v^{ϕ s} = g_{2}^{ρ s} {(g_{1}^{- s_{1}} g_{2}^{- s_{2}})}^{ϕ s} = g_{2}^{s ρ} \cdot g_{1}^{- s_{1} ϕ s} g_{2}^{- s_{2} ϕ s} = k^{- s_{1} ϕ} g_{2}^{s (ρ - s_{2} ϕ)} \Rightarrow τ k^{s_{1} ϕ} = {(g_{2}^{s})}^{(ρ - s_{2} ϕ)} \end{array}$ Now, $B$ can compute $g_{2}^{s}$ as: $\begin{matrix} (1) & g_{2}^{s} = {(τ k^{s_{1} ϕ})}^{{(ρ - s_{2} ϕ)}^{- 1}} \end{matrix}$

It remains to be proved that such valid signatures $σ_{1}, \tilde{σ_{1}}$ can be efficiently produced with a non-negligible probability. This, however, is a direct consequence of the Oracle Replay Attack used to prove the unforgeability of the blind Okamoto–Schnorr signatures in [31].

Assume that $A$ succeeds with probability at least ε in producing a $(l, l + 1)$ forgery for message m, where l is polylogarithmic in the security parameter. $B$ executes the signing protocol with $B$ until a forgery is produced (or at most $1 / ε$ ) times. Let $k ⩽ l$ be the actual number of times that $A$ has interacted with the signer $S$ and Q the actual number of times that $A$ has interacted with $H$ . Assume that $(m, x^{})$ was sent to $H$ on query j. Then each of the k signing interactions, is rerun with the same random data, except for $H$ , which is replaced by $\tilde{H}$ such that both oracles agree on the first $j - 1$ answers to queries. It is proved in [31], that with a polynomial overhead, at most, a forgery will be produced on the same $(m, x^{})$ with non-negligible probability. Note that the data submitted to $H$ in both OS-CBS and the original Okamoto–Schnorr blind signatures follow the exact same distribution (cf. Fig. 1). In fact, the only difference of the two protocols for valid signatures is that the first part of the blind* signature in OS-CBS is the group element $k^{y_{1}}$ instead of the index $y_{1} \in Z_{q}$ . Even though the mapping between these values is one to one and onto, the difference occurs after the oracle call. As a result, the probabilistic analysis of the Oracle Replay Attack of [31] applies verbatim to OS-CBS as well. □

The analysis of Theorem 2 implies that deployments of this specific instantiation of CBS are constrained by the polylogarithmic number of concurrent signing sessions l and susceptible to attacks for larger values [4]. To increase the efficiency of a system using OS-CBS, while maintaining unforgeability, this restriction must be handled by the external protocol.
4.1.4. Conditional verifiability

Finally, it is shown that the system is conditionally verifiable, according to the definition of Algorithm 3, by a reduction to the DDH Assumption.

Theorem 3.
Suppose there exists a PPT adversary $A$ that wins the CondVerExp with non negligible probability. Then there exists a PPT algorithm $B$ that solves the Decisional Diffie Hellman problem with non-negligible probability.
Proof.
$B$ will be constructed. Its input will be the tuple $g, g^{a}, g^{s}, g^{c}$ and the output will be a bit indicating whether $c = a s$ or c is a random element of $Z_{q}$ . To do so, it proceeds as follows:
$B$ sets $g_{1} = g$ , $g_{2} = g^{a}$ and $k = g_{1}^{s} = g^{s}$ and randomly chooses $s_{1}, s_{2}$ for $v : = g_{1}^{- s_{1}} g_{2}^{- s_{2}}$ . It gives $g_{1}, g_{2}, k, v$ to $A$ .

Using the secret key $(s_{1}, s_{2})$ $B$ can answer $A$ ’s valid signature requests.

When $B$ gets a challenge request from $A$ it randomly chooses $r_{1}, r_{2}$ and sends $x : = g_{1}^{r_{1}} g_{2}^{r_{2}}$ to $A$ .

$A$ responds with e.

$B$ chooses random $β_{2} : = y_{2} \in Z_{q}$ and sets: $β_{1} = k^{y_{1}} : = {(g^{s})}^{r_{1}} {(g^{c})}^{r_{2}} {(g^{c})}^{- y_{2}} {(g^{s})}^{s_{1} e} {(g^{c})}^{s_{2} e}$

$B$ sends the signature pair $(β_{1}, β_{2}) : = (k^{y_{1}}, y_{2})$ and $A$ executes the unblinding phase to produce the signature σ.

As before, $B$ responds to $A$ ’s signing requests using the secret key $(s_{1}, s_{2})$ .

$B$ outputs 1 (the input is a DDH tuple) if and only if $A$ outputs 1 (the signature is valid).
According to Algorithm 5 the signature $σ = (σ_{1}, σ_{2})$ is valid if and only if: ${(x^{})}^{s} = σ_{1} \cdot g_{2}^{σ_{2} s} \cdot v^{e^{} s}$

By replacing the relevant protocol transformations from Fig. 2: $\begin{array}{l} {(x g_{1}^{u_{1}} g_{2}^{u_{2}} v^{d})}^{s} = β_{1} k^{u_{1}} \cdot g_{2}^{(β_{2} + u_{2}) s} \cdot v^{(e + d) s} \Leftrightarrow \\ x^{s} g_{1}^{s u_{1}} g_{2}^{s u_{2}} v^{s d} = β_{1} g_{1}^{s u_{1}} g_{2}^{s β_{2}} g_{2}^{s u_{2}} v^{s e} v^{s d} \Leftrightarrow \\ x^{s} = β_{1} g_{2}^{s β_{2}} v^{s e} \Leftrightarrow \\ β_{1} = x^{s} g_{2}^{- s β_{2}} v^{- s e} \Leftrightarrow \\ k^{y_{1}} = x^{s} g_{2}^{- s y_{2}} v^{- s e} \Leftrightarrow \\ {(g^{s})}^{r_{1}} {(g^{c})}^{r_{2}} {(g^{c})}^{- y_{2}} {(g^{s})}^{s_{1} e} {(g^{c})}^{s_{2} e} = x^{s} g_{2}^{- s y_{2}} v^{- s e} \Leftrightarrow \\ g^{s r_{1}} g^{c r_{2}} g^{- c y_{2}} g^{s s_{1} e} g^{c s_{2} e} = g^{s r_{1}} g_{2}^{s r_{2}} g_{2}^{- s y_{2}} g^{s s_{1} e} g_{2}^{s s_{2} e} \Leftrightarrow \\ {(g^{c})}^{(r_{2} - y_{2} + s_{2} e)} = {(g^{a s})}^{(r_{2} - y_{2} + s_{2} e)} \end{array}$

Provided that $r_{2} - y_{2} + s_{2} e \neq 0$ , the signature is valid if and only if $g^{c} = g^{a s}$ , which means that the input is a DDH tuple. Since $y_{2}$ is chosen randomly, $r_{2} - y_{2} + s_{2} e = 0$ holds with negligible probability which yields the result. □

4.2. Variations based on homomorphic encryption

The following variations of the OS-CBS construction aim to make it more versatile and, as a result, easier to be incorporated as a building block into other protocols. The design of PACBS, this work’s main result, will be based on these two variations. In this section, we abstract on some key ideas that are made concrete in Section 6.

First of all, the communication rounds of OS-CBS signing protocol can be reduced, by removing the commitment phase in Fig. 2, yielding the reduced-round scheme ${OS-CBS}_{r}$ . This means that x can be replaced with a random element of $G$ , generated by a predetermined method. For instance, a random oracle could be used. But this is not the only option, as x could be the output of a trusted setup or a secure multi-party protocol. We only require that a common x is available to both $U, S$ in the beginning of the protocol. As a result, the commitment message and the first round can be omitted. Furthermore, this enables the verifier in possession of s to generate signatures herself, by using a random group element as v. The value of $β_{1}$ will be computed in this case by reversing the relevant part of the verification equation as ${(x \cdot g_{2}^{- β_{2}} \cdot v^{- e})}^{s}$ , where $β_{2}$ is a random element in $Z_{q}$ .

Lemma 1.
The reduced-round ${OS-CBS}_{r}$ is l one-more unforgeable if the three round OS-CBS scheme is l one-more unforgeable.
Proof.
We will first describe the case where the predetermined method to compute x is a random oracle $H$ ; its programmability can be used as an advantage for the adversary. Assume that $A$ is a reduced-round ( ${OS-CBS}_{r}$ ) forger. We will construct an algorithm $B$ that forges OS-CBS signatures without having access to the signing key s. In order to answer $A$ ’s requests, $B$ can (by assumption) request signatures from the 3-round OS-CBS signer $S$ .

The input of $B$ will be the public input of $OS-CBS$ namely $G, g_{1}, g_{2}, v, k$ . When $A$ requests the commonly available x from $H$ , then $B$ intercepts the request and initiates a signing session with $S$ who computes it. $B$ stores x and forwards it to $A$ . Note that x is, by construction (Fig. 2), a random element of $G$ . $A$ executes the blinding phase of Fig. 2 and sends e to $B$ who in turn forwards it to $S$ to create the blind signature $β = (x, e, β_{1}, β_{2})$ . Since invalid signatures do not aid the forger we assume that the signature is always valid. Note that $β_{2}$ is a random element in $Z_{q}$ , since $s_{2}, r_{2}$ are sampled uniformly at random by Algorithm 4 and Fig. 2 respectively. Since the signature is valid, it is easy to see that $β_{1} = {(x \cdot g_{2}^{- β_{2}} \cdot v^{- e})}^{s}$ . As a result, the tuple β received from $S$ is indistinguishable from a valid ${OS-CBS}_{r}$ blind signature. This, by assumption, means that $A$ , after an upper bound of l interactions, will generate a one-more forgery for ${OS-CBS}_{r}$ with non-negligible probability. By Fig. 2, this forgery is valid also for $OS-CBS$ .

In order to generalize the proof, we can assume that $B$ initializes signing sessions with $S$ requesting an upper bound of $poly (λ)$ commitment values x which are then made available for $A$ to use, before the latter selects its messages. □

Moreover, OS-CBS can be easily combined with a homomorphic encryption scheme like ElGamal [15]. To this end, an encryption key pair $(z, h_{1}^{z})$ must also be created during the parameter generation phase. The encryption secret key z is in the possession of the designated verifier. In the signing phase of Fig. 2, $S$ generates the first part of the blind signature as $β_{1} : = {Enc}_{h_{1}^{z}} (k^{y_{1}})$ . The user then unblinds it by computing $σ_{1} : = β_{1} \cdot {Enc}_{h_{1}^{z}} (k^{u_{1}})$ . Due to the multiplicative homomorphic properties of the underlying cryptosystem the unblinded version of the signature is the same as CBS, albeit in encrypted form. To verify, $V$ follows Algorithm 5 after decrypting $σ_{1}$ with z.

Finally, these two variations can be combined with the signature becoming ${Enc}_{h_{1}^{z}} ({(x \cdot g_{2}^{- β_{2}} \cdot v^{- e})}^{s})$ where $β_{2}$ is a random index again. In Section 6, a concrete method to instantiate the first round message will be presented as part of the OS-PACBS construction.
5. Publicly auditable conditional blind signatures

In the CBS.Sign protocol the conditional bit b is a private input of the signer. As a result, a malicious signer can disregard it and provide an arbitrary signature. Moreover, since the verification of a CBS is performed by a designated verifier, the user cannot check its validity herself. This, while counterintuitive, is one of the design goals of the primitive, justified by its intended application to coercion-resistant e-voting (detailed in Section 7.2). However, such a goal must not come at the expense of the signature’s verifiability. In particular, the user must be protected both against a malicious signer that outputs an arbitrary signature, without taking b into account and against a verifier that does not consider $σ_{b}$ and outputs a validity result of his liking. CBS do not protect against such attacks. To do so, they must be augmented with a mechanism that will allow the user to verify that nor the signer nor the verifier cheated.

This mechanism is introduced in Publicly Auditable Conditional Blind Signatures (PACBS), an extension of CBS that provides auditable evidence for the signing and verification functionalities. In particular, the Sign protocol is augmented with audit information to ensure that the signing operations were carried out correctly and Vrfy is augmented with evidence that the verification operations conform to their specification. In order to check this evidence, two extra functionalities called PACBS.Audit-Sign and PACBS.Audit-Vrfy are proposed, that use this audit information and output if the corresponding operations are compatible with a correct protocol execution.

Moreover, in order to implement the auditability requirement in a more realistic way, the secret input bit b of CBS is replaced by a predicate function in PACBS, the input of which is provided externally – e.g. $b = pred (σ_{1}, σ_{2})$ where $σ_{1}, σ_{2}$ are credentials and $pred$ is a function that checks their equality. These credentials are not solely computed by neither the signer nor the user, but can be the output of an external protocol executed between them and possibly other parties. Additionally, the signer $S$ , accompanies the signature with evidence that he correctly followed the protocol, which means that the signature validity depends only on the result of $pred$ on the given input. This in turn, allows an honest user, in possession of some non-transferable knowledge (e.g. whether $σ_{1}$ is her actual credential), the definition of $pred$ and the evidence to verify protocol compliance by the signer and verifier and be sure that the signature she holds is a valid one. On the other hand, the public (or an adversary – either a corrupted user or a third party) can only check that the protocol was followed faithfully, but cannot extract the signature validity. In the voting scenario, this lack of evidence together with a form of deniability for the possession of (parts of) the predicate’s inputs, can protect both against an active coercer and a corrupted user (cf. Section 7.2).

A useful (but not exact) intuition for the distinction between the purpose of the predicate and the PACBS.Audit-Sign and PACBS.Audit-Vrfy is the contrast between semantics and syntax. The predicate determines the semantics of the signature, while the generated proofs and the corresponding functionalities PACBS.Audit-Sign and PACBS.Audit-Vrfy concern the syntax of the signature. Everybody can verify syntax, however, the semantics are only unlocked by the holder of the predicate’s inputs.

5.1. Definition

Definition 7.
A publicly auditable conditional blind signature scheme is a tuple ( $PACBS.Gen$ , $PACBS.Sign$ , $PACBS.Audit-Sign$ , $PACBS.Vrfy$ , $PACBS.Audit-Vrfy$ ) where:
$(({sk}_{S}, {pk}_{S}), ({sk}_{V}, {pk}_{V}), prms) \leftarrow PACBS.Gen (1^{λ})$

$(σ_{b}, π_{Sign}) \leftarrow PACBS.Sign ⟨ S ({sk}_{S}), U (m), (prms, pk, d) ⟩$

$\{0, 1\} \leftarrow PACBS.Audit-Sign (prms, pk, π_{Sign})$

$(\{0, 1\}, π_{Vrfy}) \leftarrow$ $PACBS.Vrfy (prms, pk, {sk}_{V}, m, σ_{b})$

$\{0, 1\} \leftarrow PACBS.Audit-Vrfy (prms, pk, m, σ_{b}, π_{Vrfy})$

$PACBS.Gen$ is an algorithm that takes as input the security parameter $1^{λ}$ and outputs two pairs of keys $({sk}_{S}, {pk}_{S})$ for signing and $({sk}_{V}, {pk}_{V})$ for verification, denoted as $pk = ({pk}_{S}, {pk}_{V})$ and $sk = ({sk}_{S}, {sk}_{V})$ . Moreover, PACBS.Gen outputs the message space $M$ , the signature space $S$ and the public input space $D$ which defines the inputs that determine the validity of the signature. These sets are described by some parameters (e.g. group generators) collectively denoted as $prms$ . Finally, the $PACBS.Gen$ algorithm produces a predicate function $pred : D \to \{0, 1\}$ that will extract the conditional part of the signature with the help of some public input.

PACBS.Sign is a protocol executed between the signer and the user. The public input consists of the parameters and the public keys as well as d from $D$ . The secret input of the signer is the signing key ${sk}_{S}$ . The signer takes into account the output of the $U$ algorithm on m and outputs a signature $σ_{b}$ 5
⁵
The notation $σ_{b}$ is maintained, even though there is no explicit b, in order to stress the fact that the signature is conditional.

that is conditional to some public data d along with evidence $π_{Sign}$ that the signer operated correctly. Internally, the PACBS.Sign protocol includes functionalities PACBS.Blind, PACBS.BlindSign, and PACBS.Unblind to implement operations related to the blind signature. The transcript of the PACBS.Sign protocol along with proofs that these internal functionalities were executed correctly, comprises $π_{Sign}$ .

PACBS.Audit-Sign is an algorithm, which receives $π_{Sign}$ and outputs a bit indicating if the signing operations were carried out correctly.

PACBS.Vrfy is an algorithm, which outputs a single bit representing the validity of the signature along with a proof $π_{Vrfy}$ that the verifier followed the protocol.

PACBS.Audit-Vrfy is an algorithm, which receives the signature $σ_{b}$ and the evidence $π_{Vrfy}$ produced during verification and outputs a bit indicating if the algorithm operations were carried out correctly. For simplicity, we include the verification result in $π_{Vrfy}$ .

Correctness must hold, which means that $PACBS.Vrfy (prms, pk, {sk}_{V}, m, σ_{b})$ outputs 1 if and only if $σ_{b}$ is the output of the execution of the protocol $PACBS.Sign$ on message m with public input $d \in D$ such that $pred (d) = 1$ except with negligible probability.
5.2. Security properties

PACBS extend the blindness, unforgeability, and conditional verifiability properties of CBS to take into account the predicate function. Furthermore, since the signing and verification operations output evidence, they are also available to the adversary, who might take advantage of them to break the security of the scheme.

5.2.1. Blindness

The experiment in Algorithm 6 is identical to the CBS one, except for the involvement of the predicate and the audit functionalities to check the correct operations. Furthermore, the adversary is choosing the values $d_{0}, d_{1}$ to be used during the PACBS.Sign protocols with the restriction that $pred (d_{0}) = pred (d_{1}) = 1$ as imposed by the requirements of CBS that the two outputted signatures are valid. Note that the signing transcript and proofs in $π_{Sign}$ are either generated by or are available to the adversary (signer) and as a result provide no advantage during the guessing stage. On the other hand, $A$ can use the verification proofs along with the signatures to guess. However, as $π_{Vrfy}$ will be a function of the signature, it will provide $A$ with no more information than what can be obtained from the signature itself. For completeness, however, they are handed to $A$ in Algorithm 6.

Algorithm 6:

${PACBS-BlindExp}_{A, Π}$

Definition 8.

A publicly auditable conditional blind signature scheme Π is perfectly blind if for every (unbounded) $A$ : $Pr [{PACBS-BlindExp}_{A, Π} (λ) = 1] = \frac{1}{2}$

5.2.2. Unforgeability

To capture unforgeability, the corresponding game for CBS (Algorithm 2) is slightly modified.

Algorithm 7:

${PACBS-OneMoreForge}_{A, Π}$

In the game in Algorithm 7, the aspiring forger chooses input d in each oracle request. If the adversary can find d for which he knows $pred (d)$ he can get valid and invalid signatures at will. Using this oracle, the adversary tries to obtain more than k valid signatures where k is the number of interactions resulting in a valid signature output.

Definition 9.

A publicly auditable conditional blind signature scheme Π is one-more unforgeable if for every PPT $A$ there is a negligible function of λ where: $Pr [{PACBS-OneMoreForge}_{A, Π} (λ) = 1] ⩽ negl (λ)$ .

5.2.3. Conditional verifiability

Slight modifications are also needed to capture conditional verifiability. In particular, b needs to be replaced with the value of the predicate function.

In the game in Algorithm 8, the adversary has access to a signing oracle of his choice and can ask for signatures with auxiliary values that he chooses. $A$ also selects the messages that will be signed. He is challenged on a signature which is either valid or invalid depending on a coin flip on random auxiliary values. His goal is to determine the result of the coin flip or equivalently the value of the predicate. Note that, since $S$ is assumed honest, it follows the protocol in both cases. As a result, while $π_{Sign}$ will be valid in all interactions, the collected proofs might leak information about the predicate, so they are handed to $A$ in the guessing stage.

Algorithm 8:

${PACBS-CondVerExp}_{A, Π}$

Definition 10.

A publicly auditable conditional blind signature scheme Π is conditionally verifiable if for every PPT $A$ there is a negligible function of λ such that $Pr [{PACBS-CondVerExp}_{A, Π} (λ) = 1] ⩽ \frac{1}{2} + negl (λ)$ .

Note that for the definition of a PACBS construction to be meaningful, the predicate $pred$ should be infeasible to compute on random values of its domain.

5.2.4. Public auditability

Public auditability for PACBS is defined with respect to the signing and verification functionalities.

In the case of PACBS.Audit-Sign, the desideratum is the property that the user’s output of the protocol respects the value of $pred (d)$ even when executed against a malicious signer. This means that if $σ_{b}$ is the output of PACBS.Sign on secret input m, then it is valid if and only if $pred (d) = 1$ . In other words, if $(result, π_{Vrfy}) = PACBS.Vrfy (prms, pk, {sk}_{V}, m, σ_{b})$ then $result = pred (d)$ . For this the PASignExp experiment is used, which is defined in Algorithm 9.

In this experiment, the adversary generates all the parameters and the secret keys of the PACBS scheme and he chooses the values which he wishes to be challenged on. A PACBS.Sign protocol is executed with these values and the goal of the adversary is to output a signature and evidence, such that $PACBS.Audit-Sign$ accepts and the signature validity is different from the first output of the algorithm PACBS.Vrfy.

Algorithm 9:

${PASignExp}_{A, Π}$

In the case of PACBS.Audit-Vrfy the aim is to ensure that when the designated verifier reveals the validity of a signature the result is accurate concerning $PACBS.Vrfy$ . This is necessary since the recipient of the signature does not know the value of the predicate when the inputs are randomly chosen. For this, the PAVrfyExp experiment is used, defined in Algorithm 10.

Algorithm 10:

${PAVrfyExp}_{A, Π}$

In PAVrfyExp the adversary is given all the parameters and the secret keys of the PACBS scheme and his goal is to output a message, a signature and evidence such that PACBS.Vrfy accepts b as the validity of the signature while PACBS.Vrfy outputs $1 - b$ .

Definition 11.

A publicly auditable conditional blind signature scheme Π is publicly auditable if for every PPT $A$ there is a negligible function of λ such that $Pr [{PASignExp}_{A, Π} (λ) = 1] + Pr [{PAVrfyExp}_{A, Π} (λ) = 1] ⩽ negl (λ)$

6. Okamoto–Schnorr PACBS construction

In this section, a construction for a PACBS scheme is presented. It extends the Okamoto–Schnorr CBS scheme (Section 4), using the variations presented in Section 4.2. In particular, since it is meant to be used as a building block in a coercion-resistant electronic voting scheme, there is a benefit in reducing the rounds of interaction between the user (voter) and the election authorities. As a result, the presented construction is built on the reduced-round ${OS-CBS}_{r}$ , where the first part of the issued signature is encrypted using ElGamal [15] encryption and the verifier can issue signatures. However, this is not necessary. A PACBS construction could be built on any of the variations of CBS presented in Section 4 or in Section 4.2. As a proof of concept, another PACBS construction is presented in Appendix A, which is a direct extension of CBS and where the signer and the verifier do not share a key.

The OS-PACBS scheme works in a group $G$ of prime order q ( $2^{λ - 1} ⩽ q < 2^{λ}$ ), where the DDH assumption holds. During the parameter generation phase random group elements $(g_{1}, g_{2}, v, h_{1})$ are selected. The signature message space consists of pairs of group elements (ElGamal ciphertexts). The instantiation makes heavy use of the homomorphic properties of the underlying cryptosystem.

In order to make the signature conditional to public data, a function $embed$ is used that implicitly inserts a value that replaces the ‘secret bit’ of $CBS$ : $\begin{matrix} embed : (G^{2} \times G^{2}) \to G^{2} \end{matrix}$ where: $\begin{matrix} (2) & embed (C_{1}, C_{2}) : = {(C_{2} / C_{1})}^{α} \cdot {Enc}_{h} (1, γ) \end{matrix}$

The values $α, γ \in Z_{q}^{*}$ are blinding factors selected by the signer. The predicate $pred$ is defined as: $\begin{matrix} pred : G^{2} \times G^{2} \to {0, 1} \end{matrix}$ where: $\begin{matrix} (3) & pred (C_{1}, C_{2}) : = {Dec}_{z} (C_{1}) = {Dec}_{z} (C_{2}) \end{matrix}$

The predicate function, in this instantiation, receives some group elements that represent two ciphertexts and checks that they both encrypt the same plaintext. Note that in the general case there is no restriction in the amount of public and auxiliary information to be used. For simplicity and to correspond with the usage scenario in Section 7.2 two pairs of group elements were chosen for the exposition. We assume, that these are not selected solely by the user and the signer, but by some protocol where both participate, maybe along with other players. As a result, neither $S$ , nor $U$ completely control them.

6.1. OS-PACBS parameter generation

The parameter generation procedure in Algorithm 11 selects the appropriate group generators and instantiates the predicate functions, as described in the previous section. A signing key $s \in Z_{q}$ and a decryption key $z \in Z_{q}$ are also selected. These secret keys are collectively denoted as $sk$ . Note that s plays the role of the secret signing key $s k_{S}$ , while the tuple $(s, z)$ plays the role of $s k_{V}$ in Definition 7. The corresponding public keys are $k : = g_{1}^{s}$ and $h : = h_{1}^{z}$ , denoted as $pk$ . Two random oracles $H_{1} : G^{4} \times G \to G, H_{2} : m \times G \to Z_{q}$ are assumed.

Algorithm 11:

OS-PACBS.Gen algorithm

Note that the validity of the signature is based on the value of the predicate, regardless of how it was constructed and embedded.

6.2. OS-PACBS signing

The PACBS signing protocol is shown in Fig. 4. Note that each algorithm in the protocol is explicitly named for easier reference.

Fig. 4.

$OS-PACBS.Sign$ Protocol.

NIZK proofs for signing. The proof $π_{1}$ is generated as a standard Chaum–Pedersen [9] proof for valid encryption. The proof $π_{3}$ is generated as a composition of Chaum–Pedersen [9] proofs. The proof $π_{2}$ is generated as detailed in Fig. 5 (cf. [19]).

Fig. 5.

The proof $π_{2}$ in OS-PACBS.Sign.

Theorem 4.

The protocol described for proof of knowledge $π_{2}$ is a Σ-protocol.

Proof.

Completeness is straightforward.

For special soundness, assume two valid interactions $(W^{'}, c, α^{″}, γ^{″})$ and $(W^{'}, \tilde{c}, \tilde{α^{″}}, \tilde{γ^{″}})$ , with $c \neq \tilde{c}$ :

The witness $(α, γ)$ can be extracted by setting: $α = (α^{″} - \tilde{α^{″}}) {(c - \tilde{c})}^{- 1}$ and $γ = (γ^{″} - \tilde{γ^{″}}) {(c - \tilde{c})}^{- 1}$ .

Indeed: $\begin{array}{l} {(C_{2} / C_{1})}^{(α^{″} - \tilde{α^{″}}) {(c - \tilde{c})}^{- 1}} \cdot {Enc}_{h} (1; (γ^{″} - \tilde{γ^{″}}) {(c - \tilde{c})}^{- 1}) \\ = {(C_{2} / C_{1})}^{(α c + α^{'} - α \tilde{c} - α^{'}) {(c - \tilde{c})}^{- 1}} \cdot {Enc}_{h} (1; (γ c + γ^{'} - γ \tilde{c} - γ^{'})) {(c - \tilde{c})}^{- 1}) \\ = {(C_{2} / C_{1})}^{α} \cdot {Enc}_{h} (1; γ) = W \end{array}$

For honest-verifier zero-knowledge it is easy to see that the distributions $(W^{'}, c, α^{″}, γ^{″})$ where $W^{'} = {(C_{2} / C_{1})}^{α^{'}} {Enc}_{h} (1; γ^{'})$ for uniformly distributed $α^{'}, γ^{'}, c$ from $Z_{q}$ and $α^{″} = α c + α^{'}$ , $γ^{″} = γ c + γ^{'}$ and $({(C_{2} / C_{1})}^{α^{″}} {Enc}_{h} (1; γ^{″}) W^{- c}, c, α^{″}, γ^{″})$ for uniformly distributed $α^{″}, γ^{″}, c$ from $Z_{q}^{*}$ are identical. □

The proofs $π_{1}, π_{2}, π_{3}$ can be AND combined into a single proof, detailed in Appendix B.

OS-PACBS auditing for signing. The PACBS.Audit-Sign process (Algorithm 12) is straightforward for the Okamoto–Schnorr instantiation. The auditor needs to verify the proofs issued by the signer.

Algorithm 12:

OS-PACBS.Audit-Sign algorithm

6.3. OS-PACBS verification

The OS-PACBS verification procedure is given in Algorithm 13. The verifier $V$ , given a message, a signature and a secret key, outputs whether the signature is valid or not and provides NIZK proofs that the verification operations were done correctly. In more detail, the verifier computes the verification equation and checks if it matches the first part of the signature, by blindingly dividing them. If the signature is valid, the result will decrypt to 1. In any other case the result will be random.

Algorithm 13:

OS-PACBS.Vrfy algorithm

The proofs $π_{1}, π_{2}, π_{3}, π_{4}$ are standard Chaum–Pedersen [9] proofs. Efficiency improvements can also be achieved from their AND combination. The details can be found in Appendix B.

OS-PACBS auditing for verification. Finally the PACBS.Audit-Vrfy procedure is presented in Algorithm 14.

Algorithm 14:

OS-PACBS.Audit-Vrfy algorithm

Note that the scheme is auditable by all, meaning that everyone can check the actions of the verifier. However, if the auditor has knowledge of the conditional information, then she can also check that the predicate was correctly computed and checked. This is the key property that will be utilized in the design of protocols around this primitive.

6.4. Security analysis

6.4.1. Correctness

The predicate is invariant in the algorithms that comprise the OS-PACBS scheme.

Lemma 2.
Let $β = (((n, B, N, W), y_{2}), π_{1}, π_{2}, π_{3})$ and $x = H_{1} (C_{1}, C_{2})$ be the output of $OS-PACBS.BlindSign$ algorithm executed by $S$ in the $OS-PACBS.Sign$ protocol. Then: $\begin{matrix} {Dec}_{z} (B) = x^{s} g_{2}^{- y_{2} s} v^{- e s} \Leftrightarrow pred (C_{1}, C_{2}) = 1 \end{matrix}$
Proof.
The result follows from straightforward computations and the homomorphic properties of the underlying encryption scheme: $\begin{array}{l} {Dec}_{z} (B) = x^{s} g_{2}^{- y_{2} s} v^{- e s} \Leftrightarrow \\ {Dec}_{z} ({(N W)}^{s}) = x^{s} g_{2}^{- y_{2} s} v^{- e s} \Leftrightarrow \\ {Dec}_{z} (N^{s}) {Dec}_{z} {(W)}^{s} = x^{s} g_{2}^{- y_{2} s} v^{- e s} \Leftrightarrow \\ n^{s} {Dec}_{z} {(W)}^{s} = x^{s} g_{2}^{- y_{2} s} v^{- e s} \Leftrightarrow \\ x^{s} g_{2}^{- y_{2} s} v^{- e s} {Dec}_{z} {(W)}^{s} = x^{s} g_{2}^{- y_{2} s} v^{- e s} \Leftrightarrow \\ {Dec}_{z} {(W)}^{s} = 1 \Leftrightarrow \\ {Dec}_{z} {(C_{2} / C_{1})}^{a s} = 1 \end{array}$ Now since $a \neq 0$ , ${Dec}_{z} {(C_{2} / C_{1})}^{a s} = 1 \Leftrightarrow {Dec}_{z} (C_{2} / C_{1}) = 1 \Leftrightarrow {Dec}_{z} (C_{2}) = {Dec}_{z} (C_{1})$ which gives the result. □
Lemma 3.
Let $(x^{}, e^{}, σ_{1}, σ_{2})$ be $U$ ’s output of the OS-PACBS.Sign protocol on message m and on predicate input $(C_{1}, C_{2})$ . Then it holds that $\begin{matrix} {Dec}_{z} (σ_{1}) = x^{* s} g_{2}^{- σ_{2} s} v^{- e^{} s} \Leftrightarrow pred (C_{1}, C_{2}) = 1 \end{matrix}$
Proof.
Following the protocol description in Fig. 4: $\begin{array}{l} {Dec}_{z} (σ_{1}) = x^{ s} g_{2}^{- σ_{2} s} v^{- e^{} s} \Leftrightarrow \\ {Dec}_{z} (B {Enc}_{h} (k_{1}^{u})) = x^{s} g_{1}^{u_{1} s} g_{2}^{u_{2} s} v^{d s} g_{2}^{- y_{2} s - u_{2} s} v^{- e s - d s} \Leftrightarrow \\ {Dec}_{z} (B) k_{1}^{u} = x^{s} k^{u_{1}} g_{2}^{- y_{2} s} v^{- e s} \Leftrightarrow \\ {Dec}_{z} (B) = x^{s} g_{2}^{- y_{2} s} v^{- e s} \end{array}$ and from Lemma 2 it holds that ${Dec}_{z} (B) = x^{s} g_{2}^{- y_{2} s} v^{- e s} \Leftrightarrow pred (C_{1}, C_{2}) = 1$ . □

Using Lemma 3 correctness can be proved. Theorem 5.
The Okamoto–Schnorr PACBS scheme has correctness.*
Proof.
It always holds that $H_{2} (m, x^{}) = e^{}$ . Following Lemma 3 the PACBS.Vrfy algorithm outputs 1 if and only if ${Dec}_{z} (R) = 1$ and since the blinding factor $γ \neq 0$ : $\begin{array}{l} {Dec}_{z} (R) = 1 & \Leftrightarrow {Dec}_{z} (V / σ_{1}) = 1 \\ \Leftrightarrow {Dec}_{z} (M^{s}) = {Dec}_{z} (σ_{1}) \\ \Leftrightarrow {Dec}_{z} ({Enc}_{h} {(validity)}^{s}) = {Dec}_{z} (σ_{1}) \\ \Leftrightarrow {validity}^{s} = {Dec}_{z} (σ_{1}) \\ \Leftrightarrow x^{* s} g_{2}^{- σ_{2} s} v^{- e^{*} s} = {Dec}_{z} (σ_{1}) \\ \Leftrightarrow pred (C_{1}, C_{2}) = 1 \end{array}$ which concludes the proof. □

6.4.2. Blindness

The proof follows [35]. Note that $π_{Vrfy}$ in Algorithm 13 depends solely on the signature.

Lemma 4.
Let $β = (((n, B, N, W), y_{2}), π_{1}, π_{2}, π_{3})$ be an output of the $OS-PACBS.Sign$ protocol with public transcript $(e, β, σ)$ and public input $x = H (C_{1}, C_{2})$ where $σ = (x^{}, e^{}, σ_{1}, σ_{2})$ is a valid signature on message m. Then there exist a unique tuple $(u_{1}, u_{2}, d, r)$ such that $Unblind (β, u_{1}, u_{2}, d, r) = σ$ where $Unblind$ is the algorithm issued as the last step of the $OS-PACBS.Sign$ protocol, $u_{1}, u_{2}, d$ are the blinding factors and r is the randomness used to encrypt $k^{u_{1}}$ .
Proof.
Since σ is valid, Fig. 4 yields about B: $\begin{matrix} (4) & B = {Enc}_{h} (x^{s} g_{2}^{- y_{2} s} v^{- e s} \cdot 1) \Rightarrow {Dec}_{z} (B) = x^{s} g_{2}^{- y_{2} s} v^{- e s} \end{matrix}$ Furthermore, the validity of σ means that in $OS-PACBS.Vrfy$ (Algorithm 13): $\begin{matrix} (5) & σ_{1} = M^{s} = {Enc}_{h} (x^{* s} g_{2}^{- σ_{2} s} v^{- e^{} s}) \end{matrix}$

It is immediate from the $Blind$ and $Unblind$ algorithms in Fig. 4 that the only possible tuple $(u_{1}, u_{2}, d, r)$ for a valid signature must satisfy: $\begin{array}{l} (6) & u_{1} = {log}_{k} ({Dec}_{z} (σ_{1}) \cdot {Dec}_{z} (B^{- 1})) \end{array}$ and $u_{2} = σ_{2} - y_{2}, d = e^{} - e, r = r_{s} - r_{B}$ , where $r_{B}$ is the encryption randomness of $B$ and $r_{s}$ the randomness in $σ_{1}$ .

The value $\tilde{x^{}}$ computed when unblinding with these values equals $x^{}$ . From (4) and (6): $\begin{array}{l} g_{1}^{u_{1}} = k^{u_{1} s^{- 1}} = {Dec}_{z} {(σ_{1})}^{s^{- 1}} {Dec}_{z} {(B^{- 1})}^{s^{- 1}} = {Dec}_{z} {(σ_{1})}^{s^{- 1}} x^{- 1} g_{2}^{y_{2}} v^{e} \end{array}$ From (5): ${\tilde{x}}^{} = x g_{1}^{u_{1}} g_{2}^{u_{2}} v^{d} = x ({Dec}_{z} {(σ_{1})}^{s^{- 1}} x^{- 1} g_{2}^{y_{2}} v^{e}) g_{2}^{σ_{2} - y_{2}} v^{e^{} - e} = {Dec}_{z} {(σ_{1})}^{s^{- 1}} g_{2}^{σ_{2}} v^{e^{}} = x^{}$ □

As a result: Theorem 6.
The Okamoto–Schnorr PACBS scheme satisfies perfect blindness.
Proof.
Let $S^{}$ be the unbounded adversary in the blindness game in Algorithm 6 and $vie w_{i} = (e_{i}, β_{i})$ for $i \in {0, 1}$ be his view in each case. From Lemma 4 it follows that, for both cases of $i, j \in {0, 1}$ , there exists a unique tuple $(u_{1}, u_{2}, d, r)$ that maps $vie w_{i}$ to $σ_{j}$ and the unbounded adversary can always compute it. This means that the view of the adversary and the produced signatures are statistically independent. As a result in the blindness game (Algorithm 6) both signatures $σ_{c}, σ_{1 - c}$ are perfectly indistinguishable for $S^{}$ and his advantage in the PACBS-BlindExp is zero. □

6.4.3. Unforgeability

Theorem 7.
If the OS-CBS scheme is l one-more unforgeable then the OS-PACBS scheme is l one-more unforgeable under the assumption that no signatures with the same input $C$ to the predicate are requested.
Proof.
It will be shown that if there exists an $A$ that wins the $PACBS-OneMoreForge$ game with non-negligible probability, an algorithm $B$ can be constructed that wins the $CBS-OneMoreForge$ game with non-negligible probability.

The role of $B$ will be to simulate an OS-PACBS signer for $A$ , by responding to his requests for signatures without having the signing key s.

If the conversation between $A$ and $B$ is indistinguishable from a conversation between $A$ and a real OS-PACBS signer, then $A$ will issue a forgery with non-negligible probability (by assumption). Then $B$ can utilize it to issue an OS-CBS forgery when interacting with the OS-CBS signer $S$ .

Fig. 6.
Forging OS-PACBS by using OS-CBS.

An overview of the reduction is presented in Fig. 6.

The input of $B$ will be the public input of OS-CBS namely $G, g_{1}, g_{2}, v, k$ . The OS-CBS signing oracle $S$ is initialized with s by the challenger in order to be able to answer signing requests. In order to simulate a PACBS Signer, $B$ generates a random $w \in Z_{q}$ and computes $h_{1} = g_{1}^{w} \in G$ . Moreover he selects $z \in Z_{q}$ and computes $h = h_{1}^{z} \in G$ . $B$ must know the decryption key z in order to be able to check the value of the predicate and properly derive the validity of the signature generated by $A$ .

$B$ initializes $A$ with $G, g_{1}, g_{2}, v, k, h_{1}, h$ . $A$ can query the two random oracles $H_{1}, H_{2}$ and $B$ with $C = (C_{1}, C_{2})$ of his choice. As an OS-PACBS signer, $B$ should be able to answer these requests indistinguishably from a real execution of the experiment. To do so, $B$ utilizes the random oracle $H$ and the signing interactions with $S$ .

For the $H_{2}$ queries that $A$ makes, $B$ queries the random oracle $H$ on the same message and forwards the response.

For the $H_{1}$ queries that $A$ makes on input $C$ , if $H_{1} (C)$ is not yet defined, $B$ can check the validity of the predicate since he can decrypt $C = (C_{1}, C_{2})$ by utilizing z and check if $p r e d (C) = 1$ or equivalently if ${Dec}_{z} (C_{1}) = {Dec}_{z} (C_{2})$ . After the decryption $B$ proceeds as follows:
If $pred (C) = 1$ , $B$ begins an interaction (which he might continue or abort later) with the valid OS-CBS signer $S$ and receives the first message x. He sets $H_{1} (C) = x$ and responds to $A$ with x.

If $pred (C) = 0$ , $B$ responds with a uniformly selected element of $G$ .
Without loss of generality, it can be assumed that whenever $A$ queries $B$ with $C$ he has queried $H_{1} (C)$ .

To answer the signing queries of $A$ , $B$ proceeds as follows:

When receiving $C, e$ from $A$ , if $pred (C) = 1$ , $B$ continues the interaction started with $S$ when answering $H_{1} (C)$ by forwarding e.

$B$ receives an OS-CBS signature $β = (β_{1}, β_{2})$ from $S$ where $β_{2} \leftarrow_{$} Z_{q}$ and $β_{1} = {Enc}_{h} ({(x g_{2}^{- β_{2}} v^{- e})}^{s})$ . Then $B$ must compute $n, N, W, B$ as specified in Fig. 4. $B$ proceeds as follows:
n is computed as specified by the protocol: $n = x g_{2}^{- β_{2}} v^{- e}$ . This is straightforward since all values are known. Indeed, v was provided by the challenger, $x, β_{2}$ were provided by $S$ and e by $A$ .

$B$ can also compute $n^{s} = {Dec}_{z} (β_{1})$ . Note that $β_{1} = {Enc}_{h} (n^{s})$ (cf. Section 4.2 and Fig. 4). Since $B$ knows the decryption key, decryption is straightforward.

$N$ is computed normally as $N = {Enc}_{h} (n, r_{1}) = (h_{1}^{r_{1}}, n h^{r_{1}}) = (h_{1}^{r_{1}}, n h_{1}^{z r_{1}})$ . $B$ also generates the proof $π_{1}$ in the normal manner, as he knows the randomness used in the encryption.

W is computed as an encryption of 1 since the signature will be valid. $B$ selects $r, (α, γ)$ and computes $r_{2} = α r + γ$ and $W = {Enc}_{h} (1, r_{2}) = (h_{1}^{r_{2}}, h^{r_{2}}) = (h_{1}^{r_{2}}, h_{1}^{z r_{2}})$ which is a valid reencryption of $\frac{C_{2}}{C_{1}} = {Enc}_{h} (1)$ . $B$ simulates the proof $π_{2}$ .

To compute $B$ as ${(N W)}^{s}$ , $B$ must use s, which he does not possess. But he can compute $B$ using k, $n^{s}$ , $r_{1}$ and $r_{2}$ as follows: $\begin{array}{l} (k^{w r_{1} + w r_{2}}, k^{(w r_{1} + w r_{2}) z} n^{s}) \\ = (g_{1}^{s (w r_{1} + w r_{2})}, g_{1}^{s (w r_{1} + w r_{2}) z} n^{s}) \\ = (g_{1}^{s (w r_{1})}, g_{1}^{s (w r_{1}) z} n^{s}) (g_{1}^{s (w r_{2})}, g_{1}^{s (w r_{2}) z}) \\ = (h_{1}^{s r_{1}}, h_{1}^{s r_{1} z} n^{s}) (h_{1}^{s r_{2}}, h_{1}^{s r_{2}} z) \\ = (h_{1}^{s r_{1}}, h^{s r_{1}} n^{s}) (h_{1}^{s r_{2}}, h^{s r_{2}}) \\ = {Enc}_{h} {(n; r_{1})}^{s} {Enc}_{h} {(1; r_{2})}^{s} = {(N W)}^{s} \end{array}$
The proof $π_{3}$ is simulated as $B$ does not possess s, but the equation holds.

If $pred (C) = 0$ , $B$ does not use $S$ and must construct an invalid signature for $A$ on its own. This can be done in the following manner:
$B$ randomly selects $β_{2} \in Z_{q}$ .

$B$ computes $n = x g_{2}^{- β_{2}} v^{- e}$ .

$N$ is computed normally as $N = {Enc}_{h} (n, r_{1}) = (h_{1}^{r_{1}}, n h^{r_{1}}) = (h_{1}^{r_{1}}, n h_{1}^{z r_{1}})$ . $π_{1}$ is generated as before.

$W$ must contain the encryption of a random group element. $B$ chooses $r_{3} \in Z_{q}$ and computes $g_{1}^{r_{3}} n^{- 1}$ for this reason and sets $W = {Enc}_{h} (g_{1}^{r_{3}} n^{- 1}, r_{2}) = (h_{1}^{r_{2}}, g_{1}^{r_{3}} n^{- 1} h^{r_{2}})$ .

$B$ is computed using k as: $(k^{w r_{1} + w r_{2}}, k^{(w r_{1} + w r_{2}) z} k^{r_{3}})$ . It is easy to see that $B = {(N W)}^{s}$ .

Proofs $π_{2}, π_{3}$ are simulated by $B$ .

Assuming that no signing requests with the same predicate input C are issued by $A$ , all the interactions are indistinguishable from interactions with a real OS-PACBS signer. Using Lemma 3 it follows that every valid message-signature outputted by $A$ is also a valid signature for the OS-CBS scheme. Furthermore, if $A$ queries for l valid signatures then $B$ completes exactly l interactions with $S$ . So: $\begin{matrix} Pr [{PACBS-OneMoreForge}_{A, OS-PACBS} = 1] = Pr [{CBS-OneMoreForge}_{B, OS-CBS} = 1] \end{matrix}$ which concludes the proof. □

Note that Theorem 7 implies that OS-PACBS, like OS-CBS, also inherits the constraints of the Okamoto–Schnorr blind signatures [28,31] in the concurrent setting. Additionally, the security guarantees for OS-PACBS hold against adversaries who cannot ask for a signature with the same challenge more than once. The protocol that utilizes this scheme should take care of both these restrictions i.e. deny issuing signatures on challenges that are already used and limit the number of concurrent signing sessions to be polylogarithmic in the security parameter or employ additional countermeasures depending on the nature of the application.
6.4.4. Conditional verifiability

A malicious user, without any access to either the verification key or the encryption key, not knowing the decryptions of $C_{1}, C_{2}$ cannot decide the value of the predicate to determine whether a received signature is valid or not. This can be proved by a reduction to the indistinguishability of the underlying encryption scheme.

Theorem 8.
The OS-PACBS scheme has conditional verifiability.
Proof.
Suppose there exists a PPT algorithm $A$ that breaks the conditional verifiability of the OS-PACBS scheme, by winning the game in Algorithm 8. Then, there exists a PPT algorithm $B$ that breaks the indistinguishability of the underlying encryption scheme. The interactions of $B$ are:
$B$ gets as input the parameters and public key of the underlying encryption scheme $G, h_{1}, h$ where $h = h_{1}^{z}$ for some z.

$B$ creates keys and parameters for the PACBS scheme. In particular $B$ chooses random $g_{1}, g_{2}, v \in G$ and $s \in Z_{q}$ and sets $k = g_{1}^{s}$ . He hands the parameters $G, g_{1}, g_{2}, v, k, h_{1}, h$ to $A$ .

$B$ computes the signatures requested by $A$ by using the $OS-PACBS.Sign$ protocol from Fig. 4. Note that for signing only the private key s is required. So $B$ can create signatures without knowing the secret encryption key z.

When $A$ asks to be challenged on a signature, $B$ selects two known group elements $m_{1}, m_{2}$ and hands $({Enc}_{h} (m_{1}), {Enc}_{h} (m_{2}))$ to the challenger of the IND-CPA property of the encryption scheme as his own challenge. He receives $C$ as a response. $B$ hands the pair $(C, {Enc}_{h} (m_{1}))$ as the public input for the challenge predicate $pred (C, {Enc}_{h} (m_{1}))$ and receives e as a response. He computes a signature $(((n, B, N, W), y_{2}), π_{1}, π_{2}, π_{3})$ with public input $(C, {Enc}_{h} (m_{1}))$ and hands it to $A$ .

$A$ responds with 0 (valid) or 1 (invalid). In the first case $B$ outputs 1 and in the second 0.

First, the signatures $A$ receives are identically distributed as real ones since they are computed in the exact same way. In the case $C = {Enc}_{h} (m_{1})$ the view of $A$ is identical to a real interaction for a valid signature request and in the case $C = {Enc}_{h} (m_{2})$ it is identical to an invalid request. It is clear that the advantage of $A$ in distinguishing between the two cases is identical to the advantage of $B$ against the indistinguishability of the underlying encryption scheme. □

6.4.5. Public auditability for signing and verifying

Using the correctness of the protocol, it can be seen that if the statements of the proofs presented hold, a signature is valid if and only if $pred = 1$ . This means that in order for a Signer/Verifier to win one of the two Public Auditability experiments one of the proofs presented must not hold, and he must convince the auditor that it does. Thus, at least for one proof soundness must not hold, which is a contradiction.

7. Applications

We now detail the applications of our primitives. Our motivation is coercion-resistant electronic voting as implemented using PACBS [18] so this will be our main focus. However, by generalizing this usage scenario, we can also apply them to other areas.

7.1. Background: Coercion-resistant e-voting with blind signatures

Blind signatures have been penned for electronic voting since their original proposal in [6]. The most prominent such e-voting scheme was proposed in the classic FOO protocol [14], where there are two entities functionally conducting the elections. The eligibility checks are performed by a registration authority ( $RA$ ), while vote tallying is performed by a tallying authority ( $TA$ ). The voters submit their identification information along with their blinded vote to the $RA$ . In turn, it checks voter eligibility using the provided ID, and if the voter has the right to vote, signs the blinded ballot and returns it to her. She then unblinds the signature and casts it, together with the ballot, to a publicly available append-only Bulletin Board ( $B B$ ) through an anonymous channel. The $TA$ retrieves the ballots and decides which ones to count based on the validity of the signature. Secrecy protection is multilayered: The $RA$ knows the identity of the voter but cannot access the ballot contents because of the blinding. The $TA$ might know the voter choice but cannot have access to the voter ID. Finally, the $RA$ cannot associate signing sessions with unblinded signatures, because of the unlinkability provided by the blind signature scheme.

Coercion-resistance is one of the most important goals for the realization of remote electronic voting. Its absence, means that there is no way to make sure that a voter is expressing her own will or is following the commands of a coercer standing over her shoulder. In [23], Juels, Catalano and Jakobsson (JCJ) consider a framework that provides receipt-freeness and can also defend against the three most important coercion attack scenarios, namely voter impersonation, random voting and forced abstention. Their proposal is based on a combination of two defense techniques: Multiple votes per voter and authentication using anonymous credentials. As outlined in Section 1, in the JCJ setting, each vote is authenticated by an anonymous token. During an untappable registration phase the voter receives a genuine credential. It is accompanied by a designated verifier proof [22] so that the voter can simulate and fake it. The genuine credential is meant to be used when the voter is not under coercion and will authenticate the intended vote. It is assumed by [23] that all voters have at least one such moment of privacy, otherwise, coercion-resistance cannot be attained. Under coercion, they supply an indistinguishable but fake credential to accompany the vote. The $TA$ must count only the votes that correspond to authentic credentials, verifiably for the voter, but without publicly disclosing which votes are discarded so that the coercer cannot check compliance. To this end, the PET primitive (cf. Section 2.3.3) is used to compare all credentials, along with an anonymous channel which is essential to thwarting the forced abstention attack. The problem with this process is that its time complexity is quadratic to the number of votes cast – typically larger than the number of voters because of multiple votes. This makes the JCJ framework inefficient for practical usage.

Many works in the literature have tried to make efficiency improvements [2,3,37]. Our approach, originally remarked in [17], is based on the fact that the combination of the FOO and JCJ schemes can improve the complexity of detecting coerced votes, bringing it down to a linear function of the number of voters, by incorporating the credential weeding into the eligibility verification performed by the $RA$ . During this phase the voter ID is known, so only the credentials corresponding to the particular ID should be considered, instead of checking all the voters’ tokens. As a result, the $RA$ can tell if a particular vote should be counted. For the actual counting, however, this should be conveyed to the $TA$ . This can be done by extending the scope of the $RA$ ’s signature. Instead of only indicating eligibility, it can also signal if the authenticating credential is genuine or real, for the vote to be counted by their $TA$ or not. All these must be done verifiably to boost trust in the system. Every election stakeholder should be able to audit the process to check that the two authorities followed the protocol. However, the voters, should also be convinced that only the vote corresponding to the registered credential was counted. This fact should not be conveyed to the coercer. This particular idea is incorporated in the PACBS primitive.

7.2. Applying PACBS to coercion-resistant e-voting

The workflow of the PACBS voting scheme from [18], combining FOO [14] and JCJ [23] is depicted in Fig. 7 from the point of view of a single voter $V$ . The participating authorities $TA, RA$ consist of many members, with conflicting interests, that share cryptographic keys. Elections are organized by a central entity so it is not uncommon for the functionalities of the $TA, RA$ to be performed by the same election authority. As a result, the assumption that the authorities can share a cryptographic key (in this case the PACBS secret key s) is not restricting or unrealistic.

Fig. 7.

PACBS voting.

The scheme of [18] consists of 3 main phases: Registration, Voting (split into two sub-phases: authorization and casting) and Tallying. As in JCJ, $V$ obtains the real credential t through an untappable pre-election registration. When this phase ends, the $RA$ posts a list of pairs of voter ID and encrypted genuine credential to the publicly available $B B$ . Assume that $V$ has obtained the credential t encrypted as $C_{1}$ under the $RA$ public key. $C_{1}$ will be included in the public credential list. During the voting phase, $V$ first performs an authorization request. To this end, she recomputes an encryption of the credential as $C_{2}$ and computes the encryption $c$ of her vote. If the voter is under coercion, she will use a fake credential $t^{'}$ . Otherwise, she will use t, making $C_{2}$ encrypt the same plaintext as $C_{1}$ . Subsequently, she initiates the $PACBS.Sign$ protocol with the $RA$ (Fig. 4) by blinding c, using the $PACBS.Blind$ algorithm, and attaching both credentials $C_{1}, C_{2}$ . Note that there is no need to create $c$ with the same public key as $C_{1}, C_{2}$ . Then $V$ includes the $PACBS.Blind$ output e, in a voter authorization request, which includes voter identification information as in [14]. The $RA$ uses this information to find out if $V$ is eligible to vote, eliminate duplicate requests, and invokes the $PACBS.BlindSign$ functionality to compute the blind signature β, conditional to the predicate $pred (C_{1}, C_{2}) = 1 \Leftrightarrow {Dec}_{z} (C_{1}) = {Dec}_{z} (C_{2})$ and verifiable by the $TA$ . $PACBS.BlindSign$ also produces the proof $π_{Sign}$ . $V$ retrieves β and invokes the $PACBS.Unblind$ functionality to obtain the plain signature σ which is then recast with $c$ , as the ballot for $V$ .

For tallying, the $TA$ must count only the votes that correspond to uncoerced ballots i.e. ballots for which $pred (C_{1}, C_{2}) = 1$ when signed by the $RA$ . This can be determined by the execution of the $PACBS.Vrfy$ functionality for each ballot – signature pair. However, if the $TA$ is ‘careless’ and simply executes this functionality ‘as-is’, its published result will notify the coercer if his coercion attempt succeeded, beating the purpose of the fake credentials mechanism. To be concrete, to avoid this leak, if the OS-PACBS instantiation is used, the $TA$ will perform the weeding in two steps: Firstly, it will compute $R$ and $π_{Vrfy} = (π_{1}, π_{2}, π_{3})$ as specified in Algorithm 13 and post them to the $B B$ . Then it will use a verifiable shuffle to disassociate all entries from their form when they were originally cast. The result of the shuffle will be verifiably decrypted, and counted if and only if ${Dec}_{z} (R) = 1$ . The $π_{4}$ will be posted to the $B B$ . By the construction of the PACBS scheme, this means that only the votes that were not a product of coercion, as indicated by the usage of the correct credential will be counted.

7.2.1. Security analysis

The PACBS voting protocol provides individual and universal verifiability, privacy and coercion-resistance. For verifiability, each voter can audit all stages between vote creation and tallying preparation to defend against a corrupted election authority. Clash attacks [25] can be thwarted by requiring the voter to post a NIZK proof of knowledge of the ballot contents during the authorization request. The design of $PACBS.Sign$ and the $PACBS.Audit-Sign$ functionalities provides the means to check that the $RA$ followed the protocol and embedded the predicate correctly inside the signature. During tallying, the proofs that accompany the verifiable shuffle and the proof of correct decryption allow the auditing of the $TA$ ’s functionality. Furthermore, the proofs generated by $PACBS.Vrfy$ can make sure that the predicate was indeed taken into consideration, when deciding which votes to count. All these checks can be performed either by each voter individually or by external auditors for universal verifiability.

The architecture of PACBS provides coercion-resistance according to the JCJ framework. In particular, if a coercer forces the voter to reveal her credential, or vote randomly with it, then $V$ can present a fake one. The coercer cannot, at this stage, tell if the credential is authentic or not. The reason for this is the untappability of the registration phase, which provides deniability to the honest voter. For the corrupted voter, on the other hand, it provides the inability to verify claims surrounding a vote for sale. Indeed, in our protocol we also accept the assumption of [23], which states that the registration transcript for credential generation can be entirely deleted or is simulateable. Furthermore, the coercer does not fully control the $RA$ . As a result, the voter can successfully lie to the coercer. Even if the voter is corrupt, she cannot prove that the credential is real, and in effect that the vote will be counted. During the moment of privacy, $V$ can cast her real vote. Nobody, including the coercer, can tell if the credential is valid or not, since the conditional verifiability of PACBS discloses this information only to the designated verifier (the $TA$ in this case). The voter can also tell if she used the correct credential. However, this knowledge is not transferable as $V$ cannot prove this fact to the coercer, even if she wants to, because of the nature of the registration phase. As a result, our scheme provides verifiability as well as coercion-resistance (including receipt-freeness). The generated proof $π_{Vrfy}$ will merely provide information that the protocol was executed successfully. In the tallying phase, shuffling and $PACBS.Vrfy$ ensure the coercer loses track of his submitted vote and the only information he gets is the final tally. Of course, for all these to hold, the coercer is assumed not to (fully) corrupt the election authorities, which is one of the assumptions made in the JCJ framework anyway. To thwart the forced abstention attack, however, a further assumption should be made, namely that there are multiple authorization requests with the same ID. This prevents the coercer from verifying abstention by checking if a vote with a particular ID is missing from the $B B$ . Such an assumption is common in previous JCJ related schemes in the literature (e.g. [11,33]). These extra authorization requests are assumed to originate from interested third parties (e.g. pro-democracy non-governmental organizations) or other voters, and will not be counted as they cannot contain the authentic credential.

To reiterate, the public auditability of PACBS combined with the JCJ anonymous credentials, is the basic idea that allows universal verifiability to co-exist with coercion-resistance. The voter has an extra piece of non-transferable private knowledge: She knows, if she used the authentic credentials in her moment of privacy. The auditing of the outputs of the $PACBS.Sign$ and $PACBS.Vrfy$ functionality, combined with this private input, allows the voter to tell if her vote was counted or not. However, the same actions, when performed by the public (the coercer included) can only inform them if the $TA$ executed the protocol correctly, without giving away which vote will be counted.

Finally, privacy is provided against the public as well as against a corrupted election authority. During the voting phase, the secrecy of the vote contents is protected by the semantic security of the employed cryptosystem. Furthermore, during the authorization request, where voter identifying information is present, the encrypted vote is blinded as well. This protects against a malicious authority, in possession of the decryption key. In combination with the unlinkability property of the blind signature scheme, the authorization requests cannot be correlated with vote casting. Subsequently, in the tallying phase, the shuffle performed by the $TA$ disassociates the vote to be tallied from their form as they were cast.

Of course, an electronic voting protocol is a very complex construction. The description provided in the current section focused on the applicability of the PACBS primitive to verifiably weed out coerced votes to achieve coercion-resistance in the JCJ framework through the use of fake credentials. Many elements have been omitted, such as mechanisms for cast-as-intended verifiability, the proofs required from the part of the voter to prove correct encryption and to prevent clash attacks, locating and removing duplicate votes, the use of anonymous channels for defense against forced abstention attacks, a rigorous security analysis and many more. Such details appear in [18], while others are part of ongoing work.

7.3. Generalization and other applications

The general property provided by both CBS and PACBS primitives when combined with the FOO architecture [14] and the fake credentials mechanism of JCJ [23] is certified anonymity. Use cases that require this property have recently attracted attention and there have been similar proposals [20] that also follow this general pattern, differing on the use of primitives. In order to make the use of CBS/PACBS in such usage scenarios more clear, a generalization of the voting use case from Section 7.2 is provided.

A service is meant to be used by a predetermined set of users, that must be authenticated before access is granted. Access to the service is regulated by an authenticator, while the service is implemented by a provider. The authenticator and provider might be the same entity or not. The use of the service must be anonymous, concerning the identities as well as the inputs of the users. For instance, one can imagine access to adult content or a questionnaire about the evaluation of a university course, or the statistical processing of the financial results for a set of companies. In order to guarantee anonymity, the identities of the participants should be hidden. However, this is not enough, as the answers to survey questions could themselves function as a side-channel and leak identifying information. In the latter case, for instance, a company could be identified by its financial results. Consequently, data processing should be private.

A possible solution could involve homomorphic encryption, which would, however, limit the types of possible computations allowed on the data. CBS and PACBS can provide another alternative, by creating unlinkable tokens (signatures), that regulate the service use. If performance is favored and the service provider is trusted, then CBS can be used. If verifiability is required then PACBS must be used.

In more detail, the service provider creates beforehand a list of random and anonymous credentials and assigns them to the intended users, while noting the assignment. Each time a user must use the service, she provides the credential. Moreover, she includes a blinded input to the service (e.g. the answers of the survey, or the content she wishes to access). Using the identity the service authenticator checks if the user is eligible for the service, without having access to the user input. If and only if the credential is valid the authenticator provides a valid CBS or PACBS. The user can then unblind the input and submit it to the service provider, without disclosing her identity, since access regulation is provided by the signature. In fact, the possibility of both valid and invalid signatures and the conditional verifiability property prevents a third party from telling which users do access the service. This also motivates the users to obfuscate their usage patterns or inputs themselves by providing fake credentials on purpose. A third party observing the protocol, will not be able to distinguish which users do access the service and their inputs, thus eliminating the side-channel. However, the users will know which requests are granted access because they are aware if they used a valid credential or not.

8. Conclusion

In this paper, CBS and PACBS, two novel cryptographic primitives were presented. Both, but PACBS in particular, expand the semantics of digital signatures, which in most cases depend only on the message to be signed, by including publicly available data, that are considered during signature creation via a predicate. Additionally, both primitives protect the privacy of the message to be signed by providing perfect blindness. To reason about their security, a novel property, conditional verifiability was also proposed.

The introduction of these primitives, was motivated by the need to implement coercion-resistant and verifiable electronic voting in the JCJ framework. However, they were presented in a generic manner, independently of any particular usage scenario. As a result, they can be used in all cases where a signature is applied to a message and its validity depends on the evaluation of a predicate on publicly available data. Such contexts include anonymous surveys and all cases where there is the danger of coercion but also the need for privacy combined with verifiability. The trust assumptions about the signer and the verifier can provide guidance for which of the two proposed primitives can be employed.

Fig. 8.

The protocol ${OS-PACBS.Sign}_{2} ⟨ S (s_{1}, s_{2}), U (m), prms, (C_{1}, C_{2}), pk ⟩$ .

The design of more concrete protocols for applying CBS and PACBS in various usage scenarios is a natural direction for further research. Moreover, one could investigate alternative constructions that implement the main ideas of CBS and PACBS, but provide unforgeability against plain one-more forgery instead of strong one-more forgery, thus improving efficiency and scalability. Additionally, in alternative constructions, the emphasis could shift between blindness, designated verification, and auditability to express more fine-grained trust models (e.g. a corrupted signer but an honest verifier and vice versa, or computational instead of perfect blindness). Finally, another research goal would be to extend the conditional information to more than a single predicate, to a complete functionality (program) that can be embedded inside a signature and operate on encrypted data.

Algorithm 15:

OS-PACBS.Vrfy $_{2} (prms, pk, {sk}_{V}, m, σ)$

Footnotes

Acknowledgments

The authors would like to thank the anonymous reviewers for their helpful comments and suggestions that have greatly improved the paper.

Alternative OS-PACBS instantiation

An alternative PACBS instantiation is provided, OS-PACBS₂, where the signer and the verifier do not share a key. The key generation algorithm is the same as in Algorithm 4 along with $h, h_{1}$ from Algorithm 11. The function $embed$ is defined as in (2). The predicate $pred$ is defined as in (3).

The signing protocol is presented in Fig. 8. The proofs $π_{1}, π_{2}, π_{4}$ are standard Okamoto [28] proofs. The proof $π_{3}$ is similar to the one in Fig. 5.

The verification algorithm is presented in Algorithm 15. The proofs $π_{1}, π_{2}, π_{3}$ are similar to the ones from Algorithm 13.

The algorithms for $OS-PACBS.Audit-Sign, OS-PACBS.Audit-Vrfy$ are similar to Algorithm 12 and Algorithm 14 respectively.

The security analysis of this alternative instantiation is similar to Section 6.4.

AND composition for proofs in OS-PACBS.Sign and OS-PACBS.Vrfy

The AND composition of $π_{1}, π_{2}, π_{3}$ from Fig. 4 is described in Fig. 9 where: $\begin{array}{l} π_{1} = PoK {(h_{1}, h, n, N), (r) : N = {Enc}_{h} (n; r) = (X, Y) = (h_{1}^{r}, n h^{r})} \\ π_{2} = PoK {(C_{1}, C_{2}, W), (α, γ) : W = {(C_{2} / C_{1})}^{α} \cdot {Enc}_{h} (1; γ)} \\ π_{3} = PoK {(h, k, N, W, B), (s) : B = {(N \cdot W)}^{s} AND k = g_{1}^{s}} \end{array}$

The AND combination of $π_{1}, π_{2}, π_{3}, π_{4}$ from Algorithm 13 is straightforward (Fig. 10). Efficiency improvements can be gained by reusing $T_{1}$ from $π_{1}$ in $π_{4}$ . Recall that: $\begin{array}{l} π_{1} = PoK {(h_{1}, h, M, validity), (r_{1}) : M = {Enc}_{h} (validity; r_{1}) = (A_{1}, B_{1})} \\ π_{2} = PoK {(V, M), (s) : V = M^{s}} \\ π_{3} = PoK {(V, σ_{1}, R), (γ) : R = {(\frac{V}{σ_{1}})}^{γ}} \\ π_{4} = PoK {(h_{1}, h, result, R = (A_{4}, B_{4})), (z) : result = {Dec}_{z} (R)} \end{array}$

References

Abe and

Okamoto, Provably secure partially blind signatures, in: Advances in Cryptology – CRYPTO 2000, 20th Annual International Cryptology Conference, Proceedings, Santa Barbara, California, USA, August 20–24, 2000,

Bellare, ed., Lecture Notes in Computer Science, Vol. 1880, Springer, 2000, pp. 271–286. doi:10.1007/3-540-44598-6_17.

Araújo,

Foulle and

Traoré, A practical and secure coercion-resistant scheme for remote elections, in: Frontiers of Electronic Voting, 29.07.–03.08.2007,

Chaum,

Kutylowski,

R.L.

Rivest and

P.Y.A.

Ryan, eds, Dagstuhl Seminar Proceedings, Vol. 07311, Internationales Begegnungs- und Forschungszentrum fuer Informatik (IBFI), Schloss Dagstuhl, Germany, 2007, http://drops.dagstuhl.de/opus/volltexte/2008/1295 .

Araújo,

N.B.

Rajeb,

Robbana,

Traoré and

Yousfi, Towards practical and secure coercion-resistant electronic elections, in: Cryptology and Network Security – 9th International Conference, CANS 2010, Proceedings, Kuala Lumpur, Malaysia, December 12–14, 2010,

Heng,

R.N.

Wright and

Goi, eds, Lecture Notes in Computer Science, Vol. 6467, Springer, 2010, pp. 278–297. doi:10.1007/978-3-642-17619-7_20.

Benhamouda,

Lepoint,

Loss,

Orrù and

Raykova, 2020, On the (in)security of ROS, https://eprint.iacr.org/2020/945.

Boneh, The decision Diffie–Hellman problem, in: Algorithmic Number Theory, Third International Symposium, ANTS-III, Proceedings, Portland, Oregon, USA June 21–25, 1998,

Buhler, ed., Lecture Notes in Computer Science, Vol. 1423, Springer, 1998, pp. 48–63. doi:10.1007/BFb0054851.

Chaum, Blind signatures for untraceable payments, in: Advances in Cryptology: Proceedings of CRYPTO’82, Santa Barbara, California, USA, August 23–25, 1982,

Chaum,

R.L.

Rivest and

A.T.

Sherman, eds, Plenum Press, New York, 1982, pp. 199–203.

Chaum, Designated confirmer signatures, in: Advances in Cryptology – EUROCRYPT’94, Workshop on the Theory and Application of Cryptographic Techniques, Proceedings, Perugia, Italy, May 9–12, 1994,

A.D.

Santis, ed., Lecture Notes in Computer Science, Vol. 950, Springer, 1994, pp. 86–91. doi:10.1007/BFb0053427.

Chaum and

H.V.

Antwerpen, Undeniable signatures, in: Advances in Cryptology – CRYPTO’89, 9th Annual International Cryptology Conference, Proceedings, Santa Barbara, California, USA, August 20–24, 1989,

Brassard, ed., Lecture Notes in Computer Science, Vol. 435, Springer, 1989, pp. 212–216. doi:10.1007/0-387-34805-0_20.

Chaum and

T.P.

Pedersen, Wallet databases with observers, in: Advances in Cryptology – CRYPTO’92, 12th Annual International Cryptology Conference, Proceedings, Santa Barbara, California, USA, August 16–20, 1992,

E.F.

Brickell, ed., Lecture Notes in Computer Science, Vol. 740, Springer, 1992, pp. 89–105. doi:10.1007/3-540-48071-4_7.

10.

Chaum and

van Heyst, Group Signatures, in: Advances in Cryptology – EUROCRYPT’91, Workshop on the Theory and Application of Cryptographic Techniques, Proceedings, Brighton, UK, April 8–11, 1991,

D.W.

Davies, ed., Lecture Notes in Computer Science, Vol. 547, Springer, 1991, pp. 257–265. doi:10.1007/3-540-46416-6_22.

11.

Clark and

Hengartner, Selections: Internet voting with over-the-shoulder coercion-resistance, in: Financial Cryptography and Data Security – 15th International Conference, FC 2011, Revised Selected Papers, Gros Islet, St. Lucia, February 28–March 4, 2011,

Danezis, ed., Lecture Notes in Computer Science, Vol. 7035, Springer, 2011, pp. 47–61. doi:10.1007/978-3-642-27576-0_4.

12.

Cramer,

Damgård and

Schoenmakers, Proofs of partial knowledge and simplified design of witness hiding protocols, in: Advances in Cryptology – CRYPTO’94, 14th Annual International Cryptology Conference, Proceedings, Santa Barbara, California, USA, August 21–25, 1994,

Desmedt, ed., Lecture Notes in Computer Science, Vol. 839, Springer, 1994, pp. 174–187. doi:10.1007/3-540-48658-5_19.

13.

Fiat and

Shamir, How to prove yourself: Practical solutions to identification and signature problems, in: Advances in Cryptology – CRYPTO’86, 1986, Proceedings, Santa Barbara, California, USA,

A.M.

Odlyzko, ed., Lecture Notes in Computer Science, Vol. 263, Springer, 1986, pp. 186–194. doi:10.1007/3-540-47721-7_12.

14.

Fujioka,

Okamoto and

Ohta, A practical secret voting scheme for large scale elections, in: Advances in Cryptology – AUSCRYPT’92, Workshop on the Theory and Application of Cryptographic Techniques, Proceedings, Gold Coast, Queensland, Australia December 13–16, 1992,

Seberry and

Zheng, eds, Lecture Notes in Computer Science, Vol. 718, Springer, 1992, pp. 244–251. doi:10.1007/3-540-57220-1_66.

15.

T.E.

Gamal, A public key cryptosystem and a signature scheme based on discrete logarithms, IEEE Trans. Information Theory 31(4) (1985), 469–472. doi:10.1109/TIT.1985.1057074.

16.

Gertner,

Ishai,

Kushilevitz and

Malkin, Protecting data privacy in private information retrieval schemes, J. Comput. Syst. Sci. 60(3) (2000), 592–629. doi:10.1006/jcss.1999.1689.

17.

Grontas,

Pagourtzis and

Zacharakis, Coercion resistance in a practical secret voting scheme for large scale elections, in: 14th International Symposium on Pervasive Systems, Algorithms and Networks & 11th International Conference on Frontier of Computer Science and Technology & Third International Symposium of Creative Computing, ISPAN-FCST-ISCC 2017, Exeter, United Kingdom, June 21–23, 2017, IEEE Computer Society, 2017, pp. 514–519. doi:10.1109/ISPAN-FCST-ISCC.2017.79.

18.

Grontas,

Pagourtzis,

Zacharakis and

Zhang, Towards everlasting privacy and efficient coercion resistance in remote electronic voting, in: Financial Cryptography and Data Security – FC 2018 International Workshops, BITCOIN, VOTING, and WTSC, Revised Selected Papers, Nieuwpoort, Curaçao, March 2, 2018,

Zohar,

Eyal,

Teague,

Clark,

Bracciali,

Pintore and

Sala, eds, Lecture Notes in Computer Science, Vol. 10958, Springer, 2018, pp. 210–231. doi:10.1007/978-3-662-58820-8_15.

19.

Groth, Non-interactive zero-knowledge arguments for voting, in: Applied Cryptography and Network Security, Third International Conference, ACNS, 2005, Proceedings, New York, NY, USA, June 7–10, 2005,

Ioannidis,

A.D.

Keromytis and

Yung, eds, Lecture Notes in Computer Science, Vol. 3531, 2005, pp. 467–482. doi:10.1007/11496137_32.

20.

Hohenberger,

Myers,

Pass and

Shelat, ANONIZE: A large-scale anonymous survey system, in: 2014 IEEE Symposium on Security and Privacy, SP 2014, Berkeley, CA, USA, May 18–21, 2014, IEEE Computer Society, 2014, pp. 375–389. doi:10.1109/SP.2014.31.

21.

Jakobsson and

Juels, Mix and match: Secure function evaluation via ciphertexts, in: Advances in Cryptology – ASIACRYPT 2000, 6th International Conference on the Theory and Application of Cryptology and Information Security, Proceedings, Kyoto, Japan, December 3–7, 2000,

Okamoto, ed., Lecture Notes in Computer Science, Vol. 1976, Springer, 2000, pp. 162–177. doi:10.1007/3-540-44448-3_13.

22.

Jakobsson,

Sako and

Impagliazzo, Designated verifier proofs and their applications, in: Advances in Cryptology – EUROCRYPT’96, International Conference on the Theory and Application of Cryptographic Techniques, Proceeding, Saragossa, Spain, May 12–16, 1996,

U.M.

Maurer, ed., Lecture Notes in Computer Science, Vol. 1070, Springer, 1996, pp. 143–154. doi:10.1007/3-540-68339-9_13.

23.

Juels,

Catalano and

Jakobsson, Coercion-resistant electronic elections, in: Proceedings of the 2005 ACM Workshop on Privacy in the Electronic Society, WPES 2005, Alexandria, VA, USA, November 7, 2005,

Atluri,

S.D.C.

di Vimercati and

Dingledine, eds, ACM, 2005, pp. 61–70. doi:10.1145/1102199.1102213.

24.

Juels,

Luby and

Ostrovsky, Security of blind digital signatures (extended abstract), in: Advances in Cryptology – CRYPTO’97, 17th Annual International Cryptology Conference, Proceedings, Santa Barbara, California, USA, August 17–21, 1997,

B.S.

Kaliski, ed., Lecture Notes in Computer Science, Vol. 1294, Springer, 1997, pp. 150–164. doi:10.1007/BFb0052233.

25.

Küsters,

Truderung and

Vogt, Clash attacks on the verifiability of E-voting systems, in: IEEE Symposium on Security and Privacy, SP 2012, San Francisco, California, USA, 21–23 May 2012, IEEE Computer Society, 2012, pp. 395–409. doi:10.1109/SP.2012.32.

26.

Li,

Susilo,

Mu and

Pei, Designated verifier signature: Definition, framework and new constructions, in: Ubiquitous Intelligence and Computing, 4th International Conference, UIC 2007, Proceedings, Hong Kong, China, July 11–13, 2007,

Indulska,

Ma,

L.T.

Yang,

Ungerer and

Cao, eds, Lecture Notes in Computer Science, Vol. 4611, Springer, 2007, pp. 1191–1200. doi:10.1007/978-3-540-73549-6_116.

27.

Lipmaa,

Wang and

Bao, Designated verifier signature schemes: Attacks, new security notions and a new construction, in: Automata, Languages and Programming, 32nd International Colloquium, ICALP, 2005, Proceedings, Lisbon, Portugal, July 11–15, 2005,

Caires,

G.F.

Italiano,

Monteiro,

Palamidessi and

Yung, eds, Vol. 3580, Springer, 2005, pp. 459–471. doi:10.1007/11523468_38.

28.

Okamoto, Provably secure and practical identification schemes and corresponding signature schemes, in: Advances in Cryptology – CRYPTO’92, 12th Annual International Cryptology Conference, Proceedings, Santa Barbara, California, USA, August 16–20, 1992,

E.F.

Brickell, ed., Lecture Notes in Computer Science, Vol. 740, Springer, 1992, pp. 31–53. doi:10.1007/3-540-48071-4_3.

29.

Petersen, How to convert any digital signature scheme into a group signature scheme, in: Security Protocols, 5th International Workshop, Proceedings, Paris, France, April 7–9, 1997,

Christianson,

Crispo,

T.M.A.

Lomas and

Roe, eds, Lecture Notes in Computer Science, Vol. 1361, Springer, 1997, pp. 177–190. doi:10.1007/BFb0028168.

30.

Pointcheval and

Stern, Provably secure blind signature schemes, in: Advances in Cryptology – ASIACRYPT’96, International Conference on the Theory and Applications of Cryptology and Information Security, Proceedings, Kyongju, Korea, November 3–7, 1996,

Kim and

Matsumoto, eds, Lecture Notes in Computer Science, Vol. 1163, Springer, 1996, pp. 252–265. doi:10.1007/BFb0034852.

31.

Pointcheval and

Stern, Security arguments for digital signatures and blind signatures, J. Cryptology 13(3) (2000), 361–396. doi:10.1007/s001450010003.

32.

R.L.

Rivest,

Shamir and

Tauman, How to leak a secret, in: Advances in Cryptology – ASIACRYPT 2001, 7th International Conference on the Theory and Application of Cryptology and Information Security, Proceedings, Gold Coast, Australia, December 9–13, 2001,

Boyd, ed., Lecture Notes in Computer Science, Vol. 2248, Springer, 2001, pp. 552–565. doi:10.1007/3-540-45682-1_32.

33.

Schläpfer,

Haenni,

R.E.

Koenig and

Spycher, Efficient vote authorization in coercion-resistant Internet voting, in: E-Voting and Identity – Third International Conference, VoteID 2011, Revised Selected Papers, Tallinn, Estonia, September 28–30, 2011,

Kiayias and

Lipmaa, eds, Lecture Notes in Computer Science, Vol. 7187, Springer, 2011, pp. 71–88. doi:10.1007/978-3-642-32747-6_5.

34.

Schnorr, Efficient signature generation by smart cards, J. Cryptology 4(3) (1991), 161–174. doi:10.1007/BF00196725.

35.

Schnorr, Security of blind discrete log signatures against interactive attacks, in: Information and Communications Security, Third International Conference, ICICS 2001, Xian, China, November 13–16, 2001,

Qing,

Okamoto and

Zhou, eds, Lecture Notes in Computer Science, Vol. 2229, Springer, 2001, pp. 1–12. doi:10.1007/3-540-45600-7_1.

36.

Schröder and

Unruh, Security of blind signatures revisited, in: Public Key Cryptography, Lecture Notes in Computer Science, Vol. 7293, Springer, 2012, pp. 662–679.

37.

Spycher,

R.E.

Koenig,

Haenni and

Schläpfer, A new approach towards coercion-resistant remote E-voting in linear time, in: Financial Cryptography and Data Security – 15th International Conference, FC 2011, Revised Selected Papers, Gros Islet, St. Lucia, February 28–March 4, 2011,

Danezis, ed., Lecture Notes in Computer Science, Vol. 7035, Springer, 2011, pp. 182–189. doi:10.1007/978-3-642-27576-0_15.

38.

Zacharakis,

Grontas and

Pagourtzis, Conditional Blind Signatures, Short version presented in 7th International Conference on Algebraic Informatics – CAI 2017, (2017), 682, IACR eprint report 2017/682, http://eprint.iacr.org/2017/682.

Publicly auditable conditional blind signatures

Abstract

Keywords

1. Introduction

1.1. Contribution

1 Initially proposed in [38].

2. Preliminaries

2.1. Notation

2.2. Security assumptions

Definition 1 (Computational Diffie Hellman Assumption).

Definition 2 (Decisional Diffie Hellman Assumption).

2.3. Cryptographic primitives

2.3.1. Blind signatures

2.3.3. Plaintext equivalence test

3. Conditional blind signatures

3.1. Definitions

3.2.1. Blindness

4.1.1. Correctness

4.1.2. Blindness

5.1. Definition

5.2.1. Blindness

6.1. OS-PACBS parameter generation

6.4.1. Correctness

7. Applications

7.1. Background: Coercion-resistant e-voting with blind signatures

7.2. Applying PACBS to coercion-resistant e-voting

7.3. Generalization and other applications

8. Conclusion

Footnotes

Acknowledgments

Alternative OS-PACBS instantiation

AND composition for proofs in OS-PACBS.Sign and OS-PACBS.Vrfy

References

¹
Initially proposed in [38].