Vineel Nagisetty
Honours Project
Supervisor: Dr. Antonina Kolokolova

Cryptography-based boosting?

Department of Computer Science
Friday, April 5, 2019, 1:00 p.m., Room EN-2022

---

Abstract

Learning and cryptography are two sides of the same coin, with proofs of hardness giving learning algorithms and vice versa; breakthroughs in one often lead to applications in the other. Case in point, the famous AdaBoost algorithm of Freund and Shapire was independently discovered by Impagliazzo in his proof of the Hard-Core Lemma, which was later pointed out by Klivans and Servedio. More recently, Holenstein developed a boosting algorithm with better guarantees in the context of cryptographic key agreement, and Impagliazzo outlined how it can be used for learning and generative adversarial networks (GANs). We implement this boosting algorithm derived from Impagliazzo-Holenstein's theoretical proof and show that it can compare favorably with state-of-the art boosting algorithms using binary classification data sets obtained from UCI machine learning repository.