International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

Muthuramakrishnan Venkitasubramaniam

Affiliation: University of Rochester, USA

Publications

Year
Venue
Title
2019
JOFC
On Black-Box Complexity of Universally Composable Security in the CRS Model
Carmit Hazay Muthuramakrishnan Venkitasubramaniam
In this work, we study the intrinsic complexity of black-box Universally Composable (UC) secure computation based on general assumptions. We present a thorough study in various corruption modelings while focusing on achieving security in the common reference string (CRS) model. Our results involve the following:Static UC secure computation. Designing the first static UC oblivious transfer protocol based on public-key encryption and stand-alone semi-honest oblivious transfer. As a corollary, we obtain the first black-box constructions of UC secure computation assuming only two-round semi-honest oblivious transfer.One-sided UC secure computation. Designing adaptive UC two-party computation with single corruptions assuming public-key encryption with oblivious ciphertext generation.Adaptive UC secure computation. Designing adaptively secure UC commitment scheme assuming only public-key encryption with oblivious ciphertext generation. As a corollary, we obtain the first black-box constructions of adaptive UC secure computation assuming only (trapdoor) simulatable public-key encryption (as well as a variety of concrete assumptions).We remark that such a result was not known even under non-black-box constructions.
2018
CRYPTO
Round-Optimal Secure Multi-Party Computation 📺
Shai Halevi Carmit Hazay Antigoni Polychroniadou Muthuramakrishnan Venkitasubramaniam
Secure multi-party computation (MPC) is a central cryptographic task that allows a set of mutually distrustful parties to jointly compute some function of their private inputs where security should hold in the presence of a malicious adversary that can corrupt any number of parties. Despite extensive research, the precise round complexity of this “standard-bearer” cryptographic primitive is unknown. Recently, Garg, Mukherjee, Pandey and Polychroniadou, in EUROCRYPT 2016 demonstrated that the round complexity of any MPC protocol relying on black-box proofs of security in the plain model must be at least four. Following this work, independently Ananth, Choudhuri and Jain, CRYPTO 2017 and Brakerski, Halevi, and Polychroniadou, TCC 2017 made progress towards solving this question and constructed four-round protocols based on non-polynomial time assumptions. More recently, Ciampi, Ostrovsky, Siniscalchi and Visconti in TCC 2017 closed the gap for two-party protocols by constructing a four-round protocol from polynomial-time assumptions. In another work, Ciampi, Ostrovsky, Siniscalchi and Visconti TCC 2017 showed how to design a four-round multi-party protocol for the specific case of multi-party coin-tossing.In this work, we resolve this question by designing a four-round actively secure multi-party (two or more parties) protocol for general functionalities under standard polynomial-time hardness assumptions with a black-box proof of security.
2018
TCC
Round-Optimal Fully Black-Box Zero-Knowledge Arguments from One-Way Permutations
Carmit Hazay Muthuramakrishnan Venkitasubramaniam
In this paper, we revisit the round complexity of designing zero-knowledge (ZK) arguments via a black-box construction from minimal assumptions. Our main result implements a 4-round ZK argument for any language in $$\textsf {NP}$$ NP, based on injective one-way functions, that makes black-box use of the underlying function. As a corollary, we also obtain the first 4-round perfect zero-knowledge argument for $$\textsf {NP}$$ NP based on claw-free permutations via a black-box construction and 4-round input-delayed commit-and-prove zero-knowledge argument based on injective one-way functions.
2018
TCC
Two-Round Adaptively Secure Multiparty Computation from Standard Assumptions
Fabrice Benhamouda Huijia Lin Antigoni Polychroniadou Muthuramakrishnan Venkitasubramaniam
We present the first two-round multiparty computation (MPC) protocols secure against malicious adaptive corruption in the common reference string (CRS) model, based on DDH, LWE, or QR. Prior two-round adaptively secure protocols were known only in the two-party setting against semi-honest adversaries, or in the general multiparty setting assuming the existence of indistinguishability obfuscation (iO).Our protocols are constructed in two steps. First, we construct two-round oblivious transfer (OT) protocols secure against malicious adaptive corruption in the CRS model based on DDH, LWE, or QR. We achieve this by generically transforming any two-round OT that is only secure against static corruption but has certain oblivious sampleability properties, into a two-round adaptively secure OT. Prior constructions were only secure against semi-honest adversaries or based on iO.Second, building upon recent constructions of two-round MPC from two-round OT in the weaker static corruption setting [Garg and Srinivasan, Benhamouda and Lin, Eurocrypt’18] and using equivocal garbled circuits from [Canetti, Poburinnaya and Venkitasubramaniam, STOC’17], we show how to construct two-round adaptively secure MPC from two-round adaptively secure OT and constant-round adaptively secure MPC, with respect to both malicious and semi-honest adversaries. As a corollary, we also obtain the first 2-round MPC secure against semi-honest adaptive corruption in the plain model based on augmented non-committing encryption (NCE), which can be based on a variety of assumptions, CDH, RSA, DDH, LWE, or factoring Blum integers. Finally, we mention that our OT and MPC protocols in the CRS model are, in fact, adaptively secure in the Universal Composability framework.
2017
PKC
2017
PKC
2017
PKC
Scalable Multi-party Private Set-Intersection
Carmit Hazay Muthuramakrishnan Venkitasubramaniam
2017
TCC
2017
TCC
2016
CRYPTO
On the Power of Secure Two-Party Computation 📺
Carmit Hazay Muthuramakrishnan Venkitasubramaniam
2016
TCC
2016
TCC
2015
EPRINT
2015
EPRINT
What Security can we Achieve in 4-Rounds?
Carmit Hazay Muthuramakrishnan Venkitasubramaniam
2015
EPRINT
2015
TCC
2015
ASIACRYPT
2015
ASIACRYPT
Secure Computation from Millionaire
Abhi Shelat Muthuramakrishnan Venkitasubramaniam
2014
TCC
2014
EPRINT
2014
JOFC
2013
ASIACRYPT
2012
ASIACRYPT
2012
ASIACRYPT
A Unified Framework for UC from Only OT
Rafael Pass Huijia Lin Muthuramakrishnan Venkitasubramaniam
2011
TCC
2010
TCC
2010
TCC
2010
CRYPTO
2008
TCC
2008
TCC
On Constant-Round Concurrent Zero-Knowledge
Rafael Pass Muthuramakrishnan Venkitasubramaniam
2008
EUROCRYPT
2007
EPRINT
Precise Concurrent Zero Knowledge
Omkant Pandey Rafael Pass Amit Sahai Wei-Lung Dustin Tseng Muthuramakrishnan Venkitasubramaniam
\emph{Precise zero knowledge} introduced by Micali and Pass (STOC'06) guarantees that the view of any verifier $V$ can be simulated in time closely related to the \emph{actual} (as opposed to worst-case) time spent by $V$ in the generated view. We provide the first constructions of precise concurrent zero-knowledge protocols. Our constructions have essentially optimal precision; consequently this improves also upon the previously tightest non-precise concurrent zero-knowledge protocols by Kilian and Petrank (STOC'01) and Prabhakaran, Rosen and Sahai (FOCS'02) whose simulators have a quadratic worst-case overhead. Additionally, we achieve a statistically-precise concurrent zero-knowledge property---which requires simulation of unbounded verifiers participating in an unbounded number of concurrent executions; as such we obtain the first (even non-precise) concurrent zero-knowledge protocols which handle verifiers participating in a super-polynomial number of concurrent executions.

Program Committees

Eurocrypt 2018
Crypto 2014
PKC 2011