## CryptoDB

### Hemanta K. Maji

#### Affiliation: Purdue, USA

#### Publications

**Year**

**Venue**

**Title**

2019

CRYPTO

Explicit Rate-1 Non-malleable Codes for Local Tampering
📺
Abstract

This paper constructs high-rate non-malleable codes in the information-theoretic plain model against tampering functions with bounded locality. We consider $$\delta $$-local tampering functions; namely, each output bit of the tampering function is a function of (at most) $$\delta $$ input bits. This work presents the first explicit and efficient rate-1 non-malleable code for $$\delta $$-local tampering functions, where $$\delta =\xi \lg n$$ and $$\xi <1$$ is any positive constant. As a corollary, we construct the first explicit rate-1 non-malleable code against NC$$^0$$ tampering functions.Before our work, no explicit construction for a constant-rate non-malleable code was known even for the simplest 1-local tampering functions. Ball et al. (EUROCRYPT–2016), and Chattopadhyay and Li (STOC–2017) provided the first explicit non-malleable codes against $$\delta $$-local tampering functions. However, these constructions are rate-0 even when the tampering functions have 1-locality. In the CRS model, Faust et al. (EUROCRYPT–2014) constructed efficient rate-1 non-malleable codes for $$\delta = O(\log n)$$ local tampering functions.Our main result is a general compiler that bootstraps a rate-0 non-malleable code against leaky input and output local tampering functions to construct a rate-1 non-malleable code against $$\xi \lg n$$-local tampering functions, for any positive constant $$\xi < 1$$. Our explicit construction instantiates this compiler using an appropriate encoding by Ball et al. (EUROCRYPT–2016).

2019

TCC

Estimating Gaps in Martingales and Applications to Coin-Tossing: Constructions and Hardness
Abstract

Consider the representative task of designing a distributed coin-tossing protocol for n processors such that the probability of heads is $$X_0\in [0,1]$$. This protocol should be robust to an adversary who can reset one processor to change the distribution of the final outcome. For $$X_0=1/2$$, in the information-theoretic setting, no adversary can deviate the probability of the outcome of the well-known Blum’s “majority protocol” by more than $$\frac{1}{\sqrt{2\pi n}}$$, i.e., it is $$\frac{1}{\sqrt{2\pi n}}$$ insecure.In this paper, we study discrete-time martingales $$(X_0,X_1,\dotsc ,X_n)$$ such that $$X_i\in [0,1]$$, for all $$i\in \{0,\dotsc ,n\}$$, and $$X_n\in {\{0,1\}} $$. These martingales are commonplace in modeling stochastic processes like coin-tossing protocols in the information-theoretic setting mentioned above. In particular, for any $$X_0\in [0,1]$$, we construct martingales that yield $$\frac{1}{2}\sqrt{\frac{X_0(1-X_0)}{n}}$$ insecure coin-tossing protocols. For $$X_0=1/2$$, our protocol requires only 40% of the processors to achieve the same security as the majority protocol.The technical heart of our paper is a new inductive technique that uses geometric transformations to precisely account for the large gaps in these martingales. For any $$X_0\in [0,1]$$, we show that there exists a stopping time $$\tau $$ such that The inductive technique simultaneously constructs martingales that demonstrate the optimality of our bound, i.e., a martingale where the gap corresponding to any stopping time is small. In particular, we construct optimal martingales such that any stopping time $$\tau $$ has Our lower-bound holds for all $$X_0\in [0,1]$$; while the previous bound of Cleve and Impagliazzo (1993) exists only for positive constant $$X_0$$. Conceptually, our approach only employs elementary techniques to analyze these martingales and entirely circumvents the complex probabilistic tools inherent to the approaches of Cleve and Impagliazzo (1993) and Beimel, Haitner, Makriyannis, and Omri (2018).By appropriately restricting the set of possible stopping-times, we present representative applications to constructing distributed coin-tossing/dice-rolling protocols, discrete control processes, fail-stop attacking coin-tossing/dice-rolling protocols, and black-box separations.

2018

TCC

Secure Computation Using Leaky Correlations (Asymptotically Optimal Constructions)
Abstract

Most secure computation protocols can be effortlessly adapted to offload a significant fraction of their computationally and cryptographically expensive components to an offline phase so that the parties can run a fast online phase and perform their intended computation securely. During this offline phase, parties generate private shares of a sample generated from a particular joint distribution, referred to as the correlation. These shares, however, are susceptible to leakage attacks by adversarial parties, which can compromise the security of the secure computation protocol. The objective, therefore, is to preserve the security of the honest party despite the leakage performed by the adversary on her share.Prior solutions, starting with n-bit leaky shares, either used 4 messages or enabled the secure computation of only sub-linear size circuits. Our work presents the first 2-message secure computation protocol for 2-party functionalities that have $$\varTheta (n)$$ circuit-size despite $$\varTheta (n)$$-bits of leakage, a qualitatively optimal result. We compose a suitable 2-message secure computation protocol in parallel with our new 2-message correlation extractor. Correlation extractors, introduced by Ishai, Kushilevitz, Ostrovsky, and Sahai (FOCS–2009) as a natural generalization of privacy amplification and randomness extraction, recover “fresh” correlations from the leaky ones, which are subsequently used by other cryptographic protocols. We construct the first 2-message correlation extractor that produces $$\varTheta (n)$$-bit fresh correlations even after $$\varTheta (n)$$-bit leakage.Our principal technical contribution, which is of potential independent interest, is the construction of a family of multiplication-friendly linear secret sharing schemes that is simultaneously a family of small-bias distributions. We construct this family by randomly “twisting then permuting” appropriate Algebraic Geometry codes over constant-size fields.

2015

TCC

2010

EPRINT

A Zero-One Law for Deterministic 2-Party Secure Computation
Abstract

We use security in the Universal Composition framework as a means to study the ``cryptographic complexity'' of 2-party secure computation tasks (functionalities). We say that a functionality $F$ {\em reduces to} another functionality $G$ if there is a UC-secure protocol for $F$ using ideal access to $G$. This reduction is a natural and fine-grained way to compare the relative complexities of cryptographic tasks. There are two natural ``extremes'' of complexity under the reduction: the {\em trivial} functionalities, which can be reduced to any other functionality; and the {\em complete} functionalities, to which any other functionality can be reduced.
In this work we show that under a natural computational assumption (the existence of a protocol for oblivious transfer secure against semi-honest adversaries), there is a {\bf zero-one law} for the cryptographic complexity of 2-party deterministic functionalities. Namely, {\em every such functionality is either trivial or complete.} No other qualitative distinctions exist among functionalities, under this computational assumption.
While nearly all previous work classifying multi-party computation functionalities has been restricted to the case of secure function evaluation, our results are the first to consider completeness of arbitrary {\em reactive} functionalities, which receive input and give output repeatedly throughout several rounds of interaction. One important technical contribution in this work is to initiate the comprehensive study of the cryptographic properties of reactive functionalities. We model these functionalities as finite automata and develop an automata-theoretic methodology for classifying and studying their cryptographic properties. Consequently, we completely characterize the reactive behaviors that lead to cryptographic non-triviality. Another contribution of independent interest is to optimize the hardness assumption used by Canetti et al.\ (STOC 2002) in showing that the common random string functionality is complete (a result independently obtained by Damg{\aa}rd et al.\ (TCC 2010)).

2008

EPRINT

Attribute-Based Signatures: Achieving Attribute-Privacy and Collusion-Resistance
Abstract

We introduce a new and versatile cryptographic primitive called {\em Attribute-Based Signatures} (ABS), in which a signature attests not to the identity of the individual who endorsed a message, but instead to a (possibly complex) claim regarding the attributes she posseses. ABS offers:
* A strong unforgeability guarantee for the verifier,
that the signature was produced by a {\em single} party whose
attributes satisfy the claim being made; i.e., not by a
collusion of individuals who pooled their attributes together.
* A strong privacy guarantee for the signer, that the
signature reveals nothing about the identity or attributes of the
signer beyond what is explicitly revealed by the claim being made.
We formally define the security requirements of ABS as a cryptographic primitive, and then describe an efficient ABS construction based on groups with bilinear pairings. We prove that our construction is secure in the generic group model. Finally, we illustrate several applications of this new tool; in particular, ABS fills a critical security requirement in attribute-based messaging (ABM) systems.
A powerful feature of our ABS construction is that unlike many other attribute-based cryptographic primitives, it can be readily used
in a {\em multi-authority} setting, wherein users can make claims involving combinations of attributes issued by independent
and mutually distrusting authorities.

2008

EPRINT

Complexity of Multiparty Computation Problems: The Case of 2-Party Symmetric Secure Function Evaluation
Abstract

In symmetric secure function evaluation (SSFE), Alice has an input
$x$, Bob has an input $y$, and both parties wish to securely
compute $f(x,y)$. We classify these functions $f$ according
to their ``cryptographic complexities,'' and show that the
landscape of complexity among these functions is surprisingly
rich.
We give combinatorial characterizations of the SSFE
functions $f$ that have passive-secure protocols, and those which are
protocols secure in
the standalone setting. With respect to universally composable
security (for unbounded parties), we show that there is an infinite
hierarchy of increasing complexity for SSFE functions,
That is, we describe a family of SSFE functions $f_1, f_2, \ldots$
such that there exists a UC-secure protocol for $f_i$ in the
$f_j$-hybrid world if and only if $i \le j$.
Our main technical tool for deriving complexity separations
is a powerful protocol simulation theorem which states that,
even in the strict setting of UC security, the canonical
protocol for $f$ is as secure as any other protocol for $f$,
as long as $f$ satisfies a certain combinatorial characterization.
We can then show intuitively clear impossibility results by
establishing the combinatorial properties of $f$ and then
describing attacks against the very simple canonical
protocols, which by extension are also feasible
attacks against {\em any} protocol for the same functionality.

#### Program Committees

- Asiacrypt 2019
- PKC 2016
- Asiacrypt 2015
- TCC 2013

#### Coauthors

- Divesh Aggarwal (2)
- Shashank Agrawal (5)
- Alexander R. Block (2)
- Jean-Sébastien Coron (2)
- Craig Gentry (2)
- Divya Gupta (8)
- Shai Halevi (2)
- Yuval Ishai (1)
- Hamidreza Amini Khorasgani (1)
- Dakshita Khurana (3)
- Daniel Kraschewski (3)
- Tancrède Lepoint (2)
- Mohammad Mahmoody (1)
- Eric Miles (2)
- Tamalika Mukherjee (1)
- Hai H. Nguyen (2)
- Pichayoot Ouppaphan (1)
- Omkant Pandey (5)
- Manoj Prabhakaran (15)
- Mariana Raykova (2)
- Mike Rosulek (6)
- Amit Sahai (8)
- Mehdi Tibouchi (2)
- Mingyuan Wang (1)