## CryptoDB

### Nishanth Chandran

#### Publications

**Year**

**Venue**

**Title**

2021

EUROCRYPT

Function Secret Sharing for Mixed-Mode and Fixed-Point Secure Computation
Abstract

Recently Boyle et al. (TCC 2019) proposed a new approach for secure computation in the {\em preprocessing model} building on {\em function secret sharing} (FSS). This approach can be used to realize any circuit containing gates that admit efficient FSS schemes. In this work, we make the following three technical contributions:
{\bf Improved Key Size.} The complexity of the preprocessing phase directly depends on the FSS key size. We improve the size of FSS keys for several existing FSS constructions through two important steps. First, we present a roughly $4\times$ reduction in FSS key size for the Distributed Comparison Function (DCF), i.e. ($f_\alpha(x) = \beta$ for all $x < \alpha$ and $0$, otherwise). Second, prior FSS schemes for many important function classes are obtained via reductions to multiple instances of DCF; for example, 2 instances for interval containment and $2m$ for splines with $m$ pieces. We significantly improve these reductions for public intervals and obtain {\em optimal} FSS schemes, i.e., through a {\em single instance of DCF}, thereby reducing the key sizes by up to $6-22\times$ for commonly used functions in mixed-mode secure computation such as ReLU and sigmoid.
{\bf FSS for New Function Families.} We present the first constructions of FSS schemes for arithmetic and logical right shift, as well as for bit-decomposition, where the output bits must be secret shared in a larger ring. These functions are crucial for many applications such as fixed-point arithmetic and machine learning.
{\bf FSS for Fixed-Point Arithmetic and Barrier.} One of the important functions in the realization of secure fixed-point arithmetic is that of multiply-then-truncate. While our work shows how to obtain a construction for this function in 2 rounds using sequential calls to FSS schemes for multiply and shift, we demonstrate a barrier towards improving this via FSS beyond what we achieve. Specifically, we show that a 1-round solution would require settling a major open problem in the area of FSS: namely, building an FSS for the class of bit-conjunction functions based on only symmetric-key cryptographic assumptions.

2021

CRYPTO

Adaptive Extractors and their Application to Leakage Resilient Secret Sharing
📺
Abstract

We introduce Adaptive Extractors, which unlike traditional randomness extractors, guarantee security even when an adversary obtains leakage on the source \textit{after} observing the extractor output. We make a compelling case for the study of such extractors by demonstrating their use in obtaining adaptive leakage in secret sharing schemes.
Specifically, at FOCS 2020, Chattopadhyay, Goodman, Goyal, Kumar, Li, Meka, Zuckerman, built an adaptively secure leakage resilient secret sharing scheme (LRSS) with both rate and leakage rate being $\mathcal{O}(1/n)$, where $n$ is the number of parties. In this work, we build an adaptively secure LRSS that offers an interesting trade-off between rate, leakage rate, and the total number of shares from which an adversary can obtain leakage. As a special case, when considering $t$-out-of-$n$ secret sharing schemes for threshold $t = \alpha n$ (constant $0<\alpha<1$), we build a scheme with constant rate, constant leakage rate, and allow the adversary leakage from all but $t-1$ of the shares, while giving her the remaining $t-1$ shares completely in the clear. (Prior to this, constant rate LRSS scheme tolerating adaptive leakage was unknown for \textit{any} threshold.)
Finally, we show applications of our techniques to both non-malleable secret sharing and secure message transmission.

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

- N. Nalla Anandakumar (1)
- Prabhanjan Ananth (1)
- Elette Boyle (1)
- Harry Buhrman (1)
- Jan Camenisch (2)
- Melissa Chase (3)
- Wutichai Chongchitmate (2)
- Serge Fehr (2)
- Juan A. Garay (2)
- Ran Gelles (2)
- Niv Gilboa (1)
- Shafi Goldwasser (1)
- Vipul Goyal (8)
- Divya Gupta (1)
- William E. Skeith III (1)
- Yuval Ishai (1)
- Aayush Jain (1)
- Bhavana Kanukurthi (5)
- Feng-Hao Liu (2)
- Ryan Moriarty (1)
- Pratyay Mukherjee (1)
- Ryo Nishimaki (2)
- Sai Lakshmi Bhavana Obbattu (1)
- Rafail Ostrovsky (9)
- Omkant Pandey (1)
- Srinivasan Raghuraman (5)
- Mayank Rathee (1)
- Amit Sahai (3)
- Christian Schaffner (1)
- Sruthi Sekar (1)
- Victor Shoup (2)
- Jalaj Upadhyay (1)
- Vinod Vaikuntanathan (1)
- Dhinakaran Vinayagamurthy (3)
- Ivan Visconti (1)
- Keita Xagawa (2)
- Vassilis Zikas (1)