In my first post on this blog I would like to expand its range of topics to applied cryptography and share some interesting new findings that so far have not been reported anywhere else except a Eurocrypt'12 rump session talk. On Valentine's Day earlier this year, the paper with a somewhat enigmatic title ``Ron was … Continue reading Factoring RSA Moduli. Part I.

The first question we'd like to answer is this: which is the monotone, balanced, transitive Boolean function which is least sensitive to bit-flips? We know that Majority is the worst possible with $latex NS( Maj) = \Theta(1/\sqrt{n})$. The new champion turns out to be the Tribes function first studied by Ben-Or and Linial. $latex Tribes_{s,w}$ … Continue reading When did Majority become the stablest? (Part 2)

The fireworks happening over at Ryan O'Donnell's blog reminded me of something that always puzzles me: Is Majority the Stablest? Or the Unstablest? Consider the class of all monotone, balanced Boolean functions $latex f:\{-1,1\}^n \rightarrow \{-1,1\}$. We define the noise sensitivity $latex NS(f)$ of a function $latex f$ as $latex NS(f) = P_{x,e}[f(x) \neq f( … Continue reading When did Majority become the stablest?

Every year the ACM gives out an award for the best doctoral dissertation, as well as up to 3 honorable mentions. This year, both honorable mentions were given to CS theorists: Aleksander Madry and David Steurer (the dissertation award was given to Seth Cooper for his work on protein folding games). Both Aleksander's and David's … Continue reading Aleksander Madry and David Steurer win ACM honorable mention

Guest post by Boaz Barak and Zvika Brakerski (part 2) In the previous post, we demonstrated the versatility of fully homomorphic encryption and its applicability for multiple applications. In this post we will demonstrate (not too painfully, we hope) how fully homomorphic encryption is constructed. Our goal is to present the simplest solution that (we … Continue reading Building the Swiss Army Knife

Guest post by Boaz Barak and Zvika Brakerski In 2009, Craig Gentry shook the world of cryptography by presenting a construction of a Fully Homomorphic Encryption Scheme (FHE). In this post and the next one, we will explain what FHE is, why cryptographers are so excited about it, and how its construction works. There is … Continue reading The Swiss Army Knife of Cryptography

This post has some tidbits regarding the problem of computing a 'fingerprint' of a long sequence of characters, often called 'string hashing'. Most of the results I will describe are quite old, but they are scattered upon several papers, so I think it is worthwhile to have a post where they are  put together. This … Continue reading How to collapse the universe?

As promised in the previous post, I will explain how an algorithm designed for the approximate near neighbor problem, the LSH algorithm, leads to a solution for the exact near neighbor problem (henceforth NNS). While, the algorithm for the exact problem will not have full guarantees, we will be able to give some partial guarantees. Usually … Continue reading Exact Algorithms from Approximation Algorithms? (part 2)

One great "soft" challenge in (T)CS I find to be how to go on to find useful algorithms for problems that we believe (or have even proven!) to be hard in general. Let me explain by giving the all-too-common-example: Practitioner: I need to solve problem X. Theoretician: Nice question, let me think... Hm, it seems hard. … Continue reading Exact Algorithms from Approximation Algorithms? (part 1)

Tiny ToCT studies the following question: could a marvelous field of huge impact be squeezed into a tiny space of 140 characters? Good luck!