2:30-3:30 pm

Room 3305, CUNY Graduate Center

365 Fifth Avenue at 34th Street

**September 12, Graduate Center**: Kurt Rohloff (New Jersey Institute
of Technology), *Towards Practical Implementations of Fully Homomorphic Encryption*

**Abstract: ** One of the first major breakthroughs of computer science in the 21st century is the
demonstration of public-key Fully Homomorphic Encryption (FHE). Unfortunately, FHE was not practical when it
was discovered - it was several orders of magnitude too inefficient to be economically feasible. In this talk
we will discuss how we have been accelerating the development of practical implementations of Fully
Homomorphic Encryption (FHE). For the past three years, our team has succeeded in accelerating various aspects
of the FHE implementation resulting in implementations of FHE schemes that have achieved multiple orders of
magnitude improvement in computation. Further means of parallel software and hardware acceleration, such as
for multicore and FPGA hardware, can improve the speed of computation even further by several additional
orders of magnitude. This talk will review our advances in FHE, from theory, implementation and application
perspectives. We discuss our design and implementations of cryptographic primitives and that can make
efficient use of multi/many-core and parallel computing capabilities in both software and hardware. We also
discuss ours plan to continue this research that will enable practical secure out-sourced computation for
specific application domains, such as to support homomorphic encryption in resource-limited environments such
as on smartphones.

**October 10, Graduate Center**: Bren Cavallo (CUNY Graduate Center),
* Decoy-Based Secure Delegation of Computation, With Application to RSA. *

**Abstract: ** In this talk, I will introduce a method of secure delegation of computation where the
security is not based on any computational assumptions, but rather on numerous "decoys". As an application,
this method can be used by a computationally weak party to delegate the exponentiation that takes place in the
RSA protocol. This is joint work with Delaram Kahrobaei and Vladimir Shpilrain.

**October 17, Graduate Center**: Artem Shevlyakov (Omsk University),
*Semigroups with inversion: equations and algebraic sets*

**Abstract: ** I consider equations over inverse, completely simple and completely regular
semigroups. The disjunction of two solution sets of an equation is not necessarily equal to a solution set of
an appropriate system of equations. We describe the semigroups from the classes above, where ANY disjunction
of the solution sets is algebraic (i.e., is a solution set of some system of equations).

**October 24, Graduate Center**: Andrey Nikolaev (Stevens Institute of
Technology), * Knapsack problems in products of groups *

**Abstract: ** The classic knapsack and related problems have natural generalizations to arbitrary
(non-commutative) groups, collectively called knapsack-type problems in groups. We study the effect of free
and direct products on their time complexity. We show that free products in certain sense preserve time
complexity of knapsack-type problems, while direct products may amplify it. This is joint work with Elizaveta
Frenkel and Alexander Ushakov.

**October 31, Graduate Center**: Prasad Rao (Hewlett Packard),
* Multicore tree hashing with functional programming *

**Abstract: ** We report on our progress in implementing general-purpose tree-hashing on multicore
computing devices: We implemented several tree-hashing modes (i.e. tree shapes), using the Sakura encoding1
and writing the implementation in the functional languages Clojure and Haskell, using the languages'
mechanisms for specifying parallel computation. We argue that functional languages are appropriate mechanisms
for implementing algorithms across multiple cores. We have designed a tree-hash description language, enabling
the concise description of a large class of useful tree shapes.

As one part of the general process of establishing a new standard for cryptographic hashing, NIST plans
to standardize methods for tree hashing, generalizing the Merkle hash tree to a broader class of sound tree
shapes. They plan to make use of the same authors' Sakura encoding to unambiguously describe these shapes. The
choice of shape itself was left outside the scope of Sakura, and must be communicated separately between users
and verifiers of a tree hashing mode. In order to do this flexibly and concisely we have designed a tree-hash
description language, which can specify a superset of the classes of modes illustrated in the Sakura
document.

For parallel programming, protecting data structures from stray updates or accesses is hard. In order to
do so, traditional imperative programming languages use exclusion mechanisms such as locks; however, using
these mechanisms is difficult to understand and therefore error-prone. Immutable data structures eliminate
these errors, although at a performance cost (which we plan to quantify in this work). Functional programming
languages such as Clojure and Haskell and their libraries use immutable data structures natively.
Additionally, they have parallel-programming constructs, which enable us to operate at a higher level of
abstraction. The simplicity of the implementation and the immutability of the data structures considerably
simplify reasoning about their correctness.

We implemented our tree-hash description language using two different functional programming languages,
namely Clojure, which is untyped, and Haskell, which is strongly typed. In each of these languages we
implemented tree hashing, parametrized over a standard hash function (e.g. SHA-256 and Keccak). Our
preliminary performance measurements have revealed some promising scale-up with respect to the number of cores
in use.

Joint work with Stuart Haber.

**November 14, Graduate Center:** Sven Dietrich (John Jay College),
* TBA *

**December 5, Graduate Center**: Manhattan Algebra Day

To subscribe to the seminar mailing list, click here