Memory-bounded randomness for hardware-constrained encrypted computation

Nektarios Georgios Tsoutsos, Oleg Mazonka, Michail Maniatakos

Research output: Chapter in Book/Report/Conference proceedingConference contribution


Encrypted computation enables processing sensitive data directly in the encrypted domain, which allows outsourcing to third parties without compromising privacy. Recent solutions that leverage partial homomorphic encryption, however, require excessive lookup tables or obfuscated software oracles to implement branching over encrypted control values. To address these limitations and make encrypted computations more practical on memory-constrained systems, we present a novel approach for limiting the amount of randomness in probabilistic ciphertexts, using number theory primitives and hash tables. This allows de-randomizing probabilistic ciphertexts and define a new encrypted abstract machine that is memory-friendly to the target system. Compared to obfuscated oracles in previous work, our method performs control flow decisions over ciphertexts twice as fast, while requiring selectively small lookup tables.

Original languageEnglish (US)
Title of host publicationProceedings - 35th IEEE International Conference on Computer Design, ICCD 2017
PublisherInstitute of Electrical and Electronics Engineers Inc.
Number of pages8
ISBN (Electronic)9781538622544
StatePublished - Nov 22 2017
Event35th IEEE International Conference on Computer Design, ICCD 2017 - Boston, United States
Duration: Nov 5 2017Nov 8 2017

Publication series

NameProceedings - 35th IEEE International Conference on Computer Design, ICCD 2017


Other35th IEEE International Conference on Computer Design, ICCD 2017
Country/TerritoryUnited States


  • Abstract machine
  • Bounded randomness
  • Encrypted computation
  • One instruction set computing
  • Paillier encryption

ASJC Scopus subject areas

  • Hardware and Architecture


Dive into the research topics of 'Memory-bounded randomness for hardware-constrained encrypted computation'. Together they form a unique fingerprint.

Cite this