Hash Proof System

Hash proof systems were introduced in [CS02] as a generalisation of the techniques used in [CS98] to design chosen ciphertext secure PKE schemes.

Consider a set of words , an NP language  such that  where  is the relation defining the language,  is the language of true statements in  and for  is a witness for 

The set  defines an instance of a subset membership problem, i.e. the problem of deciding if an element  is in  or in  We denote  an algorithm which on input a parameter  outputs the description  of a subgroup membership problem.

A HPS associates a projective hash family (PHF) to such a subset membership problem. The PHF defines a key generation algorithm PHF.KeyGen which outputs a secret hashing key  sampled from distribution of hashing keys  over a hash key space  and a public projection key  projkg(hk) in projection key space (where projkg :   is an efficient auxiliary function). The secret hashing key  defines a hash function  and hp allows for the (public) evaluation of the hash function on words  i.e. projhash  for  A projective hash family PHF is thus defined by  projkg).

Basic Properties

 -smoothness

The standard smoothness property of a PHF requires that for any  the value hash  be uniformly distributed knowing .

A projective hash family is  -smooth over  on  if for any  a random  and a randomly sampled hashing key  the distributions  projkg  hash  and  projkg  hash  are  -close.

 -hard subset membership problem

For security to hold  must be an instance of a hard subset membership problem, i.e. no polynomial time algorithm can distinguish random elements of  from those of  with significant advantage. Consider a positive integer . We say Gen  is a generator for a  -hard subset membership problem if for any  is the maximal advantage of any polynomial time adversary in distinguishing random elements of  from those of  For conciseness, we often simply say  is a  - hard subset membership problem.

Linearly homomorphic PHF

We require that the projective hash family also be homomorphic as defined in [HO09].

The projective hash family PHF :  projkg) is homomorphic if and  are groups, and for all  and  we have hash  hash  hash , that is to say hash  is a homomorphism for each hk.

This clearly implies that for hp  projkg(hk) the public projective hash function is linearly homomorphic with respect to elements .

Homomorphically extended 

Note that the co-domain of projkg, which specifies the set of valid projection keys, may not be efficiently recognisable. It is essential that even if a public key is chosen maliciously (i.e. there does not exist such that hp  projkg(hk), which may go unnoticed to honest parties in the protocol), the homomorphic properties of the public projective hash function still hold. We thus require that the co-domain of projkg, which defines valid projection keys, be contained in an efficiently recognisable space  such that for all hash  is a homomorphism (respectively to its inputs in .

We say that the projective hash family PHF  projkg) is homomorphically extended if  projkg) is a homomorphic PHF and that there exists an efficiently recognizable space  such that for any  the function projhash  is a homomorphism (respectively to its inputs in  ).

Key homomorphic PHF

Projective hash families are linearly homomorphic w.r.t. the hashing keys.

A projective hash family PHF is key homomorphic if  is a cyclic additive Abelian group,  is a multiplicative finite Abelian group; and  and  it holds that .