Chris Peikert, Alon Rosen

The generalized knapsack function is defined as $f_{\a}(\x) = \sum_i

a_i \cdot x_i$, where $\a = (a_1, \ldots, a_m)$ consists of $m$

elements from some ring $R$, and $\x = (x_1, \ldots, x_m)$ consists

of $m$ coefficients from a specified subset $S \subseteq R$.

Micciancio ...
more >>>

Iftach Haitner, Mohammad Mahmoody, David Xiao

We investigate the question of what languages can be decided efficiently with the help of a recursive collision-finding oracle. Such an oracle can be used to break collision-resistant hash functions or, more generally, statistically hiding commitments. The oracle we consider, $Sam_d$ where $d$ is the recursion depth, is based on ... more >>>

Marshall Ball, Elette Boyle, Akshay Degwekar, Apoorvaa Deshpande, Alon Rosen, Vinod Vaikuntanathan, Prashant Vasudevan

Reductions between problems, the mainstay of theoretical computer science, efficiently map an instance of one problem to an instance of another in such a way that solving the latter allows solving the former. The subject of this work is ``lossy'' reductions, where the reduction loses some information about the input ... more >>>