CoChat
Sign Up
PreprintCited by 17Cryptography and Data SecurityCryptographic Implementations and SecurityUser Authentication and Security Systems

The DOI matches its DataCite record.

Egalitarian computing

Open access
Biryukov, Alex, Khovratovich, Dmitry·2016·arXiv
DOI 10.48550/arxiv.1606.03588arXiv 1606.03588
Open this paper in CoChat — free accountOpen PDF

Abstract

In this paper we explore several contexts where an adversary has an upper hand over the defender by using special hardware in an attack. These include password processing, hard-drive protection, cryptocurrency mining, resource sharing, code obfuscation, etc. We suggest memory-hard computing as a generic paradigm, where every task is amalgamated with a certain procedure requiring intensive access to RAM both in terms of size and (very importantly) bandwidth, so that transferring the computation to GPU, FPGA, and even ASIC brings little or no cost reduction. Cryptographic schemes that run in this framework become egalitarian in the sense that both users and attackers are equal in the price-performance ratio conditions. Based on existing schemes like {Argon2} and the recent generalized-birthday proof-of-work, we suggest a generic framework and two new schemes: MTP, a memory-hard Proof-of-Work based on the memory-hard function with fast verification and short proofs. It can be also used for memory-hard time-lock puzzles. {MHE}, the concept of memory-hard encryption, which utilizes available RAM to strengthen the encryption for the low-entropy keys (allowing to bring back 6 letter passwords).

Overview

The claims and statistics of this paper haven’t been checked yet.

Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.

A few free checks a day · papers already verified open instantly · results are public

Integrity signals

Registry

DataCite · 10.48550/arxiv.1606.03588

Cites

Statistics

Verification

Claims the paper makes

The claims and statistics of this paper haven’t been checked yet.

Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.

A few free checks a day · papers already verified open instantly · results are public

Claims other papers make about this one

Each is checked against this paper’s own text: does it say what the citing paper says it does?

  • The paper proposes to use memory-hard functions to delete encrypted sensor data at the cloud during the state transition phase.

    “We propose to use memory-hard functions [6, 13, 18, 19] to delete encrypted sensor data at the cloud, during state transition phase.”

    From IoT Expunge: Implementing Verifiable Retention of IoT Data (2020) · cites this paper as [13]

Self-check

Percentages, sums and reported differences re-computed from the paper’s own numbers.

The self-check needs the paper’s full text.

Citations

Cites

No references could be resolved yet.

Research works printed but not linked: 21

  1. [6][6] ABADI, M., BURROWS, M., AND WOBBER, T. Moderately hard, memory-bound functions. In NDSS'03 (2003), The Internet Society. -
  2. [9][9] BERNSTEIN, D. J., AND LANGE, T. Non-uniform cracks in the concrete: The power of free precomputation. In ASIACRYPT'13 (2013), vol. 8270 of Lecture Notes in Computer Science , Springer, pp. 321-340. -
  3. [13][13] BIRYUKOV, A., AND KHOVRATOVICH, D. Equihash: Asymmetric proof-of-work based on the generalized birthday problem. In NDSS'16 (2016). available at https://eprint.iacr.org/ 2015/946.pdf . -
  4. [14][14] CAI, J., LIPTON, R. J., SEDGEWICK, R., AND YAO, A. C. Towards uncheatable benchmarks. In Structure in Complexity Theory Conference (1993), IEEE Computer Society, pp. 2-11. -
  5. [16][16] DINUR, I., AND NADLER, N. Time-memory tradeoff attacks on the MTP proof-of-work scheme. In CRYPTO (2) (2017), vol. 10402 of Lecture Notes in Computer Science , Springer, pp. 375-403. -
  6. [17][17] DWORK, C., GOLDBERG, A., AND NAOR, M. On memorybound functions for fighting spam. In CRYPTO'03 (2003), vol. 2729 of Lecture Notes in Computer Science , Springer, pp. 426-444. -
  7. [18][18] DWORK, C., AND NAOR, M. Pricing via processing or combatting junk mail. In CRYPTO'92 (1992), vol. 740 of Lecture Notes in Computer Science , Springer, pp. 139-147. -
  8. [19][19] DWORK, C., NAOR, M., AND WEE, H. Pebbling and proofs of work. In CRYPTO'05 (2005), vol. 3621 of Lecture Notes in Computer Science , Springer, pp. 37-54. -
  9. [20][20] DZIEMBOWSKI, S., FAUST, S., KOLMOGOROV, V., AND PIETRZAK, K. Proofs of space. In CRYPTO'15 (2015), R. Gennaro and M. Robshaw, Eds., vol. 9216 of Lecture Notes in Computer Science , Springer, pp. 585-605. -
  10. [21][21] GIRIDHAR, B., CIESLAK, M., DUGGAL, D., DRESLINSKI, R. G., CHEN, H., PATTI, R., HOLD, B., CHAKRABARTI, C., MUDGE, T. N., AND BLAAUW, D. Exploring DRAM organizations for energy-efficient and resilient exascale memories. In International Conference for High Performance Computing, Networking, Storage and Analysis 2013 (2013), ACM, pp. 23-35. -
  11. [22][22] HOANG, V. T., REYHANITABAR, R., ROGAWAY, P., AND VIZ ´ AR, D. Online authenticated-encryption and its noncereuse misuse-resistance. In CRYPTO'15 (2015), R. Gennaro and M. Robshaw, Eds., vol. 9215 of Lecture Notes in Computer Science , Springer, pp. 493-517. -
  12. [23][23] HOPCROFT, J. E., PAUL, W. J., AND VALIANT, L. G. On time versus space. J. ACM 24 , 2 (1977), 332-337. -
  13. [25][25] JERSCHOW, Y. I., AND MAUVE, M. Offline submission with RSA time-lock puzzles. In CIT (2010), IEEE Computer Society, pp. 1058-1064. -
  14. [27][27] MAHMOODY, M., MORAN, T., AND VADHAN, S. P. Publicly verifiable proofs of sequential work. In ITCS (2013), ACM, pp. 373-388. -
  15. [28][28] MALVONI, K. Energy-efficient bcrypt cracking, 2014. Passwords'14 conference. -
  16. [29][29] MARTIN, L. Xts: A mode of aes for encrypting hard disks. IEEE Security & Privacy , 3 (2010), 68-69. -
  17. [32][32] PARK, S., PIETRZAK, K., ALWEN, J., FUCHSBAUER, G., AND GAZI, P. Spacecoin: A cryptocurrency based on proofs of space. IACR Cryptology ePrint Archive 2015 (2015), 528. -
  18. [34][34] PIPPENGER, N. Superconcentrators. SIAM J. Comput. 6 , 2 (1977), 298-304. -
  19. [37][37] THOMPSON, C. D. Area-time complexity for VLSI. In STOC'79 (1979), ACM, pp. 81-88. -
  20. [39][39] VAN OORSCHOT, P. C., AND WIENER, M. J. Parallel collision search with cryptanalytic applications. J. Cryptology 12 , 1 (1999), 1-28. -
  21. [40][40] WAGNER, D. A generalized birthday problem. In CRYPTO'02 (2002), vol. 2442 of Lecture Notes in Computer Science , Springer, pp. 288-303. -

Cited by

Sorted by citations

Metadata

Authors
Biryukov, A., & Khovratovich, D.
Affiliations
University of Luxembourg (LU)
ORCID
Venue
arXiv
Publisher
arXiv
Published
2016
ISSN
2331-8422 (ISSN-L)
DOI
10.48550/arxiv.1606.03588
arXiv
1606.03588
OpenAlex
W3037417735
Cited by
17
References
0
Citations by year
2023: 1 · 2022: 1 · 2021: 3 · 2020: 4 · 2019: 1 · 2018: 5 · 2017: 2
Type
posted content
Language
en
Open access
Licence
arxiv.org/licenses/nonexclusive-distrib/1.0/
Locations
  • arXiv (Cornell University) (submittedVersion)
  • Open Repository and Bibliography (University of Luxembourg) (submittedVersion, cc-by-nc-sa)
  • arXiv (Cornell University)
Topics
  • Physical Sciences › Computer Science › Computer Networks and Communications › Cryptography and Data Security
  • Physical Sciences › Computer Science › Artificial Intelligence › Cryptographic Implementations and Security
  • Physical Sciences › Computer Science › Information Systems › User Authentication and Security Systems
Keywords
memory-hard functions, password security, proof-of-work, time-lock puzzles, Argon2, cryptocurrency mining, code obfuscation, resource sharing

About these checks

Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.

Statistics and arithmetic are recomputed, not judged.

Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.

What counts as a claim ›How we measure confidence ›How we check this ›

Are you an author, or do you see a problem with this page? Request a review