Computing Functions Securely: Theory, Implementation and Cryptanalysis

Alexander Davidson

Research output: ThesisDoctoral Thesis

327 Downloads (Pure)


The study of secure computation assesses the ability of one or more entities to securely compute functions over privately chosen inputs. Numerous different methods of computation exist, ranging from protocols for securely computing functions over data from multiple entities; to providing cryptographically obfuscated versions of functions that still evaluate correctly. In the former case, security guarantees that the inputs are not revealed beyond what is revealed naturally by the output of the function. In the latter case, the function itself should remain hidden, even when ran in an adversary-controlled environment.

The vast array of conveyed functionality has led to a wealth of research literature with varying motivations. The theory of secure computation has existed for around three decades, and more recent work has considered the plausibility of developing practical applications based on the underlying concepts of this theory. In particular, demonstrating how efficiently we can run protocols for securely computing general functions. As always, cryptanalysis also remains useful for establishing the actual security guarantees that we can expect for those schemes.

In this thesis we provide a study of the feasibility of various forms of secure computation --- through theory, practice and cryptanalysis. Firstly, we give theoretical constructions of general secure computation protocols for performing set operations whilst maintaining the privacy of the input sets. Secondly, we provide a new construction of a constrained pseudorandom function. In comparison to previous work, we achieve stronger security properties from much weaker assumptions. Thirdly, we establish a browser-based implementation of a protocol for anonymous authentication, built upon the secure computation of a verifiable, oblivious pseudorandom function between a client and server. Lastly, we give a cryptanalysis of indistinguishability obfuscation candidates for branching programs, when instantiated under a non-trivial adaptation of an existing graded encoding scheme.
Original languageEnglish
Awarding Institution
  • Royal Holloway, University of London
  • Cid, Carlos, Supervisor
  • Albrecht, Martin, Advisor
Thesis sponsors
Award date1 Jul 2019
Publication statusUnpublished - 2019


  • Secure computation
  • Cryptographic protocols
  • Cryptography
  • Pseudorandom functions

Cite this