Subset sum at constant density above one ⇒ UOWHF

Standard model · IN96

Statement

Let with for a constant , so that the density is . If subset sum is hard at constant density above one for this , then the family from to , keyed by uniform , is target collision resistant — IN96. One evaluation compresses bits to bits using only additions — IN96.

Notes

  • The density gap must be a constant. The reduction programs the target and the key, and the distance of their distribution from uniform is bounded by , which is the constant at — IN96.
  • A collision gives with , a nonzero ternary kernel vector of the one-row matrix , and conversely, so collision resistance of the family is hardness of finding such a vector — standard.