Questions tagged [notation]

Questions on the meaning, history, and usage of symbols and notation in cryptography. Please remember to mention where (book, paper, webpage, etc.) you encountered any notation you are asking about.

Filter by
Sorted by
Tagged with
29 votes
2 answers
22k views

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

The mathematical definition of neglible and non-neglible functions is fairly clear-cut, but why they are important and how they are used in cryptography?
Nico Bellic's user avatar
22 votes
3 answers
4k views

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

In my lecture, the lecturer said: Let $K$ be the key generation algorithm. Given a security parameter represented in unary, $1^k$, $K(1^k)$ will output a keypair $(pk; sk)$, known as the public ...
juaninf's user avatar
  • 2,701
17 votes
2 answers
3k views

How did || come to be used in crypto texts to represent concatenation?

In RFC5647, NIST SP 800-38D, etc., || is used to denote concatenation. How did that come to be? In most programming languages || ...
neubert's user avatar
  • 2,927
14 votes
1 answer
1k views

What the X stands for in the front of Elliptic curve names like X25519

I have seen Curve25519 and X25519, Curve448 and X448. I've seen a small note in this answer (Historical note: Originally, X25519 was called Curve25519, but now Curve25519 just means the elliptic ...
kelalaka's user avatar
  • 48.5k
12 votes
1 answer
14k views

Encoding vs. Compression vs. Encryption

In what ways does encryption differ from proprietary/secret compression schemes and codecs?
ProductionValues's user avatar
11 votes
1 answer
2k views

Why do crypto tools display key components in such an unusual format?

openssl x509 (v1.0.1f) displays public key moduli as arrays of hex-encoded bytes, 15 columns wide, starting with a leading 00:: ...
Dan Lenski's user avatar
11 votes
1 answer
665 views

How can I instantiate a generalized hash function?

I've come across a bunch of "strange" hash function notations, such as the following ones and now I don't know how to choose / instantiate them. Can you please explain me what this notation means and ...
SEJPM's user avatar
  • 46k
10 votes
2 answers
2k views

Why is the polynomial of an LFSR called so?

As far as I understand, the "polynomial" of the LFSR tells us the positions of the register where taps are situated. However, the natural way to look at the positions would be to think of them as $...
Agnishom Chattopadhyay's user avatar
9 votes
1 answer
504 views

What does "$<\!\!<\!\!<$" mean?

What does the symbol $<\!\!<\!\!<$ mean? It is normally followed by a number. An example: It would be appreciated if you could explain it in fairly basic terms.
Nat's user avatar
  • 415
9 votes
1 answer
2k views

What is the recommended format/notation for crypto design?

Is there a recommended format or formal notation for documenting the combination of symmetric and asymmetric encryption, key derivation and other algorithms (and their inputs and outputs) that I think ...
Oli's user avatar
  • 201
8 votes
1 answer
2k views

What does the $\|$ operation mean in cryptographic notation?

I am studying elliptic curves problems, which also includes study of related protocols such as ECIES. The problem is that I don't understand the notation $\|$. What does this operation mean? Some ...
eXPi's user avatar
  • 95
7 votes
2 answers
7k views

What does ⊕ mean in cryptography?

Can someone please help me with the question below? Explain why 0 ⊕ x ≠ 1 ⊕ x, whatever the value of the bit x. Hence, explain why flipping a bit in the plaintext produces a predictable change in the ...
user avatar
7 votes
1 answer
1k views

Why is the BSI not using powers of two?

In their Technical Guideline TR-02102-2 Cryptographic Mechanisms: Recommendations and Key Lengths the BSI is giving minimal key lengths for - e.g. the TLS handshake protocol. All of these are not ...
Tom K.'s user avatar
  • 215
7 votes
2 answers
620 views

Probability conventions in cryptography

I am working on Victor Shoup's tutorial on game-based security proof and want to figure out some notions from the perspective of probability theory. Consider the following PRF advantage defined on ...
X. G.'s user avatar
  • 424
6 votes
2 answers
3k views

Why is this the inverse of a Enigma Machine rotor?

I am learning about how the Enigma Machine works and I found this example of one letter being encrypted by an Enigma Machine. It shows the letter "G" going through three rotors and then it goes into ...
michaelpri's user avatar
6 votes
1 answer
2k views

Confusing XOR notation in textbook sample solution

I am preparing for the midterm exam in my Data Security class so I am trying to read and understand the textbook's exercise questions. The sample solution at the end the textbook makes this problem ...
Node.JS's user avatar
  • 312
6 votes
1 answer
647 views

"Power of one" as input to functions of a cryptosystem

What does $1^\lambda$ mean when you pass it as a parameter to the functions of a cryptosystem. The cryptosystem in question is this and a picture reference is this. I have been told it signifies the ...
Papa Delta's user avatar
6 votes
1 answer
1k views

What are the curly brackets in this cryptographic hash function definition?

Reading the Schnorr signature Wikipedia page, I stumbled upon the following statement: All users agree on a cryptographic hash function $H:\{0,1\}^*\to\mathbb{Z}_q$. What do these curly brackets ...
Paul Razvan Berg's user avatar
6 votes
1 answer
1k views

Strange notation using dollar sign

In the paper Multi-Signatures in the Plain Public-Key Model and a General Forking Lemma, the authors Bellare and Neven use notation which looks like left arrow with dollar sign above it. Authors ...
Student20's user avatar
  • 431
6 votes
1 answer
1k views

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

In a paper about predicate encryption or attribute based encryption, the setup function is mentioned with the $setup(1^n)$ or $setup(1^l)$. I want to know what is meant here. Is it multiples of ones ...
s.venkatesan's user avatar
5 votes
2 answers
16k views

what is meaning of operator " := " in cryptography?

I've seen := used in several cryptography papers where the this symbol has been used instead of assignment operator ($ \leftarrow $ ) or equal sign (=), but never with an accompanying explanation. It'...
Sumit Jaiswal's user avatar
5 votes
3 answers
2k views

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

Let $f$ = $\{f_k\}$ be a pseudorandom function family. Let $G(x)$ be a pseudo-random generator such that: $G(x) = f_x(0^k)f_x(1^k)$ where $k=|x|$. I don't understand the meaning of $1^n$ and $0^n$, ...
Yoni Hassin's user avatar
5 votes
1 answer
725 views

What does this notation stand for when describing a code?

This code has appeared in some online course material. I understand the $(5, 4, 3)$ refers to (length, num codewords, distance) but no explanation of the $Z_2^5$ notation is given: One $(5,4,3)$ ...
Dawson's user avatar
  • 161
5 votes
1 answer
2k views

What does 0...0 and 1...1 mean

I am very new to cryptography but can someone explain what exactly does 0...0 and 1...1 mean in general term. Is it that 1st and ...
kthxbai's user avatar
  • 51
5 votes
1 answer
2k views

What does the probability subscript mean in Shannon's secrecy definition?

Shannon's secrecy can be defined as: $$P_M (M=m) = P_{SK,M}(M=m|E(SK,m)=c)$$ What does $P_M$ means? (same question for $P_{SK,M}$) I know that is the probability space M, M being the messages; I do ...
graphtheory92's user avatar
4 votes
1 answer
2k views

What is meant by $\tilde\Omega(\lambda^4)$?

I'm currently reading the paper (Leveled) fully homomorphic encryption without bootstrapping , and the following paragraph was near the start: What is meant by the symbol used? Is it merely to ...
Masutatsu's user avatar
  • 207
4 votes
1 answer
271 views

SIMON Cryptanalysis

I'm reading Cryptanalysis of the SIMON Family of Block Ciphers. In Section 3.1, it says: For SIMON, consider an n-bit input difference $\alpha= x\oplus x'$ to $F$ of Hamming weight one. As the ...
juaninf's user avatar
  • 2,701
4 votes
1 answer
552 views

Is there a difference between $\mathbb{Z}_2^b$, $\text{GF}(2^b)$ and $\text{GF}(2)^b$?

I have read a lot about Galois Fields (GF). They are also presented in The The Design of Rijndael: AES - The Advanced Encryption Standard on pages 13 and 14. In computer memory, the polynomials in $...
Biv's user avatar
  • 9,988
4 votes
1 answer
420 views

Is there a standard notation for a message concatenated with its signature?

I'm wondering what's the standard (or canonical) notation for "a message along with its signature", i.e. $$ \mathit{Message}~\Vert~\sigma_k(\mathit{Message}) \text. $$ Here the duplicated $\mathit{...
qweruiop's user avatar
  • 326
4 votes
1 answer
100 views

Definition of Cascade for Blockciphers

I have seen that given blockciphers $F,G : \mathcal{K} \times \mathcal{M} \to \mathcal{M}$, their cascade $F \circ G$ is defined to be $F \circ G : \mathcal{K}^2 \times \mathcal{M} \times \mathcal{M}$ ...
Sam OT's user avatar
  • 448
3 votes
1 answer
181 views

Understanding $\mathbb{Z}_q[X]/(X^N + 1)$ notation in cryptography paper

I can't seem to understand what $A_{N,q}$ represents in this paper (Section 2.1 - Notations). More specifically, I'm struggling to grasp the meaning of $\mathbb{Z}_q[X]/(X^N + 1)$. Could someone ...
Al A's user avatar
  • 43
3 votes
2 answers
400 views

Hash Family Example

I am reading my lecture and I found this definition: Let be $F$ be a family of hash functions, that is, a parameterized set $$F=\{g_k:\{0,1\}^{*}\rightarrow\{0,1\}^{n}|k\in K\},$$ where $n\in \...
juaninf's user avatar
  • 2,701
3 votes
2 answers
821 views

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

I have the following definition (highlights by me): An (efficient secret-key) encryption scheme $(Gen,Enc,Dec)$, where $Gen$ and $Enc$ are PPT algorithms and $Dec$ is a Deterministic Polytime ...
Alan Bletchley's user avatar
3 votes
1 answer
518 views

Ciphertext notation where the ciphertext consists of two parts

I've see in several places (here or there) the notation $c = (U, V)$ or $c =\langle U, V \rangle$, where $c$ is a ciphertext (to be transmitted). But as both $U$ and $V$ are "key-like". I can't find ...
3isenHeim's user avatar
  • 200
3 votes
1 answer
161 views

Carter-Wegman MAC different notations

While studying Carter-Wegman message authentication codes MAC, I got two different notations for the broader concept and have problems with understanding the difference, if any exist. Let $K, K_1, K_2$...
Titanlord's user avatar
  • 2,264
3 votes
2 answers
476 views

What does $\langle A, B\rangle$ mean?

I'm reading about CL-PKC and in Al-Riyami's FullIndent, I find some notations I must be sure to understand, to well explain it ...
3isenHeim's user avatar
  • 200
3 votes
3 answers
2k views

Finding the probability of a message encrypting to a given ciphertext

I have been watching a crypto course and when they wanted to prove that the OTP is a secure cipher they refer to the probability and what I can't get so far is the understanding of this notation ? $$...
saltosian's user avatar
2 votes
1 answer
238 views

Unable to understand hash function representations

I have some hash function representations, which I find it hard to understand. I have searched a lot but didn't found anything helpful. Please help me understand the hash function representations ...
Hitsugaya's user avatar
2 votes
1 answer
2k views

Top notation as exponent

In cryptography, what does the Top notation mean? It resembles a capital T: T In particular, I saw it in the follwing context: $c = (c_1,c_2)^\top$ where $c_1$ and $c_2$ are homomorphic ciphertexts
dfsdf sdfdsf's user avatar
2 votes
1 answer
157 views

What does a vertical bar mean in this context?

I'm doing a few exercises regarding Schnorr's identification scheme. I have the exercise starting off like this, with the values defined: Let $p = 311$ and $r = 31\ |\ (p - 1)$. Let $g = 169$, which ...
Garsty100's user avatar
2 votes
2 answers
2k views

Understanding Hash function notations

I am implementing a Certificateless Cryptography Algorithm by referencing the paper An Efficient Certificateless Encryption for Secure Data Sharing in Public Clouds. In this paper on page no. 4 during ...
Vighanesh Gursale's user avatar
2 votes
1 answer
225 views

How do these figures represent a boolean function?

In the Wikipedia article "Bent functions", there are some figures representing those Bent functions: How do these figures represent a boolean function ?
Mahdi Khosravi's user avatar
2 votes
2 answers
139 views

Rational exponents on group generators

In elementary concepts, mostly scalar exponents shows up in group operations: $g^x$ As one may encounter in more advanced papers, there are rational exponents over generators. Simply seems like: $g^...
oniki's user avatar
  • 23
2 votes
2 answers
331 views

What is the correct way to notate elliptic curve properties

When looking through elliptic curve and modulus posts i can see many examples of people referencing $p$ and $n$, in upper and lower case, and sometimes $Q$ is written instead of $p$ or $P$, and I ...
Sean Bradley's user avatar
2 votes
1 answer
174 views

What is the meaning of the notation $\langle a, b\rangle$ in certain cryptography papers?

I'm trying to understand a paper from Brakerski and Vaikuntanathan. In it, they use the notation $\langle a,b \rangle$ but they don't explain what that means. The answers on this question say that it'...
Mahkoe's user avatar
  • 135
2 votes
1 answer
1k views

How to select elements randomly from a multiplicative group Zn*

I am working on a problem in which I have two large safe primes say p and q randomly selected each of 512 bits. I have generated ...
skii's user avatar
  • 57
2 votes
1 answer
119 views

Meaning of pseudocode "$(C, S):=$"

I've seen pseudocode of this form in the Montgomery multiplication related theses: $(C, S) := a[j]*b[0]+C$. What's the meaning of "$(C, S):=$", or what is the real code that was converted from this ...
user3042720's user avatar
2 votes
1 answer
734 views

Vertical bar and comma in hash function input

I came across to a definition of a term PMKID while studying 4-way handshake in IEEE 802.11i. It is defined as: PMKID = H(PMK,"PMK name"||AA||SPA) I know the vertical bar || in the input of the hash ...
James's user avatar
  • 29
2 votes
1 answer
197 views

local collisions in SHA 0

I have found interesting for me paper about constructing collisions in SHA 0. On page 60 the author determines M variable which is a concatenation of 32-bits vectors $M^{(i)}$, but I can't find any ...
Setplus's user avatar
  • 153
2 votes
0 answers
536 views

What does it mean for “1^n”(i.e., the security parameter written in unary)? [duplicate]

As it is mentioned above, I am confused about “Gen takes as input $1^n$ and outputs a key“. Does it mean that the input of Gen is 1111....111 with length of n?
Xinyu Tu's user avatar