Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

All reports by Author Vadim Lyubashevsky:

TR05-142 | 1st December 2005
Vadim Lyubashevsky, Daniele Micciancio

Generalized Compact Knapsacks are Collision Resistant

The generalized knapsack problem is the following: given $m$ random
elements $a_1,\ldots,a_m\in R$ for some ring $R$, and a target $t\in
R$, find elements $z_1,\ldots,z_m\in D$ such that $\sum{a_iz_i}=t$
where $D$ is some given subset of $R$. In (Micciancio, FOCS 2002),
it was proved that for appropriate choices of $R$ ... more >>>

TR05-007 | 15th December 2004
Vadim Lyubashevsky

On Random High Density Subset Sums

In the Subset Sum problem, we are given n integers a_1,...,a_n
and a target number t, and are asked to find the subset of the
a_i's such that the sum is t. A version of the subset sum
problem is the Random Modular Subset Sum problem. In this version,
the ... more >>>

ISSN 1433-8092 | Imprint