Scloud: Public Key Encryption and Key Encapsulation Mechanism Based on Learning with Errors

Abstract. We propose Scloud, a public key encryption and key encapsulation mechanism based on the Learning with Errors (LWE) problem. Unlike many lattice-based schemes that rely on structured lattices (rings or modules) for efficiency, Scloud is built on unstructured LWE, offering stronger security guarantees against potential algebraic attacks. Scloud achieves practical performance by employing optimized parameter selection, efficient encoding techniques, and balanced error reconciliation. We provide detailed parameter sets for multiple security levels and analyze the security against known attacks. Scloud serves as a foundation for subsequent improvements that led to Scloud+, with the core design principles of avoiding algebraic structures while maintaining competitive efficiency.