International Association
for Cryptologic Research

<p>Salient in many cryptosystems, the exponent-inversion technique began without randomization in the random oracle model (SCIS '03, PKC '04), evolved into the Boneh-Boyen short signature scheme (JoC '08) and exerted a wide influence. Seen as a notable case, Gentry's (EuroCrypt '06) identity-based encryption (IBE) applies exponent inversion on a randomized base in its identity-based trapdoors. Making use of the non-static q-strong Diffie-Hellman assumption, Boneh-Boyen signatures are shown to be unforgeable against q-chosen-message attacks, while a variant q-type decisional assumption is used to establish the security of Gentry-IBE. Challenges remain in proving their security under weaker static assumptions.</p><p>Supported by the dual form/system framework (Crypto '09, AsiaCrypt '12), we propose dual form exponent-inversion Boneh-Boyen signatures and Gentry-IBE, with security proven under the symmetric external Diffie-Hellman (SXDH) assumption. Starting from our signature scheme, we extend it into P-signatures (TCC '08), resulting in the first anonymous credential scheme from the SXDH assumption, serving as a competitive alternative to the static-assumption construction of Abe et al. (JoC '16). Moreover, from our Gentry-IBE variant, we propose an accountable-authority IBE scheme also from SXDH, surpassing the fully secure Sahai-Seyalioglu scheme (PKC '11) in efficiency and the generic Kiayias-Tang transform (ESORICS '15) in security. Collectively, we present a suite of results under static assumptions. </p>

We formally study “non-malleable functions” (NMFs), a general cryptographic primitive which simplifies and relaxes “non-malleable one-way/hash functions” (NMOWHFs) introduced by Boldyreva et al. (in: Advances in cryptology—ASIACRYPT 2009, pp 524–541, 2009) and refined by Baecher et al. (in: CT-RSA 2011, pp 268–283, 2011). NMFs focus on basic functions, rather than one-way/hash functions considered in the literature of NMOWHFs. We formalize a game-based definition for NMFs. Roughly, a function f is non-malleable if given an image $$y^* \leftarrow f(x^*)$$ y ∗ ← f ( x ∗ ) for a randomly chosen $$x^*$$ x ∗ , it is hard to output a value y together with a transformation $$\phi $$ ϕ from some prefixed transformation class such that y is an image of $$\phi (x^*)$$ ϕ ( x ∗ ) under f . Our non-malleable notion is strong in the sense that only trivial copy solution $$(\mathsf {id}, y^*)$$ ( id , y ∗ ) is forbidden, where $$\mathsf {id}$$ id is the identity transformation. We also consider the adaptive notion, which stipulates that non-malleability holds even when an inversion oracle is available. We investigate the relations between non-malleability and one-wayness in depth. In the non-adaptive setting, we show that non-malleability generally implies one-wayness for poly-to-one functions but not vice versa. In the adaptive setting, we show that for most algebra-induced transformation classes, adaptive non-malleability (ANM) is equivalent to adaptive one-wayness (AOW) for injective functions. These results establish theoretical connections between non-malleability and one-wayness for functions and extend to trapdoor functions as well, resolving the open problems left by Kiltz et al. (in: Advances in cryptology—EUROCRYPT 2010, pp 673–692, 2010). We also study the relations between standard OW/NM and hinting OW/NM, where the latter notions are typically more useful in practice. Toward efficient realizations of NMFs, we give a deterministic construction from adaptive trapdoor functions as well as a randomized construction from all-but-one lossy functions and one-time signature. This partially solves an open problem posed by Boldyreva et al. (in: Advances in cryptology—ASIACRYPT 2009, pp 524–541, 2009). Finally, we explore applications of NMFs in security against related-key attacks (RKA). We first show that, somewhat surprisingly, the implication AOW $$\Rightarrow $$ ⇒ ANM sheds light on addressing non-trivial copy attacks in RKA security. We then show that NMFs give rise to a generic construction of RKA-secure authenticated key derivation functions, which have proven to be very useful in achieving RKA security for numerous cryptographic primitives. Particularly, our construction simplifies and unifies the result due to Qin et al. (in: Public-key cryptography—PKC 2015, volume 9020 of LNCS. Springer, Berlin, pp 557–578, 2015).

Oblivious RAM enables oblivious access to memory in the single-client setting, which may not be the best fit in the network setting. Multi-client oblivious RAM (MCORAM) considers a collaborative but untrusted environment, where a database owner selectively grants read access and write access to different entries of a confidential database to multiple clients. Their access pattern must remain oblivious not only to the server but also to fellow clients. This upgrade rules out many techniques for constructing ORAM, forcing us to pursue new techniques. MCORAM not only provides an alternative solution to private anonymous data access (Eurocrypt 2019) but also serves as a promising building block for equipping oblivious file systems with access control and extending other advanced cryptosystems to the multi-client setting. Despite being a powerful object, the current state-of-the-art is unsatisfactory: The only existing scheme requires $O(\sqrt n)$ communication and client computation for a database of size $n$. Whether it is possible to reduce these complexities to $\mathsf{polylog}(n)$, thereby matching the upper bounds for ORAM, is an open problem, i.e., can we enjoy access control and client-obliviousness under the same bounds? Our first result answers the above question affirmatively by giving a construction from fully homomorphic encryption (FHE). Our main technical innovation is a new technique for cross-key trial evaluation of ciphertexts. We also consider the same question in the setting with $N$ non-colluding servers, out of which at most $t$ of them can be corrupt. We build multi-server MCORAM from distributed point functions (DPF), and propose new constructions of DPF via a virtualization technique with bootstrapping, assuming the existence of homomorphic secret sharing and pseudorandom generators in NC0, which are not known to imply FHE.

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.

Homomorphic signatures (HS) allows the derivation of the signature of the message-function pair (m, g), where $$m = g(m_1, \ldots , m_K)$$, given the signatures of each of the input messages $$m_k$$ signed under the same key. Multi-key HS (M-HS) introduced by Fiore et al.  (ASIACRYPT’16) further enhances the utility by allowing evaluation of signatures under different keys. The unforgeability of existing M-HS notions assumes that all signers are honest. We consider a setting where an arbitrary number of signers can be corrupted, called unforgeability under corruption, which is typical for natural applications (e.g., verifiable multi-party computation) of M-HS. Surprisingly, there is a huge gap between M-HS (for arbitrary circuits) with and without unforgeability under corruption: While the latter can be constructed from standard lattice assumptions (ASIACRYPT’16), we show that the former likely relies on non-falsifiable assumptions. Specifically, we propose a generic construction of M-HS with unforgeability under corruption from zero-knowledge succinct non-interactive argument of knowledge (ZK-SNARK) (and other standard assumptions), and then show that such M-HS implies zero-knowledge succinct non-interactive arguments (ZK-SNARG). Our results leave open the pressing question of what level of authenticity and utility can be achieved in the presence of corrupt signers under standard assumptions.