Kotlin Falcon-512 Migration Guide: s1/s2 → z0/z1 Format

Overview

This guide documents the migration from the old s1/s2 signature format to the new z0/z1 format that is compatible with the Rust reference implementation.

Format Differences

Old Format (s1/s2)

New Format (z0/z1)

Migration Steps

1. Update Signature Class

Old:

data class Signature(val data: ByteArray)

New:

data class SignatureZ0Z1(
    val nonce: ByteArray,
    val z0: IntArray,
    val z1: IntArray
)

2. Update Signing Function

Old Implementation:

fun sign(message: ByteArray, privateKey: PrivateKey): Signature {
    // ... sampling code ...
    val (s1, s2) = sampler.sample(cPoly, rngFunc)
    
    // Only compress and store s2
    val compressedSig = Compression.compressSignature(nonce, s2)
    return Signature(compressedSig)
}

New Implementation:

fun sign(message: ByteArray, privateKey: PrivateKey): SignatureZ0Z1 {
    // ... sampling code ...
    val (tempS1, tempS2) = sampler.sample(cPoly, rngFunc)
    
    // Map to z0/z1 format
    val z1 = tempS2  // Short vector
    val z0 = tempS1  // Or compute: c - h*z1
    
    return SignatureZ0Z1(nonce, z0, z1)
}

3. Update Verification Function

Old Implementation:

fun verify(message: ByteArray, signature: Signature, publicKey: PublicKey): Boolean {
    // Decompress to get s2
    val (nonce, s2) = Compression.decompressSignature(signature.data)
    
    // Reconstruct s1 = c - h*s2
    val s1 = computeS1FromS2(publicKey.h, s2, cPoly)
    
    // Check bounds on s1 and s2
    // ...
}

New Implementation:

fun verify(message: ByteArray, signature: SignatureZ0Z1, publicKey: PublicKey): Boolean {
    // Compute expected z0 = c - h*z1
    val expectedZ0 = computeZ0(publicKey.h, signature.z1, cPoly)
    
    // Verify z0 matches
    for (i in 0 until Constants.N) {
        if (abs(signature.z0[i] - expectedZ0[i]) > threshold) {
            return false
        }
    }
    // Check bounds on z0 and z1
    // ...
}

4. Compression Updates

The z0/z1 format requires different compression:

// New compression for z0/z1 format
fun compressZ0Z1(sig: SignatureZ0Z1): ByteArray {
    // Format: nonce || compressed_z0 || compressed_z1
    val buffer = ByteBuffer.allocate(estimatedSize)
    buffer.put(sig.nonce)
    
    // Compress z0 coefficients (2 bytes each)
    for (coeff in sig.z0) {
        buffer.putShort(coeff.toShort())
    }
    
    // Compress z1 coefficients (2 bytes each)
    for (coeff in sig.z1) {
        buffer.putShort(coeff.toShort())
    }
    
    return buffer.array()
}

Backward Compatibility

To maintain backward compatibility during migration:

object Falcon512Compat {
    fun signatureFromOldFormat(
        oldSig: Signature,
        publicKey: PublicKey,
        message: ByteArray
    ): SignatureZ0Z1? {
        // Extract s2 from old signature
        val (nonce, s2) = Compression.decompressSignature(oldSig.data)
        
        // Compute challenge
        val c = computeChallenge(nonce, message)
        
        // Map to new format
        val z1 = s2
        val z0 = computeZ0(publicKey.h, z1, c)
        
        return SignatureZ0Z1(nonce, z0, z1)
    }
}

Testing the Migration

1. Unit Tests

@Test
fun testZ0Z1Format() {
    val keypair = Falcon512Z0Z1.generateKeyPair()
    val message = "Test message".toByteArray()
    
    // Sign with new format
    val signature = Falcon512Z0Z1.sign(message, keypair.privateKey)
    
    // Verify signature
    assertTrue(Falcon512Z0Z1.verify(message, signature, keypair.publicKey))
    
    // Verify equation: z0 = c - h*z1 (mod q)
    val c = computeChallenge(signature.nonce, message)
    val expectedZ0 = computeZ0(keypair.publicKey.h, signature.z1, c)
    assertArrayEquals(expectedZ0, signature.z0)
}

2. Cross-Platform Validation

@Test
fun testCrossPlatformCompatibility() {
    // Load test vectors from Rust implementation
    val testVectors = loadTestVectors("falcon512_test_vectors.json")
    
    for (tv in testVectors) {
        val message = tv.message
        val rustSignature = tv.signature
        
        // Verify Rust signature with Kotlin
        val sig = SignatureZ0Z1.fromBytes(rustSignature)
        val publicKey = PublicKey.fromBytes(tv.publicKey)
        
        assertTrue(Falcon512Z0Z1.verify(message, sig, publicKey))
    }
}

Performance Considerations

The z0/z1 format has different performance characteristics:

Operation Old (s1/s2) New (z0/z1)
Signing Faster (store less) Slower (store more)
Verification Slower (reconstruct) Faster (direct check)
Signature Size Smaller Larger (uncompressed)
Memory Usage Lower Higher

Migration Timeline

  1. Phase 1: Implement Falcon512Z0Z1 alongside existing implementation
  2. Phase 2: Add compatibility layer for old signatures
  3. Phase 3: Update all new signatures to use z0/z1 format
  4. Phase 4: Deprecate old s1/s2 format
  5. Phase 5: Remove old implementation

Common Issues and Solutions

Issue 1: Signature Size Increase

Solution: Implement proper compression for z0/z1 format to maintain ~666 byte target size

Issue 2: Verification Failures

Solution: Ensure modular arithmetic is handled correctly when comparing z0 values

Issue 3: Performance Regression

Solution: Optimize NTT operations and consider caching frequently used computations

Code Location

The new implementation is located at:

metamui-crypto-kotlin/src/main/kotlin/id/metamui/crypto/falcon512/Falcon512Z0Z1.kt

Next Steps

  1. Review and test the new Falcon512Z0Z1 implementation
  2. Create comprehensive test suite for format migration
  3. Update all dependent code to use new format
  4. Validate against Rust test vectors
  5. Performance optimization if needed

References