[Busec] BUsec this week: Daniele Micciancio (Thurs 11AM), Sharon Goldberg (Tues 11AM)
goldbe at cs.bu.edu
Mon Apr 2 09:52:40 EDT 2012
This week, we have Daniele Micciancio visiting from UCSD to give a
talk on lattices. Thursday 11AM in MCS148, 111 Cummington Street.
Also, on Tuesday, I'll be giving a talk on my new paper with Zhenming
Liu, Tuesday 11AM in MCS137.
Lunch will be provided on both days, and the talks are open to the public.
See you then!
Trapdoors for Lattices: Simpler, Tighter, Faster, Smaller
Speaker: Daniele Micciancio (UCSD)
Thursday 11AM, MCS148
Cryptographic constructions based on the hardness of solving
computational problems on point lattices are among the most prominent
alternatives to traditional cryptography based on integer
factorization and related problems from number theory. A fundamental
operation in most lattice based cryptographic constructions is the
generation of a hard random lattice, together with some trapdoor
information (typically a good lattice basis) for the efficient
solution of the associated hard lattice problems. In this talk we give
new methods for generating and using strong trapdoors in cryptographic
lattices, which are simultaneously simple, efficient, easy to
implement (even in parallel), and asymptotically optimal with very
small hidden constants. Our methods involve a new kind of trapdoor,
and include specialized algorithms for solving the most important
operations employed in the construction of cryptographic functions.
These tasks were previously the main bottleneck for a wide range of
cryptographic schemes, and our techniques substantially improve upon
the prior ones, both in terms of practical performance and quality of
the produced outputs.
(Joint work with Chris Peikert. To appear in Eurocrypt 2012.)
- Bio sketch: Daniele Micciancio got his PhD from MIT in 1998, and
joined the UCSD CSE faculty in 1999. He is the recipient of several
awards, including an NSF CAREER award, Sloan Fellowship and Hellman
Fellowship. He is most known for his research on the complexity of
lattice problems, which spans the whole spectrum from computational
complexity and algorithms, to cryptography. His most notable
achievements include the first significant inapproximability result
for the Shortest Vector Problem, pioneering the use of cyclic and
ideal lattices in cryptographic constructions based on worst-case
complexity assumptions, and the discovery of the asymptotically
fastest known algorithms to solve all the most important
computational problems on point lattices.
The Diffusion of Networking Technologies
Sharon Goldberg. BU.
Tuesday 11AM, MCS137
In the rich and growing literature on diffusion and cascade effects in
social networks, it is assumed that a node's actions are influenced
only by its immediate neighbors in the social network. However, there
are other contexts in which this highly-local view of influence is not
applicable. The diffusion of technologies in communication networks is
one important example; here, a node's actions should also be
influenced by remote nodes that it can communicate with using the new
technology. We propose a new model of technology diffusion inspired
by the networking literature on this topic, and consider an
algorithmic problem that is well understood in the context of social
networks, but thus far has only heuristic solutions in the context of
communication networks: determining the smallest seedset of early
adopter nodes, that once activated, cause a cascade that eventually
causes all other nodes in the network to activate as well. Our main
result is an approximation algorithm that returns a seedset that is an
$O(r\ell \log|V|)$-factor larger than then the optimal seedset, where
$r$ is the graph diameter and each node's threshold can take on one of
at most $\ell$ possible values. Our results highlight the substantial
algorithmic difference between our problem and the work in diffusion
on social networks.
Joint work with Zhenming Liu.
More information about the Busec