Difference between revisions of "Open Problems:53"

From Open Problems in Sublinear Algorithms
Jump to: navigation, search
(Created page with "{{Header |title=Homomorphic hash functions |source=dortmund12 |who=Ely Porat }} '''Question''': to construct a hash function $ h:\F_p^n \to \F_p^m $, where $m<n$, satisfying ...")
 
m (updated header)
 
(One intermediate revision by the same user not shown)
Line 1: Line 1:
 
{{Header
 
{{Header
|title=Homomorphic hash functions
 
 
|source=dortmund12
 
|source=dortmund12
 
|who=Ely Porat
 
|who=Ely Porat
 
}}
 
}}
'''Question''': to construct a hash function  
+
'''Question:''' Construct a hash function  
 
$
 
$
 
h:\F_p^n \to \F_p^m
 
h:\F_p^n \to \F_p^m
Line 11: Line 10:
 
* for any $u,v$, we have $\Pr_h[h(u)=h(v)]=\frac{c}{p^m}$ for some constant $c$ independent of $n,m$.
 
* for any $u,v$, we have $\Pr_h[h(u)=h(v)]=\frac{c}{p^m}$ for some constant $c$ independent of $n,m$.
  
One solution is by considering a random linear function, given by the matrix $M$. Then we have that $\Pr_M[Mu=Mv]=\Pr_M[M(u-v)=0]=1/p^m$. This function would require $O(nm\log p)$ random bits, and computing $h$ takes $O(nm)$ time. We would like more efficient solutions.
+
One solution is by considering a random linear function, given by the matrix $M$. Then we have that $\Pr_M[Mu=Mv]=\Pr_M[M(u-v)=0]=1/p^m$. This function would require $O(nm\log p)$ random bits, and computing $h$ takes $O(nm)$ time. We would like more efficient solutions. Ely and coauthors claim a solution with $O((n+m)\log p)$ bits, and $O((n+m)\log (n+m))$ time. If one considers Reed-Salomon codes, it seems that they would give worse bound on second property (probability of collision).
 
 
Ely and coauthors claim a solution with $O((n+m)\log p)$ bits, and $O((n+m)\log (n+m))$ time.
 
 
 
If one considers Reed-Salomon codes, it seems that they would give worse bound on second property (probability of collision).
 

Latest revision as of 01:59, 7 March 2013

Suggested by Ely Porat
Source Dortmund 2012
Short link https://sublinear.info/53

Question: Construct a hash function $ h:\F_p^n \to \F_p^m $, where $m<n$, satisfying the following properties:

  • h is linear: $h(u+v)=h(u)+h(v)$ for all $u,v\in \F_p^n$;
  • for any $u,v$, we have $\Pr_h[h(u)=h(v)]=\frac{c}{p^m}$ for some constant $c$ independent of $n,m$.

One solution is by considering a random linear function, given by the matrix $M$. Then we have that $\Pr_M[Mu=Mv]=\Pr_M[M(u-v)=0]=1/p^m$. This function would require $O(nm\log p)$ random bits, and computing $h$ takes $O(nm)$ time. We would like more efficient solutions. Ely and coauthors claim a solution with $O((n+m)\log p)$ bits, and $O((n+m)\log (n+m))$ time. If one considers Reed-Salomon codes, it seems that they would give worse bound on second property (probability of collision).