## CryptoDB

### Nishanth Chandran

#### Affiliation: Microsoft Research, India

#### Publications

**Year**

**Venue**

**Title**

2019

CRYPTO

Universally Composable Secure Computation with Corrupted Tokens
📺
Abstract

We introduce the corrupted token model. This model generalizes the tamper-proof token model proposed by Katz (EUROCRYPT ’07) relaxing the trust assumption on the honest behavior of tokens. Our model is motivated by the real-world practice of outsourcing hardware production to possibly corrupted manufacturers. We capture the malicious behavior of token manufacturers by allowing the adversary to corrupt the tokens of honest players at the time of their creation.We show that under minimal complexity assumptions, i.e., the existence of one-way functions, it is possible to UC-securely realize (a variant of) the tamper-proof token functionality of Katz in the corrupted token model with n stateless tokens assuming that the adversary corrupts at most $$n-1$$ of them (for any $$n>0$$). We apply this result to existing multi-party protocols in Katz’s model to achieve UC-secure MPC in the corrupted token model assuming only the existence of one-way functions. Finally, we show how to obtain the above results using tokens of small size that take only short inputs. The technique in this result can also be used to improve the assumption of UC-secure hardware obfuscation recently proposed by Nayak et al. (NDSS ’17). While their construction requires the existence of collision-resistant hash functions, we can obtain the same result from only one-way functions. Moreover using our main result we can improve the trust assumption on the tokens as well.

2014

EPRINT

2010

EPRINT

Position-Based Quantum Cryptography
Abstract

In this work, we initiate the study of position-based cryptography in the quantum setting. The aim of position-based cryptography is to use the geographical position of a party as its only credential. This has interesting applications, e.g., it enables two military bases to talk to each other over insecure (i.e. neither private nor authenticated) channels and without having any pre-shared key, with the guarantee that only parties within the bases learn the content of the conversation. We present schemes for several important position-based cryptographic tasks: positioning, authentication, and key exchange, and we prove them unconditionally secure, i.e., without assuming any restriction on the adversaries (beyond the laws of quantum mechanics). At the core of our security proofs lies the strong complementary information tradeoff recently introduced by Renes and Boileau. An attractive feature of all our schemes is that they only involve ``simple'' quantum operations, namely to prepare, communicate and measure-upon-arrival individual qubits. We stress that
the above position-based tasks are impossible in the classical setting without limiting the adversary. Therefore, our work shows that position-based quantum cryptography is one of the rare examples besides QKD for which there is such a strong separation between classical and quantum cryptography. Besides the schemes for which we give rigorous security proofs, we also present a couple of significantly more efficient schemes for which we can merely conjecture security; proving them secure remains an interesting challenge. Our results open a fascinating new direction for position-based security in cryptography where security of protocols is solely based on the laws of physics and proofs of security do not require any pre-existing infrastructure.

2009

EUROCRYPT

2008

EPRINT

Public-Key Encryption with Efficient Amortized Updates
Abstract

Searching and modifying public-key encrypted data (without having the decryption key) has received a lot of attention in recent literature. In this paper we re-visit this important problem and achieve much better amortized communication-complexity bounds. Our solution resolves the main open question posed by Boneh at al., \cite{BKOS07}.
First, we consider the following much simpler to state problem (which turns out to be central for the above): A server holds a copy of Alice's database that has been encrypted under Alice's public key. Alice would like to allow other users in the system to replace a
bit of their choice in the server's database by communicating directly with the server, despite other users not having Alice's private key. However, Alice requires that the server should not know
which bit was modified. Additionally, she requires that the
modification protocol should have ``small" communication complexity
(sub-linear in the database size). This task is referred to as
private database modification, and is a central tool in building a more general protocol for modifying and searching over public-key encrypted data with small communication complexity. The problem was first considered by Boneh at al., \cite{BKOS07}. The protocol of \cite{BKOS07} to modify $1$ bit of an $N$-bit database has communication complexity $\mathcal{O}(\sqrt N)$. Naturally, one can ask if we can improve upon this. Unfortunately, \cite{OS08} give evidence to the contrary, showing that using current algebraic techniques, this is not possible to do. In this paper, we ask the following question: what is the communication complexity when modifying $L$ bits of an $N$-bit database? Of course, one can achieve naive communication complexity of $\mathcal{O}(L\sqrt N)$ by simply repeating the protocol of \cite{BKOS07}, $L$ times. Our main result is a private database modification protocol to modify $L$ bits of an $N$-bit database that has communication complexity
$\mathcal{O}(\sqrt{NL^{1+\alpha}}\textrm{poly-log~} N)$, where
$0<\alpha<1$ is a constant. (We remark that in contrast with recent work of Lipmaa \cite{L08} on the same topic, our database size {\em does not grow} with every update, and stays exactly the same size.)
As sample corollaries to our main result, we obtain the following:
\begin{itemize}
\item First, we apply our private database modification protocol to
answer the main open question of \cite{BKOS07}. More specifically, we
construct a public key encryption scheme supporting PIR queries that
allows every message to have a non-constant number of keywords
associated with it.
\item Second, we show that one can apply our
techniques to obtain more efficient communication complexity when
parties wish to increment or decrement multiple cryptographic
counters (formalized by Katz at al. ~\cite{KMO01}).
\end{itemize}
We believe that ``public-key encrypted'' amortized database modification is an important cryptographic primitive in it's own right and will be a useful in other applications.

2008

EPRINT

A public key encryption scheme secure against key dependent chosen plaintext and adaptive chosen ciphertext attacks
Abstract

Recently, at Crypto 2008, Boneh, Halevi, Hamburg, and Ostrovsky (BHHO)
solved the long-standing open problem of ``circular encryption,''
by
presenting a public key encryption scheme
and proving that it
is semantically secure against key dependent chosen plaintext attack (KDM-CPA security)
under standard assumptions (and without resorting to random oracles).
However, they left as an open problem that of designing
an encryption scheme that \emph{simultaneously} provides security
against both key dependent chosen plaintext \emph{and} adaptive chosen ciphertext
attack (KDM-CCA2 security).
In this paper, we solve this problem.
First, we show that by applying the Naor-Yung ``double encryption''
paradigm, one can combine
any KDM-CPA secure scheme with any (ordinary) CCA2 secure scheme,
along with an appropriate non-interactive zero-knowledge proof,
to obtain a KDM-CCA2 secure scheme.
Second, we give a concrete instantiation that makes use
the above KDM-CPA secure scheme of BHHO,
along with a generalization of the Cramer-Shoup CCA2 secure
encryption scheme,
and recently developed
pairing-based NIZK proof systems.
This instantiation increases the complexity of the BHHO
scheme by just a small constant factor.

2007

EPRINT

New Constructions for UC Secure Computation using Tamper-proof Hardware
Abstract

The Universal Composability framework was introduced by Canetti to study the security of protocols which are concurrently executed with other protocols in a network environment. Unfortunately it was shown that in the so called plain model, a large class of functionalities cannot be securely realized. These severe impossibility results motivated the study of other models involving some sort of setup assumptions, where general positive results can be obtained. Until recently, all the setup assumptions which were proposed required some trusted third party (or parties).
Katz recently proposed using a \emph{physical setup} to avoid such trusted setup assumptions. In his model, the physical setup phase includes the parties exchanging tamper proof hardware tokens implementing some functionality. The tamper proof hardware is modeled so as to assume that the receiver of the token can do nothing more than observe its input/output characteristics. It is further assumed that the sender \emph{knows} the program code of the hardware token which it distributed. Based on the DDH assumption, Katz gave general positive results for universally composable multi-party computation tolerating any number of dishonest parties making this model quite attractive.
In this paper, we present new constructions for UC secure computation using tamper proof hardware (in a stronger model). Our results represent an improvement over the results of Katz in several directions using substantially different techniques. Interestingly, our security proofs do not rely on being able to rewind the hardware tokens created by malicious parties. This means that we are able to relax the assumptions that the parties \emph{know} the code of the hardware token which they distributed. This allows us to model real life attacks where, for example, a party may simply pass on the token obtained from one party to the other without actually knowing its functionality. Furthermore, our construction models the interaction with the tamper-resistant hardware as a simple request-reply protocol. Thus, we show that the hardware tokens used in our construction can be \emph{resettable}. In fact, it suffices to use token which are completely stateless (and thus cannot execute a multi-round protocol). Our protocol is also based on general assumptions (namely enhanced trapdoor permutations).

#### Program Committees

- Eurocrypt 2020
- PKC 2019
- Asiacrypt 2019
- TCC 2018
- PKC 2017
- Crypto 2016
- TCC 2016
- Crypto 2015

#### Coauthors

- Prabhanjan Ananth (1)
- Harry Buhrman (1)
- Jan Camenisch (2)
- Melissa Chase (3)
- Wutichai Chongchitmate (2)
- Serge Fehr (2)
- Juan A. Garay (2)
- Ran Gelles (2)
- Shafi Goldwasser (1)
- Vipul Goyal (8)
- William E. Skeith III (1)
- Aayush Jain (1)
- Bhavana Kanukurthi (4)
- Feng-Hao Liu (2)
- Ryan Moriarty (1)
- Pratyay Mukherjee (1)
- Ryo Nishimaki (2)
- Rafail Ostrovsky (9)
- Omkant Pandey (1)
- Srinivasan Raghuraman (5)
- Amit Sahai (3)
- Christian Schaffner (1)
- Victor Shoup (2)
- Jalaj Upadhyay (1)
- Vinod Vaikuntanathan (1)
- Dhinakaran Vinayagamurthy (3)
- Ivan Visconti (1)
- Keita Xagawa (2)
- Vassilis Zikas (1)