# Tag Info

7

Your problem seems to be at least as hard as the 2-weak Bilinear Diffie-Hellman Inversion Problem (2-wBDHI problem): Given $g, g^x, g^{x^2}, g^y \in \mathbb G$, and $T \in \mathbb G_T$ to determine whether or not $T = e(g,g)^{x^3 y}$. Proof: We first need to define an equivalent version of your problem, where we take some generator $h$ so $g = h^b$. ...

6

Let me try to answer your second question, and hopefully shed some light on the first one in doing so. When we encrypt a message, it's because we want to keep something about that message secret. But what is it that we actually want to protect? Let's say the message we're encrypting is AGENT DOE REPORTS 23 UNITS ON BOARD SHIP TO BASE ALPHA, DEPARTED ON ...

5

As fgrieu notes in the comments, the protocol might not even work reliably in the absence of adversaries: if the tag fails to receive the reader's reply of "True", the keys will get out of sync. (If that happens, the tag will just retry the next exchange with the old key, so this could be fixed by having the reader remember one more "subkey". But the ...

5

My experience of such proofs is that often you're proving a much stronger statement: in any execution of Game i+1, either everything is distributed identically to Game i or else F must have happened. In other words, the conditional distribution of game i+1 conditioned on F not happening is identical to the distribution of Game i. For example, one of ...

5

This is in principle similar as how "normal" cryptosystems are proven. With some algorithms we can reduce them to some "hard problem", but we do not know that those problems are actually hard to solve. Only that we cannot solve them efficiently. For example, the Diffie-Hellman problem is not even known to be NP-hard, never mind the whole issue of P vs. NP. ...

5

You can generate a random string $s_1$ as long as the plaintext. Then XOR this value with the plaintext generating $s_2$. Now encrypt both parts using $\mathrm{Enc}_1$ and $\mathrm{Enc}_2$. You need to decrypt both to XOR the two parts together again. This is similar to secret sharing where you need two parts of a key to decrypt. If $\mathrm{Gen}_1$ and ...

4

The point why a simulation must not deviate too much from the real game is due to the following reasoning. You assume you have an adversary that wins the original game, but you do not know how the adversary acts if you deviate from the behaviour of the real game and the adversary can notice this. Exactly because you make no assumption whatsoever about the ...

4

Collision and preimage resistance does not imply this; suppose we select a collision and preimage resistant function $H$ with a known value $I$ with $H(I) = 1$ (the group identity); this additional assertion does not contradict the assumptions of collision or preimage resistance. Then, given $a$, we can easily output the tuple $(I, a)$; as we have $H(I) ... 4 Your proof certainly has to work even if the adversary doesn't use the random oracle. One technique that you can try is to begin by proving a separate lemma that if the adversary doesn't ask a certain query first, then it definitely cannot succeed in distinguishing. Then, you proceed to prove the simulation conditioned on it asking this query. However, if ... 4 Before answering the actual question, I will offer some general advice. It is important to pay attention, both in class and to the textbook you are reading. If learning how to solve such exercises is a key goal of the course, such solutions have very probably been discussed at length in class. Moreover, your textbook also has proof examples, and in this ... 4 Realizes vs Implements Given the context of the cited papers, they mean the same thing. That said, I would prefer realizes. Implements has a connotation of a source code implementation. There could be implementation flaws (buffer overflow, etc) that impact security. The protocol design is secure, but the implementation is not. That, to me, is the primary ... 4 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 ... 3 Ok, here's a version that definitely works. Three points: If we know$S_2$is close to$1/2$, then the statement that$S_1$and$S_2$are close is equivalent to saying that$S_1$is close to$1/2$. So I'll prove the latter version. The way to deal with the edge cases, I think, is to demand Pr$[S_2|F] = 1/2$. This is the case whenever the game (not the ... 3 However I think that the requirement on$\Pr[F]$is way too strong: one can prove security with much more frequent faults. Maybe this short paper by Alexander W. Dent could be of interest: A Note On Game-Hopping Proofs? In this paper he introduces a fourth kind of game hop, namely transitions based on large failure events, which seems to be exactly what ... 3 The reason NIST chose one algorithm out of the five AES finalists, even though all of them were pretty well-respected (and some were, at the time, considered likely to be more secure then Rijndael) is because NIST is a standards body, and the whole point of the AES project was to find a standard algorithm. The issue with approving lots of algorithms is that ... 3 You have to worry not just about a pair of blinding values being equal, but more complex relationships between them. Thus, finding a proof of security for this approach looks non-trivial to me. Let me elaborate. Suppose$R_j$is the$j$th blinding variable you use. If$R_i = R_j$, that's a problem, but as you say, that can be made very unlikely. ... 3 Let's take a set with$p$uniquely defined elements. A uniformly random distribution is that every element has a chance$1/p$to be picked. What if the last element is never picked and the rest are with an uniform probability of$(p-1)^{-1}$? If you see$k$items you expect to see the last one with probability$1-(1-1/n)^k$. When$n$is large, that is ... 3$\mathbb{F}_p$actually has p elements. Hence, an element would be picked uniformly at random if every element was chosen with probability$1/p$. Already if one element is chosen with probability$\frac{1}{p-1}$this is not a uniform distribution anymore. Depending on the size of$p$you can argue that the distribution is statistically indistinguishable from ... 3 Assuming that the probability distributions of$\pi_{k_1}$and$\pi_{k_2}$are both uniform (that is, each permutation can take on any particular setting with probability$1/n!$), then no, adversary does not have enough information to learn anything about the original positions. This remains true even if we assume the adversary can perform unbounded ... 3 For any$n \in \mathbf{N}$, let$X_n$be a random variable which always equals$n$, and$Y_n$be a random variable which equals$n$or$n+1$each with probability$1/2$. Then the probability ensembles$X = \{X_n\}_{n\in \mathbf{N}}$and$Y = \{Y_n\}_{n\in \mathbf{N}}$are not computationally indisinguishable. A possible distinguisher is an algorithm$D$... 3 I would think these numbers would have been put on the google search engine, and yield (probably) many hits. This assumption is wrong. Certificate serial numbers are not indexed by common search engines, nor are they typically posted to any HTML site. Frankly, I'm not sure why you would assume they'd be indexed. The Wordpress certificate is used for ... 3 Note that in the definition you gave, it says that in order for$\Pi$to be an indistinguishable scheme, then the above inequality must hold for all PPT adversaries. So it seems that if$\Pi$holds the indistinguishability, then there should not exist any adversary A that$\Pr[\mathsf{Exp}_{A,\Pi}(\lambda) = 1] < 1/2 + \mathsf{negl}(\lambda)$, for ... 3 The ideal encryption scheme$E$would be one that, for every ciphertext$C=E(K, M)$, if the key remains secret for the adversary, the probability of identifying$M$is negligible. Since that is not possible in practice, the second most reasonable approach is to define constraints strong enough to satisfy some definition of security. The$IND-$notation ... 3 "simulator": That's a definition of security in a model that is related to but weaker than the universal composability framework (thanks to Yehuda Lindell for making that clear and you can look at the paper in his comment). You could also look up the wiki link and I think there are also several question on this site. As @Yehuda Lindell mentions in a ... 3 There is quite a bit of confusion in your question. First, differentiate between the real and ideal models. The adversary in the ideal model sends the adversary's input and gets its output (and can also sometimes determine if the honest party gets output, depending on the model). We often call the ideal adversary a "simulator" since this is how we build the ... 3 Detection of malicious behavior can happen anywhere. However, it is not true that you can run semi-honest protocols and then check later. This is because such protocols can reveal the honest party's input when interacting with a malicious adversary. In such as case, even if you detect the cheating, security is not achieved. Thus, you need to make sure that ... 3 This is very strange, and somewhat suspect. The abort here is one that prevents the client from getting output. However, the real-world adversary may behave in a way that the client does get output. I suggest writing to the authors to ask and/or going through this very carefully. Without having gone through the details at all, my initial guess is that this ... 2 As the other answers already state here, game-based definitions are easier to write proofs for, but simulation-based definitions are often clearer in terms of the security guarantee that you get. The best example of this is IND-CPA (game-based definition) versus semantic security (simulation-based definition). Note that IND-CPA is really not a convincing ... 2 Well, there is not much to prove. The server can do any change to$v$. So actually, this means the server with throw away your$v$and just choose a new random number. Or alternatively, he chooses$w$uniformaly random and sets$v'=v+w$, which is now also uniformly random. When you get back that value, you have your (for you known/fixed) values$a,b$... 2 It is called circular security. It is problematic because it is not captured by the usual security definitions. I.e., even if an encryption scheme is proven secure by some regular definition, it is usually not a given to be circular secure. To see why consider, for example, the usual definition of semantic security for a public-key encryption scheme$\Pi = ...

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