Hash proof system

A hash proof system for a language is a family of keyed functions with a public projection that determines on , so that for is computable from and a witness for , while for the value is statistically close to uniform given and ; the language comes from a subset membership problem in which elements of and of are computationally indistinguishable — CS02.

Syntax

A subset membership problem has, for each , an instance distribution over instances , each describing finite nonempty sets and a witness relation with , and efficient algorithms:

  • an instance sampler whose output is within statistical distance of ,
  • a subset sampler that, for every in the support of , outputs with within statistical distance of uniform on ,
  • an algorithm that decides, given and a bit string, whether the string encodes an element of .

The instance error and the subset error are negligible — CS02.

A hash proof system for associates to each a projective hash family : a key space , a projection space , a finite group with , functions for and a projection , with efficient algorithms:

  • , sampling uniformly from ,
  • , computing ,
  • , computing for ,
  • , computing for and .

Properties

Correctness

The family is projective: for all and .

Hardness of the subset membership problem

\begin{algorithm}
\algname{Game}
\caption{$\Game^{\mathrm{smp}}_{\calM,\calA}(\secpar)$}
\begin{algorithmic}
\State $\Lambda \gets \mathsf{I}(1^\secpar)$; $b \getsr \bits$
\State $x_0 \getsr L$; $x_1 \getsr X \setminus L$
\State $b' \gets \calA(\Lambda, x_b)$
\Return $[b' = b]$
\end{algorithmic}
\end{algorithm}

A subset membership problem is hard if for all efficient ,

is negligible — CS02.

Ideal families and approximation

The statistical properties below are stated for a projective hash family on the same sets, an ideal family whose keys need not be efficiently sampleable. For a projective hash family , let be the distribution of the pair , a function together with a projection, for . is a -approximation of if and are at statistical distance at most .

A hash proof system for is -smooth, -universal or -universal-2 if there are a negligible function , its key approximation error, and for every in the support of an ideal family with the property of that name below such that is a -approximation of — CS02, Definition 7. With the property holds for itself.

For smoothness, a -approximation of an -smooth family is itself -smooth — standard. For the pointwise bounds of universality and universal-2 this fails: enlarge the key space of an ideal -universal family by one key whose projection no other key has. Uniform keys then give a -approximation, yet given the value is determined, so the enlarged family is not -universal for any — standard.

Smoothness

A projective hash family is -smooth if the distributions

are at statistical distance at most — CS02. As an object, a hash proof system denotes an -smooth hash proof system for a hard subset membership problem, with negligible.

Universality

A projective hash family is -universal if for all , and ,

whenever has nonzero probability: for every , has min-entropy at least given — CS02. A universal hash proof system is an -universal hash proof system for a hard subset membership problem, with negligible. A -universal ideal family is -smooth, since is then uniform in given for every — standard.

Universal-2 hash proof systems

An extended hash proof system takes a tag from a finite set as a second input, , with approximation defined as above for the functions on . A projective hash family of this form is -universal-2 if for all , all and with and , and all ,

whenever the conditioning event has nonzero probability. A universal-2 hash proof system for is a pair of a smooth hash proof system with values in and an extended -universal-2 hash proof system with tag set and values in some , for the same hard subset membership problem, with negligible; this pair is the input to the IND-CCA2 construction of CS02.

Variations

Smooth projective hashing for languages of ciphertexts

TODO: the smooth projective hashing notion of GL03, stated from the paper.

Other results

Participates in

Builds on Hash proof system

Produces Hash proof system