Paper 2023/1643
Oblivious Turing Machine
Abstract
In the ever-evolving landscape of Information Tech- nologies, private decentralized computing on an honest yet curious server has emerged as a prominent paradigm. While numerous schemes exist to safeguard data during computation, the focus has primarily been on protecting the confidentiality of the data itself, often overlooking the potential information leakage arising from the function evaluated by the server. Recognizing this gap, this article aims to address the issue by presenting and implementing an innovative solution for ensuring the privacy of both the data and the program. We introduce a novel approach that combines the power of Fully Homomorphic Encryption with the concept of the Turing Machine model, resulting in the first fully secure practical, non-interactive oblivious Turing Machine. Our Oblivious Turing Machine construction is based on only three hypotheses, the hardness of the Ring Learning With Error problem, the ability to homomorphically evaluate non-linear functions and the capacity to blindly rotate elements of a data structure. Only based on those three assumptions, we propose an implementation of an Oblivious Turing Machine relying on the TFHE cryptosystem and present some implementation results.
Metadata
- Available format(s)
-
PDF
- Category
- Cryptographic protocols
- Publication info
- Published elsewhere. EDCC24
- Keywords
- Turing machineOblivious computingFully Homomorphic EncryptionTFHEBlind Matrix Access
- Contact author(s)
-
azogagh sofiane @ courrier uqam ca
delfour victor @ courrier uqam ca
killijian marc-olivier 2 @ uqam ca - History
- 2024-10-16: last of 2 revisions
- 2023-10-23: received
- See all versions
- Short URL
- https://ia.cr/2023/1643
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2023/1643,
author = {Sofiane Azogagh and Victor Delfour and Marc-Olivier Killijian},
title = {Oblivious Turing Machine},
howpublished = {Cryptology {ePrint} Archive, Paper 2023/1643},
year = {2023},
url = {https://eprint.iacr.org/2023/1643}
}