# [Cryptography] of possible interest to those in the Boston area

R. Hirschfeld ray at unipay.nl
Mon Dec 1 13:40:35 EST 2014

------- Start of forwarded message -------
Date: Mon, 1 Dec 2014 07:08:34 -0800 (PST)
From: Nir Bitansky <nbitansky at gmail.com>
Subject: [charles-river-crypto-day] Reminder: Charles River Crypto Day, Dec 5 @ BU

<https://bostoncryptoday.wordpress.com/> on Friday, December 5 at Boston
University.

Location: 111 Cummington Mall <https://goo.gl/maps/Y5Quk> Room 180.
[directions] <http://www.bu.edu/hic/directions/>

Parking: Thereâ€™s a pay lot <http://www.bu.edu/maps/?id=2307> across the
street and 4-hour meters on Bay State Road.

The schedule and abstracts can be found below.
Hope to see you there!

Yael, Vinod, Daniel, and Nir

p.s.: if someone forwarded to you this email, and you would like to join
the mailing list for future announcements send an email to
Schedule9:30 â€“ 10:00.Introduction/Coffee10:00 â€“ 11:00.
Yuval Ishai, Technion
*Circuits Resilient to Additive Attacks, with Applications to Secure
Computation*
11:30 â€“ 12:30.Omer Paneth, Boston University
*Publicly-Verifiable Non-Interactive Arguments for Delegating Computations*12:30
â€“ 2:00.Lunch (provided)2:00 â€“ 3:00.Elaine Shi, University of Maryland
*Programs to Circuits: Towards a Programming Language for Cryptography*3:30
â€“ 4:30.Sergey Gorbunov, MIT
*Leveled Fully Homomorphic Signatures from Standard Lattices*

Thanks: NSF Frontier Grant: Modular Approach to Cloud Security (MACS),
Hariri Institute for Computing and Center for RISCS.

Special thanks to Leo Reyzin, Debbie Lehto, and Lauren Dupee for help with
organization
Abstracts:

*Speaker: Yuval Ishai *
*Title: Circuits Resilient to Additive Attacks, with Applications to Secure
Computation*

We study the question of protecting arithmetic circuits against additive
attacks that can add an arbitrary fixed value to each wire in the circuit.
We show how to transform an arithmetic circuit C into a functionally
equivalent, randomized circuit Câ€™ of comparable size, such that the effect
of any additive attack on the wires of Câ€™ can be simulated (up to a small
statistical distance) by an additive attack on just the inputs and outputs
of C.

Our study of this question is motivated by the goal of simplifying and
improving protocols for secure multiparty computation (MPC). It is
typically the case that securing MPC protocols against active adversaries
is much more difficult than securing them against passive adversaries. We
observe that in simple MPC protocols that were designed to protect circuit
evaluation only against passive adversaries, the effect of any active
wires. Thus, to securely evaluate a circuit C in the presence of active
adversaries, it suffices to apply the passive-case protocol to a
corresponding circuit Câ€™ which is secure against additive attacks. We use
this methodology to simplify feasibility results and obtain efficiency
improvements in several standard MPC models.

Joint work with Daniel Genkin, Manoj Prabhakaran, Amit Sahai, and Eran
Tromer.

*Speaker: Omer Paneth *
*Title: Publicly-Verifiable Non-Interactive Arguments for Delegating
Computations*

We construct publicly verifiable non-interactive arguments that can be used
to delegate polynomial time computations. These computationally sound proof
systems are completely non-interactive in the common reference string
model. The verifierâ€™s running time is nearly-linear in the input length,
and poly-logarithmic in the complexity of the delegated computation. Our
protocol is based on graded encoding schemes, introduced by Garg, Gentry
and Halevi (Eurocrypt 2012). Security is proved under a falsifiable and
publicly verifiable non-interactive argument systems were based on
non-falsifiable knowledge assumptions. Our new result builds on the
beautiful recent work of Kalai, Raz and Rothblum (STOC 2014), who
constructed privately verifiable 2-message arguments. While building on
their techniques, our protocols avoid no-signaling PCPs, and we obtain a
simplified and modular analysis.

As a second contribution, we also construct a publicly verifiable
non-interactive argument for (logspace-uniform) computations of bounded
depth. The verifierâ€™s complexity grows with the depth of the circuit. This
second protocol is adaptively sound, and its security is based on a
encodings (a milder cryptographic assumption). This result builds on the
interactive proof of Goldwasser, Kalai and Rothblum (STOC 2008), using
graded encodings to construct a non-interactive version of their protocol.

Joint work with Guy Rothblum.

*Speaker: Elaine Shi*
*Title: Programs to Circuits: Towards a Programming Language for
Cryptography*

Modern cryptography (e.g., secure multi-party computation,
fully-homomorphic encryption, program obfuscation) commonly models
computation as â€œcircuitsâ€. To make modern cryptography work for real-world
programs, it is necessary to compile â€œprogramsâ€ into compact â€œcircuitsâ€.
The key difficulty is that programs make dynamic memory accesses, whereas
circuits have static wiring. To address this challenge, we need efficient
Oblivious RAM and oblivious algorithms.

In this talk, I will first describe Circuit ORAM, a new ORAM scheme that
yields very small circuit size. Circuit ORAM shows the tightness of certain
stronger interpretations of the well-known Goldreich-Ostrovsky lower bound.

Next, I will describe ObliVM, a programming framework that compiles
real-life programs into compact circuits, while offering formal security
guarantees.

*Speaker: Sergey Gorbunov*

*Title: Leveled Fully Homomorphic Signatures from Standard Lattices*

In a homomorphic signature scheme, a user Alice signs some large dataset *x* using
her secret signing key and uploads the signed data to an untrusted remote
server. The server can then run some computation y=f(x) over the signed
data and homomorphically derive a short signature \sigma_{f,y} certifying
that y is the correct output of the computation f. Anybody can verify the
tuple (f, y, \sigma_{f,y}) using Aliceâ€™s public verification key and become
convinced of this fact without having to retrieve the entire underlying
data.

In this work, we construct the first (leveled) fully homomorphic signature
schemes that can evaluate arbitrary circuits over signed data. Only the
maximal depth d of the circuits needs to be fixed a-priori at setup, and
the size of the evaluated signature grows polynomially in d, but is
otherwise independent of the circuit size or the data size. Our solution is
based on the (sub-exponential) hardness of the small integer solution (SIS)
problem in standard lattices. In the standard model, we get a scheme with
large public parameters whose size exceeds the total size of a dataset. In
the random-oracle model, we get a scheme with short public parameters. In
both cases, the schemes can be used to sign many different datasets. The
complexity of verifying a signature for a computation f is at least as
large as that of computing f, but can be amortized when verifying the same
computation over many different datasets. Furthermore, the signatures can
be made context-hiding so as not to reveal anything about the data beyond
the outcome of the computation.

These results offer a significant improvement in capabilities and
assumptions over the best prior homomorphic signature schemes, which were
limited to evaluating polynomials of constant degree.

As a building block of independent interest, we introduce and construct a
new object called homomorphic trapdoor functions (HTDF) which conceptually
unites homomorphic encryption and signatures.

Joint work with Vinod Vaikuntanathan (MIT) and Daniel Wichs (Northeastern).

--
You received this message because you are subscribed to the Google Groups "Charles River Crypto Day" group.
To unsubscribe from this group and stop receiving emails from it, send an email to charles-river-crypto-day+unsubscribe at googlegroups.com.