Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

All reports by Author Vinod Vaikuntanathan:

TR18-056 | 20th March 2018
Zvika Brakerski, Vadim Lyubashevsky, Vinod Vaikuntanathan, Daniel Wichs

Worst-Case Hardness for LPN and Cryptographic Hashing via Code Smoothing

We present a worst case decoding problem whose hardness reduces to that of solving the Learning Parity with Noise (LPN) problem, in some parameter regime. Prior to this work, no worst case hardness result was known for LPN (as opposed to syntactically similar problems such as Learning with Errors). The ... more >>>

TR17-076 | 21st April 2017
Tianren Liu, Vinod Vaikuntanathan, Hoeteck Wee

New Protocols for Conditional Disclosure of Secrets (and More)

Revisions: 2

We present new protocols for conditional disclosure of secrets (CDS),
where two parties want to disclose a secret to a third party if and
only if their respective inputs satisfy some predicate.

- For general predicates $\text{pred} : [N] \times [N] \rightarrow \{0,1\}$,
we present two protocols that achieve ... more >>>

TR17-008 | 14th January 2017
Benny Applebaum, Naama Haramaty, Yuval Ishai, Eyal Kushilevitz, Vinod Vaikuntanathan

Low-Complexity Cryptographic Hash Functions

Cryptographic hash functions are efficiently computable functions that shrink a long input into a shorter output while achieving some of the useful security properties of a random function. The most common type of such hash functions is {\em collision resistant} hash functions (CRH), which prevent an efficient attacker from finding ... more >>>

TR16-091 | 3rd June 2016
Nir Bitansky, Akshay Degwekar, Vinod Vaikuntanathan

Structure vs Hardness through the Obfuscation Lens

Revisions: 3

Cryptography relies on the computational hardness of structured problems. While one-way functions, the most basic cryptographic object, do not seem to require much structure, as we advance up the ranks into public-key cryptography and beyond, we seem to require that certain structured problems are hard. For example, factoring, quadratic residuosity, ... more >>>

TR15-187 | 24th November 2015
Nir Bitansky, Vinod Vaikuntanathan

A Note on Perfect Correctness by Derandomization

Revisions: 1

In this note, we show how to transform a large class of erroneous cryptographic schemes into perfectly correct ones. The transformation works for schemes that are correct on every input with probability noticeably larger than half, and are secure under parallel repetition. We assume the existence of one-way functions ... more >>>

TR15-009 | 16th January 2015
Aloni Cohen, Shafi Goldwasser, Vinod Vaikuntanathan

Aggregate Pseudorandom Functions and Connections to Learning

Revisions: 1

In the first part of this work, we introduce a new type of pseudo-random function for which ``aggregate queries'' over exponential-sized sets can be efficiently answered. An example of an aggregate query may be the product of all function values belonging to an exponential-sized interval, or the sum of all ... more >>>

TR11-111 | 10th August 2011
Zvika Brakerski, Craig Gentry, Vinod Vaikuntanathan

Fully Homomorphic Encryption without Bootstrapping

We present a radically new approach to fully homomorphic encryption (FHE) that dramatically improves performance and bases security on weaker assumptions. A central conceptual contribution in our work is a new way of constructing leveled fully homomorphic encryption schemes (capable of evaluating arbitrary polynomial-size circuits), {\em without Gentry's bootstrapping procedure}.

... more >>>

TR11-109 | 9th August 2011
Zvika Brakerski, Vinod Vaikuntanathan

Efficient Fully Homomorphic Encryption from (Standard) LWE

We present a fully homomorphic encryption scheme that is based solely on the (standard) learning with errors (LWE) assumption. Applying known results on LWE, the security of our scheme is based on the worst-case hardness of ``short vector problems'' on arbitrary lattices.

Our construction improves on previous works in two ... more >>>

TR07-133 | 20th November 2007
Craig Gentry, Chris Peikert, Vinod Vaikuntanathan

Trapdoors for Hard Lattices and New Cryptographic Constructions

We show how to construct a variety of ``trapdoor'' cryptographic tools
assuming the worst-case hardness of standard lattice problems (such as
approximating the shortest nonzero vector to within small factors).
The applications include trapdoor functions with \emph{preimage
sampling}, simple and efficient ``hash-and-sign'' digital signature
schemes, universally composable oblivious transfer, ... more >>>

ISSN 1433-8092 | Imprint