## CryptoDB

### Susumu Kiyoshima

#### Publications

Year
Venue
Title
2020
CRYPTO
We give a four-round black-box construction of a commit-and-prove protocol with succinct communication. Our construction is WI and has constant soundness error, and it can be upgraded into a one that is ZK and has negligible soundness error by relying on a round-preserving transformation of Khurana et al. (TCC 2018). Our construction is obtained by combining the MPC-in-the-head technique of Ishai et al. (SICOMP 2009) with the two-round succinct argument of Kalai et al. (STOC 2014), and the main technical novelty lies in the analysis of the soundness---we show that, although the succinct argument of Kalai et al. does not necessarily provide soundness for NP statements, it can be used in the MPC-in-the-head technique for proving the consistency of committed MPC views. Our construction is based on sub-exponentially hard collision-resistant hash functions, two-round PIRs, and two-round OTs.
2020
JOFC
Concurrent non-malleable zero-knowledge ( $\mathrm {CNMZK}$ CNMZK ) protocols are zero-knowledge protocols that provides security even when adversaries interact with multiple provers and verifiers simultaneously. It is known that $\mathrm {CNMZK}$ CNMZK arguments for $\mathcal {NP}$ NP can be constructed in the plain model. Furthermore, it was recently shown that statistical $\mathrm {CNMZK}$ CNMZK arguments for $\mathcal {NP}$ NP can also be constructed in the plain model. However, although the former requires only the existence of one-way functions, the latter requires the DDH assumption. In this paper, we construct a statistical $\mathrm {CNMZK}$ CNMZK argument for $\mathcal {NP}$ NP assuming only the existence of one-way functions. The security is proven via black-box simulation, and the round complexity is $\mathsf {poly}(n)$ poly ( n ) . Under the existence of collision-resistant hash functions, the round complexity is reduced to $\omega (\log n)$ ω ( log n ) , which is essentially optimal for black-box concurrent zero-knowledge protocols.
2019
JOFC
We give a new proof of the existence of $O(n^{\epsilon })$ O ( n ϵ ) -round public-coin concurrent zero-knowledge arguments for $\mathcal {NP}$ NP , where $\epsilon >0$ ϵ > 0 is an arbitrary constant. The security is proven in the plain model under the assumption that collision-resistant hash functions exist. The existence of such concurrent zero-knowledge arguments was previously proven by Goyal (STOC’13) in the plain model under the same assumption. In the proof, we use a new variant of the non-black-box simulation technique of Barak (FOCS’01). An important property of our simulation technique is that the simulator runs in a “straight-line” manner in the fully concurrent setting. Compared with the simulation technique of Goyal, which also has such a property, the analysis of our simulation technique is (arguably) simpler.
2019
JOFC
We present a round-efficient black-box construction of a general multi-party computation (MPC) protocol that satisfies composability in the plain model. The security of our protocol is proven in the angel-based UC framework [Prabhakaran and Sahai, STOC’04] under the minimal assumption of the existence of semi-honest oblivious transfer protocols. The round complexity of our protocol is $\max (\widetilde{O}(\log ^2n), O(R_{{{{\mathsf {O}}}{{\mathsf {T}}}}}))$ max ( O ~ ( log 2 n ) , O ( R O T ) ) when the round complexity of the underlying oblivious transfer protocol is $R_{{{{\mathsf {O}}}{{\mathsf {T}}}}}$ R O T . Since constant-round semi-honest oblivious transfer protocols can be constructed under standard assumptions (such as the existence of enhanced trapdoor permutations), our result gives a $\widetilde{O}(\log ^2n)$ O ~ ( log 2 n ) -round protocol under these assumptions. Previously, only an $O(\max (n^{\epsilon }, R_{{{{\mathsf {O}}}{{\mathsf {T}}}}}))$ O ( max ( n ϵ , R O T ) ) -round protocol was shown, where $\epsilon >0$ ϵ > 0 is an arbitrary constant. We obtain our MPC protocol by constructing a $\widetilde{O}(\log ^2n)$ O ~ ( log 2 n ) -round CCA-secure commitment scheme in a black-box way under the assumption of the existence of one-way functions.
2018
EUROCRYPT
2018
TCC
In this paper, we give a no-signaling linear probabilistically checkable proof (PCP) system for polynomial-time deterministic computation, i.e., a PCP system for ${\mathcal {P}}$P such that (1) the PCP oracle is a linear function and (2) the soundness holds against any (computational) no-signaling cheating prover, who is allowed to answer each query according to a distribution that depends on the entire query set in a certain way. To the best of our knowledge, our construction is the first PCP system that satisfies these two properties simultaneously.As an application of our PCP system, we obtain a 2-message scheme for delegating computation by using a known transformation. Compared with existing 2-message delegation schemes based on standard cryptographic assumptions, our scheme requires preprocessing but has a simpler structure and makes use of different (possibly cheaper) standard cryptographic primitives, namely additive/multiplicative homomorphic encryption schemes.
2017
EUROCRYPT
2017
TCC
2016
EUROCRYPT
2015
EPRINT
2015
EPRINT
2015
TCC
2015
CRYPTO
2015
ASIACRYPT
2014
CRYPTO
2014
TCC
2014
EPRINT

Eurocrypt 2020
TCC 2019