# Tag Info

17

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

9

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

8

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

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

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

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

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

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

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, ... 3 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 ... 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$\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

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) 1/2 + negl(n). He can always toss a coin (that gives hom probability ...

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