nach oben

2023 | Buch

Kapitel lesen Erstes Kapitel lesen

Theory of Cryptography

21st International Conference, TCC 2023, Taipei, Taiwan, November 29 – December 2, 2023, Proceedings, Part I

herausgegeben von: Guy Rothblum, Hoeteck Wee

Verlag: Springer Nature Switzerland

Buchreihe : Lecture Notes in Computer Science

Enthalten in: Springer Professional "Wirtschaft+Technik" , Springer Professional "Technik" , Springer Professional "Wirtschaft"

Einloggen, um Zugang zu erhalten

Über dieses Buch

The four-volume set LNCS 14369 until 14372 constitutes the refereed proceedings of the 21st International Conference on Theory of Cryptography, TCC 2023, held in Taipei, Taiwan, in November/December 2023. The total of 68 full papers presented in the proceedings was carefully reviewed and selected from 168 submissions. They focus on topics such as proofs and outsourcing; theoretical foundations; multi-party computation; encryption; secret sharing, PIR and memory checking; anonymity, surveillance and tampering; lower bounds; IOPs and succinctness; lattices; quantum cryptography; Byzantine agreement, consensus and composability.

Inhaltsverzeichnis

Frontmatter

Proofs and Outsourcing

Frontmatter

Beyond MPC-in-the-Head: Black-Box Constructions of Short Zero-Knowledge Proofs

Abstract

In their seminal work, Ishai, Kushilevitz, Ostrovsky, and Sahai (STOC‘07) presented the MPC-in-the-Head paradigm, which shows how to design Zero-Knowledge Proofs (ZKPs) from secure Multi-Party Computation (MPC) protocols. This paradigm has since then revolutionized and modularized the design of efficient ZKP systems, with far-reaching applications beyond ZKPs. However, to the best of our knowledge, all previous instantiations relied on fully-secure MPC protocols and have not been able to leverage the fact that the paradigm only imposes relatively weak privacy and correctness requirements on the underlying MPC.

In this work, we extend the MPC-in-the-Head paradigm to game-based cryptographic primitives supporting homomorphic computations (e.g., fully-homomorphic encryption, functional encryption, randomized encodings, homomorphic secret sharing, and more). Specifically, we present a simple yet generic compiler from these primitives to ZKPs which use the underlying primitive as a black box. We also generalize our paradigm to capture commit-and-prove protocols, and use it to devise tight black-box compilers from Interactive (Oracle) Proofs to ZKPs, assuming One-Way Functions (OWFs).

We use our paradigm to obtain several new ZKP constructions:

1. The first ZKPs for \(\textsf {NP}\) relations \(\mathcal{R}\) computable in (polynomial-time uniform) \(\textsf{NC}^1\), whose round complexity is bounded by a fixed constant (independent of the depth of \(\mathcal{R}\)’s verification circuit), with communication approaching witness length (specifically, \(n\cdot {\textsf{poly}}\left( \kappa \right) \), where n is the witness length, and \(\kappa \) is a security parameter), assuming DCR. Alternatively, if we allow the round complexity to scale with the depth of the verification circuit, our ZKPs can make black-box use of OWFs.

2. Constant-round ZKPs for NP relations computable in bounded polynomial space, with \(O\left( n\right) +o\left( m\right) \cdot {\textsf{poly}}\left( \kappa \right) \) communication assuming OWFs, where m is the instance length. This gives a black-box alternative to a recent non-black-box construction of Nassar and Ron (CRYPTO‘22).

3. ZKPs for NP relations computable by a logspace-uniform family of depth-\(d\left( m\right) \) circuits, with \(n\cdot {\textsf{poly}}\left( \kappa ,d\left( m\right) \right) \) communication assuming OWFs. This gives a black-box alternative to a result of Goldwasser, Kalai and Rothblum (JACM).

Carmit Hazay, Muthuramakrishnan Venkitasubramaniam, Mor Weiss

Your Reputation’s Safe with Me: Framing-Free Distributed Zero-Knowledge Proofs

Abstract

Distributed Zero-Knowledge (dZK) proofs, recently introduced by Boneh et al. (CRYPTO‘19), allow a prover \(\mathcal{P}\) to prove NP statements on an input x which is distributed between k verifiers \(\mathcal{V}_1,\ldots ,\mathcal{V}_k\), where each \(\mathcal{V}_i\) holds only a piece of x. As in standard ZK proofs, dZK proofs guarantee Completeness when all parties are honest; Soundness against a malicious prover colluding with t verifiers; and Zero Knowledge against a subset of t malicious verifiers, in the sense that they learn nothing about the NP witness and the input pieces of the honest verifiers.

Unfortunately, dZK proofs provide no correctness guarantee for an honest prover against a subset of maliciously corrupted verifiers. In particular, such verifiers might be able to “frame” the prover, causing honest verifiers to reject a true claim. This is a significant limitation, since such scenarios arise naturally in dZK applications, e.g., for proving honest behavior, and such attacks are indeed possible in existing dZKs (Boneh et al., CRYPTO‘19).

We put forth and study the notion of strong completeness for dZKs, guaranteeing that true claims are accepted even when t verifiers are maliciously corrupted. We then design strongly-complete dZK proofs using the “MPC-in-the-head” paradigm of Ishai et al. (STOC‘07), providing a novel analysis that exploits the unique properties of the distributed setting.

To demonstrate the usefulness of strong completeness, we present several applications in which it is instrumental in obtaining security. First, we construct a certifiable version of Verifiable Secret Sharing (VSS), which is a VSS in which the dealer additionally proves that the shared secret satisfies a given NP relation. Our construction withstands a constant fraction of corruptions, whereas a previous construction of Ishai et al. (TCC‘14) required \(k={\textsf{poly}}\left( t\right) \). We also design a reusable version of certifiable VSS that we introduce, in which the dealer can prove an unlimited number of predicates on the same shared secret.

Finally, we extend a compiler of Boneh et al. (CRYPTO‘19), who used dZKs to transform a class of “natural” semi-honest protocols in the honest-majority setting into maliciously secure ones with abort. Our compiler uses strongly-complete dZKs to obtain identifiable abort.

Carmit Hazay, Muthuramakrishnan Venkitasubramaniam, Mor Weiss

Locally Verifiable Distributed SNARGs

Abstract

The field of distributed certification is concerned with certifying properties of distributed networks, where the communication topology of the network is represented as an arbitrary graph; each node of the graph is a separate processor, with its own internal state. To certify that the network satisfies a given property, a prover assigns each node of the network a certificate, and the nodes then communicate with one another and decide whether to accept or reject. We require soundness and completeness: the property holds if and only if there exists an assignment of certificates to the nodes that causes all nodes to accept. Our goal is to minimize the length of the certificates, as well as the communication between the nodes of the network. Distributed certification has been extensively studied in the distributed computing community, but it has so far only been studied in the information-theoretic setting, where the prover and the network nodes are computationally unbounded.

In this work we introduce and study computationally bounded distributed certification: we define locally verifiable distributed \(\textsf{SNARG}\)s (

https://static-content.springer.com/image/chp%3A10.1007%2F978-3-031-48615-9_3/MediaObjects/549757_1_En_3_Figa_HTML.gif

s), which are an analog of \(\textsf{SNARG}\)s for distributed networks, and are able to circumvent known hardness results for information-theoretic distributed certification by requiring both the prover and the verifier to be computationally efficient (namely, PPT algorithms).

We give two

https://static-content.springer.com/image/chp%3A10.1007%2F978-3-031-48615-9_3/MediaObjects/549757_1_En_3_Figb_HTML.gif

constructions: the first allows us to succinctly certify any network property in \({\textsf{P}}\), using a global prover that can see the entire network; the second construction gives an efficient distributed prover, which succinctly certifies the execution of any efficient distributed algorithm. Our constructions rely on non-interactive batch arguments for \({\textsf{NP}}\) (\(\textsf{BARG}\)s) and on \(\textsf{RAM}~\textsf{SNARG}\)s, which have recently been shown to be constructible from standard cryptographic assumptions.

Eden Aldema Tshuva, Elette Boyle, Ran Cohen, Tal Moran, Rotem Oshman

Distributed-Prover Interactive Proofs

Abstract

Interactive proof systems enable a verifier with limited resources to decide an intractable language (or compute a hard function) by communicating with a powerful but untrusted prover. Such systems guarantee soundness: the prover can only convince the verifier of true statements. This is a central notion in computer science with far-reaching implications. One key drawback of the classical model is that the data on which the prover operates must be held by a single machine.

In this work, we initiate the study of distributed-prover interactive proofs (dpIPs): an untrusted cluster of machines, acting as a distributed prover, interacts with a single verifier. The machines in the cluster jointly store and operate on a massive data-set that no single machine can store. The goal is for the machines in the cluster to convince the verifier of the validity of some statement about its data-set. We formalize the communication and space constraints via the massively parallel computation (MPC) model, a widely accepted analytical framework capturing the computational power of massive data-centers.

Our main result is a compiler that generically augments any verification algorithm in the MPC model with a (computational) soundness guarantee. Concretely, for any language L for which there is an MPC algorithm verifying whether \(x \in L\), we design a new MPC protocol capable of convincing a verifier of the validity of \(x \in L\) and where if \(x\not \in L\), the verifier rejects with overwhelming probability. The new protocol requires only slightly more rounds, i.e., a \(\textsf{poly}(\log N)\) blowup, and a slightly bigger memory per machine, i.e., \(\textsf{poly}(\lambda )\) blowup, where N is the total size of the dataset and \(\lambda \) is a security parameter independent of N.

En route, we introduce distributed-prover interactive oracle proofs (dpIOPs), a natural adaptation of the (by now classical) IOP model to the distributed prover setting. We design a dpIOP for verification algorithms in the MPC model and then translate them to “plain model” dpIPs via an adaptation of existing polynomial commitment schemes into the distributed prover setting.

Sourav Das, Rex Fernando, Ilan Komargodski, Elaine Shi, Pratik Soni

Rogue-Instance Security for Batch Knowledge Proofs

Abstract

We propose a new notion of knowledge soundness, denoted rogue-instance security, for interactive and non-interactive batch knowledge proofs. Our notion, inspired by the standard notion of rogue-key security for multi-signature schemes, considers a setting in which a malicious prover is provided with an honestly-generated instance \(\mathbb {x}_1\), and may then be able to maliciously generate related “rogue” instances \(\mathbb {x}_2,\ldots ,\mathbb {x}_{k}\) for convincing a verifier in a batch knowledge proof of corresponding witnesses \(\mathbb {w}_1,\ldots ,\mathbb {w}_{k}\) for all k instances – without actually having knowledge of the witness \(\mathbb {w}_1\) corresponding to the honestly-generated instance. This setting provides a powerful security guarantee for batch versions of a wide variety of practically-relevant protocols, such as Schnorr’s protocol and similar ones.

We present a highly-efficient generic construction of a batch proof-of-knowledge applicable to any algebraic Sigma protocols. The algebraic property refers to a homomorphic structure of the underlying group and includes Schnorr’s protocol and others. We provide an almost tight security analysis for our generic batch protocol, which significantly improves upon the previously known security bounds even for the specific case of batch Schnorr protocol. We extend our results beyond algebraic Sigma protocols. We analyze the rogue-instance security of a general batch protocol with plus-one special soundness (a generalization of standard special soundness) and achieve improved security bounds in the generic case.

Our results use a particular type of high-moment assumptions introduced by Rotem and Segev (CRYPTO 2021). These assumptions consider the hardness of a relation against algorithms with bounded expected running time. Although Rotem and Segev introduced these assumptions, they did not provide evidence to support their hardness. To substantiate and validate the high-moment assumptions, we present a new framework for assessing the concrete hardness of cryptographic problems against oracle algorithms with bounded expected runtime. Our framework covers generic models, including the generic group model, random oracle model, and more. Utilizing our framework, we achieve the first hardness result for these high-moment assumptions. In particular, we establish the second-moment hardness of the discrete-logarithm problem against expected-time algorithms in the generic group model.

Gil Segev, Amit Sharabi, Eylon Yogev

On Black-Box Verifiable Outsourcing

Abstract

We study verifiable outsourcing of computation in a model where the verifier has black-box access to the function being computed. We introduce the problem of oracle-aided batch verification of computation (OBVC) for a function class \(\mathcal {F}\). This allows a verifier to efficiently verify the correctness of any \(f \in \mathcal {F}\) evaluated on a batch of n instances \(x_1, \ldots , x_n\), while only making \(\lambda \) calls to an oracle for f (along with \(O(n \lambda )\) calls to low-complexity helper oracles), for security parameter \(\lambda \). We obtain the following positive and negative results:

We build OBVC protocols for the class of all functions that admit random-self-reductions. Some of our protocols rely on homomorphic encryption schemes.
We show that there cannot exist OBVC schemes for the class of all functions mapping \(\lambda \)-bit inputs to \(\lambda \)-bit outputs, for any \(n = \textsf{poly} (\lambda )\).\(^{1}\)(\(^{1}\) The authors grant IACR a non-exclusive and irrevocable license to distribute the article under the https://creativecommons.org/licenses/by-nc/3.0/.)

Amit Agarwal, Navid Alamati, Dakshita Khurana, Srinivasan Raghuraman, Peter Rindal

Theoretical Foundations

Frontmatter

Counting Unpredictable Bits: A Simple PRG from One-Way Functions

Abstract

A central result in the theory of Cryptography, by Håstad, Imagliazzo, Luby and Levin [SICOMP’99], demonstrates that the existence one-way functions (OWF) implies the existence of pseudo-random generators (PRGs). Despite the fundamental importance of this result, and several elegant improvements/simplifications, analyses of constructions of PRGs from OWFs remain complex (both conceptually and technically).

Our goal is to provide a construction of a PRG from OWFs with a simple proof of security; we thus focus on the setting of non-uniform security (i.e., we start off with a OWF secure against non-uniform PPT, and we aim to get a PRG secure against non-uniform PPT).

Our main result is a construction of a PRG from OWFs with a self-contained, simple, proof of security, relying only on the Goldreich-Levin Theorem (and the Chernoff bound). Although our main goal is simplicity, the construction, and a variant there-of, also improves the efficiency—in terms of invocations and seed lengths—of the state-of-the-art constructions due to [Haitner-Reingold-Vadhan, STOC’10] and [Vadhan-Zheng, STOC’12], by a factor \(O(\log ^2 n)\).

The key novelty in our analysis is a generalization of the Blum-Micali [FOCS’82] notion of unpredictabilty—rather than requiring that every bit in the output of a function is unpredictable, we count how many unpredictable bits a function has, and we show that any OWF on n input bits (after hashing the input and the output) has \(n+O(\log n)\) unpredictable output bits. Such unpredictable bits can next be “extracted” into a pseudorandom string using standard techniques.

Noam Mazor, Rafael Pass

On One-Way Functions and Sparse Languages

Abstract

We show equivalence between the existence of one-way functions and the existence of a sparse language that is hard-on-average w.r.t. some efficiently samplable “high-entropy” distribution. In more detail, the following are equivalent:

The existence of a \(S(\cdot )\)-sparse language L that is hard-on-average with respect to some samplable distribution with Shannon entropy \(h(\cdot )\) such that \(h(n)-\log (S(n)) \ge 4\log n\);
The existence of a \(S(\cdot )\)-sparse language \(L \in \textsf{NP}\), that is hard-on-average with respect to some samplable distribution with Shannon entropy \(h(\cdot )\) such that \(h(n)-\log (S(n)) \ge n/3\);
The existence of one-way functions.

where a language L is said to be \(S(\cdot )\)-sparse if \(|L \cap \{0,1\}^n| \le S(n)\) for all \(n \in \mathbb {N}\). Our results are inspired by, and generalize, results from the elegant recent paper by Ilango, Ren and Santhanam (IRS, STOC’22), which presents similar connections for specific sparse languages.

Yanyi Liu, Rafael Pass

Security Proofs for Key-Alternating Ciphers with Non-Independent Round Permutations

Abstract

This work studies the key-alternating ciphers (KACs) whose round permutations are not necessarily independent. We revisit existing security proofs for key-alternating ciphers with a single permutation (KACSPs), and extend their method to an arbitrary number of rounds. In particular, we propose new techniques that can significantly simplify the proofs, and also remove two unnatural restrictions in the known security bound of 3-round KACSP (Wu et al., Asiacrypt 2020). With these techniques, we prove the first tight security bound for t-round KACSP, which was an open problem. We stress that our techniques apply to all variants of KACs with non-independent round permutations, as well as to the standard KACs.

Liqing Yu, Yusai Wu, Yu Yu, Zhenfu Cao, Xiaolei Dong

Public-Key Encryption, Local Pseudorandom Generators, and the Low-Degree Method

Abstract

The low-degree method postulates that no efficient algorithm outperforms low-degree polynomials in certain hypothesis-testing tasks. It has been used to understand computational indistinguishability in high-dimensional statistics.

We explore the use of the low-degree method in the context of cryptography. To this end, we apply it in the design and analysis of a new public-key encryption scheme whose security is based on Goldreich’s pseudorandom generator. The scheme is a combination of two proposals of Applebaum, Barak, and Wigderson, and inherits desirable features from both.

Andrej Bogdanov, Pravesh K. Kothari, Alon Rosen

Cryptography from Planted Graphs: Security with Logarithmic-Size Messages

Abstract

We study the following broad question about cryptographic primitives: is it possible to achieve security against arbitrary \(\textsf{poly}(n)\)-time adversary with \(O(\log n)\)-size messages? It is common knowledge that the answer is “no” unless information-theoretic security is possible. In this work, we revisit this question by considering the setting of cryptography with public information and computational security.

We obtain the following main results, assuming variants of well-studied intractability assumptions:

A private simultaneous messages (PSM) protocol for every \(f:[n]\times [n]\rightarrow \{0,1\}\) with \((1+\epsilon )\log n\)-bit messages, beating the known lower bound on information-theoretic PSM protocols. We apply this towards non-interactive secure 3-party computation with similar message size in the preprocessing model, improving over previous 2-round protocols.
A secret-sharing scheme for any “forbidden-graph” access structure on n nodes with \(O(\log n)\) share size.
On the negative side, we show that computational threshold secret-sharing schemes with public information require share size \(\varOmega (\log \log n)\). For arbitrary access structures, we show that computational security does not help with 1-bit shares.

The above positive results guarantee that any adversary of size \(n^{o(\log n)}\) achieves an \(n^{-\varOmega (1)}\) distinguishing advantage. We show how to make the advantage negligible by slightly increasing the asymptotic message size, still improving over all known constructions.

The security of our constructions is based on the conjectured hardness of variants of the planted clique problem, which was extensively studied in the algorithms, statistical inference, and complexity theory communities. Our work provides the first applications of such assumptions to improving the efficiency of mainstream cryptographic primitives, gives evidence for the necessity of such assumptions, and suggests new questions in this domain that may be of independent interest.

Damiano Abram, Amos Beimel, Yuval Ishai, Eyal Kushilevitz, Varun Narayanan

Multi-party Computation I

Frontmatter

Randomized Functions with High Round Complexity

Abstract

Consider two-party secure function evaluation against an honest-but-curious adversary in the information-theoretic plain model. We study the round complexity of securely realizing a given secure function evaluation functionality.

Chor-Kushilevitz-Beaver (1989) proved that the round complexity of securely evaluating a deterministic function depends solely on the cardinality of its domain and range. A natural conjecture asserts that this phenomenon extends to functions with randomized output.

Our work falsifies this conjecture – revealing intricate subtleties even for this elementary security notion. For every r, we construct a function \(f_r\) with binary inputs and five output alphabets that has round complexity r. Previously, such a construction was known using \((r+1)\) output symbols. Our counter-example is optimal – we prove that any securely realizable function with binary inputs and four output alphabets has round complexity at most four.

We work in the geometric framework Basu-Khorasgani-Maji-Nguyen (FOCS–2022) introduced to investigate randomized functions’ round complexity. Our work establishes a connection between secure computation and the lamination hull (geometric object originally motivated by applications in hydrodynamics). Our counterexample constructions are related to the “tartan square” construction in the lamination hull literature.

Saugata Basu, Hamidreza Amini Khorasgani, Hemanta K. Maji, Hai H. Nguyen

Towards Topology-Hiding Computation from Oblivious Transfer

Abstract

Topology-Hiding Computation (THC) enables parties to securely compute a function on an incomplete network without revealing the network topology. It is known that secure computation on a complete network can be based on oblivious transfer (OT), even if a majority of the participating parties are corrupt. In contrast, THC in the dishonest majority setting is only known from assumptions that imply (additively) homomorphic encryption, such as Quadratic Residuosity, Decisional Diffie-Hellman, or Learning With Errors.

In this work we move towards closing the gap between MPC and THC by presenting a protocol for THC on general graphs secure against all-but-one semi-honest corruptions from constant-round constant-overhead secure two-party computation. Our protocol is therefore the first to achieve THC on arbitrary networks without relying on assumptions with rich algebraic structure. As a technical tool, we introduce the notion of locally simulatable MPC, which we believe to be of independent interest.

Marshall Ball, Alexander Bienstock, Lisa Kohl, Pierre Meyer

On the Impossibility of Surviving (Iterated) Deletion of Weakly Dominated Strategies in Rational MPC

Abstract

Rational multiparty computation (rational MPC) provides a framework for analyzing MPC protocols through the lens of game theory. One way to judge whether an MPC protocol is rational is through weak domination: Rational players would not adhere to an MPC protocol if deviating never decreases their utility, but sometimes increases it.

Secret reconstruction protocols are of particular importance in this setting because they represent the last phase of most (rational) MPC protocols. We show that most secret reconstruction protocols from the literature are not, in fact, stable with respect to weak domination. Furthermore, we formally prove that (under certain assumptions) it is impossible to design a secret reconstruction protocol which is a Nash equilibrium but not weakly dominated if (1) shares are authenticated or (2) half of all players may form a coalition.

Johannes Blömer, Jan Bobolz, Henrik Bröcher

Synchronizable Fair Exchange

Abstract

Fitzi, Garay, Maurer, and Ostrovsky (J. Cryptology 2005) showed that in the presence of a dishonest majority, no primitive of cardinality \(n - 1\) is complete for realizing an arbitrary n-party functionality with guaranteed output delivery. In this work, we introduce a new 2-party primitive \(\mathcal {F}_{\textsf{SyX}}\) (“synchronizable fair exchange”) and show that it is complete for realizing any n-party functionality with fairness in a setting where all parties are pairwise connected by instances of \(\mathcal {F}_{\textsf{SyX}}\).

In the \(\mathcal {F}_{\textsf{SyX}}\)-hybrid model, the two parties load \(\mathcal {F}_{\textsf{SyX}}\) with some input, and following this, either party can trigger \(\mathcal {F}_{\textsf{SyX}}\) with a “witness” at a later time to receive the output from \(\mathcal {F}_{\textsf{SyX}}\). Crucially the other party also receives output from \(\mathcal {F}_{\textsf{SyX}}\) when \(\mathcal {F}_{\textsf{SyX}}\) is triggered. The trigger witnesses allow us to synchronize the trigger phases of multiple instances of \(\mathcal {F}_{\textsf{SyX}}\), thereby aiding in the design of fair multiparty protocols. Additionally, a pair of parties may reuse a single a priori loaded instance of \(\mathcal {F}_{\textsf{SyX}}\) in any number of multiparty protocols (involving different sets of parties). (The authors grant IACR a non-exclusive and irrevocable license to distribute the article under the https://creativecommons.org/licenses/by-nc/3.0/), (This work was done in part while all the authors were at MIT).

Ranjit Kumaresan, Srinivasan Raghuraman, Adam Sealfon

DORAM Revisited: Maliciously Secure RAM-MPC with Logarithmic Overhead

Abstract

Distributed Oblivious Random Access Memory (DORAM) is a secure multiparty protocol that allows a group of participants holding a secret-shared array to read and write to secret-shared locations within the array. The efficiency of a DORAM protocol is measured by the amount of communication required per read/write query into the array. DORAM protocols are a necessary ingredient for executing Secure Multiparty Computation (MPC) in the RAM model.

Although DORAM has been widely studied, all existing DORAM protocols have focused on the setting where the DORAM servers are semi-honest. Generic techniques for upgrading a semi-honest DORAM protocol to the malicious model typically increase the asymptotic communication complexity of the DORAM scheme.

In this work, we present a 3-party DORAM protocol which requires \(O((\kappa + D)\log N)\) communication per query, for a database of size N with D-bit values, where \(\kappa \) is the security parameter. Our hidden constants in the big-O nation are small. We show that our protocol is UC-secure in the presence of a malicious, static adversary. This matches the communication complexity of the best semi-honest DORAM protocols, and is the first malicious DORAM protocol with this complexity.

Brett Falk, Daniel Noble, Rafail Ostrovsky, Matan Shtepel, Jacob Zhang

3-Party Secure Computation for RAMs: Optimal and Concretely Efficient

Abstract

A distributed oblivious RAM (DORAM) is a method for accessing a secret-shared memory while hiding the accessed locations. DORAMs are the key tool for secure multiparty computation (MPC) for RAM programs that avoids expensive RAM-to-circuit transformations.

We present new and improved 3-party DORAM protocols. For a logical memory of size N and for each logical operation, our DORAM requires \(O(\log N)\) local CPU computation steps. This is known to be asymptotically optimal. Our DORAM satisfies passive security in the honest majority setting. Our technique results with concretely-efficient protocols and does not use expensive cryptography (such as re-randomizable or homomorphic encryption). Specifically, our DORAM is 25X faster than the known most efficient DORAM in the same setting.

Lastly, we extend our technique to handle malicious attackers at the expense of using slightly larger blocks (i.e., \(\omega ((\lambda + b)\log N)\) vs. \(\lambda +b\) where \(b=\varOmega (\log N)\) is original block size). To the best of our knowledge, this is the first concretely-efficient maliciously secure DORAM.

Technically, our construction relies on a novel concretely-efficient 3-party oblivious permutation protocol. We combine it with efficient non-oblivious hashing techniques (i.e., Cuckoo hashing) to get a distributed oblivious hash table. From this, we build a full-fledged DORAM using a distributed variant of the hierarchical approach of Goldreich and Ostrovsky (J. ACM ’96). These ideas, and especially the permutation protocol, are of independent interest.

Atsunori Ichikawa, Ilan Komargodski, Koki Hamada, Ryo Kikuchi, Dai Ikarashi

Backmatter

Titel: Theory of Cryptography
herausgegeben von: Guy Rothblum
Hoeteck Wee
Verlag: Springer Nature Switzerland
Electronic ISBN: 978-3-031-48615-9
Print ISBN: 978-3-031-48614-2
DOI: https://doi.org/10.1007/978-3-031-48615-9

Springer Professional

Über dieses Buch

Inhaltsverzeichnis

Frontmatter

Proofs and Outsourcing

Frontmatter

Beyond MPC-in-the-Head: Black-Box Constructions of Short Zero-Knowledge Proofs

Your Reputation’s Safe with Me: Framing-Free Distributed Zero-Knowledge Proofs

Locally Verifiable Distributed SNARGs

Distributed-Prover Interactive Proofs

Rogue-Instance Security for Batch Knowledge Proofs

On Black-Box Verifiable Outsourcing

Theoretical Foundations

Frontmatter

Counting Unpredictable Bits: A Simple PRG from One-Way Functions

On One-Way Functions and Sparse Languages

Security Proofs for Key-Alternating Ciphers with Non-Independent Round Permutations

Public-Key Encryption, Local Pseudorandom Generators, and the Low-Degree Method

Cryptography from Planted Graphs: Security with Logarithmic-Size Messages

Multi-party Computation I

Frontmatter

Randomized Functions with High Round Complexity

Towards Topology-Hiding Computation from Oblivious Transfer

On the Impossibility of Surviving (Iterated) Deletion of Weakly Dominated Strategies in Rational MPC

Synchronizable Fair Exchange

DORAM Revisited: Maliciously Secure RAM-MPC with Logarithmic Overhead

3-Party Secure Computation for RAMs: Optimal and Concretely Efficient

Backmatter

Premium Partner