Abstract : Plausible deniability seems like the ultimate get-out-of-jail-free card. But how can we make it work when it comes to digital information sent in a public network.

Deniable encryption, defined by Canetti et al (Crypto 1997), suggests a method to achieve deniability by the sender of encrypted messages to overcome this problem. The idea is especially interesting in the context of electronic elections to eliminate the threat of vote buying after a vote has been cast.

I will present two new works on the subject.

1) With Agarwal and S. Mossel (Crypto21) we define and construct sender Deniable Fully Homomorphic Encryption with compact ciphertexts based on the Learning With Errors (LWE) polynomial hardness assumption. Deniable FHE enables storing encrypted data in the cloud to be processed securely without decryption, maintaining deniability of the encrypted data.

2) With Coladangelo and Vazirani (STOC22), we show a sender deniable encryption scheme where the encryption scheme is a quantum algorithm but the ciphertext is classical which is secure under the LWE polynomial hardness assumption. This scheme achieves for the first time simultaneously compactness, negligible deniability and polynomial encryption timeunder LWE. Furthermore, it is possible to extend the scheme so that coercion in an election cannot take place when the coercer is able to dictate all inputs to the deniable encryption algorithm even prior to encryption.

Abstract : The low-degree method postulates that no efficient algorithm outperforms low-degree polynomials in certain hypothesis-testing tasks. It has been used to understand computational indistinguishability in high-dimensional statistics.

We explore the use of the low-degree method in the context of cryptography. To this end, we apply it in the design and analysis of a new fine-grained public-key encryption scheme whose security is based on Goldreich's pseudorandom generator. The scheme is a combination of two proposals of Applebaum, Barak, and Wigderson, and inherits desirable features from both.

Joint work with Andrej Bogdanov and Pravesh Kothari.

Abstract: In the classical model of computation, one-way functions (OWF) are arguably minimal for computational cryptography, namely they are essential for almost any cryptographic application that can only be realized with respect to computationally bounded adversaries. In the quantum setting, however, OWFs appear not to be essential (Kretschmer 2021; Ananth et al., Morimae and Yamakawa 2022); in particular, no minimal primitive is known.

We consider EFI pairs — efficiently samplable, statistically far and computationally indistinguishable pairs of quantum states. Building on the work of Yan (2022), which essentially shows equivalence between EFI pairs and statistical commitment schemes, we show that, in the quantum setting, EFI pairs are necessary for a large class of cryptographic applications. Specifically, we construct EFI pairs from minimalistic versions of commitments schemes, oblivious transfer, and general secure multiparty computation, as well as from QCZK proofs for essentially any non-trivial language. We also construct quantum computational zero knowledge (QCZK) proofs for all of QIP from any EFI pair.

This suggests that, for much of quantum cryptography, EFI pairs play a similar role to that played by OWFs in the classical setting: they are simple to describe, essential, and also serve as a linchpin for demonstrating equivalence between primitives.

Joint work with Zvika Brakerski and Luowen Qian.

Abstract: Side channel attacks, and in particular timing attacks, are a fundamental obstacle for secure implementation of algorithms and cryptographic protocols, and have been widely researched for decades. In this talk we will offer a new perspective on resistance to timing attacks.

We will discuss security of cryptographic systems that leak information from their running time, focusing mainly on keyed functions such as signature and encryption schemes. We suggest several definitions to express the property that the leaked information does not help an adversary to expose sensitive information, e.g. the key or the queries made. The most interesting definition we propose is key obliviousness, which means that an adversary cannot tell whether it received the timing of the queries with the actual key or the timing of the same queries with a random key. We show that key obliviousness implies security of many types of schemes (e.g. private key encryption) that fall under the suggested notion of noticeable security.

We construct key oblivious pseudorandom permutations on small or medium sized domains. This construction is not ``fixed time", and at the same time is secure against any number of queries even in case the adversary knows the running time exactly. Our construction, which we call Janus Sometimes Recurse, is a variant of the ``Sometimes Recurse” (SR) shuffle by Morris and Rogaway.

We will also consider sampling algorithms where the goal is not to reveal information on the chosen output from their running time. Specifically

1. We will see a characterization of the distributions that can be sampled in a time oblivious way, meaning that the running time does not leak any information on the output.

2. We investigate the impact of timing attacks on (pure) differential privacy mechanisms. It turns out that if the range of the mechanism is unbounded (e.g. counting), then any time oblivious pure DP mechanism must give a useless output with constant probability. We show that up to this limitation it is possible to transform any pure DP mechanism into a time oblivious one.

Joint work with Yoav Ben-Dov, Liron David and Elad Tzalik.