2024-09-01 zk-insights Weekly

Highlights

Is Telegram really an encrypted messaging app?

Apropos Pavel Durov’s arrest, cryptographer Matthew Green wrote a short post about whether Telegram is an “encrypted messaging app”. The TL;DR here is that Telegram has an optional end-to-end encryption mode that you have to turn on manually. It only works for individual conversations, not for group chats.

• <https://blog.cryptographyengineering.com/2024/08/25/telegram-is-not-really-an-encrypted-messaging-app/>

Zirgen Circuit Compiler

Zirgen is a compiler for a domain-specific language, also called "zirgen", which creates arithmetic circuits for the RISC Zero proof system.

• <https://github.com/risc0/zirgen>

  Signed web pages with SXG

• <https://vivs.wiki/blog/SXG>

How Base 3 Computing Beats Binary

Long explored but infrequently embraced, base 3 computing may yet find a home in cybersecurity.

• <https://www.quantamagazine.org/how-base-3-computing-beats-binary-20240809/>

How Does Math Keep Secrets?

Cryptography is the thread that connects Julius Caesar, World War II and quantum computing, and it now lies under nearly every part of modern life. In this week’s episode, computer scientist Boaz Barak and co-host Janna Levin discuss the past and future of secrecy.

• <https://www.quantamagazine.org/how-does-math-keep-secrets-20240801/>

Updates

A major breakthrough in multiplication over Bitcoin, and in STARK verification on Bitcoin signet

A new algorithm for M31 multiplication reduces multiplication cost by 70%. Unlike STARKs, this new multiplication algorithm (like the previous algorithm) does not require OP_CAT, cementing M31’s status as a Bitcoin-friendly prime, regardless of OP_CAT.

• <https://github.com/Bitcoin-Wildlife-Sanctuary/bitcoin-circle-stark>

plonky3-ccs

A plonky3 to CCS converter.

• <https://github.com/dmpierre/plonky3-ccs>

  ZKVMs and Proof Verification with @ZKVProtocol, @RiscZero, @ProjectZKM and @alignedlayer

• <https://x.com/i/broadcasts/1ynJODXEAPvxR>

IACR Crypto 2024 (Videos)

• <https://www.youtube.com/playlist?list=PLeeS-3Ml-rprqjxP_UcoPRdnj1BmELWfp>

  Frontiers in Complexity Theory: A Graduate Workshop （Videos）

• <https://www.youtube.com/playlist?list=PLKVCRT3MRed7d05URwQ9xVFF5qdfHxUxc>

  ZK Con 2024 : ZK For Consumer Use (Videos)

• <https://www.youtube.com/playlist?list=PLMl4DDeHR107CCfrRsebFFtPmeOlBFFMP>

Papers

ECC’s Achilles’ Heel: Unveiling Weak Keys in Standardized Curves

• <https://eprint.iacr.org/2024/1321>

  SoK: Instruction Set Extensions for Cryptographers

• <https://eprint.iacr.org/2024/1323>

  On the structure of quaternion rings over ℤ/nℤ

• <https://arxiv.org/abs/1402.0956v2>

  Generalized one-way function and its application

• <https://eprint.iacr.org/2024/1343>

  Quantum Security of a Compact Multi-Signature

• <https://eprint.iacr.org/2024/1344>

  SoK: An Engineer’s Guide to Post-Quantum Cryptography for Embedded Devices

• <https://eprint.iacr.org/2024/1345>

  Zero-Knowledge Validation for an Offline Electronic Document Wallet using Bulletproofs

• <https://eprint.iacr.org/2024/1348>

  Proximity Gaps in Interleaved Codes

• <https://eprint.iacr.org/2024/1351>

  Direct Range Proofs for Paillier Cryptosystem and Their Applications

• <https://eprint.iacr.org/2024/1355>

  What Did Come Out of It? Analysis and Improvements of DIDComm Messaging

• <https://eprint.iacr.org/2024/1361>

  A Documentation of Ethereum’s PeerDAS

• <https://eprint.iacr.org/2024/1362>

  FLIP-and-prove R1CS

• <https://eprint.iacr.org/2024/1364>

Learnings

Foundations and Applications of Zero-Knowledge Proofs

The workshop will cover several topics within this field, including classical results, interactive oracle proofs, proof from symmetric primitives, group and pairing-based proof systems such as ZK-SNARKs, lattice-based proof systems, and real-world applications.

• <https://www.icms.org.uk/ZeroKnowledgeProofs>

  Error Correction Zoo

• <https://errorcorrectionzoo.org/>

  STARK101-rs

  A Rust tutorial for a basic STARK protocol to prove the calculation of a Fibonacci-Square sequence, as designed for StarkWare Sessions, and authored by the StarkWare team.

• <https://github.com/lambdaclass/STARK101-rs/>

  ZK Hack Montréal

• Polygon - The eSTARK Proving System & Plonky3 : <https://www.youtube.com/watch?v=2WjcXZYo7eA&list=PLj80z0cJm8QFGB6AsiAG3EB06L7xr5S1c&index=90>
• Risc Zero - Boundless On-chain Execution using Proven Off-chain Coprocessing : <https://www.youtube.com/watch?v=7M5aKRaGG1Q&list=PLj80z0cJm8QFGB6AsiAG3EB06L7xr5S1c&index=89>

  Programming ZKPs: From Zero to Hero

  This post will show you how to write basic Zero Knowledge Proofs (ZKPs) from scratch.

• <https://zkintro.com/articles/programming-zkps-from-zero-to-hero>