Tag Info

18

What does this mean, exactly? The purpose of the environment is to model "everything else happening in the universe" besides the protocol execution. In the UC model, the adversary is allowed to talk to the environment during the execution of the protocol. So UC security means "security no matter what else is going on in the world, even if other things are ...

13

In general, the role of the simulator in simulation-based proofs is to show that the real protocol behaves like some idealized one. Actually, simulation goes back to the original definition of semantic security for encryption and is also the way zero knowledge is defined. In these settings, the aim of the simulator is to show that nothing is revealed (in ...

13

The different guarantees of security In security proofs, you have several guarantees that you can obtain on the security of a protocol. The most famous are maybe the following: game-based security sequential composable security general composable security (sequential + parallel composition) Game-based security The weaker guarantee that you can obtain is ...

10

Consider the function $f : \{L,R\} \times \{ U,D \} \to \{0,1,2\}$ defined by the following table: $$\begin{array}{c|cc} f & L & R \\ \hline U & 0 & 0 \\ D & 1 & 2 \end{array}$$ Let's say Alice has input from $\{L,R\}$ (she chooses a column) and Bob has input from $\{U,D\}$ (he chooses a row). A ...

6

Extractability inherently requires that the party who holds the extraction trapdoor can extract the witness. Therefore, it is important that the common reference string (CRS) is set up by a trusted party in the real protocol. However, this requirement for setting up the CRS in a trusted way is not only specific to extractability but also required by other ...

6

I think it is still possible to use UC in this case. Recall the setup for the UC framework. We have an ideal world and a real world. There are parties $P_1,\dots,P_n$ in each world and an environment $\mathcal{Z}$ in each. In the real world we have the adversary $\mathcal{A}$ while in the ideal world, we have an ideal functionality $\mathcal{F}$ and a ...

5

What's the principle to design the functionality, if it aims to a new scene that Canetti hasn't treated? Are the ability to corrupt parties (by some unknown methods) required to be written into the functionality? What else (except the normal functions) should be written into it? Basically, you can design the ideal functionality as you wish. The ...

4

Constant rate in general means that the overhead from a non-secure method is constant. So, in a simple way, if I am committing to an $\ell$-bit message, then the size of the commitment is $O(\ell)$. In some cases, however, one also allows an additive factor that is independent of the message size. Thus, for example, it could be that to commit to a message of ...

4

My goal is just to complete Mikero's answer, notably on that part: Also, I would be most grateful if you should show me example proofs in the UC framework. The shorter/easier the better, just so I can get my head around it. I just wrote a simple sketch of proof in this other answer. The goal is not to write a full formal proof in UC, but rather to give the ...

4

The standard (stand-alone) definitions were developed over many years, including the original GMW, Beaver, Goldwasser-Levin, and Micali-Rogaway. However, the standard definition used today is by Canetti, and was published in the Journal of Cryptology in 2000. That paper also proved the modular sequential composition theorem. Here is a link to that paper: ...

3

You're right that it's not UC-secure, for exactly the reason you say. It allows offline dictionary attacks. Here's how that problem manifests in the UC model: Consider this particular environment: Environment chooses honest party's password $pw$ uniformly from some known polynomial-size dictionary $\mathcal D$ (without loss of generality $\mathcal{D} = \{1,... 3 Lindell's "How to Simulate It" tutorial uses what is known as the standalone security model. See Section 10.1 for a discussion. The standalone model analyzes the security of a protocol instance, in isolation. The UC model analyzes security in the presence of arbitrary "other things going on in the world" concurrent with the protocol ... 2 Since fairness cannot be modeled, does that mean I cannot prove that a voting scheme, for example is fair (that is, that either the protocol finishes execution and everybody learns the result or nobody learns anything)? In the UC model, fairness is a property of the ideal functionality itself. A "fair functionality" is one that gives output to everybody or ... 2 UC broadcast can be defined by a functionality$\mathcal{F}_{\textrm{BC}}$, which upon receiving a message$x$from party$P_i$, sends$(x, P_i)$to all parties and the adversary. This is formally given in, e.g. Section 3.2 of a paper by Goldwasser and Lindell. However, many higher-level protocols use broadcast without explicitly specifying the ... 2 These two cases are trivial cases, usually don't need to argue about because they are definitely simulatable. In the first case, both parties are controlled by the adversary. In the simulation, the simulator simulates both the corrupted sender and the corrupted receiver. The simulator can simply use the adversary as a subroutine to simulate each party, ... 2 No, your construction is insecure, specifically it fails to be hiding. A receiver who has a guess of$M$can simply check whether$H(M)=c$since$H$is public. You can see that your suggested simulation strategy fails when the adversary has already queried$H$on$M$before the simulator learns that the commitment should hold$M$. The argument to$H$should ... 2 Is passive corruption actually equivalent to Byzantine corruption? The answer is clearly no, otherwise cryptographers wouldn't spend so much time on developing protocols for active security. Let me add an example to assist explanation. Consider that I can passively corrupt the webserver of CVS. I can steal their TLS/SSL certificate private keys in the CVS ... 2 An additional example to complement the other answers: the classical zero-knowledge protocol of Goldwasser, Micali, and Rackoff, based on quadratic residuosity (here), is perfectly zero-knowledge (and its statistical soundness can be made negligibly small via sequential repetition). A long standing open problem has been to understand whether it remains zero-... 2 Theorem 3.2 of the following paper presents a constructive counterexample for ZK concurrent composition about the DL problem. It is a very interesting construction. Uriel Feige, Adi Shamir. Witness Indistinguishable and Witness Hiding Protocols (STOC'90). https://www.isical.ac.in/~rcbose/internship/lectures2016/rt02feigeshamir.pdf 2 What Mark said in his answer is the crux of the matter, but here's how you interpret it in this particular situation: When they talk about the smart contract primitive they're referring to an object with the security guarantees we expect from smart contracts, with input-output behavior agrees with our intuitive idea of smart contracts. When they say "... 2 It is difficult to answer this question without looking at the same papers you are looking at. Still, I interpret these concepts as fairly different, for reasons I will sketch below. A function is common in mathematics, and can be written as some mapping$f : X\to Y$of inputs to outputs. Many algorithms implement the behavior of functions --- they take ... 2 The point that you are missing is as follows. If a protocol is UC secure for specialized simulators, then$\forall A \forall E\exists S$. In particular, this is true for the universal environment$E_u$. Denote this simulator by$S_u$. The argument is that$S_u$is a simulator for all environments. In particular,$S_u$working with$E_u$on input$(\langle E\...

2

The paper you cited gives that exact example. It shows that zero-knowledge that is NOT zero-knowledge for auxiliary input is not strong enough. The fact is that most known zero-knowledge proofs are secure for auxiliary input and thus are secure under sequential composition.

1

The paper contains text that explains why this is OK. I quote: The main idea behind the FKE functionality is as follows: If both participating parties are not corrupted, then they receive the same uniformly-distributed session key, and the adversary learns nothing about the key except that it was generated. However, if one of the parties is corrupted, then ...

1

@WYC, I suggest you take a look at the Lindell tutorial on https://eprint.iacr.org/2016/046.pdf To answer you #1 question, I'll get from that tutorial the following requirements for the simulator: It must generate a view for the real adversary that is indistinguishable from its real view; It must extract the effective inputs used by the adversary in the ...

1

"Simulation-based security" is a very general notion. UC security is much more specific - it refers to a simulation-based security proof in the UC framework. As such, simulation-based security encompass the UC framework, which is a particular case of it, and there is no general transformation from any primitive with a simulation-style security argument to a ...

1

Do not take my word for it, but as far as I remember: a GUC-secure protocol is secure in the UC framework; the converse is not true since a protocol secure in the UC framework might not allow for a global setup. The JUC framework is mainly aimed toward having, in the end, a proof in the standard UC framework: a protocol secure in the JUC framework can be ...

1

In the real world we do have adversary and environment. The environment interacts with the protocol (real function) and the adversary. The parties are part of the environment. The real function leaks information to the environment/adversary However, in the ideal world there is no such leakage. Therefore, in order to prevent the environment from ...

1

I think this would be the relevant paper to understand how to model synchronicity in the UC model: Universally composable synchronous computation: Jonathan Katz and Ueli Maurer and Bjoern Tackmann and Vassilis Zikas (TCC 2013) Basically, they define a "clock" functionality that performs a "tick" (increments a public counter) only after all honest parties ...

1

Try to prove something non-trivial using the universal composability framework and you will quickly understand why few people use it. EDIT: Snide remarks aside, it is pretty widely acknowledge that universal composability is really hard to use in papers. It's even hard to typeset - I've seen proofs with UC functionalities that don't fit on a single page! A ...

Only top voted, non community-wiki answers of a minimum length are eligible