I want to prove if the composite are equal to each other

  • Thread starter Thread starter behzad_b
  • Start date Start date
  • Tags Tags
    Composite
Click For Summary
SUMMARY

This discussion focuses on proving that if the function f: {0,1}^n → {0,1}^n is a one-way permutation, then the derived function f′: {0,1}^{2n} → {0,1}^{2n}, defined as f′(x∘r) := f(x)∘r, is also a one-way permutation. Participants express confusion regarding the decomposition of f′ and the definitions of one-way permutations and the set {0,1}^n. Clarification on these concepts is essential for understanding the proof process.

PREREQUISITES
  • Understanding of one-way permutations in cryptography
  • Familiarity with function composition and bijections
  • Knowledge of the notation and properties of the set {0,1}^n
  • Basic concepts of cryptographic functions and their proofs
NEXT STEPS
  • Study the properties of one-way functions and their implications in cryptography
  • Learn about the composition of bijections and how it relates to permutations
  • Research the mathematical notation and implications of {0,1}^n in cryptographic contexts
  • Explore formal proof techniques used in cryptographic function analysis
USEFUL FOR

Cryptographers, computer scientists, and students studying cryptographic functions and their properties will benefit from this discussion.

behzad_b
Messages
1
Reaction score
0
Given f:{0,1}n→{0,1}n, define f′:{0,1}2n→{0,1}2n as follows: for x,r∈{0,1}n define f′(x∘r):=f(x)∘r (where ∘ denotes concatenation). Prove that if f(⋅) is one way permutation then so is f′(⋅).

i don't understand f′(x∘r):=f(x)∘r how to decompose it in order to prove it

I tried proving it by using a composition of tow bijection, as a permutation is a sect of bijection function.

I am stuck on the proof, I don't know how to do the proof
 
Physics news on Phys.org
What is the definition of {0,1}n?
 
Do you mean ##\{0,1\}^n##?

What is a "one way" permutation?
 

Similar threads

Replies
1
Views
2K
  • · Replies 58 ·
2
Replies
58
Views
5K
  • · Replies 4 ·
Replies
4
Views
1K
  • · Replies 11 ·
Replies
11
Views
1K
  • · Replies 5 ·
Replies
5
Views
2K
  • · Replies 6 ·
Replies
6
Views
2K
  • · Replies 4 ·
Replies
4
Views
2K
  • · Replies 7 ·
Replies
7
Views
2K
Replies
10
Views
2K
Replies
5
Views
2K