Questions tagged [bijection]
A bijection (or a bijective function) is a function $f$ from a set $X$ to a set $Y$ with the property that, for every $y$ in $Y$, there is exactly one $x$ in $X$ such that $f(x) = y$. It follows from this definition that no unmapped element exists in either $X$ or $Y$.
26
questions
1
vote
1
answer
185
views
Does an binary elliptic curve like sect571r1 support a bijective asymmetric operation pair on bytes? If so, is there a self-contained example?
I'm wondering if a binary elliptic curve (such as sect571r1 aka B-571) supports pairs of asymmetric operations (for example, either sign/verify or encrypt/decrypt) on a fixed bit or byte input size in ...
- 111
-1
votes
2
answers
154
views
How are the cipher, the key and the initial message (that is not encrypted) are releted?
Suppose that $m$ is a message that someone player $i$ wants to send to a network of other players $j\neq -i$. The player to prevent his message from cheating by others uses an encyrpstion scheme. Say $...
- 137
2
votes
1
answer
220
views
Hash functions, bijectiveness, and entropy
For those who don't know, a bijective function is one for which each input yields one and only one output. A block cipher, for example, is guaranteed to be bijective or you could not decrypt.
When a ...
- 896
1
vote
0
answers
34
views
How is it possible to prove that Shanon entropy does not change applying any bijective function to X? [duplicate]
I was wondering how is it possible to mathematically prove that Shannon entropy does not change when applying any bijective function to X? For instance H(X) = H(f(X)) assuming that f is invertible and ...
- 11
0
votes
1
answer
119
views
How to prove that permutation and substitution ciphers satisfy H(X) = H(Y) in Shanon Entropy?
I was not able to mathematically prove that all permutation and substitution ciphers satisfy H(X)=H(Y) if we say that Y is the set of ciphertexts while X is the corresponding set of plaintexts in ...
- 1
2
votes
0
answers
57
views
How is the 'Algebraic Degree' calculated in the paper about analysing the white-box AES(Chow et al. 2002) by exploiting internal collisions?
This paper proposed a new attack on the initial white-box AES implementation of Chow et al.
In order to determine the good solution, we use the
particular structure of the function $S_{0}$.
$S^{-1} \...
- 21
2
votes
1
answer
144
views
Bijective function with unknown reciprocal function
I have a use case where I need to build a unique identifier for my users with the email address and the "family member number". However, the two personal informations used to build the ...
- 123
3
votes
1
answer
217
views
Proving that RSA encryption function with non-square free modulus is not a permutation
Here is a backgroung for the question on hand. While studying RSA I came up to the question about what happens if $p$ and $q$ involved in modulus computation are not actually primes? There is already ...
- 143
2
votes
2
answers
633
views
Is it reasonable to consider that an encryption scheme must be invertible?
I am in a dispute regarding a test question in an exam.
The question is something like that:
What would happen if one were to use RSA with $n=100$ and $e=13$ to
encrypt a message $m$?
a) You would be ...
- 267
1
vote
1
answer
106
views
Why $f(x)=x^e$ is a bijection i.f.f $e\in{\mathbf{Z^*_{\phi(N)}}}$?
I understand that if $e\in{\mathbf{Z^*_{\phi(N)}}}$ then $\gcd(e,\phi(N))=1$
and if $e\not\in{\mathbf{Z^*_{\phi(N)}}}$ than $\gcd(e,\phi(N))\neq{}1$.
But I couldn't figure out why this implies ...
- 113
0
votes
1
answer
69
views
Are bijective polynomials of degree $2 \bmod 2^m$ efficiently inverted?
Take a bijective polynomial of degree $2 \bmod 2^{64}$ like:
$m = (n(n+1)/2)\ \bmod 2^{64}$
It is bijective and can trivially be inverted for numbers up to $2^{32}$ by calculating $\lfloor\sqrt{2m}\...
- 101
0
votes
0
answers
36
views
Rekeying procedure - how "far" from bijection?
Imagine that I want to change the key in order to prevent side-channel attacks on key and to protect against big load on the one key. It is desirable that key change procedure would look like random ...
- 589
2
votes
1
answer
330
views
Explain mixing bijection with an example
I am reading whitebox AES. "Mixing Bijection" is one of the important definition. For example, I copy one paragraph here:
The look-up tables that incorporate bytes of round keys can be considered ...
- 477
2
votes
1
answer
182
views
Symmetric property of DDT of inverse function
Given a bijective function $F: \mathbb{F}_2^n \rightarrow \mathbb{F}_2^n$.
The entry of the Difference Distribution Table (DDT) at row $\alpha$ and column $\beta$ is defined as
$$DDT_{F}(\alpha,\...
- 23
1
vote
1
answer
253
views
Random semantic security and bijective PRGs
I'm working through Boneh and Shoup's "Graduate Course in Applied Cryptography", and have just finished reading the chapter on stream ciphers and PRGs.
The first exercise for this chapter introduces ...
- 21
0
votes
1
answer
483
views
Is triple-CRC-32 a bad (or not) idea for generating a uniform distribution hash? [closed]
I have an input of 288 bits (comprising 4 × 32-bit and 10 × 16-bit integers). I need to hash this to 96 bits with as few collisions as possible.
I'm aware that CRC is a bijective hash, thus ensuring ...
- 101
1
vote
3
answers
439
views
Does there exist a deterministic, invertible function $\{0,1\}^n \rightarrow \{0,1\}^n$ that is not a bijection?
One of the requirements for a function to be a PRP is
For any $K \in \{0,1\}^s$, $F$ is a bijection from $\{0,1\}^n \rightarrow \{0,1\}^n$.
Taken from Wikipedia
Does this have to be ...
- 2,379
3
votes
1
answer
278
views
Are non bijective sboxes weaker (on feistel networks)?
I have heard it anecdotically that non-bijective sboxes are potentially weaker to be used in designs like feistel networks. (since by design, it is allowed for the sbox to be non-reversible)
Is that ...
- 391
1
vote
1
answer
201
views
Create a bijective and invertible table that are depending on the cipher key
I'm creating my own symmetric-key algorithm that in many ways are similar to DES. My key is 16 bits long and is random generated, I will encrypt blocks of 16 bit strings that are split into two 8 bit ...
- 11
1
vote
1
answer
211
views
Key-Bijective Secure Symmetric Encryption Methods
In AES, an N-bit message is mapped 1-to-1 message-to-output (for a fixed key).
If we use a key with N bits, however, the key is not mapped 1-to-1 key-to-output
(for a fixed message).
So, is there any ...
- 315
5
votes
2
answers
912
views
A bijective hash function
Suppose:
$H: \{0,1\}^{n} \rightarrow \{0,1\}^{n}$.
$H$ is bijective.
It is difficult to derive $x$ from $H(x)$.
Is this type of function possible? What would the strength of it be?
I realize that ...
- 3,635
2
votes
1
answer
1k
views
I read ECB is bad because the same plaintext outputs the same ciphertext. Isn't that a requirement of a cipher?
In the Wikipedia article on Block Ciphers, it says about the Electronic Code Block mode:
The disadvantage of this method is that identical plaintext blocks are
encrypted into identical ciphertext ...
- 153
2
votes
1
answer
996
views
Why is a Feistel network bijective?
EDIT: Fixed for clarity of intention
I was reading "The FFX Mode of Operation for Format-Preserving Encryption" when I came across Figure 1 (see below). It's obvious why it's reversible (top-down ...
- 1,697
4
votes
2
answers
1k
views
Need 32-bit mixing function that has perfect avalanche between octets
for my hobby tinkering project, I need a mixing function that takes 32-bit input and has 32-bit output (and will, most likely, run in a 32-bit C environment) and the following property (independent of ...
- 293
4
votes
2
answers
1k
views
Are there any bijective one-way functions not based on number-theoretic hardness assumptions?
I'm trying to find a bijective function $y=F(x)$ which should be easy to compute in one direction but hard to compute in the other, where the one-way property is not based on a number theoretic ...
- 1,867
2
votes
1
answer
528
views
Selecting bijective functions for permutations
How would one go about selecting an appropriate bijective function for introducing permutations into a cipher or hash?
For example, $f(x) = x+1 \space mod \space n$ is a bijective function, but isn't ...
- 3,527