Tal Moran

Academic Profile

Conferences (PC Member)

Publications

• Iddo Bentov, Pavel Hubácek, Tal Moran and Asaf Nadler
  Tortoise and Hares Consensus: The Meshcash Framework for Incentive-compatible, Scalable Cryptocurrencies
  CSCML 2021 [BibTex]
  
  @inproceedings{bhmn21meshcash,
    author = {Iddo Bentov and Pavel Hub\'{a}cek and Tal Moran and Asaf Nadler},
    title = {Tortoise and Hares Consensus: The Meshcash Framework for Incentive-compatible, Scalable Cryptocurrencies},
    editor = {Shlomi Dolev and Oded Margalit and Benny Pinkas and Alexander Schwarzmann},
    booktitle = {CSCML 2021},
    pages = {114--127},
    series = {Lecture Notes in Computer Science},
    volume = {12716},
    year = {2021},
    publisher = {Springer},
    url = {https://eprint.iacr.org/2017/300.pdf},
  }
  
  [Abstract]

  In this paper, we propose Meshcash, a protocol for implementing a permissionless ledger (blockchain). Unlike most existing proof-of-work based consensus protocols, Meshcash does not rely on leader-election (e.g., the single miner who managed to extend the longest chain). Rather, we use ideas from traditional (permissioned) Byzantine agreement protocols in a novel way to guarantee convergence to a consensus from any starting state. Our construction combines a local “hare” protocol that guarantees fast consensus on recent blocks (but doesn't, by itself, imply irreversibility) with a global “tortoise” protocol that guarantees irreversibility. Our global protocol also allows the ledger to “self-heal” from arbitrary violations of the security assumptions, reconverging to consensus after the assumptions hold again. Meshcash is designed to be race-free: there is no “race” to generate the next block and honestly-generated blocks are always rewarded. This property, which we define formally as a game-theoretic notion, turns out to be useful in analyzing rational miners' behavior: we prove (using a generalization of the blockchain mining games of Kiayias et al.) that race-free blockchain protocols are incentive-compatible and satisfy linearity of rewards (i.e., a party receives rewards proportional to its computational power).

  Because Meshcash can tolerate a high block rate regardless of network propagation delays (which will only affect latency), it allows us to lower both the variance and the expected time between blocks for honest miners; together with linearity of rewards, this makes pooled mining far less attractive. Moreover, race-free protocols scale more easily (in terms of transaction rate). This is because the race-free property implies that the network propagation delays are not a factor in terms of rewards, which removes the main impediment to accommodating a larger volume of transactions. We formally prove that all of our guarantees hold in the bounded-delay communication model of Pass, Seeman and shelat, and against a constant fraction of Byzantine (malicious) miners; not just rational ones.

  [pdf]
• Chen-Da Liu-Zhang, Julian Loss, Ueli Maurer, Tal Moran and Daniel Tschudi
  MPC with Synchronous Security and Asynchronous Responsiveness
  Asiacrypt 2020 [BibTex]
  
  @inproceedings{llmmt20async-mpc,
    author = {Chen{-}Da Liu{-}Zhang and Julian Loss and Ueli Maurer and Tal Moran and Daniel Tschudi},
    title = {MPC with Synchronous Security and Asynchronous Responsiveness},
    editor = {Shiho Moriai and Huaxiong Wang},
    booktitle = {Asiacrypt 2020},
    pages = {92--119},
    series = {Lecture Notes in Computer Science},
    volume = {12493},
    year = {2020},
    month = {December},
    publisher = {Springer},
    url = {https://eprint.iacr.org/2019/159.pdf},
  }
  
  [Abstract]

  Two paradigms for secure MPC are synchronous and asynchronous protocols. While synchronous protocols tolerate more corruptions and allow every party to give its input, they are very slow because the speed depends on the conservatively assumed worst-case delay $\Delta$ of the network. In contrast, asynchronous protocols allow parties to obtain output as fast as the actual network allows, a property called responsiveness, but unavoidably have lower resilience and parties with slow network connections cannot give input.

  It is natural to wonder whether it is possible to leverage synchronous MPC protocols to achieve responsiveness, hence obtaining the advantages of both paradigms: full security with responsiveness up to $t$ corruptions, and extended security (full security or security with unanimous abort) with no responsiveness up to $T \ge t$ corruptions. We settle the question by providing matching feasibility and impossibility results:

  • For the case of unanimous abort as extended security, there is an MPC protocol if and only if $T + 2t < n$.
  • For the case of full security as extended security, there is an MPC protocol if and only if $T < \frac{n}{2}$ and $T + 2t < n$. In particular, setting $t = \frac{n}{4}$ allows to achieve a fully secure MPC for honest majority, which in addition benefits from having substantial responsiveness.

  [pdf]
• Marshall Ball, Elette Boyle, Ran Cohen, Lisa Kohl, Tal Malkin, Pierre Meyer and Tal Moran
  Topology-Hiding Communication from Minimal Assumptions
  TCC 2020 [BibTex]
  
  @inproceedings{bbckmmm20minimal-thc,
    author = {Marshall Ball and Elette Boyle and Ran Cohen and Lisa Kohl and Tal Malkin and Pierre Meyer and Tal Moran},
    title = {Topology-Hiding Communication from Minimal Assumptions},
    editor = {Rafael Pass and Krzysztof Pietrzak},
    booktitle = {TCC 2020},
    pages = {473--501},
    series = {Lecture Notes in Computer Science},
    volume = {12551},
    year = {2020},
    month = {November},
    publisher = {Springer},
    url = {https://eprint.iacr.org/2021/388},
  }
  
  [Abstract]

  Topology-hiding broadcast (THB) enables parties communicating over an incomplete network to broadcast messages while hiding the topology from within a given class of graphs. THB is a central tool underlying general topology-hiding secure computation (THC) (Moran et al. TCC'15). Although broadcast is a privacy-free task, it was recently shown that THB for certain graph classes necessitates computational assumptions, even in the semi-honest setting, and even given a single corrupted party.

  In this work we investigate the minimal assumptions required for topology-hiding communication—both Broadcast or Anonymous Broadcast (where the broadcaster's identity is hidden). We develop new techniques that yield a variety of necessary and sufficient conditions for the feasibility of THB/THAB in different cryptographic settings: information theoretic, given existence of key agreement, and given existence of oblivious transfer. Our results show that feasibility can depend on various properties of the graph class, such as connectivity, and highlight the role of different properties of topology when kept hidden, including direction, distance, and/or distance-of-neighbors to the broadcaster.

  An interesting corollary of our results is a dichotomy for THC with a public number of at least three parties, secure against one corruption: information-theoretic feasibility if all graphs are 2-connected; necessity and sufficiency of key agreement otherwise.

  [pdf]
• Tal Moran and Daniel Wichs
  Incompressible Encodings
  Crypto 2020 [BibTex]
  
  @inproceedings{mw20incompressible-encodings,
    author = {Tal Moran and Daniel Wichs},
    title = {Incompressible Encodings},
    booktitle = {Crypto 2020},
    pages = {494--523},
    series = {Lecture Notes in Computer Science},
    volume = {12171},
    year = {2020},
    month = {August},
    url = {https://eprint.iacr.org/2020/814.pdf},
  }
  
  [Abstract]

  An incompressible encoding can probabilistically encode some data $m$ into a codeword $c$, which is not much larger. Anyone can decode the codeword $c$ to recover the original data $m$. However, the codeword $c$ cannot be efficiently compressed, even if the original data $m$ is given to the decompression procedure on the side. In other words, $c$ is an efficiently decodable representation of $m$, yet is computationally incompressible even given $m$. An incompressible encoding is composable if many encodings cannot be simultaneously compressed. The recent work of Damgård, Ganesh and Orlandi (CRYPTO '19) defined a variant of incompressible encodings as a building block for “proofs of replicated storage”. They constructed incompressible encodings in an ideal permutation model, but it was left open if they can be constructed under standard assumptions, or even in the more basic random-oracle model. In this work, we undertake the comprehensive study of incompressible encodings as a primitive of independent interest and give new constructions, negative results and applications:

  • We construct incompressible encodings in the common random string (CRS) model under either Decisional Composite Residuosity (DCR) or Learning with Errors (LWE). However, the construction has several drawbacks: (1) it is not composable, (2) it only achieves selective security, and (3) the CRS is as long as the data $m$.
  • We leverage the above construction to also get a scheme in the random-oracle model, under the same assumptions, that avoids all of the above drawbacks. Furthermore, it is significantly more efficient than the prior ideal-model construction.
  • We give black-box separations, showing that incompressible encodings in the plain model cannot be proven secure under any standard hardness assumption, and incompressible encodings in the CRS model must inherently suffer from all of the drawbacks above.
  • We give a new application to “big-key cryptography in the bounded-retrieval model”, where secret keys are made intentionally huge to make them hard to exfiltrate. Using incompressible encodings, we can get all the security benefits of a big key without wasting storage space, by having the key to encode useful data.

  [pdf]
• Rio LaVigne, Chen-Da Liu-Zhang, Ueli Maurer, Tal Moran, Marta Mularczyk and Daniel Tschudi
  Topology-Hiding Computation for Networks with Unknown Delays
  PKC 2020 [BibTex]
  
  @inproceedings{llmmmt20async-thc,
    author = {Rio LaVigne and Chen-Da Liu-Zhang and Ueli Maurer and Tal Moran and Marta Mularczyk and Daniel Tschudi},
    title = {Topology-Hiding Computation for Networks with Unknown Delays},
    booktitle = {PKC 2020},
    pages = {215--245},
    series = {Lecture Notes in Computer Science},
    volume = {12111},
    year = {2020},
    month = {June},
    publisher = {Springer},
    url = {https://eprint.iacr.org/2019/1211.pdf},
  }
  
  [Abstract]

  Topology-Hiding Computation (THC) allows a set of parties to securely compute a function over an incomplete network without revealing information on the network topology. Since its introduction in TCC'15 by Moran et al., the research on THC has focused on reducing the communication complexity, allowing larger graph classes, and tolerating stronger corruption types.

  All of these results consider a fully synchronous model with a known upper bound on the maximal delay of all communication channels. Unfortunately, in any realistic setting this bound has to be extremely large, which makes all fully synchronous protocols inefficient. In the literature on multi-party computation, this is solved by considering the fully asynchronous model. However, THC is unachievable in this model (and even hard to define), leaving even the definition of a meaningful model as an open problem.

  The contributions of this paper are threefold.

  First, we introduce a meaningful model of unknown and random communication delays for which THC is both definable and achievable. The probability distributions of the delays can be arbitrary for each channel, but one needs to make the (necessary) assumption that the delays are independent. The existing fully-synchronous THC protocols do not work in this setting and would, in particular, leak information about the topology.

  Second, in the model with trusted stateless hardware boxes introduced at Eurocrypt'18 by Ball et al., we present a THC protocol that works for any graph class.

  Third, we explore what is achievable in the standard model without trusted hardware and present a THC protocol for specific graph types (cycles and trees) secure under the DDH assumption.

  The speed of all protocols scales with the actual (unknown) delay times, in contrast to all previously known THC protocols whose speed is determined by the assumed upper bound on the network delay.

  [pdf]
• Adi Akavia, Rio LaVigne and Tal Moran
  Topology-Hiding Computation on All Graphs
  J. Cryptology, 33(1):176–227, 2020 [BibTex]
  
  @article{alm20topology-random,
    author = {Adi Akavia and Rio LaVigne and Tal Moran},
    title = {Topology-Hiding Computation on All Graphs},
    pages = {176--227},
    volume = {33},
    number = {1},
    year = {2020},
    month = {January},
    url = {https://eprint.iacr.org/2017/296.pdf},
    journal = {J. Cryptology},
    doi = {10.1007/s00145-019-09318-y},
  }
  
  [Abstract]

  A distributed computation in which nodes are connected by a partial communication graph is called topology-hiding if it does not reveal information about the graph beyond what is revealed by the output of the function. Previous results have shown that topology-hiding computation protocols exist for graphs of constant degree and logarithmic diameter in the number of nodes [Moran-Orlov-Richelson, TCC'15; Hirt et al., Crypto'16] as well as for other graph families, such as cycles, trees, and low circumference graphs [Akavia-Moran, Eurocrypt'17], but the feasibility question for general graphs was open.

  In this work we positively resolve the above open problem: we prove that topology-hiding computation is feasible for all graphs under either the Decisional Diffie-Hellman or Quadratic-Residuosity assumption.

  Our techniques employ random or deterministic walks to generate paths covering the graph, upon which we apply the Akavia-Moran topology-hiding broadcast for chain-graphs (paths). To prevent topology information revealed by the random-walk, we design multiple graph-covering sequences that, together, are locally identical to receiving at each round a message from each neighbor and sending back a processed message from some neighbor (in a randomly permuted order).

  [pdf]
  [Preliminary version appeared in Crypto 2017 | BibTex

  
  @inproceedings{alm17topology-random,
    author = {Adi Akavia and Rio LaVigne and Tal Moran},
    title = {Topology-Hiding Computation for All Graphs},
    booktitle = {Crypto 2017},
    pages = {447--467},
    series = {Lecture Notes in Computer Science},
    volume = {10401},
    year = {2017},
    month = {August},
    publisher = {Springer},
    url = {https://eprint.iacr.org/2017/296},
    doi = {10.1007/978-3-319-63688-7_15},
  }
  

  | pdf]
• Tal Moran and Ilan Orlov
  Simple Proofs of Spacetime and Rational Proofs of Storage
  Crypto 2019 [BibTex]
  
  @inproceedings{mo19post,
    author = {Tal Moran and Ilan Orlov},
    title = {Simple Proofs of Spacetime and Rational Proofs of Storage},
    booktitle = {Crypto 2019},
    pages = {381--409},
    series = {Lecture Notes in Computer Science},
    volume = {11692},
    year = {2019},
    publisher = {Springer},
    url = {https://eprint.iacr.org/2016/035.pdf},
    doi = {10.1007/978-3-030-26948-7\_14},
  }
  
  [Abstract]

  We introduce a new cryptographic primitive: Proofs of Space-Time (PoSTs) and construct an extremely simple, practical protocol for implementing these proofs. A PoST allows a prover to convince a verifier that she spent a “space-time” resource (storing data—space—over a period of time). Formally, we define the PoST resource as a trade-off between CPU work and space-time (under reasonable cost assumptions, a rational user will prefer to use the lower-cost space-time resource over CPU work).

  Compared to a proof-of-work, a PoST requires less energy use, as the “difficulty” can be increased by extending the time period over which data is stored without increasing computation costs. Our definition is very similar to “Proofs of Space” [ePrint 2013/796, 2013/805] but, unlike the previous definitions, takes into account amortization attacks and storage duration. Moreover, our protocol uses a very different (and much simpler) technique, making use of the fact that we explicitly allow a space-time tradeoff, and doesn't require any non-standard assumptions (beyond random oracles). Unlike previous constructions, our protocol allows incremental difficulty adjustment, which can gracefully handle increases in the price of storage compared to CPU work. In addition, we show how, in a crypto-currency context, the parameters of the scheme can be adjusted using a market-based mechanism, similar in spirit to the difficulty adjustment for PoW protocols.

  [pdf]
• Marshall Ball, Elette Boyle, Ran Cohen, Tal Malkin and Tal Moran
  Is Information-Theoretic Topology-Hiding Computation Possible?
  TCC 2019 [BibTex]
  
  @inproceedings{bbcmm19infotheoretic-thc,
    author = {Marshall Ball and Elette Boyle and Ran Cohen and Tal Malkin and Tal Moran},
    title = {Is Information-Theoretic Topology-Hiding Computation Possible?},
    editor = {Dennis Hofheinz and Alon Rosen},
    booktitle = {TCC 2019},
    pages = {502--530},
    series = {Lecture Notes in Computer Science},
    volume = {11891},
    year = {2019},
    month = {November},
    publisher = {Springer},
    url = {https://eprint.iacr.org/2019/1094.pdf},
    doi = {10.1007/978-3-030-36030-6\_20},
  }
  
  [Abstract]

  Topology-hiding computation (THC) is a form of multi-party computation over an incomplete communication graph that maintains the privacy of the underlying graph topology. Existing THC protocols consider an adversary that may corrupt an arbitrary number of parties, and rely on cryptographic assumptions such as DDH.

  In this paper we address the question of whether information-theoretic THC can be achieved by taking advantage of an honest majority. In contrast to the standard MPC setting, this problem has remained open in the topology-hiding realm, even for simple “privacy-free” functions like broadcast, and even when considering only semi-honest corruptions.

  We uncover a rich landscape of both positive and negative answers to the above question, showing that what types of graphs are used and how they are selected is an important factor in determining the feasibility of hiding topology information-theoretically. In particular, our results include the following.

  • We show that topology-hiding broadcast (THB) on a line with four nodes, secure against a single semi-honest corruption, implies key agreement. This result extends to broader classes of graphs, e.g., THB on a cycle with two semi-honest corruptions.
  • On the other hand, we provide the first feasibility result for information-theoretic THC: for the class of cycle graphs, with a single semi-honest corruption.

  Given the strong impossibilities, we put forth a weaker definition of distributional-THC, where the graph is selected from some distribution (as opposed to worst-case).

  • We present a formal separation between the definitions, by showing a distribution for which information theoretic distributional-THC is possible, but even topology-hiding broadcast is not possible information-theoretically with the standard definition.
  • We demonstrate the power of our new definition via a new connection to adaptively secure low-locality MPC, where distributional-THC enables parties to “reuse” a secret low-degree communication graph even in the face of adaptive corruptions.

  [pdf]
• Rio LaVigne, Chen-Da Liu-Zhang, Ueli Maurer, Tal Moran, Marta Mularczyk and Daniel Tschudi
  Topology-Hiding Computation Beyond Semi-Honest Adversaries
  TCC 2018 [BibTex]
  
  @inproceedings{lzmmmt18topology-hiding,
    author = {Rio LaVigne and Chen{-}Da Liu{-}Zhang and Ueli Maurer and Tal Moran and Marta Mularczyk and Daniel Tschudi},
    title = {Topology-Hiding Computation Beyond Semi-Honest Adversaries},
    booktitle = {TCC 2018},
    pages = {3--35},
    series = {Lecture Notes in Computer Science},
    volume = {11240},
    year = {2018},
    month = {November},
    publisher = {Springer},
    url = {https://eprint.iacr.org/2018/255.pdf},
    doi = {10.1007/978-3-030-03810-6\_1},
  }
  
  [Abstract]

  Topology-hiding communication protocols allow a set of parties, connected by an incomplete network with unknown communication graph, where each party only knows its neighbors,to construct a complete communication network such that the network topology remains hidden even from a powerful adversary who can corrupt parties. This communication network can then be used to perform arbitrary tasks, for example secure multi-party computation, in a topology-hiding manner.

  Previously proposed protocols could only tolerate passive corruption. This paper proposes protocols that can also tolerate fail-corruption (i.e., the adversary can crash any party at any point in time) and so-called semi-malicious corruption (i.e., the adversary can control a corrupted party’s randomness), without leaking more than an arbitrarily small fraction of a bit of information about the topology. A small-leakage protocol was recently proposed by Ball et al. [Eurocrypt’18], but only under the unrealistic set-up assumption that each party has a trusted hardware module containing secret correlated pre-set keys, and with the further two restrictions that only passively corrupted parties can be crashed by the adversary, and semi-malicious corruption is not tolerated. Since leaking a small amount of information is unavoidable, as is the need to abort the protocol in case of failures, our protocols seem to achieve the best possible goal in a model with fail-corruption. Further contributions of the paper are applications of the protocol to obtain secure MPC protocols, which requires a way to bound the aggregated leakage when multiple small-leakage protocols are executed in parallel or sequentially. Moreover, while previous protocols are based on the DDH assumption, a new so-called PKCR public-key encryption scheme based on the LWE assumption is proposed, allowing to base topology-hiding computation on LWE. Furthermore, a protocol usingfully-homomorphic encryption achieving very low round complexity is proposed.

  [pdf]
• Marshall Ball, Elette Boyle, Tal Malkin and Tal Moran
  Exploring the Boundaries of Topology-Hiding Computation
  Eurocrypt 2018 [BibTex]
  
  @inproceedings{bbmm18-fail-stop-thc,
    author = {Marshall Ball and Elette Boyle and Tal Malkin and Tal Moran},
    title = {Exploring the Boundaries of Topology-Hiding Computation},
    booktitle = {Eurocrypt 2018},
    pages = {294--325},
    series = {Lecture Notes in Computer Science},
    volume = {10822},
    year = {2018},
    month = {April},
    publisher = {Springer},
    doi = {10.1007/978-3-319-78372-7_10},
  }
  
  [Abstract]

  Topology-hiding computation (THC) is a form of multi-party computation over an incomplete communication graph that maintains the privacy of the underlying graph topology. In a line of recent works [Moran, Orlov & Richelson, TCC'15, Hirt et al. CRYPTO'16, Akavia & Moran EUROCRYPT'17, Akavia et al. CRYPTO'17], THC protocols for securely computing any function in the semi-honest setting have been constructed. In addition, it was shown by Moran et al. that in the fail-stop setting THC with negligible leakage on the topology is impossible.

  In this paper, we further explore the feasibility boundaries of THC.

  • We show that even against semi-honest adversaries, topology-hiding broadcast on a small (4-node) graph implies oblivious transfer; in contrast, trivial broadcast protocols exist unconditionally if topology can be revealed.
  • We strengthen the lower bound of Moran et al., identifying and extending a relation between the amount of leakage on the underlying graph topology that must be revealed in the fail-stop setting, as a function of the number of parties and communication round complexity: Any $n$-party protocol leaking $\delta$ bits for $\delta \in (0,1]$ must have $\Omega(n/\delta)$ rounds.

  We then present THC protocols providing close-to-optimal leakage rates, for unrestricted graphs on $n$ nodes against a fail-stop adversary controlling a dishonest majority of the $n$ players. These constitute the first general fail-stop THC protocols. Specifically, for this setting we show:

  • A THC protocol that leaks at most one bit and requires $O(n^2)$ rounds.
  • A THC protocol that leaks at most $\delta$ bits for arbitrarily small non-negligible $\delta$, and requires $O(n^3/\delta)$ rounds.

  These protocols also achieve full security (with no leakage) for the semi-honest setting. Our protocols are based on one-way functions and a (stateless) secure hardware box primitive. This provides a theoretical feasibility result, a heuristic solution in the plain model using general-purpose obfuscation candidates, and a potentially practical approach to THC via commodity hardware such as Intel SGX. Interestingly, even with such hardware, proving security requires sophisticated simulation techniques.

  [pdf]
• Adi Akavia and Tal Moran
  Topology-Hiding Computation Beyond Logarithmic Diameter
  Eurocrypt 2017 [BibTex]
  
  @inproceedings{am17topology-circle,
    author = {Adi Akavia and Tal Moran},
    title = {Topology-Hiding Computation Beyond Logarithmic Diameter},
    booktitle = {Eurocrypt 2017},
    pages = {609--637},
    series = {Lecture Notes in Computer Science},
    volume = {10212},
    year = {2017},
    month = {April},
    url = {https://eprint.iacr.org/2017/130.pdf},
    doi = {10.1007/978-3-319-56617-7},
  }
  
  [Abstract]

  A distributed computation in which nodes are connected by a partial communication graph is called topology-hiding if it does not reveal information about the graph (beyond what is revealed by the output of the function). Previous results [Moran, Orlov, Richelson; TCC'15] have shown that topology-hiding computation protocols exist for graphs of logarithmic diameter (in the number of nodes), but the feasibility question for graphs of larger diameter was open even for very simple graphs such as chains, cycles and trees.

  In this work, we take a step towards topology-hiding computation protocols for arbitrary graphs by constructing protocols that can be used in a large class of large-diameter networks, including cycles, trees and graphs with logarithmic circumference. Our results use very different methods from [MOR15] and can be based on a standard assumption (such as DDH).

  [pdf]
• Tal Moran, Moni Naor and Gil Segev
  An Optimally Fair Coin Toss
  J. Cryptology, 29(3):491–513, 2016 [BibTex]
  
  @article{mns16cointoss,
    author = {Tal Moran and Moni Naor and Gil Segev},
    title = {An Optimally Fair Coin Toss},
    pages = {491--513},
    volume = {29},
    number = {3},
    year = {2016},
    url = {http://dx.doi.org/10.1007/s00145-015-9199-z},
    journal = {J. Cryptology},
    doi = {10.1007/s00145-015-9199-z},
  }
  
  [Abstract]

  We address one of the foundational problems in cryptography: the bias of coin-flipping protocols. Coin-flipping protocols allow mutually distrustful parties to generate a common unbiased random bit, guaranteeing that even if one of the parties is malicious, it cannot significantly bias the output of the honest party. A classical result by Cleve (Proceedings of the 18th annual ACM symposium on theory of computing, pp 364–369, 1986) showed that for any two-party $r$-round coin-flipping protocol there exists an efficient adversary that can bias the output of the honest party by $\Omega(1/r)$. However, the best previously known protocol only guarantees $O(1/\sqrt{r})$ bias, and the question of whether Cleve?s bound is tight has remained open for more than 20 years. In this paper, we establish the optimal trade-off between the round complexity and the bias of two-party coin-flipping protocols. Under standard assumptions (the existence of oblivious transfer), we show that Cleve's lower bound is tight: We construct an $r$-round protocol with bias $O(1/r)$.

  [pdf]
  [Preliminary version appeared in TCC 2009 | BibTex

  
  @inproceedings{MNS09-coinflip,
    author = {Tal Moran and Moni Naor and Gil Segev},
    title = {An Optimally Fair Coin Toss},
    booktitle = {TCC 2009},
    pages = {1--18},
    series = {Lecture Notes in Computer Science},
    volume = {5444},
    year = {2009},
    month = {March},
    publisher = {Springer},
  }
  

  ]
• Yiling Chen, Stephen Chong, Ian A. Kash, Tal Moran and Salil P. Vadhan
  Truthful Mechanisms for Agents That Value Privacy
  ACM Trans. Economics and Comput., 4(3):13:1–13:30, 2016 [BibTex]
  
  @article{cckmv16private-truthfulness,
    author = {Yiling Chen and Stephen Chong and Ian A. Kash and Tal Moran and Salil P. Vadhan},
    title = {Truthful Mechanisms for Agents That Value Privacy},
    pages = {13:1--13:30},
    volume = {4},
    number = {3},
    year = {2016},
    url = {http://doi.acm.org/10.1145/2892555},
    journal = {ACM Trans. Economics and Comput.},
    doi = {10.1145/2892555},
  }
  
  [Abstract]

  Recent work has constructed economic mechanisms that are both truthful and differentially private. In these mechanisms, privacy is treated separately from truthfulness; it is not incorporated in players' utility functions (and doing so has been shown to lead to nontruthfulness in some cases). In this work, we propose a new, general way of modeling privacy in players' utility functions. Specifically, we only assume that if an outcome $o$ has the property that any report of player $i$ would have led to $o$ with approximately the same probability, then $o$ has a small privacy cost to player $i$. We give three mechanisms that are truthful with respect to our modeling of privacy: for an election between two candidates, for a discrete version of the facility location problem, and for a general social choice problem with discrete utilities (via a VCG-like mechanism). As the number $n$ of players increases, the social welfare achieved by our mechanisms approaches optimal (as a fraction of $n$).

  [pdf]
  [Preliminary version appeared in EC 2013 | BibTex

  
  @inproceedings{cckmv13private-truthfulness,
    author = {Yiling Chen and Stephen Chong and Ian A. Kash and Tal Moran and Salil Vadhan},
    title = {Truthful Mechanisms for Agents that Value Privacy},
    editor = {Michael Kearns and R. Preston McAfee and {\'E}va Tardos},
    booktitle = {EC 2013},
    pages = {215--232},
    year = {2013},
    month = {June},
    publisher = {ACM},
  }
  

  ]
• Tal Moran, Ilan Orlov and Silas Richelson
  Topology-Hiding Computation
  TCC 2015 [BibTex]
  
  @inproceedings{mor15topology-hiding,
    author = {Tal Moran and Ilan Orlov and Silas Richelson},
    title = {Topology-Hiding Computation},
    editor = {Yevgeniy Dodis and Jesper Buus Nielsen},
    booktitle = {TCC 2015},
    pages = {169--198},
    series = {Lecture Notes in Computer Science},
    volume = {9014},
    year = {2015},
    publisher = {Springer},
    ee = {\url{https://eprint.iacr.org/2014/1022}},
  }
  
  [Abstract]

  Secure Multi-party Computation (MPC) is one of the foundational achievements of modern cryptography, allowing multiple, distrusting, parties to jointly compute a function of their inputs, while revealing nothing but the output of the function. Following the seminal works of Yao and Goldreich, Micali and Wigderson and Ben-Or, Goldwasser and Wigderson, the study of MPC has expanded to consider a wide variety of questions, including variants in the attack model, underlying assumptions, complexity and composability of the resulting protocols.

  One question that appears to have received very little attention, however, is that of MPC over an underlying communication network whose structure is, in itself, sensitive information. This question, in addition to being of pure theoretical interest, arises naturally in many contexts: designing privacy-preserving social-networks, private peer-to-peer computations, vehicle-to-vehicle networks and the “internet of things” are some of the examples.

  In this paper, we initiate the study of “topology-hiding computation” in the computational setting. We give formal definitions in both simulation-based and indistinguishability-based flavors. We show that, even for fail-stop adversaries, there are some strong impossibility results. Despite this, we show that protocols for topology-hiding computation can be constructed in the semi-honest and fail-stop models, if we somewhat restrict the set of nodes the adversary may corrupt.

  [pdf]
• Giulia Alberini, Tal Moran and Alon Rosen
  Public Verification of Private Effort
  TCC 2015 [BibTex]
  
  @inproceedings{amr15verifiable-polling,
    author = {Giulia Alberini and Tal Moran and Alon Rosen},
    title = {Public Verification of Private Effort},
    editor = {Yevgeniy Dodis and Jesper Buus Nielsen},
    booktitle = {TCC 2015},
    pages = {159--181},
    series = {Lecture Notes in Computer Science},
    volume = {9014},
    year = {2015},
    publisher = {Springer},
    ee = {\url{https://eprint.iacr.org/2014/983}},
  }
  
  [Abstract]

  We introduce a new framework for polling responses from a large population. Our framework allows gathering information without violating the responders' anonymity and at the same time enables public verification of the poll's result. In contrast to prior approaches to the problem, we do not require trusting the pollster for faithfully announcing the poll's results, nor do we rely on strong identity verification.

  We propose an “effort based” polling protocol whose results can be publicly verified by constructing a “responder certification graph” whose nodes are labeled by responders' replies to the poll, and whose edges cross-certify that adjacent nodes correspond to honest participants. Cross-certification is achieved using a newly introduced (privately verifiable) “Private Proof of Effort” (PPE). In effect, our protocol gives a general method for converting privately-verifiable proofs into a publicly-verifiable protocol. The soundness of the transformation relies on expansion properties of the certification graph.

  Our results are applicable to a variety of settings in which crowd-sourced information gathering is required. This includes crypto-currencies, political polling, elections, recommendation systems, viewer voting in TV shows, and prediction markets.

  [pdf]
• Ranjit Kumaresan, Tal Moran and Iddo Bentov
  How to Use Bitcoin to Play Decentralized Poker
  CCS 2015 [BibTex]
  
  @inproceedings{kmb15bitpoker,
    author = {Ranjit Kumaresan and Tal Moran and Iddo Bentov},
    title = {How to Use Bitcoin to Play Decentralized Poker},
    booktitle = {CCS 2015},
    pages = {195--206},
    year = {2015},
    url = {http://doi.acm.org/10.1145/2810103.2813712},
    doi = {10.1145/2810103.2813712},
  }
  
  [Abstract]

  Back and Bentov (arXiv 2014) and Andrychowicz et al. (Security and Privacy 2014) introduced techniques to perform secure multiparty computations on Bitcoin. Among other things, these works constructed lottery protocols that ensure that any party that aborts after learning the outcome pays a monetary penalty to all other parties. Following this, Andrychowicz et al. (Bitcoin Workshop 2014) and concurrently Bentov and Kumaresan (Crypto 2014) extended the solution to arbitrary secure function evaluation while guaranteeing fairness in the following sense: any party that aborts after learning the output pays a monetary penalty to all parties that did not learn the output. Andrychowicz et al. (Bitcoin Workshop 2014) also suggested extending to scenarios where parties receive a payoff according to the output of a secure function evaluation, and outlined a 2-party protocol for the same that in addition satisfies the notion of fairness described above.

  In this work, we formalize, generalize, and construct multiparty protocols for the primitive suggested by Andrychowicz et al. We call this primitive secure cash distribution with penalties. Our formulation of secure cash distribution with penalties poses it as a multistage reactive functionality (i.e., more general than secure function evaluation) that provides a way to securely implement smart contracts in a decentralized setting, and consequently suffices to capture a wide variety of stateful computations involving data and/or money, such as {decentralized} auctions, markets, and games such as poker, etc. Our protocol realizing secure cash distribution with penalties works in a hybrid model where parties have access to a claim-or-refund transaction functionality $\mathcal{F}_{\mathrm{CR}}^\star$ which can be efficiently realized in (a variant of) Bitcoin, and is otherwise independent of the Bitcoin ecosystem. We emphasize that our protocol is dropout-tolerant in the sense that any party that drops out during the protocol is forced to pay a monetary penalty to all other parties. Our formalization and construction generalize both secure computation with penalties of Bentov and Kumaresan (Crypto 2014),and secure lottery with penalties of Andrychowicz et al.\ (Security and Privacy 2014).

  [pdf]
• Ilan Komargodski, Tal Moran, Moni Naor, Rafael Pass, Alon Rosen and Eylon Yogev
  One-Way Functions and (Im)perfect Obfuscation
  FOCS 2014 [BibTex]
  
  @inproceedings{kmnpry14obfuscation,
    author = {Ilan Komargodski and Tal Moran and Moni Naor and Rafael Pass and Alon Rosen and Eylon Yogev},
    title = {One-Way Functions and (Im)perfect Obfuscation},
    booktitle = {FOCS 2014},
    pages = {374--383},
    year = {2014},
    ee = {http://dx.doi.org/10.1109/FOCS.2014.47},
  }
  
  [Abstract]

  A program obfuscator takes a program and outputs an "scrambled" version of it, where the goal is that the obfuscated program will not reveal much about its structure beyond what is apparent from executing it. There are several ways of formalizing this goal. Specifically, in indistinguishability obfuscation, first defined by Barak et al. (CRYPTO 2001), the requirement is that the results of obfuscating any two functionally equivalent programs (circuits) will be computationally indistinguishable. Recently, a fascinating candidate construction for indistinguishability obfuscation was proposed by Garg et al. (FOCS 2013). This has led to a flurry of discovery of intriguing constructions of primitives and protocols whose existence was not previously known (for instance, fully deniable encryption by Sahai and Waters, STOC 2014). Most of them explicitly rely on additional hardness assumptions, such as one-way functions.

  Our goal is to get rid of this extra assumption. We cannot argue that indistinguishability obfuscation of all polynomial-time circuits implies the existence of one-way functions, since if $P = NP$, then program obfuscation (under the indistinguishability notion) is possible. Instead, the ultimate goal is to argue that if $P \neq NP$ and program obfuscation is possible, then one-way functions exist.

  Our main result is that if $NP \not\subseteq ioBPP$ and there is an efficient (even imperfect) indistinguishability obfuscator, then there are one-way functions. In addition, we show that the existence of an indistinguishability obfuscator implies (unconditionally) the existence of SZK-arguments for $NP$. This, in turn, provides an alternative version of our main result, based on the assumption of hard-on-the average $NP$ problems. To get some of our results we need obfuscators for simple programs such as 3CNF formulas.

  [pdf]
• Mohammad Mahmoody, Tal Moran and Salil Vadhan
  Publicly Verifiable Proofs of Sequential Work
  ITCS 2013 [BibTex]
  
  @inproceedings{mmv13proofs-of-work,
    author = {Mohammad Mahmoody and Tal Moran and Salil Vadhan},
    title = {Publicly Verifiable Proofs of Sequential Work},
    editor = {Robert D. Kleinberg},
    booktitle = {ITCS 2013},
    pages = {373--388},
    year = {2013},
    month = {January},
    publisher = {ACM},
  }
  
  [Abstract]

  We construct a publicly verifiable protocol for proving computational work based on collision-resistant hash functions and a new plausible complexity assumption regarding the existence of “inherently sequential” hash functions. Our protocol is based on a novel construction of time-lock puzzles. Given a sampled “puzzle” $\mathcal{P}\mathbin{\stackrel{\tiny{\$}}{\gets}} \mathbf{D}_n$, where $n$ is the security parameter and $\mathbf{D}_n$ is the distribution of the puzzles, a corresponding “solution” can be generated using $N$ evaluations of the sequential hash function, where $N>n$ is another parameter, while any feasible adversarial strategy for generating valid solutions must take at least as much time as $\Omega(N)$ sequential evaluations of the hash function after receiving $\mathcal{P}$. Thus, valid solutions constitute a “proof” that $\Omega(N)$ parallel time elapsed since $\mathcal{P}$ was received. Solutions can be publicly and efficiently verified in time $poly(n) \cdot polylog(N)$. Applications of these “time-lock puzzles” include noninteractive timestamping of documents (when the distribution over the possible documents corresponds to the puzzle distribution $\mathbf{D}_n$) and universally verifiable CPU benchmarks.

  Our construction is secure in the standard model under complexity assumptions (collision-resistant hash functions and inherently sequential hash functions), and makes black-box use of the underlying primitives. Consequently, the corresponding construction in the random oracle model is secure unconditionally. Moreover, as it is a public-coin protocol, it can be made non-interactive in the random oracle model using the Fiat-Shamir Heuristic.

  Our construction makes a novel use of “depth-robust” directed acyclic graphs—ones whose depth remains large even after removing a constant fraction of vertices—which were previously studied for the purpose of complexity lower bounds. The construction bypasses a recent negative result of Mahmoody, Moran, and Vadhan (CRYPTO `11) for time-lock puzzles in the random oracle model, which showed that it is impossible to have time-lock puzzles like ours in the random oracle model if the puzzle generator also computes a solution together with the puzzle.

  [pdf]
• Shahram Khazaei, Tal Moran and Douglas Wikström
  A Mix-Net From Any CCA2 Secure Cryptosystem
  Asiacrypt 2012 [BibTex]
  
  @inproceedings{kmw12-mixnets,
    author = {Shahram Khazaei and Tal Moran and Douglas Wikstr\"{o}m},
    title = {A Mix-Net From Any CCA2 Secure Cryptosystem},
    editor = {Xiaoyun Wang and Kazue Sako},
    booktitle = {Asiacrypt 2012},
    pages = {607--625},
    series = {Lecture Notes in Computer Science},
    volume = {7658},
    year = {2012},
    month = {December},
    publisher = {Springer},
  }
  
  [Abstract]

  We construct a provably secure mix-net from any CCA2 secure cryptosystem. The mix-net is secure against active adversaries that statically corrupt less than $\lambda$ out of $k$ mix-servers, where $\lambda$ is a threshold parameter, and it is robust provided that at most $\min(\lambda-1,k-\lambda)$ mix-servers are corrupted.

  The main component of our construction is a mix-net that outputs the correct result if all mix-servers behaved honestly, and aborts with probability $1-O(H^{-(t-1)})$ otherwise (without disclosing anything about the inputs), where $t$ is an auxiliary security parameter and $H$ is the number of honest parties. The running time of this protocol for long messages is roughly $3t c$, where $c$ is the running time of Chaum's mix-net (1981).

  [pdf]
• Yevgeniy Dodis, Abhishek Jain, Tal Moran and Daniel Wichs
  Counterexamples to Hardness Amplification Beyond Negligible
  TCC 2012 [BibTex]
  
  @inproceedings{DJMW12-hardness-amplification,
    author = {Yevgeniy Dodis and Abhishek Jain and Tal Moran and Daniel Wichs},
    title = {Counterexamples to Hardness Amplification Beyond Negligible},
    booktitle = {TCC 2012},
    pages = {476--493},
    series = {Lecture Notes in Computer Science},
    volume = {7194},
    year = {2012},
    month = {March},
    publisher = {Springer},
    isbn = {978-3-642-28914-9},
  }
  
  [Abstract]

  If we have a problem that is mildly hard, can we create a problem that is significantly harder? A natural approach to hardness amplification is the “direct product”; instead of asking an attacker to solve a single instance of a problem, we ask the attacker to solve several independently generated ones. Interestingly, proving that the direct product amplifies hardness is often highly non-trivial, and in some cases may be false. For example, it is known that the direct product (i.e. “parallel repetition”) of general interactive games may not amplify hardness at all. On the other hand, positive results show that the direct product does amplify hardness for many basic primitives such as one-way functions/relations, weakly-verifiable puzzles, and signatures.

  Even when positive direct product theorems are shown to hold for some primitive, the parameters are surprisingly weaker than what we may have expected. For example, if we start with a weak one-way function that no poly-time attacker can break with probability $> \frac{1}{2}$, then the direct product provably amplifies hardness to some negligible probability. Naturally, we would expect that we can amplify hardness exponentially, all the way to $2^{-n}$ probability, or at least to some fixed/known negligible such as $n^{-\log n}$ in the security parameter $n$, just by taking sufficiently many instances of the weak primitive. Although it is known that such parameters cannot be proven via black-box reductions, they may seem like reasonable conjectures, and, to the best of our knowledge, are widely believed to hold. In fact, a conjecture along these lines was introduced in a survey of Goldreich, Nisan and Wigderson (ECCC '95). In this work, we show that such conjectures are false by providing simple but surprising counterexamples. In particular, we construct weakly secure signatures and one-way functions, for which standard hardness amplification results are known to hold, but for which hardness does not amplify beyond just negligible. That is, for any negligible function $\epsilon(n)$, we instantiate these primitives so that the direct product can always be broken with probability $\epsilon(n)$, no matter how many copies we take.

  [pdf]
• Mohammad Mahmoody, Tal Moran and Salil Vadhan
  Time-Lock Puzzles in the Random Oracle Model
  CRYTPO 2011 [BibTex]
  
  @inproceedings{MMV11-timelock,
    author = {Mohammad Mahmoody and Tal Moran and Salil Vadhan},
    title = {Time-Lock Puzzles in the Random Oracle Model},
    booktitle = {CRYTPO 2011},
    pages = {39--50},
    series = {Lecture Notes in Computer Science},
    volume = {6841},
    year = {2011},
    month = {August},
    publisher = {Springer-Verlag},
  }
  
  [Abstract]

  A time-lock puzzle is a mechanism for sending messages “to the future”. The sender publishes a puzzle whose solution is the message to be sent, thus hiding it until enough time has elapsed for the puzzle to be solved. For time-lock puzzles to be useful, generating a puzzle should take less time than solving it. Since adversaries may have access to many more computers than honest solvers, massively parallel solvers should not be able to produce a solution much faster than serial ones.

  To date, we know of only one mechanism that is believed to satisfy these properties: the one proposed by Rivest, Shamir and Wagner (1996), who originally introduced the notion of time-lock puzzles. Their puzzle is based on the serial nature of exponentiation and the hardness of factoring, and is therefore vulnerable to advances in factoring techniques (as well as to quantum attacks).

  In this work, we study the possibility of constructing time-lock puzzles in the random-oracle model. Our main result is negative, ruling out time-lock puzzles that require more parallel time to solve than the total work required to generate a puzzle. In particular, this rules out black-box constructions of such time-lock puzzles from one-way permutations and collision-resistant hash-functions. On the positive side, we construct a time-lock puzzle with a linear gap in parallel time: a new puzzle can be generated with one round of $n$ parallel queries to the random oracle, but $n$ rounds of serial queries are required to solve it (even for massively parallel adversaries).

  [pdf]
• John Kelsey, Andrew Regenscheid, Tal Moran and David Chaum
  Attacking Paper-Based E2E Voting Systems
  Towards Trustworthy Elections [BibTex]
  
  @inproceedings{KRMC10-attackvote,
    author = {John Kelsey and Andrew Regenscheid and Tal Moran and David Chaum},
    title = {Attacking Paper-Based E2E Voting Systems},
    booktitle = {Towards Trustworthy Elections},
    pages = {370--387},
    series = {Lecture Notes in Computer Science},
    volume = {6000},
    year = {2010},
    month = {August},
    publisher = {Springer},
    isbn = {978-3-642-12979-7},
  }
  
  [Abstract]

  In this paper, we develop methods for constructing vote-buying/coercion attacks on end-to-end voting systems, and describe vote-buying/coercion attacks on three proposed end-to-end voting systems: Punchscan, Pret-a-voter and ThreeBallot. We also demonstrate a different attack on Punchscan, which could permit corrupt election officials to change votes without detection in some cases. Additionally, we consider some generic attacks on end-to-end voting systems.

  [pdf]
• Tal Moran and Tyler Moore
  The Phish-Market Protocol: Secure Sharing Between Competitors
  IEEE Security & Privacy, 8(4):40–45, 2010 (A version of this article aimed at a more technical audience was previously published in FC 2010.) [BibTex]
  
  @article{MM10b-phishmarket,
    author = {Tal Moran and Tyler Moore},
    title = {The Phish-Market Protocol: Secure Sharing Between Competitors},
    pages = {40--45},
    volume = {8},
    number = {4},
    year = {2010},
    month = {July},
    note = {A version of this article aimed at a more technical audience was previously published in FC 2010.},
    journal = {IEEE Security \& Privacy},
    doi = {10.1109/MSP.2010.138},
  }
  
  [Abstract]

  The Phish-Market protocol encourages take-down companies to share information about malicious websites by compensating them for this data without revealing sensitive information to their competitors. Cryptography lets contributing firms verify payment amounts without learning which offered website URLs were “purchased.”

  [pdf]
• Tal Moran and Moni Naor
  Basing Cryptographic Protocols on Tamper-Evident Seals
  Theoretical Computer Science, 411:1283–1310, 2010 [BibTex]
  
  @article{MN10-tamper-evident-full,
    author = {Tal Moran and Moni Naor},
    title = {Basing Cryptographic Protocols on Tamper-Evident Seals},
    pages = {1283--1310},
    volume = {411},
    year = {2010},
    month = {March},
    publisher = {Elsevier Science Publishers Ltd.},
    journal = {Theoretical Computer Science},
    doi = {10.1016/j.tcs.2009.10.023},
  }
  
  [Abstract]

  In this paper we attempt to formally study two very intuitive physical models: sealed envelopes and locked boxes, often used as illustrations for common cryptographic operations. We relax the security properties usually required from locked boxes (such as in bit-commitment protocols) and require only that a broken lock or torn envelope be identifiable to the original sender. Unlike the completely impregnable locked box, this functionality may be achievable in real life, where containers having this property are called “tamper-evident seals”. Another physical object with this property is the “scratch-off card”, often used in lottery tickets. We consider three variations of tamper-evident seals, and show that under some conditions they can be used to implement oblivious transfer, bit-commitment and coin flipping. We also show a separation between the three models. Of particular interest, we give a strongly-fair coin flipping protocol with bias bounded by $O(1/r)$ (where r is the number of rounds), beating the best known bias in the standard model even with cryptographic assumptions.

  [pdf]
  [Preliminary version appeared in ICALP 2005 | BibTex

  
  @inproceedings{MN05-tamper-evident,
    author = {Tal Moran and Moni Naor},
    title = {Basing Cryptographic Protocols on Tamper-Evident Seals},
    editor = {L. Caires et al.},
    booktitle = {ICALP 2005},
    pages = {285--297},
    series = {Lecture Notes in Computer Science},
    volume = {3580},
    year = {2005},
    month = {Jul},
    publisher = {Springer-Verlag},
  }
  

  ]
• Tal Moran and Moni Naor
  Split-Ballot Voting: Everlasting Privacy With Distributed Trust
  ACM Transactions on Information and System Security, 13:16:1–16:43, 2010 [BibTex]
  
  @article{MN10-split-ballot,
    author = {Tal Moran and Moni Naor},
    title = {Split-Ballot Voting: Everlasting Privacy With Distributed Trust},
    pages = {16:1--16:43},
    volume = {13},
    year = {2010},
    month = {March},
    publisher = {ACM},
    journal = {ACM Transactions on Information and System Security},
    doi = {http://doi.acm.org/10.1145/1698750.1698756},
  }
  
  [Abstract]

  In this paper we propose a new voting protocol with desirable security properties. The voting stage of the protocol can be performed by humans without computers; it provides every voter with the means to verify that all the votes were counted correctly (universal verifiability) while preserving ballot secrecy. The protocol has “everlasting privacy”: even a computationally unbounded adversary gains no information about specific votes from observing the protocol's output. Unlike previous protocols with these properties, this protocol distributes trust between two authorities: a single corrupt authority will not cause voter privacy to be breached. Finally, the protocol is receipt-free: a voter cannot prove how she voted even she wants to do so. We formally prove the security of the protocol in the Universal Composability framework, based on number-theoretic assumptions.

  [pdf]
  [Preliminary version appeared in CCS 2007 | BibTex

  
  @inproceedings{MN07-split-ballot,
    author = {Tal Moran and Moni Naor},
    title = {Split-Ballot Voting: Everlasting Privacy With Distributed Trust},
    booktitle = {CCS 2007},
    pages = {246--255},
    year = {2007},
    month = {October},
    publisher = {ACM},
    isbn = {978-1-59593-703-2},
  }
  

  ]
• Dov Gordon, Yuval Ishai, Tal Moran, Rafail Ostrovsky and Amit Sahai
  On Complete Primitives for Fairness
  TCC 2010 [BibTex]
  
  @inproceedings{GIMOS10-fairness,
    author = {Dov Gordon and Yuval Ishai and Tal Moran and Rafail Ostrovsky and Amit Sahai},
    title = {On Complete Primitives for Fairness},
    editor = {Daniele Micciancio},
    booktitle = {TCC 2010},
    pages = {91--108},
    series = {Lecture Notes in Computer Science},
    volume = {5978},
    year = {2010},
    month = {February},
    publisher = {Springer Berlin / Heidelberg},
  }
  
  [Abstract]

  For secure two-party and multi-party computation with abort, classification of which primitives are complete has been extensively studied in the literature. However, for fair secure computation, where (roughly speaking) either all parties learn the output or none do, the question of complete primitives has remained largely unstudied. In this work, we initiate a rigorous study of completeness for primitives that allow fair computation. We show the following results:

  • No “short” primitive is complete for fairness. In surprising contrast to other notions of security for secure two-party computation, we show that for fair secure two-party computation, no primitive of size $O(\log k)$ is complete, where $k$ is a security parameter. This is the case even if we can enforce parallelism in calls to the primitives (i.e., the adversary does not get output from any primitive in a parallel call until it sends input to all of them). This negative result holds regardless of any computational assumptions.
  • Coin Flipping and Simultaneous Broadcast are not complete for fairness. The above result rules out the completeness of two natural candidates: coin flipping (for any number of coins) and simultaneous broadcast (for messages of arbitrary length).
  • A fairness hierarchy. We clarify the fairness landscape further by exhibiting the existence of a “fairness hierarchy”. We show that for every “short” $\ell = O(\log k)$, no protocol making (serial) access to any $\ell$-bit primitive can be used to construct even a $(\ell+1)$-bit simultaneous broadcast.
  • Positive results. To complement the negative results, we exhibit a $k$-bit primitive that is complete for two-party fair secure computation. This primitive implements a “fair reconstruction” procedure for a secret sharing scheme with some robustness properties. We show how to generalize this result to the multi-party setting.
  • Fairness combiners. We also introduce the question of constructing a protocol for fair secure computation from primitives that may be faulty. We show a simple functionality that is complete for two-party fair computation when the majority of its instances are honest. On the flip side, we show that this result is tight: no functionality is complete for fairness if half (or more) of the instances can be malicious.

  [pdf]
• Tal Moran and Tyler Moore
  The Phish Market Protocol: Securely Sharing Attack Data Between Competitors
  FC 2010 [BibTex]
  
  @inproceedings{MM10-phishing,
    author = {Tal Moran and Tyler Moore},
    title = {The Phish Market Protocol: Securely Sharing Attack Data Between Competitors},
    editor = {Radu Sion},
    booktitle = {FC 2010},
    pages = {222--237},
    series = {Lecture Notes in Computer Science},
    volume = {6052},
    year = {2010},
    month = {January},
  }
  
  [Abstract]

  A key way in which banks mitigate the effects of phishing is to remove fraudulent websites or suspend abusive domain names. This `take-down' is often subcontracted to specialist firms. Prior work has shown that these take-down companies refuse to share `feeds' of phishing website URLs with each other, and consequently, many phishing websites are not removed because the firm with the take-down contract remains unaware of their existence. The take-down companies are reticent to exchange feeds, fearing that competitors with less comprehensive lists might `free-ride' off their efforts by not investing resources to find new websites, as well as use the feeds to poach clients. In this paper, we propose the Phish Market protocol, which enables companies with less comprehensive feeds to learn about websites impersonating their own clients that are held by other firms. The protocol is designed so that the contributing firm is compensated only for those websites affecting its competitor's clients and only those previously unknown to the receiving firm. Crucially, the protocol does not reveal to the contributing firm which URLs are needed by the receiver, as this is viewed as sensitive information by take-down firms. Using complete lists of phishing URLs obtained from two large take-down companies, our elliptic-curve-based implementation added a negligible average 5 second delay to securely share URLs.

  [pdf]
• Tal Moran, Moni Naor and Gil Segev
  Deterministic History-Independent Strategies for Storing Information on Write-Once Memories
  Theory of Computing, 5(1):43–67, 2009 [BibTex]
  
  @article{MNS09-history-full,
    author = {Tal Moran and Moni Naor and Gil Segev},
    title = {Deterministic History-Independent Strategies for Storing Information on Write-Once Memories},
    pages = {43--67},
    volume = {5},
    number = {1},
    year = {2009},
    publisher = {Theory of Computing},
    url = {http://www.theoryofcomputing.org/articles/v005a002},
    journal = {Theory of Computing},
    doi = {10.4086/toc.2009.v005a002},
  }
  
  [Abstract]

  Motivated by the challenging task of designing “secure” vote storage mechanisms, we deal with information storage mechanisms that operate in extremely hostile environments. In such environments, the majority of existing techniques for information storage and for security are susceptible to powerful adversarial attacks. In this setting, we propose a mechanism for storing a set of at most K elements from a large universe of size N on write-once memories in a manner that does not reveal the insertion order of the elements. We consider a standard model for write-once memories, in which the memory is initialized to the all 0's state, and the only operation allowed is flipping bits from 0 to 1. Whereas previously known constructions were either inefficient (required $\Theta(K^2)$ memory), randomized, or employed cryptographic techniques which are unlikely to be available in hostile environments, we eliminate each of these undesirable properties. The total amount of memory used by the mechanism is linear in the number of stored elements and poly-logarithmic in the size of the universe of elements. In addition, we consider one of the classical distributed computing problems: conflict resolution in multiple-access channels. By establishing a tight connection with the basic building block of our mechanism, we construct the first deterministic and non-adaptive conflict resolution algorithm whose running time is optimal up to poly-logarithmic factors.

  [pdf]
  [Preliminary version appeared in ICALP 2007 | BibTex

  
  @inproceedings{MNS07-history,
    author = {Tal Moran and Moni Naor and Gil Segev},
    title = {Deterministic History-Independent Strategies for Storing Information on Write-Once Memories},
    booktitle = {ICALP 2007},
    series = {Lecture Notes in Computer Science},
    volume = {4596},
    year = {2007},
    month = {July},
    publisher = {Springer},
    isbn = {987-5-540-73419-2},
  }
  

  ]
• Josh Benaloh, Tal Moran, Lee Naish, Kim Ramchen and Vanessa Teague
  Shuffle-Sum: Coercion-Resistant Verifiable Tallying for STV Voting
  IEEE Transactions on Information Forensics and Security, 4(4):685–698, 2009 [BibTex]
  
  @article{BMNRT09-shuffle-sum,
    author = {Josh Benaloh and Tal Moran and Lee Naish and Kim Ramchen and Vanessa Teague},
    title = {Shuffle-Sum: Coercion-Resistant Verifiable Tallying for STV Voting},
    pages = {685--698},
    volume = {4},
    number = {4},
    year = {2009},
    month = {December},
    journal = {IEEE Transactions on Information Forensics and Security},
    doi = {10.1109/TIFS.2009.2033757},
  }
  
  [Abstract]

  There are many advantages to voting schemes in which voters rank all candidates in order, rather than just choosing their favourite. However, these schemes inherently suffer from a coercion problem when there are many candidates, because a coercer can demand a certain permutation from a voter and then check whether that permutation appears during tallying. Recently developed cryptographic voting protocols allow anyone to audit an election (universal verifiability), but existing systems are either not applicable to ranked voting at all, or reveal enough information about the ballots to make voter coercion possible. We solve this problem for the popular single transferable vote (STV) ranked voting system, by constructing an algorithm for the verifiable tallying of encrypted votes. Our construction improves upon existing work because it extends to multiple-seat STV and reveals less information than other schemes. The protocol is based on verifiable shuffling of homomorphic encryptions, a well-studied primitive in the voting arena. Our protocol is efficient enough to be practical, even for a large election.

  [pdf]
• Tal Moran, Ronen Shaltiel and Amnon Ta-Shma
  Non-interactive Timestamping in the Bounded Storage Model
  J. Cryptology, 22(2):189–226, 2009 [BibTex]
  
  @article{MST09-timestamping-full,
    author = {Tal Moran and Ronen Shaltiel and Amnon Ta-Shma},
    title = {Non-interactive Timestamping in the Bounded Storage Model},
    pages = {189--226},
    volume = {22},
    number = {2},
    year = {2009},
    month = {April},
    journal = {J. Cryptology},
    doi = {10.1007/s00145-008-9035-9},
  }
  
  [Abstract]

  A timestamping scheme is a mechanism allowing one party, the “stamper”, to prove that it knew of a certain document at some earlier time. We say that such a scheme is passive if a stamper can stamp a document without communicating with any other player. The only communication performed is at validation time. Passive timestamping has many advantages, such as information theoretic privacy and enhanced robustness. Passive timestamping, however, is not possible against polynomial time adversaries that have unbounded (but polynomial) storage at their disposal. As a result, no passive timestamping schemes were constructed up to date. We show that passive timestamping is possible in the Bounded Storage Model. I.e., where there is an upper bound on the amount of storage that the adversary has and all players have access to a long random string. To the best of our knowledge, this is the first example of a cryptographic task that is possible in the bounded storage model, but is impossible in the “standard cryptographic setting”, even assuming cryptographic assumptions. We give an explicit construction that is secure against all bounded storage adversaries, and a significantly more efficient construction secure against all bounded storage adversaries that run in polynomial time.

  [pdf]
  [Preliminary version appeared in CRYPTO 2004 | BibTex

  
  @inproceedings{MST04-timestamping,
    author = {Tal Moran and Ronen Shaltiel and Amnon Ta-Shma},
    title = {Non-interactive Timestamping in the Bounded Storage Model.},
    editor = {Matthew K. Franklin},
    booktitle = {CRYPTO 2004},
    pages = {460--476},
    series = {Lecture Notes in Computer Science},
    volume = {3152},
    year = {2004},
    month = {August},
    publisher = {Springer},
  }
  

  ]
• Tal Moran and Gil Segev
  David and Goliath Commitments: UC Computation for Asymmetric Parties Using Tamper-Proof Hardware
  Eurocrypt 2008 [BibTex]
  
  @inproceedings{MS08-david-and-goliath,
    author = {Tal Moran and Gil Segev},
    title = {David and Goliath Commitments: UC Computation for Asymmetric Parties Using Tamper-Proof Hardware},
    booktitle = {Eurocrypt 2008},
    pages = {527--544},
    series = {Lecture Notes in Computer Science},
    volume = {4965},
    year = {2008},
    month = {April},
    publisher = {Springer},
    isbn = {978-3-540-78966-6},
  }
  
  [Abstract]

  Designing secure protocols in the Universal Composability (UC) framework confers many advantages. In particular, it allows the protocols to be securely used as building blocks in more complex protocols, and assists in understanding their security properties. Unfortunately, most existing models in which universally composable computation is possible (for useful functionalities) require a trusted setup stage. Recently, Katz [Eurocrypt '07] proposed an alternative to the trusted setup assumption: tamper-proof hardware. Instead of trusting a third party to correctly generate the setup information, each party can create its own hardware tokens, which it sends to the other parties. Each party is only required to trust that its own tokens are tamper-proof. Katz designed a UC commitment protocol that requires both parties to generate hardware tokens. In addition, his protocol relies on a specific number-theoretic assumption. In this paper, we construct UC commitment protocols for “David” and “Goliath”: we only require a single party (Goliath) to be capable of generating tokens. We construct a version of the protocol that is secure for computationally unbounded parties, and a more efficient version that makes computational assumptions only about David (we require only the existence of a one-way function). Our protocols are simple enough to be performed by hand on David's side. These properties may allow such protocols to be used in situations which are inherently asymmetric in real-life, especially those involving individuals versus large organizations. Classic examples include voting protocols (voters versus “the government”) and protocols involving private medical data (patients versus insurance-agencies or hospitals).

  [pdf]
• Tal Moran and Moni Naor
  Receipt-Free Universally-Verifiable Voting With Everlasting Privacy
  CRYPTO 2006 [BibTex]
  
  @inproceedings{MN06-voting,
    author = {Tal Moran and Moni Naor},
    title = {Receipt-Free Universally-Verifiable Voting With Everlasting Privacy},
    editor = {Cynthia Dwork},
    booktitle = {CRYPTO 2006},
    pages = {373--392},
    series = {Lecture Notes in Computer Science},
    volume = {4117},
    year = {2006},
    month = {September},
    publisher = {Springer},
    isbn = {3-540-37432-9},
  }
  
  [Abstract]

  We present the first universally verifiable voting scheme that can be based on a general assumption (existence of a non-interactive commitment scheme). Our scheme is also the first receipt-free scheme to give “everlasting privacy” for votes: even a computationally unbounded party does not gain any information about individual votes (other than what can be inferred from the final tally). Our voting protocols are designed to be used in a “traditional” setting, in which voters cast their ballots in a private polling booth (which we model as an untappable channel between the voter and the tallying authority). Following in the footsteps of Chaum and Neff, our protocol ensures that the integrity of an election cannot be compromised even if the computers running it are all corrupt (although ballot secrecy may be violated in this case). We give a generic voting protocol which we prove to be secure in the Universal Composability model, given that the underlying commitment is universally composable. We also propose a concrete implementation, based on the hardness of discrete log, that is more efficient.

  [pdf]
• Tal Moran and Moni Naor
  Polling with Physical Envelopes: A Rigorous Analysis of a Human-Centric Protocol
  Eurocrypt 2006 [BibTex]
  
  @inproceedings{MN06-crrt,
    author = {Tal Moran and Moni Naor},
    title = {Polling with Physical Envelopes: A Rigorous Analysis of a Human-Centric Protocol},
    editor = {Serge Vaudenay},
    booktitle = {Eurocrypt 2006},
    pages = {88--108},
    series = {Lecture Notes in Computer Science},
    volume = {4004},
    year = {2006},
    month = {May},
    publisher = {Springer-Verlag},
  }
  
  [Abstract]

  We propose simple, realistic protocols for polling that allow the responder to plausibly repudiate his response, while at the same time allow accurate statistical analysis of poll results. The protocols use simple physical objects (envelopes or scratch-off cards) and can be performed without the aid of computers. One of the main innovations of this work is the use of techniques from theoretical cryptography to rigorously prove the security of a realistic, physical protocol. We show that, given a few properties of physical envelopes, the protocols are unconditionally secure in the universal composability framework.

  [pdf]

Miscellanea

• A tool for visualizing the Fourier-Walsh transforms of arbitrary Boolean functions.
• A great example of "human cryptography" (i.e., cryptographic protocols that can be performed with materials in every kitchen) is this puzzle, due to Naor, Naor and Reingold, and published in the highly respected Journal of Craptology