# Tag Info

## Hot answers tagged notation

11

### What exactly is a negligible (and non-negligible) function?

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

6

### Why does key generation take an input $1^k$, and how do I represent it in practice?

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

4

### ECIES protocol - what does the || operation mean?

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

### What do $0^n$ and $1^n$ mean in cryptography?

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

3

### Why is a non fixed-length encryption scheme worse than a fixed-length one?

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

### Why is a non fixed-length encryption scheme worse than a fixed-length one?

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

### What does the expression $1^n$ mean as a function argument?

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

### What does $(\mathbb{Z}_n^*)^2$ mean?

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

### What do $0^n$ and $1^n$ mean in cryptography?

$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

### What exactly is a negligible (and non-negligible) function?

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
{"extraction_info": {"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 39, "mathjax_display_tex": 0, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0}, "config": {"markdown_headings": true, "markdown_code": true, "boilerplate_config": {"ratio_threshold": 0.18, "absolute_threshold": 10, "end_threshold": 15, "enable": true}, "remove_buttons": true, "remove_image_figures": true, "remove_link_clusters": true, "table_config": {"min_rows": 2, "min_cols": 3, "format": "github"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "english_confidence": 0.9255374073982239, "perplexity_flag": "middle"}