2206#

三篇最新的关于UC model的论文

We provide formal proofs for the construction of the V-zkHawk protocol. The proofs and theorems in this paper are modeled in the UC framework. We define the ideal functionalities for our real world protocols that also interacts with a sim- ulator (mimicking an adversary in real world) such that no PPT (Probabilistic Polynomial Time) environment can distinguish between ideal and real worlds.

Existing Private Smart Contract Protocols#

PSC

  • Hawk->zkHawk-> V-zkHawk

  • zkay

  • Arbitrum

  • Kachina

  • Zether

  • Shielded Computations in Smart Contracts

  • ShadowEth

2205#

a signature scheme \(\Pi\) yields \(k\) bits of (multi-user) security if any attacker running in time at most \(t\) can forge a signature with probability at most \(\varepsilon_{t}=t / 2^{k}\) in the (multi-user) signature forgery game, and this should hold for all time bounds \(t \leq 2^{k}\).

To achieve \(k\) bits of security, we select a hash function \(\mathrm{H}\) with \(2 k\)-bit outputs, and we select \(p\) to be a random \(2 k\)-bit prime so that the length of a signature is \(4 k\) bits.

In Schnorr’s original paper [Sch90], the author proposed the possibility of achieving even shorter Schnorr signatures by selecting a hash function \(\mathrm{H}\) with \(k\)-bit outputs (or truncating to only use the first \(k\) bits) so that the final signature \(\sigma=(s, e)\) can be encoded with \(3 k\) bits. We refer to this signature scheme as the short Schnorr signature scheme.

The framework [15, 16] guarantees strong security for multi-party composed protocols like our CIPs since the interactions between the multiple parties and multiple protocols must be thoroughly modeled to realize the security. Informally, UC says that if there is an ideal function with the desired security properties, and a real protocol that acts the same as the ideal function, then the real protocol also has the ideal function’s security properties.

The Universal Composability (UC) model [Can01, Can04, CF01, DN02] is a framework used to analyze the security of composed protocols that combine multiple protocols together.

In the UC model, there are an ideal system, a real system, and an environment \(\mathcal{E}\) (challengee). \(\mathcal{E}\) ‘s task is to identify which system it is interacting with: ideal or real.

We say the real system realizes the ideal system if \(\mathcal{E}\) can not identify the correct system with more than \(1 / 2+\epsilon(\lambda)\) probability.

In that case, informally, Universal Composability says that the real system provides the security properties of the ideal system.

[ANO+21]

Gemini: [BCHO22]

The code structure follows the modular design of the protocol, which involves combining an elastic polynomial commitment scheme and an elastic (holographic) PIOP. We deem each of the single components of the protocol (the streaming infrastructure, the commitment scheme,and the sub-protocols for sumcheck, tensor check, entry product, lookup protocol, etc.) to be independent interest for future space-efficient projects.

There is a long line of work on improving the time complexity of SNARK provers, both asymptotically and concretely; this has culminated in SNARKs with linear-time provers. See [GLS+21] and references therein.

However, these optimizations typically come at the expense of space complexity, which is typically linear in the computation size either due to the use of FFTs or dynamic programming algorithms.

Document

Modified

Method

Run Time (s)

Status

np/polynomial_python

2023-02-01 11:46

cache

-

❌