Digestly

Dec 9, 2024

A Closer Look at Falcon

Microsoft Research - A Closer Look at Falcon

The presentation by Yonana focuses on the Falcon signature scheme, one of the NIST post-quantum signature algorithms. Falcon is noted for its compactness, making it a strong candidate for post-quantum cryptography. However, its implementation complexity, particularly due to Gaussian sampling, poses challenges. The talk highlights the need for provable security, which is not straightforward with Falcon due to issues with statistical distance and the need for modifications to achieve security proofs. The speaker proposes modifications, such as hashing the public key and adjusting the sampling process, to enhance security without significant efficiency loss. The presentation also discusses the use of Rényi divergence instead of statistical distance to measure distribution closeness, which helps in achieving tighter security bounds. The results show that with these modifications, Falcon can achieve significant security levels, though challenges remain, particularly with the number of signing queries and the complexity of the proof structure.

Key Points:

  • Falcon is compact but complex to implement due to Gaussian sampling.
  • Modifications like hashing the public key can improve security.
  • Rényi divergence is used for better security bounds than statistical distance.
  • Security proofs require careful handling of signing queries and distribution closeness.
  • Proposed changes aim to make Falcon more secure without major efficiency loss.
View Full Content
Upgrade to Plus to unlock complete episodes, key insights, and in-depth analysis
Starting at $5/month. Cancel anytime.