Open Problems:53 - Revision history

Krzysztof Onak: updated header

2013-03-07T01:59:53Z

updated header

2012-12-12T04:43:50Z

@@ Line 1: / Line 1: @@
 {{Header
 |source=dortmund12
 |who=Ely Porat

@@ Line 1: / Line 1: @@
 {{Header
-|title=Homomorphic hash functions
+|title=Homomorphic Hash Functions
 |source=dortmund12
 |who=Ely Porat
 }}
-'''Question''': to construct a hash function
+'''Question:''' Construct a hash function
+$
 h:\F_p^n \to \F_p^m
@@ Line 11: / Line 11: @@
 * 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).