Skip to main content

crypto directory

Links

“OpenSquare: Decentralized Repeated Modular Squaring Service”, Aravinda et al 2021

“OpenSquare: Decentralized Repeated Modular Squaring Service”⁠, Sri Aravinda, Krishnan Thyagarajan, Tiantian Gong, Adithya Bhat, Aniket Kate, Dominique Schröder (2021-09-22; backlinks; similar):

Repeated Modular Squaring is a versatile computational operation that has led to practical constructions of timed-cryptographic primitives like time-lock puzzles (TLP) and verifiable delay functions (VDF) that have a fast growing list of applications. While there is a huge interest for timed-cryptographic primitives in the blockchains area, we find 2 real-world concerns that need immediate attention towards their large-scale practical adoption: Firstly, the requirement to constantly perform computations seems unrealistic for most of the users. Secondly, choosing the parameters for the bound T seems complicated due to the lack of heuristics and experience.

We present OpenSquare, a decentralized repeated modular squaring service, that overcomes the above concerns. OpenSquare lets clients outsource their repeated modular squaring computation via smart contracts to any computationally powerful servers that offer computational services for rewards in an unlinkable manner. OpenSquare naturally gives us publicly computable heuristics about a pre-specified number (T) and the corresponding reward amounts of repeated squarings necessary for a time period. Moreover, OpenSquare rewards multiple servers for a single request, in a sybil resistant manner to incentivize maximum server participation and is therefore resistant to censorship and single-points-of failures.

We give game-theoretic analysis to support the mechanism design of OpenSquare: (1) incentivizes servers to stay available with their services, (2) minimizes the cost of outsourcing for the client, and (3) ensures the client receives the valid computational result with high probability. To demonstrate practicality, we also implement OpenSquare’s smart contract in Solidity and report the gas costs for all of its functions.

Our results show that the on-chain computational costs for both the clients and the servers are quite low, and therefore feasible for practical deployments and usage.

[Keywords: cryptographic protocols / time-lock puzzles, repeated modular squaring, smart contracts]

“Verifiable Timed Signatures Made Practical”, Thyagarajan et al 2020

2020-thyagarajan.pdf: “Verifiable Timed Signatures Made Practical”⁠, Sri Aravinda Krishnan Thyagarajan, Adithya Bhat, Giulio Malavolta, Nico Döttling, Aniket Kate, Dominique Schröder et al (2020-10-01; backlinks; similar):

A verifiable timed signature (VTS) scheme allows one to time-lock a signature on a known message for a given amount of time T such that after performing a sequential computation for time T anyone can extract the signature from the time-lock. Verifiability ensures that anyone can publicly check if a time-lock contains a valid signature on the message without solving it first, and that the signature can be obtained by solving the same for time T.

This work formalizes VTS, presents efficient constructions compatible with BLS, Schnorr, and ECDSA signatures, and experimentally demonstrates that these constructions can be employed in practice. On a technical level, we design an efficient cut-and-choose protocol based on the homomorphic time-lock puzzles to prove the validity of a signature encapsulated in a time-lock puzzle. We also present a new efficient range proof protocol that substantially improves upon existing proposals in terms of the proof size, and is also of independent interest.

While VTS is a versatile tool with numerous existing applications, we demonstrate VTS’s applicability to resolve three novel challenging issues in the space of cryptocurrencies. Specifically, we show how VTS is the cryptographic cornerstone to construct: (1) Payment channel networks with improved on-chain unlinkability of users involved in a transaction, (2) multi-party signing of transactions for cryptocurrencies without any on-chain notion of time and (3) cryptocurrency-enabled fair multi-party computation protocol.

[Keywords: timed signatures, time lock puzzles, payment channel network, multi-party signing]

“How to Build Time-lock Encryption”, Liu et al 2018

“How to build time-lock encryption”⁠, Jia Liu, Tibor Jager, Saqib A. Kakvi, Bogdan Warinschi (2018-01-20; ; backlinks; similar):

Time-lock encryption is a method to encrypt a message such that it can only be decrypted after a certain deadline has passed.

We propose a novel time-lock encryption scheme, whose main advantage over prior constructions is that even receivers with relatively weak computational resources should immediately be able to decrypt after the deadline, without any interaction with the sender, other receivers, or a trusted third party.

We build our time-lock encryption on top of the new concept of computational reference clocks and an extractable witness encryption scheme. We explain how to construct a computational reference clock based on Bitcoin. We show how to achieve constant level of multilinearity for witness encryption by using SNARKs. We propose a new construction of a witness encryption scheme which is of independent interest: our scheme, based on SubsetSum, achieves extractable security without relying on obfuscation. The scheme employs multilinear maps of arbitrary order and is independent of the implementations of multilinear maps.

“Easy Cryptographic Timestamping of Files”, Branwen 2015

Timestamping: “Easy Cryptographic Timestamping of Files”⁠, Gwern Branwen (2015-12-04; ⁠, ⁠, ⁠, ; backlinks; similar):

Scripts for convenient free secure Bitcoin-based dating of large numbers of files/​strings

Local archives are useful for personal purposes, but sometimes, in investigations that may be controversial, you want to be able to prove that the copy you downloaded was not modified and you need to timestamp it and prove the exact file existed on or before a certain date. This can be done by creating a cryptographic hash of the file and then publishing that hash to global chains like centralized digital timestampers or the decentralized Bitcoin blockchain. Current timestamping mechanisms tend to be centralized, manual, cumbersome, or cost too much to use routinely. Centralization can be overcome by timestamping to Bitcoin; costing too much can be overcome by batching up an arbitrary number of hashes and creating just 1 hash/​timestamp covering them all; manual & cumbersome can be overcome by writing programs to handle all of this and incorporating them into one’s workflow. So using an efficient cryptographic timestamping service (the OriginStamp Internet service), we can write programs to automatically & easily timestamp arbitrary files & strings, timestamp every commit to a Git repository, and webpages downloaded for archival purposes. We can implement the same idea offline, without reliance on OriginStamp, but at the cost of additional software dependencies like a Bitcoin client.

“Kadupul: Livin’ on the Edge With Virtual Currencies and Time-Locked Puzzles”, Skjegstad et al 2014

“Kadupul: Livin’ on the Edge with Virtual Currencies and Time-Locked Puzzles”⁠, Magnus Skjegstad, Anil Madhavapeddy, Jon Crowcroft (2014-12-15; backlinks; similar):

Devices connected to the Internet today have a wide range of local communication channels available, such as wireless Wifi, Bluetooth or NFC, as well as wired backhaul. In densely populated areas it is possible to create heterogeneous, multihop communication paths using a combination of these technologies, and often transmit data with lower latency than via a wired Internet connection. However, the potential for sharing meshed wireless radios in this way has never been realised due to the lack of economic incentives to do so on the part of individual nodes.

In this paper, we explore how virtual currencies such as Bitcoin might be used to provide an end-to-end incentive scheme to convince forwarding nodes that it is profitable to send packets on via the lowest latency mechanism available. Clients inject a small amount of money to transmit a datagram, and forwarding engines compete to solve a time-locked puzzle that can be claimed by the node that delivers the result in the lowest latency. This approach naturally extends congestion control techniques to a surge pricing model when available bandwidth is low. We conclude by discussing several latency-sensitive applications that would benefit for this, such as video streaming and local augmented reality systems.

“Blackmail Fail”, Branwen 2013

Blackmail: “Blackmail fail”⁠, Gwern Branwen (2013-12-10; ⁠, ; backlinks; similar):

In which the author receives surprising offers from kind strangers

In September 2012, I was extorted for $42.8[^\$32.0^~2012~]{.supsub} for being gwern; I declined to pay. In November 2013, I called an encryption bluff that I was Dread Pirate Roberts. In December 2013, a crazy person tried to blackmail me for billions of dollars for being Satoshi Nakamoto; I declined to pay. In March 2014, the DNM Evolution threatened to dox me if I did not reveal information about their security vulnerabilities. In February 2015, an Agora user doxed me in an unexpected way and I paid a small bounty.

“The Crypto-Currency: Bitcoin and Its Mysterious Inventor”, Davis 2013

2011-davis: “The Crypto-Currency: Bitcoin and its mysterious inventor”⁠, Joshua Davis (2013-04-18; ⁠, ; backlinks; similar):

2011 New Yorker article with descriptions of early Bitcoin people and mining, and the author’s search for Satoshi Nakamoto

Dept. Of Technology about bitcoin [sic] and its mysterious creator. There are lots of ways to make money: You can earn it, find it, counterfeit it, steal it. Or, if you’re Satoshi Nakamoto⁠, you can invent it. That’s what he did on the evening of January 3, 2009, when he pressed a button on his keyboard and created a new currency called Bitcoin. It was all bit, and no coin. There was no paper, copper, or silver-just thirty-one thousand lines of code and an announcement on the Internet. Nakamoto wanted to create a currency immune to the predations of bankers and politicians. The currency was controlled entirely by software. Every ten minutes or so, coins would be distributed through a process that resembled a lottery. This way, the bitcoin software would release a total of twenty-one million bitcoins, most all of them over the next twenty years. Interest in Nakamoto’s invention built steadily. More and more people dedicated their computers to the lottery, and forty-four exchanges popped up, allowing anyone with bitcoins to trade them for dollars, euros, or other currencies. At first, a single bitcoin was valued at less than a penny. But merchants gradually began to accept bitcoin, and at the end of 2010 the value began to appreciate rapidly. By June of 2011, a bitcoin was worth more than twenty-nine dollars. Market gyrations followed, and by September the exchange rate had fallen to five dollars. Still, with more than seven million bitcoins in circulation, Nakamoto had created thirty-five million dollars of value. And yet Nakamoto was a cipher. There was no trace of any coder with that name before the début of bitcoin. He used an e-mail address and Web site that were untraceable. In 2009 and 2010, he wrote hundreds of posts in flawless English, invited other software developers to help him improve the code. Then, in April, 2011, he sent a note to a developer saying that he had “moved on to other things.” He has not been heard from since. Tells about failed attempts to hack the bitcoin encryption code. Writer tries to deduce Nakamoto’s true identity from clues in his posts and his code. Describes the Crypto 2011 conference of cryptographers, where the writer went looking for Nakamoto. Writer speaks with two possible candidates, Michael Clear and Vili Lehdonvirta, both of whom deny that they are Nakamoto. Also tells about Kevin Groce, who runs a bitcoin-mining operation in Kentucky. Over the summer, hackers targeted bitcoin, and though they were unable to break Nakamoto’s code, they were able to disrupt the exchanges and destroy Web sites that helped users store bitcoins. The number of transactions decreased and the exchange rate plummeted. Commentators predicted the end of the currency. In September, however, volume began to increase again, and the price stabilized, at least temporarily.

“Correspondences Regarding Cryptography between John Nash and the NSA [typeset Version]”, Nash & Rosulek 2012

1955-nash-typeset.pdf: “Correspondences Regarding Cryptography between John Nash and the NSA [typeset version]”⁠, John Nash, Mike Rosulek (2012-02-20; backlinks):

In 1955, well-known mathematician John Nash was in correspondence with the United States National Security Agency. In these letters, Nash proposes a novel enciphering scheme. He also sets forth an important cryptographic principle that now underpin modern computational complexity theory and cryptography. In particular, he proposes a natural definition for “[security] in a practical sense”—that exponential computational effort is required for an enemy to recovery a secret key. Nash further conjectures that this property holds for any suitable enciphering mechanism.

These correspondences, recently declassified by the NSA1, have been transcribed and typeset in this document. [Typeset by Mike Rosulek: Department of Computer Science, University of Montana, ]

“Silk Road 1: Theory & Practice”, Branwen 2011

Silk-Road: “Silk Road 1: Theory & Practice”⁠, Gwern Branwen (2011-07-11; ⁠, ⁠, ⁠, ⁠, ⁠, ⁠, ⁠, ⁠, ⁠, ⁠, ⁠, ⁠, ⁠, ⁠, ; backlinks; similar):

History, background, visiting, ordering, using, & analyzing the drug market Silk Road 1

The cypherpunk movement laid the ideological roots of Bitcoin and the online drug market Silk Road; balancing previous emphasis on cryptography, I emphasize the non-cryptographic market aspects of Silk Road which is rooted in cypherpunk economic reasoning, and give a fully detailed account of how a buyer might use market information to rationally buy, and finish by discussing strengths and weaknesses of Silk Road, and what future developments are predicted by cypherpunk ideas.

“Bitcoin Is Worse Is Better”, Branwen 2011

Bitcoin-is-Worse-is-Better: “Bitcoin Is Worse Is Better”⁠, Gwern Branwen (2011-05-27; ⁠, ⁠, ; backlinks; similar):

2011 essay on how Bitcoin’s long gestation and early opposition indicates it is an example of the ‘Worse is Better’ paradigm in which an ugly complex design with few attractive theoretical properties compared to purer competitors nevertheless successfully takes over a niche, survives, and becomes gradually refined.

The genius of Bitcoin⁠, in inventing a digital currency successful in the real world, is not in creating any new abstruse mathematics or cryptographic breakthrough, but in putting together decades-old pieces in a semi-novel but extremely unpopular way. Everything Bitcoin needed was available for many years, including the key ideas.

The sacrifice Bitcoin makes to achieve decentralization is—however practical—a profoundly ugly one. Early reactions to Bitcoin by even friendly cryptographers & digital currency enthusiasts were almost uniformly extremely negative, and emphasized the (perceived) inefficiency & (relative to most cryptography) weak security guarantees. Critics let ‘perfect be the enemy of better’ and did not perceive Bitcoin’s potential.

However, in an example of ‘Worse is Better’, the ugly inefficient prototype of Bitcoin successfully created a secure decentralized digital currency, which can wait indefinitely for success, and this was enough to eventually lead to adoption, improvement, and growth into a secure global digital currency.

“Time-lock Encryption”, Branwen 2011

Self-decrypting-files: “Time-lock encryption”⁠, Gwern Branwen (2011-05-24; ⁠, ; backlinks; similar):

How do you encrypt a file such that it can be decrypted after a date, but not before? Use serial computations for proof-of-work using successive squaring, chained hashes, or witness encryption on blockchains.

In cryptography, it is easy to adjust encryption of data so that one, some, or all people can decrypt it, or some combination thereof. It is not so easy to achieve adjustable decryptability over time, a “time-lock crypto”: for some uses (data escrow, leaking, insurance, last-resort Bitcoin backups etc), one wants data which is distributed only after a certain point in time.

I survey techniques for time-lock crypto. Proposals often resort to trusted-third-parties, which are vulnerabilities. A better time-lock crypto proposal replaces trusted-third-parties with forcibly serial proof-of-work using number squaring and guaranteeing unlocking not after a certain point in time but after sufficient computation-time has been spent; it’s unclear how well number-squaring resists optimization or shortcuts. I suggest a new time-lock crypto based on chained hashes; hashes have been heavily attacked for other purposes, and may be safer than number-squaring. Finally, I cover obfuscation & witness-encryption which, combined with proof-of-work, can be said to solve time-lock crypto but currently remain infeasible.

“Death Note: L, Anonymity & Eluding Entropy”, Branwen 2011

Death-Note-Anonymity: “Death Note: L, Anonymity & Eluding Entropy”⁠, Gwern Branwen (2011-05-04; ⁠, ⁠, ⁠, ⁠, ⁠, ; backlinks; similar):

Applied Computer Science: On Murder Considered As STEM Field—using information theory to quantify the magnitude of Light Yagami’s mistakes in Death Note and considering fixes

In the manga Death Note, the protagonist Light Yagami is given the supernatural weapon “Death Note” which can kill anyone on demand, and begins using it to reshape the world. The genius detective L attempts to track him down with analysis and trickery, and ultimately succeeds. Death Note is almost a thought-experiment-given the perfect murder weapon, how can you screw up anyway? I consider the various steps of L’s process from the perspective of computer security, cryptography, and information theory, to quantify Light’s initial anonymity and how L gradually de-anonymizes him, and consider which mistake was the largest as follows:

  1. Light’s fundamental mistake is to kill in ways unrelated to his goal.

    Killing through heart attacks does not just make him visible early on, but the deaths reveals that his assassination method is impossibly precise and something profoundly anomalous is going on. L has been tipped off that Kira exists. Whatever the bogus justification may be, this is a major victory for his opponents. (To deter criminals and villains, it is not necessary for there to be a globally-known single anomalous or supernatural killer, when it would be equally effective to arrange for all the killings to be done naturalistically by ordinary mechanisms such as third parties/​police/​judiciary or used indirectly as parallel construction to crack cases.)

  2. Worse, the deaths are non-random in other ways—they tend to occur at particular times!

    Just the scheduling of deaths cost Light 6 bits of anonymity

  3. Light’s third mistake was reacting to the blatant provocation of Lind L. Tailor.

    Taking the bait let L narrow his target down to 1⁄3 the original Japanese population, for a gain of ~1.6 bits.

  4. Light’s fourth mistake was to use confidential police information stolen using his policeman father’s credentials.

    This mistake was the largest in bits lost. This mistake cost him 11 bits of anonymity; in other words, this mistake cost him twice what his scheduling cost him and almost 8 times the murder of Tailor!

  5. Killing Ray Penbar and the FBI team.

If we assume Penbar was tasked 200 leads out of the 10,000, then murdering him and the fiancee dropped Light just 6 bits or a little over half the fourth mistake and comparable to the original scheduling mistake. 6. Endgame: At this point in the plot, L resorts to direct measures and enters Light’s life directly, enrolling at the university, with Light unable to perfectly play the role of innocent under intense in-person surveillance.

From that point on, Light is screwed as he is now playing a deadly game of “Mafia” with L & the investigative team. He frittered away >25 bits of anonymity and then L intuited the rest and suspected him all along.

Finally, I suggest how Light could have most effectively employed the Death Note and limited his loss of anonymity. In an appendix, I discuss the maximum amount of information leakage possible from using a Death Note as a communication device.

(Note: This essay assumes a familiarity with the early plot of Death Note and Light Yagami. If you are unfamiliar with DN, see my Death Note Ending essay or consult Wikipedia or read the DN rules⁠.)

“LNCS 1796 - Time-Lock Puzzle With Examinable Evidence of Unlocking Time”, Mao 2000

2000-mao.pdf: “LNCS 1796 - Time-Lock Puzzle with Examinable Evidence of Unlocking Time”⁠, Wenbo Mao (2000-01-01; backlinks)

“Correspondences Regarding Cryptography between John Nash and the NSA”, Nash 1955

1955-nash-nsacryptography.pdf: “Correspondences Regarding Cryptography between John Nash and the NSA”⁠, John Nash (1955-01; backlinks):

[In 1955, well-known mathematician John Nash was in correspondence with the United States National Security Agency. In these letters, Nash proposes a novel enciphering scheme. He also sets forth an important cryptographic principle that now underpin modern computational complexity theory and cryptography. In particular, he proposes a natural definition for “[security] in a practical sense”—that exponential computational effort is required for an enemy to recovery a secret key. Nash further conjectures that this property holds for any suitable enciphering mechanism.

These correspondences, recently declassified by the NSA1; this document is the NSA scan with original images and drawings of Nash’s handwritten letters.]

Miscellaneous