[Busec] Eric Miles at our first busec meeting - Monday Sept 24 @ 10am

Sharon Goldberg goldbe at cs.bu.edu
Mon Sep 10 11:56:45 EDT 2012

Hi, and welcome back!

Our first BUsec meeting will be at 10am on Monday Sept 24, at room
MCS137 (111 Cummington St, Boston MA).
(We are skipping next Monday and starting the following week.)
Lunch will be provided, as usual.  See you there!


BUsec event calendar is here:
Sign up for our mailing list!  http://cs-mailman.bu.edu/mailman/listinfo/busec

Substitution-permutation networks, pseudorandom functions, and natural proofs
Speaker:  Eric Miles, Northeastern
10AM, MCS137

There currently exists a troubling gap between the construction of
pseudorandom functions (PRF) and those of their popular,
bounded-input-length counterparts including block ciphers and hash
functions. This gap is both quantitative, because these counterparts
are more efficient than PRF in various ways, and methodological,
because these counterparts are often constructed via the
substitution-permutation network paradigm (SPN) which has not been
used to construct PRF. We take a step towards closing this gap by
giving new candidate PRF that are inspired by the SPN paradigm. This
paradigm involves a "substitution function" (S-box). Our main
candidates are

1. An SPN whose S-box is a random function on b bits, given as part of
the seed. We prove unconditionally that this candidate resists attacks
that run in time at most 2^(Omega(b)). Setting b = omega(log n) we
obtain an inefficient PRF, which seems to be the first such
construction using the SPN paradigm.

2. An SPN whose S-box is field inversion, a common choice in practical
constructions. This candidate is computable with Boolean circuits of
size n * polylog(n), and we prove that it has exponential security
against linear and differential cryptanalysis.

3. A candidate using an extreme setting of the SPN parameters (one
round, one S-box), where the S-box is again field inversion. This
candidate is also computable by circuits of size n * polylog(n), and
we prove that it has exponential security against parity tests that
look at 2^(0.9n) outputs.

Assuming the security of our candidates, our work narrows the gap
between the "Natural Proofs barrier" of Razborov and Rudich and
existing lower bounds, in three models: unbounded-depth circuits, TC0
circuits, and Turing machines.

Sharon Goldberg
Computer Science, Boston University

More information about the Busec mailing list