תקצירי
ההרצאות:
|
10:00 |
פרופ' עדי שמיר – מכון ויצמן
למדע, Lightweight Cryptography for
RFID Tags RFID tags are tiny computational devices with no internal source of
power, which are likely to be deployed in a large number of applications in
the next few years. In this talk I will describe several light weight
security algorithms which were designed specifically for such devices, and in
particular a new hash function called SQUASH which is provably at least as
one-way as the Rabin scheme. It can be implemented with a very small number
of gates on RFID tags, and it is extremely fast on larger processors with
arbitrary word sizes. |
|
10:55 |
ד"ר קובי ניסים –
אוניברסיטת בן גוריון, What Can We Learn Privately? Learning problems form an important category of computational tasks
that generalizes many of the computations researchers apply to large
real-life data sets. Applying to the recent notion of differential privacy [Dwork,McSherry,Nissim,Smith], we
ask what concept classes can be learned privately, i.e., by an algorithm
whose output does not depend too heavily on any single training example. Our
goal is to understand the resources required for private learning in terms of
samples, computation time, and interaction. We draw a picture of the classes of
learning problems that are solvable subject to privacy constraints.
Informally, that roughly anything learnable is learnable privately, and in
most cases efficiently. In more detail, we show: A private analogue of Occam's razor:
generic, distribution-free private learning algorithm that uses
approximately log|C| samples to learn
a concept class C; this learner is not always computationally efficient. A computationally efficient, distribution-free private PAC learner for
the class of parity functions. A precise characterization of local (i.e. distributed, aka randomized response), private learning algorithms: we
show that a concept class is learnable by a local algorithm if and only if it
is learnable in A separation between the power of interactive and noninteractive
local learning algorithms (and, because of the equivalence to SQ learning, a
separation between adaptive and nonadaptive SQ
learning. Our results shed some light on the relationship between learning with
noise and private learning. On one hand, the equivalence between local
private learning and SQ learning suggests a similarity between the notions.
On the other hand, the class of parity functions is privately learnable while
it is thought to be hard to learn with random classification noise. Joint work with Shiva Kasiviswanathan, Homin K. Lee, Sofya Raskhodnikova, and Adam
Smith. |
|
|
|
|
12:00 |
ד"ר עמוס ביימל –
אוניברסיטת בן גוריון, Secret Sharing and Matroids Secret-sharing schemes are an important tool used in many
cryptographic protocols. In these schemes, a dealer holding a secret string
distributes shares to the parties such that only pre-defined authorized subsets of participants can reconstruct the secret from their shares. The
collection of pre-defined authorized subsets is called an access structure. In this talk we will discuss ideal secret sharing schemes, that is,
schemes in which the shares are taken from the same domain as the secrets (the domain of shares cannot be smaller). Brickell
and interesting connection between ideal secret sharing schemes and matroids -- a combinatorial structure that generalizes the linear independence.
They give a necessary condition for an access structure to have an ideal
secret sharing scheme -- the access structure must be induced by a matroid. exists an access structure induced by the Vamos
matroid that does not have an ideal scheme. We strengthen the result of access structure induced by the Vamos matroid does not have a scheme that is close to being ideal. Our bounds are obtained by using non-Shannon inequalities for the entropy function. The talk is based on joint works with Carles
Padro and Noam Livne. |
|
|
|
|
14:10 |
פרופ' שפי גולדווסר – מכון ויצמן
למדע, Obfuscation and One-Time
Programs Program obfuscation is the process of taking a program as an input and
modifying it so that the resulting program has the same I/O behavior as the
input program but otherwise looks `completely garbled' to the entity that
runs it, even if this entity is adversarial and has full access to the
program. Impossibility results, origination with the work of Barak etal in 2001, have been
proved that assert that several strong (albeit natural) formulations of
obfuscation are impossible to achieve for general programs. That is, there is
no generic mechanism that can successfully obfuscate large classes of
programs. Yet, even more recent theoretical results have pointed out a way in
which, in spite of these generic impossibility results, the basic concept of
program obfuscation is obtainable in certain settings. One setting on which
we will elaborate is of *one-time programs:* programs that can be executed
only a restricted and pre-specified number of times. Naturally, these
programs cannot be achieved using software alone. We show how to build them
using `simple' and `universal' secure memory components. One-time programs serve many of the same purposes of program
obfuscation, the obvious one being software protection. However, the
applications of one-time programs go well beyond those of obfuscation, since
one-time programs can only be executed once (or more generally, a limited
number of times) while obfuscated programs have no such bounds. For example, one-time
programs lead naturally to temporary delegation of cryptographic ability, electronic
token schemes such as subway tokens, and to ``one-time proofs'': proofs
that can only be verified once and then become useless and unconvincing. We
show how to use a classical witness and simple secure memory to efficiently
construct such ``one-time proofs'' for any NP statement. Joint work with Yael kalai
and Guy Rothblum. |
|
|
|
|
15:05 |
פרופ' אלי ביהם – הטכניון, On the Security of GSM Cellular
Phones In this talk we describe the
ciphers and protocols used for the GSM cellular phone network, and discuss the
(in)security of the system. We describe several techniques to
attack the ciphers A5/2 and A5/1, and how they can be applied as a ciphertext-only attack. We also show that active attacks
on the protocols can recover keys of ciphers that are not used during that
transmission. As a result, it is possible to listen in to GSM phone
conversations, steal calls during the conversation, and even issue new calls
on behalf of (and paid by) an attacked phone. This talk summarizes several
papers on this issue. This is a joint work with Elad
Barkan and Nathan Keller. |
|
|
|