## CryptoDB

### Hong-Sheng Zhou

#### Publications

Year
Venue
Title
2020
JOFC
Non-malleable codes, introduced as a relaxation of error-correcting codes by Dziembowski, Pietrzak, and Wichs (ICS ’10), provide the security guarantee that the message contained in a tampered codeword is either the same as the original message or is set to an unrelated value. Various applications of non-malleable codes have been discovered, and one of the most significant applications among these is the connection with tamper-resilient cryptography. There is a large body of work considering security against various classes of tampering functions, as well as non-malleable codes with enhanced features such as leakage resilience . In this work, we propose combining the concepts of non-malleability , leakage resilience , and locality in a coding scheme. The contribution of this work is threefold: 1. As a conceptual contribution, we define a new notion of locally decodable and updatable non-malleable code that combines the above properties. 2. We present two simple and efficient constructions achieving our new notion with different levels of security. 3. We present an important application of our new tool—securing RAM computation against memory tampering and leakage attacks. This is analogous to the usage of traditional non-malleable codes to secure implementations in the circuit model against memory tampering and leakage attacks.
2019
PKC
We study how to construct secure digital signature schemes in the presence of kleptographic attacks. Our work utilizes an offline watchdog to clip the power of subversions via only one-time black-box testing of the implementation. Previous results essentially rely on an online watchdog which requires the collection of all communicating transcripts (or active re-randomization of messages).We first give a simple but generic construction, without random oracles, in the partial-subversion model in which key generation and signing algorithms can be subverted. Then, we give the first digital signature scheme in the complete-subversion model in which all cryptographic algorithms can be subverted. This construction is based on the full-domain hash. Along the way, we enhance the recent result of Russell et al.  (CRYPTO 2018) about correcting a subverted random oracle.
2019
JOFC
We continue the line of work initiated by Katz (Eurocrypt 2007) on using tamper-proof hardware tokens for universally composable secure computation. As our main result, we show an oblivious-transfer (OT) protocol in which two parties each create and transfer a single, stateless token and can then run an unbounded number of OTs. We also show a more efficient protocol, based only on standard symmetric-key primitives (block ciphers and collision-resistant hash functions), that can be used if a bounded number of OTs suffice. Motivated by this result, we investigate the number of stateless tokens needed for universally composable OT. We prove that our protocol is optimal in this regard for constructions making black-box use of the tokens (in a sense we define). We also show that nonblack-box techniques can be used to obtain a construction using only a single stateless token.
2019
JOFC
The literature on leakage-resilient cryptography contains various leakage models that provide different levels of security. In the bounded leakage model (Akavia et al.—TCC 2009 ), it is assumed that there is a fixed upper bound L on the number of bits the attacker may leak on the secret key in the entire lifetime of the scheme. Alternatively, in the continual leakage model (Brakerski et al.—FOCS 2010 , Dodis et al.—FOCS 2010 ), the lifetime of a cryptographic scheme is divided into “time periods” between which the scheme’s secret key is updated. Furthermore, in its attack the adversary is allowed to obtain some bounded amount of leakage on the current secret key during each time period. In the continual leakage model, a challenging problem has been to provide security against leakage on key updates , that is, leakage that is a function of not only the current secret key but also the randomness used to update it. We propose a modular approach to overcome this problem based on program obfuscation. Namely, we present a compiler that transforms any public key encryption or signature scheme that achieves a slight strengthening of continual leakage resilience, which we call consecutive continual leakage resilience, to one that is continual leakage resilient with leakage on key updates, assuming indistinguishability obfuscation (Barak et al.—CRYPTO 2001 , Garg et al.—FOCS 2013 ). Under stronger forms of obfuscation, the leakage rate tolerated by our compiled scheme is essentially as good as that of the starting scheme. Our compiler is derived by making a connection between the problems of leakage on key updates and so-called sender-deniable encryption (Canetti et al.—CRYPTO 1997 ), which was recently constructed based on indistinguishability obfuscation by Sahai and Waters (STOC 2014 ). In the bounded leakage model, we give an approach to constructing leakage-resilient public key encryption from program obfuscation based on the public key encryption scheme of Sahai and Waters (STOC 2014 ). In particular, we achieve leakage-resilient public key encryption tolerating L bits of leakage for any L from ${\mathsf {iO}}$ iO and one-way functions. We build on this to achieve leakage-resilient public key encryption with optimal leakage rate of $1-o(1)$ 1 - o ( 1 ) based on stronger forms of obfuscation and collision-resistant hash functions. Such a leakage rate is not known to be achievable in a generic way based on public key encryption alone. We then develop additional techniques to construct public key encryption that is (consecutive) continual leakage resilient under appropriate assumptions, which we believe is of independent interest.
2018
CRYPTO
The random oracle methodology has proven to be a powerful tool for designing and reasoning about cryptographic schemes, and can often act as an effective bridge between theory and practice. In this paper, we focus on the basic problem of correcting faulty—or adversarially corrupted—random oracles, so that they can be confidently applied for such cryptographic purposes.We prove that a simple construction can transform a “subverted” random oracle—which disagrees with the original one at a negligible fraction of inputs—into a construction that is indifferentiable from a random function. Our results permit future designers of cryptographic primitives in typical kleptographic settings (i.e., with adversaries who may subvert the implementation of cryptographic algorithms but undetectable via blackbox testing) to use random oracles as a trusted black box, in spite of not trusting the implementation. Our analysis relies on a general rejection re-sampling lemma which is a tool of possible independent interest.
2018
ASIACRYPT
In this work, we develop a framework for building leakage-resilient cryptosystems in the bounded leakage model from puncturable primitives and indistinguishability obfuscation ( $i\mathcal {O}$ ). The major insight of our work is that various types of puncturable pseudorandom functions (PRFs) can achieve leakage resilience on an obfuscated street.First, we build leakage-resilient weak PRFs from weak puncturable PRFs and $i\mathcal {O}$ , which readily imply leakage-resilient secret-key encryption. Then, we build leakage-resilient publicly evaluable PRFs (PEPRFs) from puncturable PEPRFs and $i\mathcal {O}$ , which readily imply leakage-resilient key encapsulation mechanism and thus public-key encryption. As a building block of independent interest, we realize puncturable PEPRFs from either newly introduced puncturable objects such as puncturable trapdoor functions and puncturable extractable hash proof systems or existing puncturable PRFs with $i\mathcal {O}$ . Finally, we construct the first leakage-resilient public-coin signature from selective puncturable PRFs, leakage-resilient one-way functions and $i\mathcal {O}$ . This settles the open problem posed by Boyle, Segev, and Wichs (Eurocrypt 2011).By further assuming the existence of lossy functions, all the above constructions achieve optimal leakage rate of $1 - o(1)$ . Such a leakage rate is not known to be achievable for weak PRFs, PEPRFs and public-coin signatures before. This also resolves the open problem posed by Dachman-Soled, Gordon, Liu, O’Neill, and Zhou (PKC 2016, JOC 2018).
2016
EUROCRYPT
2016
PKC
2016
ASIACRYPT
2016
TCC
2015
TCC
2015
TCC
2015
EUROCRYPT
2015
CRYPTO
2014
EUROCRYPT
2014
TCC
2013
PKC
2013
PKC
2013
TCC
2013
ASIACRYPT
2012
TCC
2009
PKC
2009
CRYPTO
2008
TCC

Asiacrypt 2021
PKC 2020
TCC 2017
Asiacrypt 2014
Asiacrypt 2010