# Tag Info

29

In perfectly secret schemes like the one-time pad, the probability of success does not improve with greater computational power. However, in modern cryptographic schemes, we generally do not try to achieve perfect secrecy(yes governments may use the one time pad, but this is generally not practical for the average user). In fact, given unbounded ...

15

The $1^k$ is a formalism that's only there to make the theoreticians happy. You can safely ignore it. When you actually implement the cryptosystem, you don't try to pass the string $1^k$; instead, you pass $k$, the security parameter (a representation of how much cryptographic strength is desired from the key generation algorithm). I wish I could leave it ...

14

The example is using a shorthand notation for the rotors that somewhat obscures the way they actually work. For example, the first rotor in your example, BDFHJLCPRTXVZNYEIWGAKMUSQO, actually applies the following permutation of the alphabet: ABCDEFGHIJKLMNOPQRSTUVWXYZ ↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓ BDFHJLCPRTXVZNYEIWGAKMUSQO Applying this rotor in the ...

10

As you probably know $f(\lambda)=O(\lambda^4)$ means that $|f|$ asymptotically upper bounded by some constant times $\lambda^4$. The notation $f(\lambda)=\Omega(\lambda^4)$ corresponds to an asymptotic lower-bound. Now, the $\tilde O$ and $\tilde \Omega$ are closely related notations, where we not only ignore constants but also values which are polynomial ...

7

The symbol of the circle with the + in it is one of many symbols for exclusive-or. XOR, EOR, EXOR, ⊻, ⊕, ↮, and ≢. Binary OR is true when either input is true; binary XOR is true when exactly one input is true. If both inputs are true, the XOR result is false. One property of this is that if either input bit flips, the output bit will also flip. That's sort ...

6

This example is correct. The inversed versions are the inverse permutation; that is, if the forward direction is the permutation $P$, then the inverse permutation $P^{-1}$ has the property that $P^{-1}(P(X)) = X$ for all $X$. That is, if $X$ is a plaintext letter, and we run it through in the forward direction (giving us $P(X)$), and then run it through in ...

6

Typically that means a string of either $n$ zeros or $n$ ones.

6

While this is a very good explanation, I would like to add that you will see negligible functions also in other proofs. One example are peusdorandom strings. If an attacker looks at a string, he should only be able to decide if this string is pseudo-random or "real" random" with probability (distribution) $$½ + negl(n)$$ He can always toss a coin (that ...

5

The image description page for the larger image describes it pretty well. Specifically, the line at the top of the figure: shows the 4-ary Boolean function $f(x_1, x_2, x_3, x_4) = x_1 x_2 + x_3 x_4$ in a graphical form. Specifically, interpreting each possible input as a 4-bit binary number (e.g. $(0, 1, 0, 1) \mapsto 0101_2 = 5$), the corresponding ...

4

Without seeing the entire formal construction: It seems like they wanted different strings. Meaning they needed $f_x(a)||f_x(b)$ where $a≠b$. The easiest way to express this is using the all $0$ and all $1$ strings, but any other pair of distinct strings of that length would yield the same effect. As to why they wanted this: They're using a PRF twice to ...

4

If you got an expression that resembles $\{1\}^n$ (or $1^n$) at a place in a surrounding expression where you would expect an $n$-bit bit string to be, the $\{1\}^n$ expression means a string of $n$ bits each with the bit value $1$. Conversely, $\{0\}^n$ means a string of $n$ zero valued bits, and $\{0,1\}^n$ just means any bit string of length $n$. In ...

4

As explained in @fgrieu answer, you can always create such a function from a regular hash function by taking variations on the IVs or internal constant. However, if you ask for a clean standardized hash function family, you will be hard pressed to find something satisfying. If you are wondering why we encounter this dilemna, some additional explanation ...

4

In terms of algorithms, it usually means concatenate - as in, join two binary (or otherwise defined) strings together (in this order). For wikipedia's cryptography articles that's nearly always the case. When it is on the left side of an assignment, this means split the string from the right side into these component strings. This makes only sense if the ...

4

The notation is "", i.e., the empty string. $\;\;$ Since $k$ is not an input of $f$, $f$ has no knowledge of $k$.

4

The encryption scheme in the experiment you describe does not have to be fixed-length. We simply require that the two messages the adversary sends to its oracle have the same length. The restriction is on the adversary, not on the encryption algorithm. So why do we put this requirement on the adversary? The reason is that in every practical encryption ...

4

That definition is a standard definition which defines encryption as a function $E$. That function takes two inputs, a $\kappa$ bit key and a $n$ bit message. Hence it is defined over the cartesian product - denoted as $\times$ - over these two sets, i.e. all bitstring of length $\kappa$ and $n$ respectively. It maps - denoted as $\rightarrow$ - to an $n$ ...

3

As one of the authors of the paper, let me give you an answer. The operation $F$ is indeed applied to both $x$ and $x'$. By stating that $\oplus$ is invariant under rotation, we mean that if you first rotate $x$ and $x'$ and take the difference with $\oplus$, you get the same result as if you first take the difference with $\oplus$ and then rotate the ...

3

You had your finger on it, you do know something about the encryption of two messages of different length before they are actually encrypted: the length of the corresponding ciphertexts. If the setting in which you're using your encryption scheme allows for a maximum message length then you can always pad to make every ciphertext the same size ...

3

A practical example with $n=128$ and $K=\{0,1\}^{32}$ would be the set $F$ of $2^{32}$ functions, one of which is MD5, obtained from the definition of MD5 by replacing the constant 0x67452301 with the integer which binary representation is $k\in K$. Each member of this family (each element of this set) is a function accepting a bitstring of any length, and ...

3

The subscript $A$ indicates that these numbers ($p_A$, $\alpha_A$, etc.) are the ones involved in Alice's key. In a description of a protocol with more participants each having their own key, Bob's public key would be $(p_B, \alpha_B, \beta_B)$, and so on. A primitive element of a finite field is a generator for the multiplicative group, i.e. the set $\{1, ... 2$\mathbb Z_n^*$is a mathematical notation for the multiplicative group of integers modulo$n$. In other words, it is the set of integers that are relatively prime to$n$, all taken modulo$n$(excluding zero). The$*$symbol is commonly used for denoting "the set of elements in the multiplicative group", which in this case means "the set of elements that ... 2$0^n$means a string of$n$zeros (the$n$-bit string that is all zeros).$1^n$means a string of$n$ones. Why were these used? There's nothing special about$0^n$or$1^n$, in this context. They could have used any pair of two constant$n$-bit strings, as long as the two strings were not the same.$0^n$and$1^n$is a convenient choice of two strings ... 2 It's exclusive or (or XOR), corresponds to$x \oplus y := x+y \pmod 2$for single bits, i.e., scalars. It is sometimes used for binary vectors as well, whereby two bitvectors of length$n$$$\mathbf{x}=(x_1,\ldots,x_n)$$ and $$\mathbf{y}=(y_1,\ldots,y_n)$$ result in $$\mathbf{x}\oplus \mathbf{y}=(x_1\oplus y_1,\ldots,x_n \oplus y_n)$$ i.e., a bitwise ... 2 It just means vectors of dimension$n$, where each entry is in$\mathbb{Z}_q$. I.e.,$(x_1, \ldots, x_n) \in \mathbb{Z}_q^n$means that$x_i \in \mathbb{Z}_q$for all$i = 1, \ldots, n$. 1 It contains the equivalence classes represented by$\{1,\ldots,6\}$. To elaborate on Nova's comment below,$\mathbb{Z}_p$is the collection of congruence classes when you divide by$p$. When$p=7$, two integers represent the same congruence class when they have the same remainder when divided by$7$. As you probably know, the only possible remainders are ... 1 It means$Q$divides$P-1$. In other words,$P-1$is a multiple of$Q$. 1 The explanation of why the security parameter$k$is given in the unary form of$1^k$as mentioned at the second footnote at page 366 of Foundations of Cryptography Volume 2 is to allow a smooth transition to fully non-uniform formulations...Specifically$1^n$indicates that the$n^{th}\$ circuit is to be used.

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