Efficient detection for malicious and random errors in additive encrypted computation

Nektarios Georgios Tsoutsos, Michail Maniatakos

Research output: Contribution to journalArticlepeer-review


Although data confidentiality is the primary security objective in additive encrypted computation applications, such as the aggregation of encrypted votes in electronic elections, ensuring the trustworthiness of data is equally important. And yet, integrity protections are generally orthogonal to additive homomorphic encryption, which enables efficient encrypted computation, due to the inherent malleability of homomorphic ciphertexts. Since additive homomorphic schemes are founded on modular arithmetic, our framework extends residue numbering to support fast modular reductions and homomorphic syndromes for detecting random errors inside homomorphic ALUs and data memories. In addition, our methodology detects malicious modifications of memory data, using keyed syndromes and block cipher-based integrity trees, which allow preserving the homomorphism of ALU operations, while enforcing non-malleability of memory data. Compared to traditional memory integrity protections, our tree-based syndrome generation and updating is parallelizable for increased efficiency, while requiring a small Trusted Computing Base for secret key storage and block cipher operations. Our evaluation shows more than 99.999 percent detection rate for random ALUs errors, as well as 100 percent detection rate of single bit-flips and clustered multiple bit upsets, for a runtime overhead between 1.2 and 5.5 percent, and a small area penalty.

Original languageEnglish (US)
Pages (from-to)16-31
Number of pages16
JournalIEEE Transactions on Computers
Issue number1
StatePublished - Jan 2018


  • Encrypted computation
  • Homomorphic encryption
  • Memory integrity
  • Mersenne primes
  • Residue numbering

ASJC Scopus subject areas

  • Software
  • Theoretical Computer Science
  • Hardware and Architecture
  • Computational Theory and Mathematics


Dive into the research topics of 'Efficient detection for malicious and random errors in additive encrypted computation'. Together they form a unique fingerprint.

Cite this