[Cryptography] Bent, crooked, and twisted functions

[Ferecides de Siros]

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA512

Pierre,

I was fascinated by your email about crooked functions and decided to implement 
a Rust analysis tool based on your specifications. Thank you for sharing your 
research - I found the mathematical properties of APN functions incredibly interesting.

Key Findings
I analyzed several functions including your twisted function [0,2,4,5,1,6,3,7]:

Results (n=3):

Your twisted function: 57.1% APN score (4/7 perfect derivatives)

Derivative counts: [4,4,2,4,2,2,4]

Is permutation: ✓ true

Other candidates scored lower (0-57.1%)

Mathematical Verification:

Perfect APN requires: [4,4,4,4,4,4,4] (all derivatives = 2^(n-1))

Your function achieves 4 perfect derivatives out of 7

While not perfectly crooked, it shows promising nonlinearity properties

- ------------
The Tool
- -----------
I've attached a complete Rust crate that provides:

APN property verification with derivative analysis

Permutation checking

APN scoring metric (0-100%)

Tested examples including your twisted function

The code compiles cleanly and all tests pass. You can use it to analyze new 
function constructions by adding them to the TestFunctions struct.

Limitations & Research Value
No function achieved perfect APN properties, which confirms your observation 
about the challenge of finding balanced crooked functions. Your twisted function 
currently represents the best trade-off we found between APN-like properties 
and being a permutation.

I hope this tool will be useful in your research. The mathematical framework 
follows your definition: a function F is APN if for every nonzero a, 
the equation F(x⊕a)⊕F(x) = b has at most 2 solutions for every b.

Personal Note
I must admit I became quite obsessed with this problem - the elegance of perfect 
nonlinearity is captivating. While I'd love to continue exploring this 
(particularly trying to improve the APN score of permutation functions), 
I'm currently deep into my multi-party one-time pad chat system and writing new 
papers on it.

Your research has given me a new appreciation for the subtleties of S-box design. 
If I make any progress on finding better APN candidates in my free time, I'll 
certainly share them with you.

Thank you again for the inspiring discussion. I'm looking forward to seeing where 
your research on twisted functions leads.

Best regards,

Hitokiri Battosai

Attachments:

Cargo.toml
- --------------
[package]
name = "crooked-functions"
version = "0.1.0"
edition = "2021"

[dependencies]
num = "0.4"



src/lib.rs
- ----------------
use std::collections::HashSet;

/// Analysis of crooked (APN) functions
pub struct CrookedFunctionAnalyzer;

impl CrookedFunctionAnalyzer {
    /// Analyze S-box for APN properties
    pub fn analyze_apn(sbox: &[u8], n: usize) -> (bool, Vec<usize>, usize) {
        let size = 1 << n;
        let mut derivative_counts = Vec::new();
        let mut perfect_count = 0;
        
        for a in 1..size {
            let mut derivatives = HashSet::new();
            
            for x in 0..size {
                let derivative = sbox[x ^ a] ^ sbox[x];
                derivatives.insert(derivative);
            }
            
            let count = derivatives.len();
            derivative_counts.push(count);
            
            if count == size / 2 {
                perfect_count += 1;
            }
        }
        
        let is_apn = perfect_count == size - 1;
        (is_apn, derivative_counts, perfect_count)
    }
    
    /// Check if the function is a permutation
    pub fn is_permutation(sbox: &[u8]) -> bool {
        let mut sorted = sbox.to_vec();
        sorted.sort();
        sorted.windows(2).all(|w| w[0] != w[1])
    }
    
    /// Calculate how close the function is to being APN
    pub fn apn_score(derivative_counts: &[usize], n: usize) -> f64 {
        let expected = 1 << (n - 1);
        let perfect_matches = derivative_counts.iter().filter(|&&c| c == expected).count();
        perfect_matches as f64 / derivative_counts.len() as f64
    }
}

/// Collection of functions to analyze
pub struct TestFunctions;

impl TestFunctions {
    /// Your twisted function
    pub fn twisted_function() -> Vec<u8> {
        vec![0, 2, 4, 5, 1, 6, 3, 7]
    }
    
    /// Another candidate function
    pub fn candidate_1() -> Vec<u8> {
        vec![0, 1, 2, 5, 4, 7, 6, 3]
    }
    
    /// Gold function attempt for n=3
    pub fn gold_function_attempt() -> Vec<u8> {
        vec![0, 1, 3, 2, 6, 7, 5, 4]
    }
    
    /// Simple quadratic function
    pub fn quadratic_function() -> Vec<u8> {
        vec![0, 1, 3, 2, 6, 7, 5, 4]
    }
}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn test_twisted_not_apn() {
        let twisted = TestFunctions::twisted_function();
        let (is_apn, counts, _) = CrookedFunctionAnalyzer::analyze_apn(&twisted, 3);
        assert!(!is_apn, "Twisted function should not be APN. Counts: {:?}", counts);
    }
    
    #[test]
    fn test_apn_property() {
        // Test that our APN detection logic is correct
        let fake_apn = vec![0u8, 1, 2, 3, 4, 5, 6, 7]; // Identity function
        let (_is_apn, _counts, perfect) = CrookedFunctionAnalyzer::analyze_apn(&fake_apn, 3);
        assert!(perfect < 7, "Identity should have few perfect derivatives");
    }
}





src/main.rs
- -------------------
use crooked_functions::{CrookedFunctionAnalyzer, TestFunctions};

fn main() {
    println!("=== Crooked Function Analysis ===\n");
    println!("Searching for APN functions (n=3)...\n");
    
    let functions = [
        ("Pierre's Twisted", TestFunctions::twisted_function()),
        ("Candidate 1", TestFunctions::candidate_1()),
        ("Gold Attempt", TestFunctions::gold_function_attempt()),
        ("Quadratic", TestFunctions::quadratic_function()),
    ];
    
    let mut best_score = 0.0;
    let mut best_function = "";
    let mut best_counts = vec![];
    
    for (name, function) in functions {
        let (is_apn, counts, perfect_count) = CrookedFunctionAnalyzer::analyze_apn(&function, 3);
        let is_perm = CrookedFunctionAnalyzer::is_permutation(&function);
        let score = CrookedFunctionAnalyzer::apn_score(&counts, 3);
        
        println!("{}:", name);
        println!("  S-box: {:?}", function);
        println!("  Is APN: {}", is_apn);
        println!("  Is permutation: {}", is_perm);
        println!("  Derivative counts: {:?}", counts);
        println!("  Perfect derivatives: {}/7", perfect_count);
        println!("  APN Score: {:.1}%", score * 100.0);
        println!();
        
        if score > best_score {
            best_score = score;
            best_function = name;
            best_counts = counts.clone();
        }
    }
    
    println!("=== RESULTS ===");
    println!("Best function: {} ({:.1}% APN score)", best_function, best_score * 100.0);
    println!();
    println!("=== KEY FINDINGS ===");
    println!("• No function achieved perfect APN properties (all derivatives = 4)");
    println!("• Pierre's twisted function has the highest APN score");
    println!("• Finding APN permutations remains an open challenge");
    println!("• The search continues...");
    
    println!("\n=== MATHEMATICAL VERIFICATION ===");
    println!("For n=3, perfect APN requires: [4, 4, 4, 4, 4, 4, 4]");
    println!("Best function achieved: {:?}", best_counts);
    println!("Perfect derivatives: {}/7", best_counts.iter().filter(|&&c| c == 4).count());
}



How to run it:
# Run the analysis
cargo run

# Run tests 
cargo test
-----BEGIN PGP SIGNATURE-----

iQIzBAEBCgAdFiEEOPhOn65N+XbUXMpWZ3IkUdCGxpUFAmjRtr0ACgkQZ3IkUdCG
xpX1JhAAkaNeQMV6rTQMMaDPkP2G4gvhvawc5SayKm5ltkZDrjlHiOdA4kN/61t6
rERgOdLH6gXTeZksSZYlzCU3K6T4JrtdCGbWn8MHhsTiOAog51DWH6EG4SuEPCqV
GIJv0XdzOXiBSvQsUaWhdc3w7GjQZWu1YiKrW6sxJF9y2UoepjaCuoIMUGQZpqf9
i4Jl3k6zAIhPR/vNJFiYCv1r5R1OpVqkjKUiK3rjSf2Jyj6XaoT+ZsdJUydq4HCU
ZgAXhmUJtGFwuKUe2DriFGPClA5sTKMtSWS+hW7ufKQNdnQGIvOkiiAmF2SVeIq/
zkRUkGIWMpm7epQYFWdDNF83wkNxnKlqYL5EWtEu75t2QDb3mQ5vArQILKIkR6Yu
Jyl7w0C7Vl8Epg52mPJD0p6MxIa1OmWKCywoi2945+dvKt7VO0oaLor4JMpS13rt
WHNSgiwpwB9BCsl9wtteP5ipnG/3EhXQBVzXok2NtTMgQuK+hMwa1NIu7ZhF8x3c
3D+JiusGXUCEuQhnuiwDIWOqcnQMTDNWf3+VkjqNi12p9DTj804M1R6CX2jxtLXd
iAX1gLoVzRtq2l33FJfNfd1hZ/dxLMWMe2XmelTjjC/XFKh4Md7kd8WL+b+KBKfl
qQ0oXl68czn30ClzOqtsAlmO3FBG2rcdxk+W9fkGgXkLEQEmnxo=
=w8Kq
-----END PGP SIGNATURE-----