TY - GEN
T1 - Falcon codes
T2 - 22nd ACM SIGSAC Conference on Computer and Communications Security, CCS 2015
AU - Juels, Ari
AU - Kelley, James
AU - Tamassia, Roberto
AU - Triandopoulos, Nikos
PY - 2015/10/12
Y1 - 2015/10/12
N2 - We introduce Falcon codes, a class of authenticated error correcting codes that are based on LT codes and achieve the following properties, for the first time simultaneously: (1) with high probability, they can correct adversarial corruptions of an encoded message, and (2) they allow very efficient encoding and decoding times, even linear in the message length. Our design framework encompasses a large number of such coding schemes. Through judicious use of simple cryptographic tools at the core LT-coding level, Falcon codes lend themselves to secure extensions of any LT-based fountain code, in particular providing Raptor codes that achieve resilience to adversarial corruptions while maintaining their fast encoding/decoding times. Falcon codes also come in three variants, each offering different performance trade-offs. For instance, one variant works well with small input messages (100s of KB to 10s of MB), but two other variants are designed to handle much larger messages (several GB). We study Falcon codes in a novel adversarial model for rateless codes over computational (corrupting) channels and prove their security under standard assumptions. We analyze the performance of our new coding schemes through a prototype implementation of their Raptor-code extension and a thorough experimental study that demonstrates their high efficiency in practice. Applied to data transmission, Falcon codes can provably protect Raptor codes against targeted-erasure attacks, which were recently shown by Lopes and Neves [Oakland, 2014] to cause decoding failures of RaptorQ-the most advanced, standardized (IETF RFC6330) rateless code used in practice. Applied to data storage, Falcon codes can provide significant efficiency gainings as drop-in replacements of Reed-Solomon codes; in particular, a 35% speed-up over the state-of-the-art PoR scheme by Shi et al. [CCS, 2013].
AB - We introduce Falcon codes, a class of authenticated error correcting codes that are based on LT codes and achieve the following properties, for the first time simultaneously: (1) with high probability, they can correct adversarial corruptions of an encoded message, and (2) they allow very efficient encoding and decoding times, even linear in the message length. Our design framework encompasses a large number of such coding schemes. Through judicious use of simple cryptographic tools at the core LT-coding level, Falcon codes lend themselves to secure extensions of any LT-based fountain code, in particular providing Raptor codes that achieve resilience to adversarial corruptions while maintaining their fast encoding/decoding times. Falcon codes also come in three variants, each offering different performance trade-offs. For instance, one variant works well with small input messages (100s of KB to 10s of MB), but two other variants are designed to handle much larger messages (several GB). We study Falcon codes in a novel adversarial model for rateless codes over computational (corrupting) channels and prove their security under standard assumptions. We analyze the performance of our new coding schemes through a prototype implementation of their Raptor-code extension and a thorough experimental study that demonstrates their high efficiency in practice. Applied to data transmission, Falcon codes can provably protect Raptor codes against targeted-erasure attacks, which were recently shown by Lopes and Neves [Oakland, 2014] to cause decoding failures of RaptorQ-the most advanced, standardized (IETF RFC6330) rateless code used in practice. Applied to data storage, Falcon codes can provide significant efficiency gainings as drop-in replacements of Reed-Solomon codes; in particular, a 35% speed-up over the state-of-the-art PoR scheme by Shi et al. [CCS, 2013].
KW - Adversarial channel
KW - Authenticated error correcting codes
KW - LT codes
KW - Proofs of retrievability
KW - Raptor codes
KW - Secure coding schemes
UR - http://www.scopus.com/inward/record.url?scp=84954178268&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84954178268&partnerID=8YFLogxK
U2 - 10.1145/2810103.2813728
DO - 10.1145/2810103.2813728
M3 - Conference contribution
AN - SCOPUS:84954178268
T3 - Proceedings of the ACM Conference on Computer and Communications Security
SP - 1032
EP - 1047
BT - CCS 2015 - Proceedings of the 22nd ACM SIGSAC Conference on Computer and Communications Security
Y2 - 12 October 2015 through 16 October 2015
ER -