Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

Lecture notes in computer science

Key-Homomorphic Computations for RAM: Fully Succinct Randomised Encodings and More

Damiano Abram, Giulio Malavolta, Lawrence Roy

Published Jan 1, 2025• 10 citations
Publisher
DOI
10.1007/978-3-032-01881-6_8

Related papers

Multi-key Fully-Homomorphic Encryption in the Plain Model

Prabhanjan Ananth, Abhishek Jain, Zhengzhong Jin +1 more

Lecture notes in computer science•Jan 1, 2020•46 citations

Additive Randomized Encodings and Their Applications

Shai Halevi, Yuval Ishai, Eyal Kushilevitz +1 more

Lecture notes in computer science•Jan 1, 2023•8 citations

Doubly Efficient Private Information Retrieval and Fully Homomorphic Ram Computation from Ring LWE

Wei-Kai Lin, Ethan Mook, Daniel Wichs

SIAM Journal on Computing•Mar 5, 2026•1 citation

Cloud-Assisted Multiparty Computation from Fully Homomorphic Encryption

Adriana López-Alt, Eran Tromer, Vinod Vaikuntanathan

We construct protocols for secure multiparty computation with the help of a computationally powerful party, namely the “cloud”. Our protocols are simultaneously ecient in a number of metrics: • Rounds: our protocols run in 4 rounds in the semi-honest setting, and 5 rounds in the malicious setting. • Communication: the number of bits exchanged in an execution of the protocol is independent of the complexity of function f being computed, and depends only on the length of the inputs and outputs. • Computation: the computational complexity of all parties is independent of the complexity of the function f, whereas that of the cloud is linear in the size of the circuit computing f. In the semi-honest case, our protocol relies on the “ring learning with errors” (RLWE) assumption, whereas in the malicious case, security is shown under the Ring LWE assumption as well as the existence of simulation-extractable NIZK proof systems and succinct non-interactive arguments. In the malicious setting, we also relax the communication and computation requirements above, and only require that they be “small” ‐ polylogarithmic in the computation size and linear in the size of the joint size of the inputs. Our constructions leverage the key homomorphic property of the recent fully homomorphic encryption scheme of Brakerski and Vaikuntanathan (CRYPTO 2011, FOCS 2011). Namely, these schemes allow combining encryptions of messages under dierent keys to produce an encryption (of the sum of the messages) under the sum of the keys. We also design an ecient, non-interactive threshold decryption protocol for these fully homomorphic encryption schemes.

•Jan 1, 2011•22 citations

Non-Interactive Cryptography in the RAM Model of Computation.

Daniel Apon, Xiong Fan, Jonathan I. Katz +3 more

•Jan 1, 2014•3 citations

Succinct Functional Encryption and Applications: Reusable Garbled Circuits and Beyond.

Shafi Goldwasser, Yael Tauman Kalai, Raluca Ada Popa +2 more

Functional encryption is a powerful primitive: given an encryption Enc(x) of a value x and a secret key skf corresponding to a circuit f, it enables efficient computation of f(x) without revealing any additional information about x. Constructing functional encryption schemes with succinct ciphertexts that guarantee security for even a single secret key (for a general function f) is an important open problem with far reaching applications, which this paper addresses. Our main result is a functional encryption scheme for any general function f of depth d, with succinct ciphertexts whose size grows with the depth d rather than the size of the circuit for f. We prove the security of our construction based on the intractability of the learning with error (LWE) problem. More generally, we show how to construct a functional encryption scheme from any public-index predicate encryption scheme and fully homomorphic encryption scheme. Previously, the only known constructions of functional encryption were either for specific inner product predicates, or for a weak form of functional encryption where the ciphertext size grows with the size of the circuit for f. We demonstrate the power of this result, by using it to construct a reusable circuit garbling scheme with

•Jan 1, 2012•36 citations
We construct protocols for secure multiparty computation with the help of a computationally powerful party, namely the “cloud”. Our protocols are simultaneously ecient in a number of metrics: • Rounds: our protocols run in 4 rounds in the semi-honest setting, and 5 rounds in the malicious setting. • Communication: the number of bits exchanged in an execution of the protocol is independent of the complexity of function f being computed, and depends only on the length of the inputs and outputs. • Computation: the computational complexity of all parties is independent of the complexity of the function f, whereas that of the cloud is linear in the size of the circuit computing f. In the semi-honest case, our protocol relies on the “ring learning with errors” (RLWE) assumption, whereas in the malicious case, security is shown under the Ring LWE assumption as well as the existence of simulation-extractable NIZK proof systems and succinct non-interactive arguments. In the malicious setting, we also relax the communication and computation requirements above, and only require that they be “small” ‐ polylogarithmic in the computation size and linear in the size of the joint size of the inputs. Our constructions leverage the key homomorphic property of the recent fully homomorphic encryption scheme of Brakerski and Vaikuntanathan (CRYPTO 2011, FOCS 2011). Namely, these schemes allow combining encryptions of messages under dierent keys to produce an encryption (of the sum of the messages) under the sum of the keys. We also design an ecient, non-interactive threshold decryption protocol for these fully homomorphic encryption schemes.
Functional encryption is a powerful primitive: given an encryption Enc(x) of a value x and a secret key skf corresponding to a circuit f, it enables efficient computation of f(x) without revealing any additional information about x. Constructing functional encryption schemes with succinct ciphertexts that guarantee security for even a single secret key (for a general function f) is an important open problem with far reaching applications, which this paper addresses. Our main result is a functional encryption scheme for any general function f of depth d, with succinct ciphertexts whose size grows with the depth d rather than the size of the circuit for f. We prove the security of our construction based on the intractability of the learning with error (LWE) problem. More generally, we show how to construct a functional encryption scheme from any public-index predicate encryption scheme and fully homomorphic encryption scheme. Previously, the only known constructions of functional encryption were either for specific inner product predicates, or for a weak form of functional encryption where the ciphertext size grows with the size of the circuit for f. We demonstrate the power of this result, by using it to construct a reusable circuit garbling scheme with