Algebra and Cryptography Seminar, Fall 2014

Organizers: Robert Gilman, Delaram Kahrobaei, Alexei Myasnikov, and Vladimir Shpilrain


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), AdLeaks: Enabling secure whistleblowing using online ads
Abstract: Whistleblower laws protect individuals who inform the public or an authority about governmental or corporate misconduct. Despite these laws, whistleblowers frequently risk reprisals and sites such as WikiLeaks emerged to provide a level of anonymity to these individuals. However, as countries increase their level of network surveillance and Internet protocol data retention, the mere act of using anonymizing software such as Tor, or accessing a whistleblowing website through an SSL channel might be incriminating enough to lead to investigations and repercussions. As an alternative submission system we propose an online advertising network called AdLeaks. AdLeaks leverages the ubiquity of unsolicited online advertising to provide complete sender unobservability when submitting disclosures. AdLeaks ads compute a random function in a browser and submit the outcome to the AdLeaks infrastructure. Such a whistleblower's browser replaces the output with encrypted information so that the transmission is indistinguishable from that of a regular browser. Its back-end design assures that AdLeaks must process only a fraction of the resulting traffic in order to receive disclosures with high probability. We describe the design of AdLeaks and evaluate its performance through analysis and experimentation.
Joint work with Volker Roth et al.

November 21, Graduate Center: Bren Cavallo (CUNY Graduate Center), Algorithmic properties of poly-Z groups and secret sharing using non-commutative groups
Abstract: Computational aspects of polycyclic groups have been used to study cryptography since 2004 when Eick and Kahrobaei proposed polycyclic groups as a platform for conjugacy based cryptographic protocols.
In the talk I describe the conjugacy problem in polycyclic groups and construct a family of torsion-free polycyclic groups where the uniform conjugacy problem over the entire family is at least as hard as the subset sum problem. We further show that the conjugacy problem in these groups is in NP, implying that the uniform conjugacy prpblem is NP-complete over these groups. We also present an algorithm for the conjugacy problem in groups of the form Z_n semidirect Z.
I then talk about the automorphisms of poly-Z groups and successive cyclic extensions of arbitrary groups. I discuss a certain kind of extension that we call “deranged”, and show that the automorphisms of the resulting group have a strict form. We also prove a version of the Tits Alternative for their automorphism groups.
In the final part of the talk I describe secret sharing schemes and variations. We begin with classical secret sharing schemes and present variations that allow them to be more practical. We then present a secret sharing scheme due to Habeeb, Kahrobaei, and Shpilrain. Finally, we present an original adjustment to their scheme that involves the shortlex order on a group and allows less information to be transmitted each time a secret is shared. Additionally, we propose additional steps that allow participants to update their information independently so that the scheme remains secure over multiple rounds.

December 5, Graduate Center: Manhattan Algebra Day


To subscribe to the seminar mailing list, click here

Spring 2014 talks

Fall 2013 talks

Spring 2013 talks

Fall 2012 talks

Spring 2012 talks

Fall 2011 talks

Spring 2011 talks

Fall 2010 talks

Spring 2010 talks

Fall 2009 talks

Spring 2009 talks

Fall 2008 talks

Spring 2008 talks

Fall 2007 talks

Spring 2007 talks

Fall 2006 talks

Spring 2006 talks

Fall 2005 talks