[go: up one dir, main page]
More Web Proxy on the site http://driver.im/

What a lovely hat

Is it made out of tin foil?




Dates are inconsistent

Dates are inconsistent

40 results sorted by ID

2024/1627 (PDF) Last updated: 2024-10-29
Lollipops of pairing-friendly elliptic curves for composition of proof systems
Craig Costello, Gaurish Korpal
Foundations

We construct lollipops of pairing-friendly elliptic curves, which combine pairing-friendly chains with pairing-friendly cycles. The cycles inside these lollipops allow for unbounded levels of recursive pairing-based proof system composition, while the chains leading into these cycles alleviate a significant drawback of using cycles on their own: the only known cycles of pairing-friendly elliptic curves force the initial part of the circuit to be arithmetised on suboptimal (much larger)...

2024/1566 (PDF) Last updated: 2025-02-14
Dynamic zk-SNARKs
Weijie Wang, Charalampos Papamanthou, Shravan Srinivasan, Dimitrios Papadopoulos
Cryptographic protocols

In this work, we put forth the notion of dynamic zk-SNARKs. A dynamic zk-SNARK is a zk-SNARK that has an additional update algorithm. The update algorithm takes as input a valid source statement-witness pair $(x,w)\in R$ along with a verifying proof $\pi$, and a valid target statement-witness pair $(x',w')\in R$. It outputs a verifying proof $\pi'$ for $(x',w')$ in sublinear time (for $(x,w)$ and $(x',w')$ with small Hamming distance) potentially with the help of a data structure. To the...

2024/1364 (PDF) Last updated: 2024-08-29
FLIP-and-prove R1CS
Anca Nitulescu, Nikitas Paslis, Carla Ràfols
Cryptographic protocols

In this work, we consider the setting where one or more users with low computational resources would lie to outsource the task of proof generation for SNARKs to one external entity, named Prover. We study the scenario in which Provers have access to all statements and witnesses to be proven beforehand. We take a different approach to proof aggregation and design a new protocol that reduces simultaneously proving time and communication complexity, without going through recursive proof...

2024/869 (PDF) Last updated: 2024-06-01
On cycles of pairing-friendly abelian varieties
Maria Corte-Real Santos, Craig Costello, Michael Naehrig
Foundations

One of the most promising avenues for realizing scalable proof systems relies on the existence of 2-cycles of pairing-friendly elliptic curves. Such a cycle consists of two elliptic curves E/GF(p) and E'/GF(q) that both have a low embedding degree and also satisfy q = #E and p = #E'. These constraints turn out to be rather restrictive; in the decade that has passed since 2-cycles were first proposed for use in proof systems, no new constructions of 2-cycles have been found. In this paper,...

2024/868 (PDF) Last updated: 2024-06-01
Loquat: A SNARK-Friendly Post-Quantum Signature based on the Legendre PRF with Applications in Ring and Aggregate Signatures
Xinyu Zhang, Ron Steinfeld, Muhammed F. Esgin, Joseph K. Liu, Dongxi Liu, Sushmita Ruj
Cryptographic protocols

We design and implement a novel post-quantum signature scheme based on the Legendre PRF, named Loquat. Prior to this work, efficient approaches for constructing post-quantum signatures with comparable security assumptions mainly used the MPC-in-the-head paradigm or hash trees. Our method departs from these paradigms and, notably, is SNARK-friendly, a feature not commonly found in earlier designs. Loquat requires significantly fewer computational operations for verification than other...

2024/640 (PDF) Last updated: 2024-04-26
On Proving Pairings
Andrija Novakovic, Liam Eagen
Cryptographic protocols

In this paper we explore efficient ways to prove correctness of elliptic curve pairing relations. Pairing-based cryptographic protocols such as the Groth16 and Plonk SNARKs and the BLS signature scheme are used extensively in public blockchains such as Ethereum due in large part to their small size. However the relatively high cost of pairing computation remains a practical problem for many use cases such as verification ``in circuit" inside a SNARK. This naturally arises in recursive SNARK...

2024/336 (PDF) Last updated: 2024-03-02
RAMenPaSTA: Parallelizable Scalable Transparent Arguments of Knowledge for RAM Programs
Khai Hanh Tang, Minh Pham, Chan Nam Ngo
Cryptographic protocols

Incremental Verifiable Computation (IVC) allows a prover to prove to a verifier the correct execution of a sequential computation. Recent works focus on improving the universality and efficiency of IVC Schemes, which can be categorized into Accumulation and Folding-based IVCs with Folding-based ones being more efficient (due to their deferred proof generation until the final step). Unfortunately, both approaches satisfy only heuristic security as they model the Random Oracle (RO) as a...

2024/306 (PDF) Last updated: 2024-06-01
Concretely Efficient Lattice-based Polynomial Commitment from Standard Assumptions
Intak Hwang, Jinyeong Seo, Yongsoo Song
Cryptographic protocols

Polynomial commitment is a crucial cryptographic primitive in constructing zkSNARKs. Most practical constructions to date are either vulnerable against quantum adversaries or lack homomorphic properties, which are essential for recursive proof composition and proof batching. Recently, lattice-based constructions have drawn attention for their potential to achieve all the desirable properties, though they often suffer from concrete inefficiency or rely on newly introduced assumptions...

2024/232 (PDF) Last updated: 2025-02-15
On the Security of Nova Recursive Proof System
Hyeonbum Lee, Jae Hong Seo
Foundations

Nova is a new type of recursive proof system that uses a folding scheme as its core building block. This brilliant idea of folding relations can significantly reduce the recursion overhead. In this paper, we study some issues related to Nova’s soundness proof, which relies on the soundness of the folding scheme in a recursive manner. First, due to its recursive nature, the proof strategy inevitably causes the running time of the recursive extractor to expand polynomially for each...

2024/162 (PDF) Last updated: 2024-07-22
Zero-Knowledge Proofs of Training for Deep Neural Networks
Kasra Abbaszadeh, Christodoulos Pappas, Jonathan Katz, Dimitrios Papadopoulos
Cryptographic protocols

A zero-knowledge proof of training (zkPoT) enables a party to prove that they have correctly trained a committed model based on a committed dataset without revealing any additional information about the model or the dataset. An ideal zkPoT should offer provable security and privacy guarantees, succinct proof size and verifier runtime, and practical prover efficiency. In this work, we present \name, a zkPoT targeted for deep neural networks (DNNs) that achieves all these goals at once. Our...

2024/099 (PDF) Last updated: 2024-01-22
Snarktor: A Decentralized Protocol for Scaling SNARKs Verification in Blockchains
Alberto Garoffolo, Dmytro Kaidalov, Roman Oliynykov
Applications

The use of zero-knowledge Succinct Non-Interactive Arguments of Knowledge (zk-SNARK) and similar types of proofs has become increasingly popular as a solution for improving scalability, privacy, and interoperability of blockchain systems. However, even with the most advanced proving systems, verifying a single SNARK proof can require a significant amount of computational resources making it expensive to be performed on-chain. This becomes a noticeable bottleneck in scaling SNARK-based...

2023/1646 (PDF) Last updated: 2024-09-11
Security Bounds for Proof-Carrying Data from Straightline Extractors
Alessandro Chiesa, Ziyi Guan, Shahar Samocha, Eylon Yogev
Foundations

Proof-carrying data (PCD) is a powerful cryptographic primitive that allows mutually distrustful parties to perform distributed computation in an efficiently verifiable manner. Real-world deployments of PCD have sparked keen interest within the applied community and industry. Known constructions of PCD are obtained by recursively-composing SNARKs or related primitives. Unfortunately, known security analyses incur expensive blowups, which practitioners have disregarded as the analyses...

2023/1282 (PDF) Last updated: 2024-07-11
Proof-Carrying Data from Multi-folding Schemes
Zibo Zhou, Zongyang Zhang, Zhiyu Zhang, Jin Dong
Foundations

Proof-carrying data (PCD) is a cryptographic primitive enabling mutually distrustful parties to perform distributed computations on directed acyclic graphs with efficient and incremental verification. Key performance metrics include the prover cost at each step and the recursion overhead, which measures the additional cost beyond proving the original computation. Despite substantial advancements in constructing efficient PCD schemes, these metrics continue to be bottlenecks hindering their...

2023/974 (PDF) Last updated: 2024-10-14
MuxProofs: Succinct Arguments for Machine Computation from Vector Lookups
Zijing Di, Lucas Xia, Wilson Nguyen, Nirvan Tyagi
Cryptographic protocols

Proofs for machine computation prove the correct execution of arbitrary programs that operate over fixed instruction sets (e.g., RISC-V, EVM, Wasm). A standard approach for proving machine computation is to prove a universal set of constraints that encode the full instruction set at each step of the program execution. This approach incurs a proving cost per execution step on the order of the total sum of instruction constraints for all of the instructions in the set, despite each step of the...

2023/869 (PDF) Last updated: 2023-07-13
UniPlonk: Plonk with Universal Verifier
Shumo Chu, Brandon H. Gomes, Francisco Hernandez Iglesias, Todd Norton, Duncan Tebbs
Public-key cryptography

We propose UniPlonK, a modification of the PlonK protocol that uniformizes the Verifier’s work for families of circuits. Specifically, a single fixed-cost “Universal Verifier” can check proofs for circuits of different: sizes, public input lengths, selector polynomials, copy constraints, and even different custom gate sets. UniPlonK therefore extends the universality of PlonK beyond the SRS; it enables a single “Universal Verifier Circuit” capable of verifying proofs from different PlonK...

2023/620 (PDF) Last updated: 2023-12-21
ProtoStar: Generic Efficient Accumulation/Folding for Special Sound Protocols
Benedikt Bünz, Binyi Chen
Public-key cryptography

Accumulation is a simple yet powerful primitive that enables incrementally verifiable computation (IVC) without the need for recursive SNARKs. We provide a generic, efficient accumulation (or folding) scheme for any $(2k-1)$-move special-sound protocol with a verifier that checks $\ell$ degree-$d$ equations. The accumulation verifier only performs $k+2$ elliptic curve multiplications and $k+d+O(1)$ field/hash operations. Using the compiler from BCLMS21 (Crypto 21), this enables building...

2022/1758 (PDF) Last updated: 2022-12-22
SuperNova: Proving universal machine executions without universal circuits
Abhiram Kothapalli, Srinath Setty
Foundations

This paper introduces SuperNova, a new recursive proof system for incrementally producing succinct proofs of correct execution of programs on a stateful machine with a particular instruction set (e.g., EVM, RISC-V). A distinguishing aspect of SuperNova is that the cost of proving a step of a program is proportional only to the size of the circuit representing the instruction invoked by the program step. This is a stark departure from prior works that employ universal circuits where the cost...

2022/1662 (PDF) Last updated: 2023-05-26
Revisiting cycles of pairing-friendly elliptic curves
Marta Bellés-Muñoz, Jorge Jiménez Urroz, Javier Silva
Public-key cryptography

A recent area of interest in cryptography is recursive composition of proof systems. One of the approaches to make recursive composition efficient involves cycles of pairing-friendly elliptic curves of prime order. However, known constructions have very low embedding degrees. This entails large parameter sizes, which makes the overall system inefficient. In this paper, we explore $2$-cycles composed of curves from families parameterized by polynomials, and show that such cycles do not...

2022/1072 (PDF) Last updated: 2023-09-04
Recursion over Public-Coin Interactive Proof Systems; Faster Hash Verification
Alexandre Belling, Azam Soleimanian, Olivier Bégassat
Cryptographic protocols

SNARK is a well-known family of cryptographic tools that is increasingly used in the field of computation integrity at scale. In this area, multiple works have introduced SNARK-friendly cryptographic primitives: hashing, but also encryption and signature verification. Despite all the efforts to create cryptographic primitives that can be proved faster, it remains a major performance hole in practice. In this paper, we present a recursive technique that can improve the efficiency of the...

2022/941 (PDF) Last updated: 2023-02-08
Lattice-Based SNARKs: Publicly Verifiable, Preprocessing, and Recursively Composable
Martin R. Albrecht, Valerio Cini, Russell W. F. Lai, Giulio Malavolta, Sri AravindaKrishnan Thyagarajan
Cryptographic protocols

A succinct non-interactive argument of knowledge (SNARK) allows a prover to produce a short proof that certifies the veracity of a certain NP-statement. In the last decade, a large body of work has studied candidate constructions that are secure against quantum attackers. Unfortunately, no known candidate matches the efficiency and desirable features of (pre-quantum) constructions based on bilinear pairings. In this work, we make progress on this question. We propose the first...

2022/596 (PDF) Last updated: 2022-05-17
Zero Knowledge Proofs of Elliptic Curve Inner Products from Principal Divisors and Weil Reciprocity
Liam Eagen
Cryptographic protocols

Zero Knowledge proofs of Elliptic Curve Inner Products (ECIPs) and elliptic curve operations more generally are an increasingly important part of zero knowledge protocols and a significant bottle neck in recursive proof composition over amicable cycles of elliptic curves. To prove ECIPs more efficiently, I represent a collection of points that sum to zero using a polynomial element of the function field and evaluate this function at a random principal divisor. By Weil reciprocity, this is...

2022/383 (PDF) Last updated: 2022-03-28
On Succinct Non-Interactive Arguments in Relativized Worlds
Megan Chen, Alessandro Chiesa, Nicholas Spooner
Foundations

Succinct non-interactive arguments of knowledge (SNARKs) are cryptographic proofs with strong efficiency properties. Applications of SNARKs often involve proving computations that include the SNARK verifier, a technique called recursive composition. Unfortunately, SNARKs with desirable features such as a transparent (public-coin) setup are known only in the random oracle model (ROM). In applications this oracle must be heuristically instantiated and used in a non-black-box way. In this...

2021/567 (PDF) Last updated: 2021-05-07
Forward-secure Multi-user Aggregate Signatures based on zk-SNARKs
Jeonghyuk Lee, Jihye Kim, Hyunok Oh
Cryptographic protocols

As a solution to mitigate the key exposure problems in the digital signature, forward security has been proposed. The forward security guarantees the integrity of the messages generated in the past despite leaks of a current time period secret key by evolving a secret key on each time period. However, there is no forward secure signature scheme whose all metrics have constant complexities. Furthermore, existing works do not support multi-user aggregation of signatures. In this paper, we...

2021/467 (PDF) Last updated: 2021-04-12
Key-schedule Security for the TLS 1.3 Standard
Chris Brzuska, Antoine Delignat-Lavaud, Christoph Egger, Cédric Fournet, Konrad Kohbrok, Markulf Kohlweiss
Cryptographic protocols

We analyze the security of the TLS 1.3 key establishment protocol, as specified at the end of its rigorous standardization process. We define a core key-schedule and reduce its security to concrete assumptions against an adversary that controls client and server configurations and adaptively chooses some of their keys. Our model supports all key derivations featured in the standard, including its negotiated modes and algorithms that combine an optional Diffie-Hellman exchange for...

2021/370 (PDF) Last updated: 2024-07-20
Nova: Recursive Zero-Knowledge Arguments from Folding Schemes
Abhiram Kothapalli, Srinath Setty, Ioanna Tzialla
Foundations

We introduce a new approach to realize incrementally verifiable computation (IVC), in which the prover recursively proves the correct execution of incremental computations of the form $y=F^{(\ell)}(x)$, where $F$ is a (potentially non-deterministic) computation, $x$ is the input, $y$ is the output, and $\ell > 0$. Unlike prior approaches to realize IVC, our approach avoids succinct non-interactive arguments of knowledge (SNARKs) entirely and arguments of knowledge in general. Instead, we...

2020/1618 (PDF) Last updated: 2021-12-01
Proof-Carrying Data without Succinct Arguments
Benedikt Bünz, Alessandro Chiesa, William Lin, Pratyush Mishra, Nicholas Spooner
Foundations

Proof-carrying data (PCD) is a powerful cryptographic primitive that enables mutually distrustful parties to perform distributed computations that run indefinitely. Known approaches to construct PCD are based on succinct non-interactive arguments of knowledge (SNARKs) that have a succinct verifier or a succinct accumulation scheme. In this paper we show how to obtain PCD without relying on SNARKs. We construct a PCD scheme given any non-interactive argument of knowledge (e.g., with...

2020/499 (PDF) Last updated: 2020-09-29
Proof-Carrying Data from Accumulation Schemes
Benedikt Bünz, Alessandro Chiesa, Pratyush Mishra, Nicholas Spooner
Foundations

Recursive proof composition has been shown to lead to powerful primitives such as incrementally-verifiable computation (IVC) and proof-carrying data (PCD). All existing approaches to recursive composition take a succinct non-interactive argument of knowledge (SNARK) and use it to prove a statement about its own verifier. This technique requires that the verifier run in time sublinear in the size of the statement it is checking, a strong requirement that restricts the class of SNARKs from...

2020/351 (PDF) Last updated: 2020-10-09
Optimized and secure pairing-friendly elliptic curves suitable for one layer proof composition
Youssef El Housni, Aurore Guillevic
Implementation

A zero-knowledge proof is a method by which one can prove knowledge of general non-deterministic polynomial (NP) statements. SNARKs are in addition non-interactive, short and cheap to verify. This property makes them suitable for recursive proof composition, that is proofs attesting to the validity of other proofs. To achieve this, one moves the arithmetic operations to the exponents. Recursive proof composition has been empirically demonstrated for pairing-based SNARKs via tailored...

2020/123 (PDF) Last updated: 2024-01-22
Zendoo: a zk-SNARK Verifiable Cross-Chain Transfer Protocol Enabling Decoupled and Decentralized Sidechains
Alberto Garoffolo, Dmytro Kaidalov, Roman Oliynykov
Cryptographic protocols

Sidechains are an appealing innovation devised to enable blockchain scalability and extensibility. The basic idea is simple yet powerful: construct a parallel chain - sidechain - with desired features, and provide a way to transfer coins between the mainchain and the sidechain. In this paper, we introduce Zendoo, a construction for Bitcoin-like blockchain systems that allows the creation and communication with sidechains of different types without knowing their internal structure. We...

2019/1407 (PDF) Last updated: 2019-12-05
Incrementally Verifiable Computation via Incremental PCPs
Moni Naor, Omer Paneth, Guy N. Rothblum

If I commission a long computation, how can I check that the result is correct without re-doing the computation myself? This is the question that efficient verifiable computation deals with. In this work, we address the issue of verifying the computation as it unfolds. That is, at any intermediate point in the computation, I would like to see a proof that the current state is correct. Ideally, these proofs should be short, non-interactive, and easy to verify. In addition, the proof at each...

2019/1177 (PDF) Last updated: 2020-12-09
Proofs for Inner Pairing Products and Applications
Benedikt Bünz, Mary Maller, Pratyush Mishra, Nirvan Tyagi, Psi Vesely
Public-key cryptography

We present a generalized inner product argument and demonstrate its applications to pairing-based languages. We apply our generalized argument to proving that an inner pairing product is correctly evaluated with respect to committed vectors of $n$ source group elements. With a structured reference string (SRS), we achieve a logarithmic-time verifier whose work is dominated by $6 \log n$ target group exponentiations. Proofs are of size $6 \log n$ target group elements, computed using $6n$...

2019/1076 (PDF) Last updated: 2020-07-15
Fractal: Post-Quantum and Transparent Recursive Proofs from Holography
Alessandro Chiesa, Dev Ojha, Nicholas Spooner
Foundations

We present a new methodology to efficiently realize recursive composition of succinct non-interactive arguments of knowledge (SNARKs). Prior to this work, the only known methodology relied on pairing-based SNARKs instantiated on cycles of pairing-friendly elliptic curves, an expensive algebraic object. Our methodology does not rely on any special algebraic objects and, moreover, achieves new desirable properties: it is *post-quantum* and it is *transparent* (the setup is public coin). We...

2019/1021 (PDF) Last updated: 2020-02-18
Recursive Proof Composition without a Trusted Setup
Sean Bowe, Jack Grigg, Daira Hopwood
Cryptographic protocols

Non-interactive arguments of knowledge are powerful cryptographic tools that can be used to demonstrate the faithful execution of arbitrary computations with publicly verifiable proofs. Increasingly efficient protocols have been described in recent years, with verification time and/or communication complexity that is sublinear in the size of the computation being described. These efficiencies can be exploited to realize recursive proof composition: the concept of proofs that attest to the...

2019/265 (PDF) Last updated: 2019-03-06
TEX - A Securely Scalable Trustless Exchange
Rami Khalil, Arthur Gervais, Guillaume Felley
Cryptographic protocols

Financial exchanges are typically built out of two trusted components: a trade matching and a trade settlement system. With the advent of decentralized ledgers, that perform transactions without a trusted intermediary, so called decentralized exchanges (DEX) emerged. Some DEXs propose to off-load trade order matching to a centralized system outside the blockchain to scale, but settle each trade trustlessly as an expensive on-chain transaction. While DEX are non-custodial, their order books...

2018/962 (PDF) Last updated: 2021-03-30
Zexe: Enabling Decentralized Private Computation
Sean Bowe, Alessandro Chiesa, Matthew Green, Ian Miers, Pratyush Mishra, Howard Wu
Cryptographic protocols

Ledger-based systems that support rich applications often suffer from two limitations. First, validating a transaction requires re-executing the state transition that it attests to. Second, transactions not only reveal which application had a state transition but also reveal the application's internal state. We design, implement, and evaluate ZEXE, a ledger-based system where users can execute offline computations and subsequently produce transactions, attesting to the correctness of these...

2015/377 (PDF) Last updated: 2015-04-28
Cluster Computing in Zero Knowledge
Alessandro Chiesa, Eran Tromer, Madars Virza
Cryptographic protocols

Large computations, when amenable to distributed parallel execution, are often executed on computer clusters, for scalability and cost reasons. Such computations are used in many applications, including, to name but a few, machine learning, webgraph mining, and statistical machine translation. Oftentimes, though, the input data is private and only the result of the computation can be published. Zero-knowledge proofs would allow, in such settings, to verify correctness of the output without...

2014/595 (PDF) Last updated: 2020-06-18
Scalable Zero Knowledge via Cycles of Elliptic Curves
Eli Ben-Sasson, Alessandro Chiesa, Eran Tromer, Madars Virza
Cryptographic protocols

Non-interactive zero-knowledge proofs of knowledge for general NP statements are a powerful cryptographic primitive, both in theory and in practical applications. Recently, much research has focused on achieving an additional property, succinctness, requiring the proof to be very short and easy to verify. Such proof systems are known as zero-knowledge succinct non-interactive arguments of knowledge (zk-SNARKs), and are desired when communication is expensive, or the verifier is...

2012/718 (PDF) Last updated: 2013-09-15
Succinct Non-Interactive Arguments via Linear Interactive Proofs
Nir Bitansky, Alessandro Chiesa, Yuval Ishai, Rafail Ostrovsky, Omer Paneth
Foundations

\emph{Succinct non-interactive arguments} (SNARGs) enable verifying NP statements with lower complexity than required for classical NP verification. Traditionally, the focus has been on minimizing the length of such arguments; nowadays researches have focused also on minimizing verification time, by drawing motivation from the problem of delegating computation. A common relaxation is a \emph{preprocessing} SNARG, which allows the verifier to conduct an expensive offline phase that is...

2012/215 (PDF) Last updated: 2012-06-18
Quadratic Span Programs and Succinct NIZKs without PCPs
Rosario Gennaro, Craig Gentry, Bryan Parno, Mariana Raykova
Foundations

We introduce a new characterization of the NP complexity class, called Quadratic Span Programs (QSPs), which is a natural extension of span programs defined by Karchmer and Wigderson. Our main motivation is the construction of succinct arguments of NP-statements that are quick to construct and verify. QSPs seem well-suited for this task, perhaps even better than Probabilistically Checkable Proofs (PCPs). In 2010, Groth constructed a NIZK argument in the common reference string (CRS) model...

2012/095 (PDF) Last updated: 2012-12-28
Recursive Composition and Bootstrapping for SNARKs and Proof-Carrying Data
Nir Bitansky, Ran Canetti, Alessandro Chiesa, Eran Tromer

\emph{Succinct non-interactive arguments} (SNARGs) enable verifying NP statements with much lower complexity than required for classical NP verification (in fact, with complexity that is \emph{independent} of the NP language at hand). In particular, SNARGs provide strong solutions to the problem of verifiably delegating computation. Despite recent progress in the understanding and construction of SNARGs, there remain unattained goals. First, \emph{publicly-verifiable SNARGs} are only known...

Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.