Skip to main content

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

Filter by
Sorted by
Tagged with
2 votes
1 answer
69 views

Is there any bijective obfuscation scheme which maintains a byte order (e.g. sorted) or does so after not too many trials? (for 128bit = 16 byte)

We have given 16 bytes and apply some order to them. For example sorting them by their absolute value. We want to obfuscate them as best as possible while maintaining their order. That means if we ...
J. Doe's user avatar
  • 453
5 votes
0 answers
455 views

Public one-way bijection [duplicate]

What methods do we know to construct a function $f:D\to D$ with domain $D=[0,n)\cap\mathbb N$ (thus $n\in\mathbb N$ elements); demonstrably surjective (thus bijective since $D$ is finite); with ...
fgrieu's user avatar
  • 141k
1 vote
1 answer
121 views

Find two hard to reverse functions f and h such that f ∘ h ∘ g = h (f and h injective, no constraints on g)

I am looking from 3 functions $f,g,h$ from $\mathbb N \to \mathbb N$ (they can be bijections, they need to be injective at least), such that: $$f \circ h \circ g = h $$ and $f$ is hard to reverse ...
Mathematical_Noob's user avatar
1 vote
1 answer
195 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 ...
user3325588's user avatar
-1 votes
2 answers
156 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 $...
Nav89's user avatar
  • 137
2 votes
1 answer
248 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 ...
Adam Ierymenko's user avatar
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 ...
bengren's user avatar
  • 11
0 votes
1 answer
120 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 ...
andyrob's user avatar
2 votes
0 answers
59 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} \...
leet's user avatar
  • 21
2 votes
1 answer
145 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 ...
Guerric P's user avatar
  • 123
3 votes
1 answer
244 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 ...
Henadzi Matuts's user avatar
2 votes
2 answers
680 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 ...
user2891462's user avatar
1 vote
1 answer
112 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 ...
A. Maman's user avatar
  • 113
0 votes
1 answer
70 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}\...
Wolfgang Brehm's user avatar
0 votes
0 answers
37 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 ...
Kirill Tsar.'s user avatar
2 votes
1 answer
366 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 ...
TJCLK's user avatar
  • 497
2 votes
1 answer
195 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,\...
Florian's user avatar
  • 23
1 vote
1 answer
259 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 ...
John Gilling's user avatar
0 votes
1 answer
521 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 ...
IamIC's user avatar
  • 101
1 vote
3 answers
462 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 ...
Daffy's user avatar
  • 2,399
3 votes
1 answer
294 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 ...
Anton Paragas's user avatar
1 vote
1 answer
206 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 ...
Mallom's user avatar
  • 11
1 vote
1 answer
212 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 ...
bobuhito's user avatar
  • 315
5 votes
2 answers
950 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 ...
Melab's user avatar
  • 3,655
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 ...
CodyBugstein's user avatar
2 votes
1 answer
1k 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 ...
DeepSpace101's user avatar
  • 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 ...
mirabilos's user avatar
  • 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 ...
SDL's user avatar
  • 1,867
2 votes
1 answer
551 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 ...
Polynomial's user avatar
  • 3,527