ABSTRACT
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].
- 3GPP. Multimedia Broadcast/Multimedia Service (MBMS); Protocols and codecs. Technical Report ETSI TS 26.346, 3GPP, Sep. 2014. v12.3.0, Rel. 12.Google Scholar
- D. Bernstein. The Salsa20 family of stream ciphers. In New Stream Cipher Designs. 2008. Google ScholarDigital Library
- K. D. Bowers, A. Juels, and A. Oprea. HAIL: A High-Availability and Integrity Layer for Cloud Storage. In CCS, 2009. Google ScholarDigital Library
- K. D. Bowers, A. Juels, and A. Oprea. Proofs of Retrievability: Theory and Implementation. In CCSW, 2009. Google ScholarDigital Library
- J. W. Byers, M. Luby, M. Mitzenmacher, and A. Rege. A Digital Fountain Approach to Reliable Distribution of Bulk Data. SIGCOMM, 28(4), October 1998. Google ScholarDigital Library
- N. Cao, S. Yu, Z. Yang, W. Lou, and Y. T. Hou. LT Codes-based Secure and Reliable Cloud Storage Service. In INFOCOM, March 2012.Google Scholar
- N. Chandran, B. Kanukurthi, and R. Ostrovsky. Locally Updatable and Locally Decodable Codes. IACR ePrint, Report 2013/520, August 2013.Google Scholar
- R. Curtmola, O. Khan, and R. Burns. Robust Remote Data Checking. In Proc. of StorageSS '08, 2008. Google ScholarDigital Library
- Digital Video Broadcasting Project. Interaction channel for satellite distribution systems. Technical Report ETSI EN 301 790, ETSI, May 2009. v1.5.1.Google Scholar
- Digital Video Broadcasting Project. IP Datacast over DVB-H. Technical Report ETSI TS 102 591--1, ETSI, Feb. 2010. v1.3.1.Google Scholar
- R. A. Fisher and F. Yates. Statistical tables for biological, agricultural and medical research. Oliver and Boyd, Edinburgh, 1963.Google Scholar
- P. Gopalan, R. J. Lipton, and Y. Z. Ding. Error correction against computationally bounded adversaries, April 2004. Unpublished manuscript.Google Scholar
- V. Guruswami and A. Smith. Codes for Computationally Simple Channels: Explicit Constructions with Optimal Rate. In FOCS, 2010. Google ScholarDigital Library
- A. Juels and B. S. Kaliski, Jr. PoRs: Proofs of Retrievability for Large Files. In CCS, 2007. Google ScholarDigital Library
- B. Kaliski. PKCS#5: Password-Based Cryptography Specification Version 2.0. RFC 2898, September 2000. Google ScholarDigital Library
- C. Karlof, N. Sastry, Y. Li, A. Perrig, and J. D. Tygar. Distillation Codes and Applications to DoS Resistant Multicast Authentication. In NDSS, 2004.Google Scholar
- H. Krawczyk. Distributed Fingerprints and Secure Information Dispersal. In PODC, 1993. Google ScholarDigital Library
- H. Krawczyk. Secret Sharing Made Short. In CRYPTO. 1994. Google ScholarDigital Library
- M. N. Krohn, M. J. Freedman, and D. Mazières. On-the-Fly Verification of Rateless Erasure Codes for Efficient Content Distribution. In IEEE Sym. on Sec. and Priv., 2004.Google ScholarCross Ref
- T. Krovetz and W. Dai. VMAC: Message Authentication Code using Universal Hashing. IETF Draft: draft-krovetz-vmac-01, 2007.Google Scholar
- M. Langberg. Private Codes or Succinct Random Codes That Are (Almost) Perfect. In FOCS, 2004. Google ScholarDigital Library
- R. J. Lipton. A new approach to information theory. In STACS. 1994. Google ScholarDigital Library
- J. Lopes and N. Neves. Robustness of the RaptorQ FEC Code Under Malicious Attacks. In Inforum, 2013.Google Scholar
- J. Lopes and N. Neves. Stopping a Rapid Tornado with a Puff. In IEEE Sym. on Sec.\ and Priv., 2014. Google ScholarDigital Library
- M. Luby. LT Codes. In FOCS, 2002. Google ScholarDigital Library
- M. Luby and M. Mitzenmacher. Verification-Based Decoding for Packet-Based Low-Density Parity-Check Codes. IEEE Trans. on Info. Theory, 51(1), 2005. Google ScholarDigital Library
- M. Luby, A. Shokrollahi, M. Watson, and T. Stockhammer. Raptor Forward Error Correction Scheme for Object Delivery. IETF RFC5053, October 2007.Google Scholar
- M. Luby, A. Shokrollahi, M. Watson, T. Stockhammer, and L. Minder. RaptorQ Forward Error Correction Scheme for Object Delivery. IETF RFC6330, August 2011.Google Scholar
- A. Lysyanskaya, R. Tamassia, and N. Triandopoulos. Multicast authentication in fully adversarial networks. In IEEE Sym. on Sec. and Priv., 2004.Google ScholarCross Ref
- P. Maymounkov. Online codes. Technical report, Secure Computer Systems Group, NYU, 2002.Google Scholar
- S. Micali, C. Peikert, M. Sudan, and D. A. Wilson. Optimal Error Correction Against Computationally Bounded Noise. IEEE Tran. on Info. Theory, 56(11), 2010. Google ScholarDigital Library
- N. Nethercote and J. Seward. Valgrind: A Framework for Heavyweight Dynamic Binary Instrumentation. In PLDI, 2007. Google ScholarDigital Library
- D. J. Newman and L. Shepp. The double dixie cup problem. American Mathematical Monthly, 67(1), 1960.Google Scholar
- R. Ostrovsky, O. Pandey, and A. Sahai. Private Locally Decodable Codes. In ICALP. 2007. Google ScholarDigital Library
- R. Palanki and J.S. Yedidia. Rateless codes on noisy channels. In ISIT, July 2004.Google ScholarCross Ref
- A. Pannetrat and R. Molva. Efficient Multicast Packet Authentication. In NDSS, 2003.Google Scholar
- J. Perry. libwireless and wireless-python. www.yonch.com/wireless, (2014/05/06).Google Scholar
- J. Perry, H. Balakrishnan, and D. Shah. Rateless Spinal Codes. In HotNets-X, 2011. Google ScholarDigital Library
- J. Perry, P. A. Iannucci, K. E. Fleming, H. Balakrishnan, and D. Shah. Spinal Codes. SIGCOMM, 42(4), 2012. Google ScholarDigital Library
- H. Pishro-Nik and F. Fekri. On raptor codes. In IEEE Int. Conf. on Comm., volume 3, June 2006.Google ScholarCross Ref
- J. S. Plank and K. M. Greenan. Jerasure: A Library in C Facilitating Erasure Coding for Storage Applications -- Version 2.0. Technical Report UT-EECS-14--721, U.\ of Tenn., 2014.Google Scholar
- M. Saito and M. Matsumoto. SIMD-Oriented Fast Mersenne Twister: a 128-bit Pseudorandom Number Generator. In MCQMCM. 2006.Google Scholar
- S. Sarkar and R. Safavi-Naini. Proofs of Retrievability via Fountain Code. In FPS, 2012. Google ScholarDigital Library
- H. Shacham and B. Waters. Compact Proofs of Retrievability. In ASIACRYPT, 2008. Google ScholarDigital Library
- E. Shi, E. Stefanov, and C. Papamanthou. Practical Dynamic Proofs of Retrievability. In CCS, 2013. Google ScholarDigital Library
- A. Shokrollahi. Raptor codes. IEEE/ACM Trans. on Networking, 14(SI), June 2006. Google ScholarDigital Library
- A. Smith. Scrambling Adversarial Errors Using Few Random Bits, Optimal Information Reconciliation, and Better Private Codes. In SODA, 2007. Google ScholarDigital Library
- STMicroelectonics and INIRA. LDPC FEC Codes, 2006.Google Scholar
- C. Tartary and H. Wang. Rateless Codes for the Multicast Stream Authentication Problem. In Adv. in Info. and Comp. Sec. 2006. Google ScholarDigital Library
Index Terms
- Falcon Codes: Fast, Authenticated LT Codes (Or: Making Rapid Tornadoes Unstoppable)
Recommendations
Simple capacity-achieving ensembles of rateless erasure-correcting codes
This paper is concerned with a simple binary erasure-recovery coding scheme that falls into the family of so-called semi-random low-density-parity-check (SR-LDPC) codes. Based on a constrained random-scrambling technique, the proposed coding scheme is ...
Towards Fountain Codes
Fountain codes are a new class of codes originally designed for robust and scalable transmission of data over lossy computer networks. Binary Fountain codes such as Luby transform codes are a class of erasure codes which have demonstrated an asymptotic ...
Quasi-systematic doped LT codes
Special issue on capaciyy approaching codesWe propose a family of binary erasure codes, namely, quasi-systematic doped Luby-Transform (QS-DLT) codes, that are rateless, almost systematic, and universally capacity-achieving without the prior knowledge of channel erasure rate. The encoding and ...
Comments