Hot answers tagged

32

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


18

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


15

The notation $c=\oplus~c_i$ is (terrible) shorthand for $$c=\bigoplus_{i \in I(c)} c_i$$ where the sum sign should be replaced by the big xor sign which could also be written as $$ c=\sum_{i \in I(c)} c_i,$$where $\sum$ denotes vector addition modulo 2. An example of this decomposition (for length 8 vectors) is $$c=(1,0,1,0,0,0,1,0)=$$ which is nonzero in ...


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


11

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


11

$Z_2^5$ means that you are working in $GF(2)^5$. $GF(2)$ is the Finite Field with two elements: 0 and 1 with the addition and multiplications defined: $0 + 0 = 0\\ 0 + 1 = 1\\ 1 + 0 = 1\\ 1 + 1 = 0$ It is equivalent to XOR. $0 \times 0 = 0\\ 0 \times 1 = 0\\ 1 \times 0 = 0\\ 1 \times 1 = 1$ It is equivalent to AND. the $ ^5$ is the dimension of the space ...


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


10

I'll review the standard mathematical notations used for $H_1:\{0,1\}^*\times\mathbb Z_p^∗\to\mathbb Z_q^∗$ , going from the bottom up. Hopefully, that will make the rest evident. $\{0,1\}$ is the set with the two elements $0$ and $1$, known as Booleans. $\{0,1\}^k$ (for some non-negative integer $k$ ) is the set of tuples with $k$ Booleans, or ...


9

Usually, $^\top$ denotes the transpose of a matrix or vector. Common variants include $^t$ and $^T$. Hence $(c_1,c_2)^\top$ is just $\begin{pmatrix}c_1\\c_2\end{pmatrix}$. Such notation is often used to fit column vectors neatly into text.


7

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


7

What exactly does $0...0$ and $1...1$ mean usually? This simply means a (more or less) long string of $0$s or $1$s or more clearly $000000...000000$ and $111111...111111$. Related notiational notes, you may have to use soon: Sometimes the notation $0^n$ and $1^n$ is also used for these strings with exactly $n$ zeroes and ones. Even more generally it's ...


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

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


6

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


6

$c = (U,V)$ means that the ciphertext is actually a tuple, made of two parts, $U$ and $V$. It is very common to have ciphertexts that are actually tuples of elements. In this particular case, this scheme is reminiscent to Hashed ElGamal, where ciphertexts are composed of two parts: $U$, which essentially encodes the randomness used, and $V$, which contains ...


5

$\mathbf{Z}_2^b$ is the direct product of $b$ copies of $\mathbf{Z}_2$ ($\mathbf{Z}_2 \times\cdots \times \mathbf{Z}_2$, $b$ times). That is, its elements are $b$-tuples of elements of $\mathbf{Z}_2$, with both addition and multiplication defined componentwise. If $b > 1$, it is not a field. In fact it is not even an integral domain, because $(0,1)\times (...


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

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

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

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


4

Yes, exactly. This can be read as "given m, c is defined as the encryption of m, with the key Ke"


4

It's a comma to separate the two things. Alice has $m$ and can calculate $c$ which is equal to $E(K_{e}, m)$. Bob has $c$ and can calculate $m$ which is equal to $D(K_{e}, c)$.


4

TL;DR: Find the most important specification that is of the same type as the one you want to write and use its style for yourself, chances are, other people also have read it. There is a myriad of ways to specify a crypto protocol / design. However, there are four things that you really should take into consideration when writing a crypto-related ...


4

To quote yyyyyyy from the comments: The $_R$ has nothing to do with the field — it is associated to $\in$! To quote your first link: "For a set $S$, by $a\in_R S$, we mean that $a$ is randomly chosen from $S$." and to quote SEJPM from the comments: If $p\in \mathbb P$ (with $\mathbb P$ being the set of all primes) then the notations $GF(p);\...


4

There is not a single standard for pseudocode. The := operator is the assignment operator from Pascal, a programming language which was in widespread usage in the 1970s and 1980s, especially for teaching purposes. Many academics have thus been exposed to Pascal and remember it. In Pascal, the equality comparison is =, which matches mathematical practice. By ...


4

Can you please explain me what this notation means? Of course, $f:A\times B\times C\rightarrow D$ is fancy mathematican's language for saying: "a function f, that takes an element from A, B and C (in this order) and maps this to an element of D" (arbitrarily extend this explanation to as many arguments as you wish). In this particular instance, the ...


3

There is no standard way, and I think it's impossible to find universal agreement. However, it is pretty common to use lowercase letters for integers and uppercase letters for elliptic curve points. And it is very common to indicate as p the prime defining the field $\mathbb F_p$ over which the curve is defined. For the order of the curve you can use $\#E(\...



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