# 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$. ...

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

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

From the key creators point of view, notice that:$g_1\bmod p=1$ and $g_2\bmod q=1$. Which means that $(g_1-1)\cdot(g_2-1)\bmod N=0$. Which implies that $g_1-1$ and $g_2-1$ share a common divisor with $p$ and $q$. To obtain $p$ we simply take $\gcd(g_1-1,N)$. To obtain $q$ we simply take $\gcd(g_2-1,N)$, or $N/p$. Because we have been able to factor the ...

4

NTRU, as it was originally introduced, is based on what people now call the "NTRU assumption", which really just assumes that it is difficult to break NTRU. Annoyingly circular, but that's how it is. Similar to how breaking RSA is not provably as hard as factoring (technically it is based on the "RSA assumption"), but people still think it is hard, NTRU ...

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 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 ... 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 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 ... 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 ... 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 I am not aware of any work that proposes a Gap problem related to LWE. The reason is probably that LWE is an average-case problem specifically designed for the use in crypto. However, there are the related worst-case problems, e.g. the shortest vector problem (SVP), that come with a Gap version. So, you might want to have a look at GapSVP and GapCVP. 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 = ...

2

For CPA security it is actually enough that the first scheme, i.e., $\pi = (gen, enc, dec)$ is CPA secure. Lets define the CPA game of a general scheme $\pi = (Gen, Enc, Dec)$ against an adversary $A$ as follows: We sample $(pk, sk) \leftarrow Gen(1^\lambda)$, and send $pk$ to $A$. $A$ outputs messages $m_0$ and $m_1$. We sample $b \leftarrow \{0,1\}$ (a ...

2

In the standard definition of security for public key encryption schemes there exists only one public key. Therefore the decryption oracle will always decrypt with the secret key that corresponds to the public key given to the attacker. It does not matter how the $c_1$ in your question is computed, it can be computed using the real public key, a different ...

2

What you present is a generalized version of the so called fixed-argument pairing inversion (FAPI) problem. The FAPI problem is given an element $z\in G_T$ and an element $h\in G$ to compute $f\in G$ such that $e(h,f)=z$. Note, that FAPI is implied by the computational Diffie Hellman problem: Given $(g,g^a,g^b)\in G^3$, call the FAPI oracle with $z\gets ... 2 One can't "get rid of" the factor 2. However, there might be a way to replace it with$2\hspace{-0.03 in}-\hspace{-0.03 in}o(1)\:$where that depends on$q$and the advantage.$||$is concatenation. Start with some encryption scheme$\mathcal{E}'\hspace{-0.04 in}$, and for any integer$n$and probability$p$, let$\mathcal{E}_{\hspace{.02 ...

2

Hint: you can notice that $n! > 2^n$ (except for very small $n$).

2

Here's an artificial example: Start with some secure encryption scheme with encryption function $\mathcal{E}(\cdot)$, and construct a new scheme with encryption function $\mathcal{E}'(\cdot)$, which for any input message $m$ copies the first bit, $b$, of the message, and outputs $b||\mathcal{E}(m)$, where $||$ denotes concatenation. For such a scheme, ...

2

As you say, CCA proofs are actually reductions to underlying problems. In all CCA proofs that I can think of at the moment, the underlying problem is a weaker security notion for an "embedded" encryption scheme - e.g. Cramer-Shoup and friends use IND-CPA of ElGamal and Fujisaki-Okamoto uses OWE of the contained scheme. The general proof strategy is to take ...

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