Lattice-Based Cryptography in Miden VM

This note discusses lattice-based cryptography over the field with $p = 2^{64}-2^{32}+1$ elements, with an eye to supporting lattice-based cryptography operations in virtual machines such as Miden VM that operate natively over this field. It discusses how to support Dilithium and Falcon, two lattice-based signature scheme recently selected by the NIST PQC project; and proposes parameters for efficient public key encryption and publicly re-randomizable commitments modulo $p$.

Read the report here or on eprint.

Event: State of the Art of Cryptography in Blockchains

On 12 November 2020, the Cryptography Working Group (jointly with CVLabs) held the first event on the theme “cryptography in blockchains”. We counted 99 (!) registrations in the Eventbrite. However, in light of the dire situation in regards to the Covid-19 pandemic, the decision was made to host the event entirely online. Approximately 40 people tuned in for the live stream, a recording of which is on YouTube. Have a look here!

The event started with an introduction by Ralf Kubli to the Cryptovalley ecosystem and CVVC specifically, followed by an introduction to CVLabs by Fabiola Luna Huerta.

The first speaker was Alan Szepieniec, of AS Discrete Mathematics and the Cryptography Working Group. He introduced the theme of the event: the focus on the intersection between two disparate worlds, cryptography and cryptocurrency respectively. This talk made the case for growing this intersection.

Next up was Jean-Philippe Aumasson of TaurusGroup, who gave a talk on the implementation pitfalls of multisignature schemes. The idea behind this type of scheme is that multiple independent parties must collaborate in order to release funds or approve a payment, thereby eliminating the security hazard posed by having a single point of failure. However, two new attacks show that upgrading a regular signature scheme to a multisignature scheme is a process fraught with vulnerabilities and pitfalls. It can work, but only if you’re extremely careful.

The third speaker was professor Kenny Paterson of ETH Zurich. He spoke about research he and his collaborators had done to undermine the privacy guarantees of private cryptocurrencies, colloquially known as privacycoins. Rather than attacking the cryptography itself from an abstract and mathematical perspective, these attacks focus on how the cryptography was implemented. For instance, clients took longer to respond to ping requests when they were validating a new transaction to which they were the recipient. This network-level information source allows the attacker to determine the IP address of the recipient of funds, even though this destination is hidden by the cryptography.

The last speaker was Luca De Feo, who is a researcher at IBM Zurich and whose research focuses on elliptic curve isogenies. Typically, isogeny-based cryptography is touted as a strategy for achieving post-quantum cryptography with compact public keys, ciphertexts and signatures. However, today’s talk was about combining isogenies with pairings, which are not post-quantum secure. However, it turns out that by combining the two one can construct verifiable delay functions whose evaluation proofs are 0 bytes — in other words, the verifier needs no extra information to verify the correct output. The scheme does rely on an updatable trusted setup, and it remains to be determined whether this trusted setup can be eliminated altogether.

Introduction to GB Attacks on AOC

Next Wednesday, 12 August 2020 at 16:30 CET, our own Ferdinand Sauer will be giving an introductory presentation on Gröbner basis attacks in the context of attacking arithmetization-oriented ciphers. Be sure to tune in if you want to learn more about the attack space for AO ciphers like Rescue and Poseidon. Email us if you want access to the zoom link.

Update: Slides & VoD

Summary slide of the introductory presentation to Gröbner bases.

Couldn’t make it? Not to worry! Take a peek at the slides, and complement them by watching the recording.

STARK-friendly hash report

Researchers at StarkWare have published a report detailing their decision process of hash function for hashing over STARKs. In the end they chose for the arithmetization oriented cipher Rescue. The report also includes an appendix by Jean-Charles Faugère and Ludovic Perret about the security of these ciphers against Gröbner basis attacks. Read the report here.