Homomorphic Signatures

Approaching the topic and the main proposals

The author thanks Janko Ferlic and Unsplash for the image

Brief introduction

Essentially, in a homomorphic signature scheme, a user Alice signs some dataset D using her secret key and uploads the signed data to an untrusted third party (either a server or a smart contract, for instance). This third party can run some computation f over the signed data and homomorphically derive a short signature σ_[f, y], certifying that y is the correct output of the computation f. Anybody will be able to take the tuple {f, y, σ_[f, y]} and get convinced, using Alice’s public key, that y is correct without having to retrieve the underlying data.

Basic definitions and concepts

A homomorphic signature scheme is a tuple of polynomial-time algorithms:

• Set(𝜆, n): it takes as inputs a security parameter 𝜆 and an integer n > 0. The output is a key pair (sk, pk). It also determines the space of messages M, the space of signatures S and the set F of admissible functions f: Mⁿ → M.
• Sig(sk, 𝜏, m, i): it takes as inputs a secret key sk, a tag 𝜏 ∈ {0, 1}^𝜆, a message m ∈ M and an index i ∈ {0, …, n}. The output is a signature σ ∈ S associated with the ith message m of the data set tagged by 𝜏.
• Vrf(pk, 𝜏, m, σ, f): it takes as input a public key pk, a tag 𝜏 ∈ {0, 1}^𝜆, a message m ∈ M, a signature σ ∈ S and a function f ∈ F. It outputs 1 if σ is a valid signature for m, and 0 otherwise. Here m is the output of f over the data set tagged by 𝜏.
• Eval(pk, 𝜏, f, Σ): it takes as input a public key pk, a tag 𝜏 ∈ {0, 1}^𝜆, a function f ∈ F and a tuple of signatures Σ = (σ₁, …, σₙ) ∈ Sⁿ corresponding to the signatures of the data set tagged by 𝜏. It outputs a signature σ’ ∈ S which is the result of evaluating f over the tuple Σ (one has to imagine that f is sought as a circuit, which performs the operation S is endowed with, instead of the operation of M).

A homomorphic signature scheme is correct if the following diagram commutes:

One should read this diagram as the following equivalence:

A homomorphic signature scheme is unforgeable if an adversary A is not able to generate a valid pair message-signature when the message has not been signed yet. In this situation, one distinguishes between:

1. Weak adversaries: they cannot freely choose the messages signed by a signing oracle OS. The attacker is restricted to making one query on a sequence of data sets of its choice.
2. Strong adversaries: they are not restricted and can query one message at a time, and even choose the next query based on the results of the previous query.

Concerning privacy one can distinguish between three scenarios:

1. Weak context-hiding: are those where given signatures σ₁, …, σₙ and a signature σ’ derived from the former, the latter only reveals information from the associated message m’, but does not leak any detail about the messages m₁, …, mₙ associated to σ₁, …, σₙ.
2. Strong context-hiding: are those where a user cannot distinguish if a signature σ’ was generated from signatures σ₁, …, σₙ or directly from a message m’. This level requires the infeasibility to link σ’ with σ₁, …, σₙ even if they are public.
3. Complete context-hiding: are those schemes where one requires strong context hiding on the signatures even in the case where the input signatures of function f ∈ F are chosen by an attacker having access to the secret key.

Homomorphic signatures in the single-user scenario

We are in a situation where there is only one key pair managed by a user. In this case one can distinguish between:

1. The space of admissible functions is composed of linear maps.
2. The space of admissible functions is composed of polynomials.
3. All functions are accepted in the space of admissible functions.

Linearly homomorphic signature schemes

In these schemes, one allows the evaluation of linear functions over signed messages. The main differences concerning the general definition are:

1. The space of messages M is the vector space Fₚⁿ for Fₚ is a finite field of prime characteristic p.
2. Messages are vectors m = (a₁, …, aₙ) for aᵢ ∈ Fₚ and i ∈ {1, …, n}.
3. For messages m₁, …, mₙ, the set F of admissible functions is composed of linear combinations over Fₚⁿ:

Homomorphic signatures for polynomial functions

The modifications in this scenario concerning the general definition follow:

1. The message space is a finite field Fₚ of prime characteristic p.
2. The space of signed messages is the ring R = ℤ[x] / P(x) for P a monic irreducible polynomial in ℤ[x] of degree d > 0.
3. The set F of admissible functions is a subspace of Fₚ[x₁, …, xₙ].

Given one signature per message m₁, …, mₙ anyone can compute a signature for

In the above identity we have:

1. l = (C_d)^(n+d) — 1
2. {Yⱼ}ⱼ (0 < j < l + 1) is a set of non-constant monomials x₁ᵉ₁ · … · xₙᵉₙ of degree e₁ + … + eₙ < d + 1
3. The coefficients cⱼ lie in Fₚ.

Fully homomorphic signatures

This is the closest scenario to the general definition. The main differences are:

1. Admissible functions are seen as circuits of the form 𝛾: Mⁿ → M. Therefore the set F of admissible functions is replaced by the set of admissible circuits C.
2. Set no longer outputs a class of admissible circuits as did in the general definition with the space F.

Concerning correctness, the notion remains unchanged and can be defined in terms of commutative diagrams.

Homomorphic signatures in the multi-user scenario

One can divide multi-user homomorphic signatures into two groups, namely:

1. Multi-source schemes.
2. Aggregate schemes.

Multi-source homomorphic signatures

Multi-source schemes are defined over a space of messages M, a space of signed messages S (both equipped with an operation) and a space of admissible functions F. The main changes concerning the general definition are:

1. Set takes as inputs a security parameter 𝜆 and n > 0 which stands for the maximum number of users allowed. The output is n key pairs together with the spaces M, S and F.
2. Sig takes a secret key skᵢ, a message mᵢ, and an index i ∈ {1, …, n} as inputs, specifying the user i signing the message mᵢ with his secret key skᵢ.
3. Vrf takes pk* = (pk₁, …, pkₙ) of public keys, a tag 𝜏 ∈ {0, 1}^𝜆, f ∈ F, m ∈ M and σ ∈ S as inputs. The output is 1 if σ is a valid signature for m, which is the output of f.
4. Eval takes as inputs pk*, a tag 𝜏 ∈ {0, 1}^𝜆, f ∈ F and a string σ* ∈ Sⁿ. It outputs a signature σ’ on the output of f over the signatures σ* ∈ Sⁿ.

The definition of correctness remains unchanged except for the obvious changes. Therefore, the scheme is correct if the following diagram commute:

One may also define multi-source signature schemes supporting linear functions over signed messages. The definitions are similar, compared to the single-user situation (the same happens concerning correctness), and easily adaptable to this new situation if the following is kept in mind:

1. Messages and signatures spaces, M and S, are vector spaces Fₚⁿ for Fₚ a finite field of prime characteristic p and n the maximum number of users.
2. The set of admissible functions is composed of linear combinations:

Aggregate signatures

An aggregate signature scheme allows deriving a single signature from several signatures on different messages and different users. More precisely, let us assume that n users u₁, …, uₙ want to obtain a signature σ as the aggregation of signatures σ₁, …, σₙ. If the user uᵢ has generated each pair (mᵢ, σᵢ) with its key pair (pkᵢ, skᵢ), it is possible to aggregate these n signatures into a single signature σ.

An aggregate signature scheme is a tuple of probabilistic polynomial-time algorithms:

1. Set(𝜆, n) takes as inputs a security parameter 𝜆 and an integer n > 0. The output is n key pairs (pkᵢ, skᵢ) for each user uᵢ, for i ∈ {1, …, n}.
2. Sig(sk, m, i) takes as inputs a secret key sk, a message m ∈ M and an index i ∈ {1, …, n}. The output is a signature σ ∈ S, corresponding to the signature of a message mᵢ signed by the user uᵢ.
3. Vrf(pk*, m, σ) takes as input a string pk* of public keys, a message m ∈ M and a signature σ ∈ S. The output is 1 if σ is a valid signature for m.
4. Aggσ(pk*, m*, σ*) takes as inputs strings of public keys, messages and signatures. It outputs a signature σ_agg which is the aggregation of signatures in σ* which come from users with public keys in pk*.

An aggregate signature scheme is valid if the following conditions hold:

1. For each i ∈ {1, …, n}, if σᵢ is the output of Sig(sk, m, i), then Vrf(pkᵢ, mᵢ, σᵢ) = 1.
2. For each i ∈ {1, …, n} if σᵢ is the output of Sig(sk, m, i), then:

Homomorphic aggregate signatures

A homomorphic aggregate signature (HAS) scheme is a collection of probabilistic polynomial-time algorithms:

1. Set(𝜆, n) takes a security parameter 𝜆 and an integer n > 0. It outputs n key pairs (skᵢ, pkᵢ), one per user, together with a space of messages M, a space of signed messages S, and a space F of admissible functions of form f: Mⁿ → M.
2. Sig(sk, 𝜏, m, i) takes as inputs a secret key sk, a tag 𝜏 ∈ {0, 1}^λ, a message m ∈ M and an index i ∈ {1, …, n}. It outputs a signature σ ∈ S generated with the secret key of user i.
3. Vrf(pk*, 𝜏, m, σ, f) takes a string of public keys pk*, a tag 𝜏 ∈ {0, 1}^λ, a message m ∈ M, a signature σ ∈ S and f ∈ F as inputs. It outputs 1 if σ is a valid signature concerning pk*, and 0 otherwise. The message m is the output of f.
4. Aggₘ(pk*, 𝜏, m*, f) outputs an aggregated message m_agg ∈ M by applying f ∈ F to the messages in m* coming from users with public keys in pk*. Mind the similarities with an Eval algorithm, special for messages.
5. Aggσ(pk*, 𝜏, σ*, f) outputs a signature σ_agg by evaluating the function f on the signatures σ in the string σ* coming from users with public keys in pk*.

As for previous scenarios, a HAS scheme is correct if it makes the following diagram commutative:

One can define linearly HAS schemes by following the steps taken in the non-aggregate scenario. In this situation both M and S are Fₚⁿ and the space F is made of linear combinations of messages mᵢ ∈ M.

Existing proposals

Schemes based on bilinear groups

Among the several proposals based on bilinear groups on finds the proposal by Attrapadun and Libert (Attrapadung and Libert), Attrapadung, Libert and Peters (Attrapadung et al.) and Freeman’s (Freeman). All these proposals a secure under the standard model; Attrapadung et al proposals can cope with weak adversaries, whereas Freeman’s proposal can resist attacks from a strong attacker. Concerning privacy, Attrapadung et al proposals are either strongly or completely context-hiding; Freeman’s proposal is weakly context-hiding.

Schemes based on RSA

One can find several proposals based on RSA, among which we highlight Freeman’s (Freeman) which is secure in the standard model, is weakly context-hiding and can resist attacks from strong adversaries.

Schemes based on lattices

One can find several kinds of schemes based on lattices: we have proposals for polynomial functions, such as Boneh — Freeman (Boneh and Freeman) or Hiromasa — Manabe — Okamoto (Hiromasa et al.) proposals which are secure in the random oracle model and can resist weak adversaries; when it comes to privacy, their level has not been researched yet.

One can also find linearly homomorphic proposals, such as Boneh — Freeman (Boneh and Freeman) or Wang — Wang (Wang et al.), which are proven secure in the random oracle model, they are weakly context-hiding and are secure against weak adversaries.

Lattices have been also used to introduce fully homomorphic schemes; in this category one highlights the proposals from Gorbunov, Vaikuntanathan and Wichs (Gorbunov et al.) and the proposal from Boyen, Freeman, Katz and Waters (Boneh et al.). Both proposals are secure in the standard model; GVW is secure against weak adversaries and is weakly context-hiding. Concerning BFKW, the proposal is strong against strong adversaries but offers no privacy.

Finally, lattices have been used for the definition of HAS schemes. Jing’s (Jing) proposal is secure in the random oracle model, can cope with strong adversaries and is weakly context-hiding.

References

• Attrapadung, Nuttapong, et al. “Computing on Authenticated Data: New Privacy Definitions and Constructions.” Lecture Notes in Computer Science, vol. 7658, 2012, pp. 367–385.
• Attrapadung, Nuttapong, and Benoît Libert. “Homomorphic Network Coding Signatures in the Standard Model.” Lecture Notes in Computer Science, vol. 6571, 2011, pp. 17–34.
• Boneh, Dan, et al. “Signing a Linear Subspace: Signature Schemes for Network Coding.” Lecture Notes in Computer Science, vol. 5443, 2009, pp. 68–87.
• Boneh, Dan, and David Mandell Freeman. “Homomorphic Signatures for Polynomial Functions.” Lecture Notes in Computer Science, vol. 6632, 2011, pp. 149–168.
• Boneh, Dan, and David Mandell Freeman. “Linearly Homomorphic Signatures over Binary Fields and New Tools for Lattice-Based Signatures.” Lecture Notes in Computer Science, vol. 6571, 2011, pp. 1–16.
• Freeman, David Mandell. “Improved Security for Linearly Homomorphic Signatures: A Generic Framework.” Lecture Notes in Computer Science, vol. 7293, 2012, pp. 697–714.
• Gorbunov, Sergey, et al. “Leveled Fully Homomorphic Signatures from Standard Lattices.” STOC ’15: Proceedings of the forty-seventh annual ACM symposium on Theory of Computing, 2015, pp. 469–477.
• Hiromasa, Ryo, et al. “Homomorphic Signatures for Polynomial Functions with Shorter Signatures.” The 30th Symposium on Cryptography and Information Security, 2013.
• Jing, Zhengjun. “An Efficient Homomorphic Aggregate Signature Scheme Based on Lattice.” Mathematical Problems in Engineering, vol. 2014, 2014.
• Wang, Feng He, et al. “Lattice-based linearly homomorphic signature scheme over binary field.” Sci. China Inf. Sci., vol. 56, 2013, pp. 1–9.