---
_id: '605'
abstract:
- lang: eng
  text: 'Position based cryptography (PBC), proposed in the seminal work of Chandran,
    Goyal, Moriarty, and Ostrovsky (SIAM J. Computing, 2014), aims at constructing
    cryptographic schemes in which the identity of the user is his geographic position.
    Chandran et al. construct PBC schemes for secure positioning and position-based
    key agreement in the bounded-storage model (Maurer, J. Cryptology, 1992). Apart
    from bounded memory, their security proofs need a strong additional restriction
    on the power of the adversary: he cannot compute joint functions of his inputs.
    Removing this assumption is left as an open problem. We show that an answer to
    this question would resolve a long standing open problem in multiparty communication
    complexity: finding a function that is hard to compute with low communication
    complexity in the simultaneous message model, but easy to compute in the fully
    adaptive model. On a more positive side: we also show some implications in the
    other direction, i.e.: we prove that lower bounds on the communication complexity
    of certain multiparty problems imply existence of PBC primitives. Using this result
    we then show two attractive ways to “bypass” our hardness result: the first uses
    the random oracle model, the second weakens the locality requirement in the bounded-storage
    model to online computability. The random oracle construction is arguably one
    of the simplest proposed so far in this area. Our results indicate that constructing
    improved provably secure protocols for PBC requires a better understanding of
    multiparty communication complexity. This is yet another example where negative
    results in one area (in our case: lower bounds in multiparty communication complexity)
    can be used to construct secure cryptographic schemes.'
alternative_title:
- LNCS
author:
- first_name: Joshua
  full_name: Brody, Joshua
  last_name: Brody
- first_name: Stefan
  full_name: Dziembowski, Stefan
  last_name: Dziembowski
- first_name: Sebastian
  full_name: Faust, Sebastian
  last_name: Faust
- first_name: Krzysztof Z
  full_name: Pietrzak, Krzysztof Z
  id: 3E04A7AA-F248-11E8-B48F-1D18A9856A87
  last_name: Pietrzak
  orcid: 0000-0002-9139-1654
citation:
  ama: 'Brody J, Dziembowski S, Faust S, Pietrzak KZ. Position based cryptography
    and multiparty communication complexity. In: Kalai Y, Reyzin L, eds. Vol 10677.
    Springer; 2017:56-81. doi:<a href="https://doi.org/10.1007/978-3-319-70500-2_3">10.1007/978-3-319-70500-2_3</a>'
  apa: 'Brody, J., Dziembowski, S., Faust, S., &#38; Pietrzak, K. Z. (2017). Position
    based cryptography and multiparty communication complexity. In Y. Kalai &#38;
    L. Reyzin (Eds.) (Vol. 10677, pp. 56–81). Presented at the TCC: Theory of Cryptography
    Conference, Baltimore, MD, United States: Springer. <a href="https://doi.org/10.1007/978-3-319-70500-2_3">https://doi.org/10.1007/978-3-319-70500-2_3</a>'
  chicago: Brody, Joshua, Stefan Dziembowski, Sebastian Faust, and Krzysztof Z Pietrzak.
    “Position Based Cryptography and Multiparty Communication Complexity.” edited
    by Yael Kalai and Leonid Reyzin, 10677:56–81. Springer, 2017. <a href="https://doi.org/10.1007/978-3-319-70500-2_3">https://doi.org/10.1007/978-3-319-70500-2_3</a>.
  ieee: 'J. Brody, S. Dziembowski, S. Faust, and K. Z. Pietrzak, “Position based cryptography
    and multiparty communication complexity,” presented at the TCC: Theory of Cryptography
    Conference, Baltimore, MD, United States, 2017, vol. 10677, pp. 56–81.'
  ista: 'Brody J, Dziembowski S, Faust S, Pietrzak KZ. 2017. Position based cryptography
    and multiparty communication complexity. TCC: Theory of Cryptography Conference,
    LNCS, vol. 10677, 56–81.'
  mla: Brody, Joshua, et al. <i>Position Based Cryptography and Multiparty Communication
    Complexity</i>. Edited by Yael Kalai and Leonid Reyzin, vol. 10677, Springer,
    2017, pp. 56–81, doi:<a href="https://doi.org/10.1007/978-3-319-70500-2_3">10.1007/978-3-319-70500-2_3</a>.
  short: J. Brody, S. Dziembowski, S. Faust, K.Z. Pietrzak, in:, Y. Kalai, L. Reyzin
    (Eds.), Springer, 2017, pp. 56–81.
conference:
  end_date: 2017-11-15
  location: Baltimore, MD, United States
  name: 'TCC: Theory of Cryptography Conference'
  start_date: 2017-11-12
date_created: 2018-12-11T11:47:27Z
date_published: 2017-11-05T00:00:00Z
date_updated: 2021-01-12T08:05:53Z
day: '05'
department:
- _id: KrPi
doi: 10.1007/978-3-319-70500-2_3
ec_funded: 1
editor:
- first_name: Yael
  full_name: Kalai, Yael
  last_name: Kalai
- first_name: Leonid
  full_name: Reyzin, Leonid
  last_name: Reyzin
intvolume: '     10677'
language:
- iso: eng
main_file_link:
- open_access: '1'
  url: https://eprint.iacr.org/2016/536
month: '11'
oa: 1
oa_version: Submitted Version
page: 56 - 81
project:
- _id: 258AA5B2-B435-11E9-9278-68D0E5697425
  call_identifier: H2020
  grant_number: '682815'
  name: Teaching Old Crypto New Tricks
publication_identifier:
  isbn:
  - 978-331970499-9
publication_status: published
publisher: Springer
publist_id: '7200'
quality_controlled: '1'
scopus_import: 1
status: public
title: Position based cryptography and multiparty communication complexity
type: conference
user_id: 3E5EF7F0-F248-11E8-B48F-1D18A9856A87
volume: 10677
year: '2017'
...
---
_id: '609'
abstract:
- lang: eng
  text: Several cryptographic schemes and applications are based on functions that
    are both reasonably efficient to compute and moderately hard to invert, including
    client puzzles for Denial-of-Service protection, password protection via salted
    hashes, or recent proof-of-work blockchain systems. Despite their wide use, a
    definition of this concept has not yet been distilled and formalized explicitly.
    Instead, either the applications are proven directly based on the assumptions
    underlying the function, or some property of the function is proven, but the security
    of the application is argued only informally. The goal of this work is to provide
    a (universal) definition that decouples the efforts of designing new moderately
    hard functions and of building protocols based on them, serving as an interface
    between the two. On a technical level, beyond the mentioned definitions, we instantiate
    the model for four different notions of hardness. We extend the work of Alwen
    and Serbinenko (STOC 2015) by providing a general tool for proving security for
    the first notion of memory-hard functions that allows for provably secure applications.
    The tool allows us to recover all of the graph-theoretic techniques developed
    for proving security under the older, non-composable, notion of security used
    by Alwen and Serbinenko. As an application of our definition of moderately hard
    functions, we prove the security of two different schemes for proofs of effort
    (PoE). We also formalize and instantiate the concept of a non-interactive proof
    of effort (niPoE), in which the proof is not bound to a particular communication
    context but rather any bit-string chosen by the prover.
alternative_title:
- LNCS
author:
- first_name: Joel F
  full_name: Alwen, Joel F
  id: 2A8DFA8C-F248-11E8-B48F-1D18A9856A87
  last_name: Alwen
- first_name: Björn
  full_name: Tackmann, Björn
  last_name: Tackmann
citation:
  ama: 'Alwen JF, Tackmann B. Moderately hard functions: Definition, instantiations,
    and applications. In: Kalai Y, Reyzin L, eds. Vol 10677. Springer; 2017:493-526.
    doi:<a href="https://doi.org/10.1007/978-3-319-70500-2_17">10.1007/978-3-319-70500-2_17</a>'
  apa: 'Alwen, J. F., &#38; Tackmann, B. (2017). Moderately hard functions: Definition,
    instantiations, and applications. In Y. Kalai &#38; L. Reyzin (Eds.) (Vol. 10677,
    pp. 493–526). Presented at the TCC: Theory of Cryptography, Baltimore, MD, United
    States: Springer. <a href="https://doi.org/10.1007/978-3-319-70500-2_17">https://doi.org/10.1007/978-3-319-70500-2_17</a>'
  chicago: 'Alwen, Joel F, and Björn Tackmann. “Moderately Hard Functions: Definition,
    Instantiations, and Applications.” edited by Yael Kalai and Leonid Reyzin, 10677:493–526.
    Springer, 2017. <a href="https://doi.org/10.1007/978-3-319-70500-2_17">https://doi.org/10.1007/978-3-319-70500-2_17</a>.'
  ieee: 'J. F. Alwen and B. Tackmann, “Moderately hard functions: Definition, instantiations,
    and applications,” presented at the TCC: Theory of Cryptography, Baltimore, MD,
    United States, 2017, vol. 10677, pp. 493–526.'
  ista: 'Alwen JF, Tackmann B. 2017. Moderately hard functions: Definition, instantiations,
    and applications. TCC: Theory of Cryptography, LNCS, vol. 10677, 493–526.'
  mla: 'Alwen, Joel F., and Björn Tackmann. <i>Moderately Hard Functions: Definition,
    Instantiations, and Applications</i>. Edited by Yael Kalai and Leonid Reyzin,
    vol. 10677, Springer, 2017, pp. 493–526, doi:<a href="https://doi.org/10.1007/978-3-319-70500-2_17">10.1007/978-3-319-70500-2_17</a>.'
  short: J.F. Alwen, B. Tackmann, in:, Y. Kalai, L. Reyzin (Eds.), Springer, 2017,
    pp. 493–526.
conference:
  end_date: 2017-11-15
  location: Baltimore, MD, United States
  name: 'TCC: Theory of Cryptography'
  start_date: 2017-11-12
date_created: 2018-12-11T11:47:28Z
date_published: 2017-11-05T00:00:00Z
date_updated: 2021-01-12T08:06:04Z
day: '05'
department:
- _id: KrPi
doi: 10.1007/978-3-319-70500-2_17
editor:
- first_name: Yael
  full_name: Kalai, Yael
  last_name: Kalai
- first_name: Leonid
  full_name: Reyzin, Leonid
  last_name: Reyzin
intvolume: '     10677'
language:
- iso: eng
main_file_link:
- open_access: '1'
  url: https://eprint.iacr.org/2017/945
month: '11'
oa: 1
oa_version: Submitted Version
page: 493 - 526
publication_identifier:
  isbn:
  - 978-331970499-9
publication_status: published
publisher: Springer
publist_id: '7196'
quality_controlled: '1'
scopus_import: 1
status: public
title: 'Moderately hard functions: Definition, instantiations, and applications'
type: conference
user_id: 3E5EF7F0-F248-11E8-B48F-1D18A9856A87
volume: 10677
year: '2017'
...