Concept
Computational hardness assumption
Related publications (53)
Extractable Witness Encryption for the Homogeneous Linear Equations Problem
Serge Vaudenay, Bénédikt Minh Dang Tran
Witness encryption is a cryptographic primitive which encrypts a message under an instance of an NP language and decrypts the ciphertext using a witness associated with that instance. In the current state of the art, most of the witness encryption construc ...
Springer2023Public-Key Encryption with Quantum Keys
In the framework of Impagliazzo's five worlds, a distinction is often made between two worlds, one where public-key encryption exists (Cryptomania), and one in which only one-way functions exist (MiniCrypt). However, the boundaries between these worlds can ...
Cham2023Enforcing Privacy in Distributed Learning With Performance Guarantees
Ali H. Sayed, Stefan Vlaski, Elsa Rizk
We study the privatization of distributed learning and optimization strategies. We focus on differential privacy schemes and study their effect on performance. We show that the popular additive random perturbation scheme degrades performance because it is ...
Piscataway2023The double exponential runtime is tight for 2-stage stochastic ILPs
Kim-Manuel Klein, Klaus Jansen, Alexandra Anna Lassota
We consider fundamental algorithmic number theoretic problems and their relation to a class of block structured Integer Linear Programs (ILPs) called 2-stage stochastic. A 2-stage stochastic ILP is an integer program of the form min{c(T)x vertical bar Ax = ...
SPRINGER HEIDELBERG2022Multiquadratic Rings and Walsh-Hadamard Transforms for Oblivious Linear Function Evaluation
The Ring Learning with Errors (RLWE) problem has become one of the most widely used cryptographic assumptions for the construction of modern cryptographic primitives. Most of these solutions make use of power-of-two cyclotomic rings mainly due to its simpl ...
IEEE2020