Efficient RLWE based Chosen-Ciphertext Secure Dual-Receiver Encryption and Sender-Binding KEM in the Standard Model

252 / BBB

2026-05-05

Robert Brede

15:45

Key encapsulation mechanism (KEM) is an often used primi-
tive in communication, closely related to public key encryption (PKE).
Dual-receiver encryption (DRE) is another primitive closely related to
PKE that allows a sender to encrypt a message to two different receivers.
Most applications of DRE need the soundness property which guarantees
that both receivers decrypt any ciphertext to the same message. Addi-
tionally, IND-CPA security is often not enough and so schemes should
satisfy a stronger notion like IND-CCA2. Meanwhile, an alternative to
IND-CCA2 for KEMs is the IND-SB-CPA security notion which was
proven to be strong enough to realize secure channels while in theory
enabling the construction of more efficient schemes.
Most IND-CCA2 security proofs rely on the FO transformation, which
is only secure in the ROM, and the standard model DREs and KEMs
are far from efficient. We fill this gap by providing a sound DRE and a
KEM satisfying IND-CCA2 and IND-SB-CPA security respectively. Both
schemes are based on RLWE, proven secure in the standard model, and
have key sizes of 150 KB and ciphertext sizes of 100 KB, improving upon
previous results by a factor of 10x to 100x.