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
- Every smooth hash proof system for a hard subset membership problem gives IND-CPA-secure PKE, and every universal-2 hash proof system gives IND-CCA2-secure PKE without random oracles: HPS ⇒ CPA-secure PKE, Universal-2 HPS ⇒ CCA-secure PKE — CS02.
- Universal-2 hash proof systems exist under DDH in prime-order groups with decidable membership, DCR for safe-prime moduli and quadratic residuosity, and the Cramer–Shoup cryptosystem is a special case of the paradigm: DDH ⇒ Universal-2 HPS, DCR (safe-prime moduli) ⇒ Universal-2 HPS — CS02.
- Smooth projective hash functions for languages of ciphertexts of a given message under a given public key give password-based authenticated key exchange in the common reference string model, built from non-malleable commitments, one-time signatures and smooth projective hash functions, abstracting the DDH-based protocol of KOY01 (DDH ⇒ PAKE) and instantiated under DDH, quadratic residuosity and -th residuosity — GL03.
- Every -universal hash proof system with key approximation error for a hard subset membership problem gives leakage-resilient PKE tolerating bits of leakage on the secret key for -bit messages, under no assumption beyond the hardness of the subset membership problem and with the same efficiency (Universal HPS ⇒ LR-PKE); the scheme this construction gives from a new hash proof system based on DDH, or on any of the -Linear assumptions, tolerates leakage of a fraction of its secret key (DDH ⇒ LR-PKE, -Linear ⇒ LR-PKE) — NS09. With the same argument tolerates bits, since for every the probability of predicting from , averaged over , is then at most — standard.
- A modification of smooth projective hashing whose smoothness holds for maliciously chosen hash families gives two-message oblivious transfer, abstracting the DDH-based protocols of NP01 and AIR01, with new instantiations under -th residuosity and under quadratic residuosity together with the extended Riemann hypothesis — HK12.
Participates in
Builds on Hash proof system
- HPS ⇒ CPA-secure PKE
- Universal HPS ⇒ LR-PKE (via Universality)
- Universal-2 HPS ⇒ HPS (via Universal-2 hash proof systems)
- Universal-2 HPS ⇒ CCA-secure PKE (via Universal-2 hash proof systems)
Produces Hash proof system