Design of Strongly Secure Communication and Computation Channels by Nonlinear Error Detecting Codes

• Published in: IEEE transactions on computers 2014-11, Vol.63 (11), p.2716-2728
• Main Authors: Karpovsky, Mark, Wang, Zhen
• Format: Article
• Language: English
• Subjects: Codes; Computation; Computer information security; Computer security; Construction; Cryptography; Encoding; Error analysis; Error correction & detection; Error detection; Errors; fault injection attacks; Hamming distance; Messages; Nonlinear codes; Nonlinear systems; Nonlinearity; reed-muller codes; Robustness; secure hardware
• ISSN: 0018-9340; 1557-9956
• DOI: 10.1109/TC.2013.146

The security of communication or computational systems protected by traditional error detecting codes rely on the assumption that the information bits of the message (output of the device-under-attack) are not known to attackers or the error patterns are not controllable by external forces. For applications where the assumption is not valid, e.g., secure cryptographic devices, secret sharing, etc, the security of systems protected by traditional error detecting codes can be easily compromised by an attacker. In this paper, we present constructions for strongly secure codes based on the nonlinear encoding functions. For (\mbi {k},\mbi {m},\mbi {r}) strongly secure codes, a message contains three parts: \mbi {k} -bit information data \mbi {y} , \mbi {m} -bit random data \mbi {x} , and \mbi {r} -bit redundancy \mbi {f}(\mbi {y},\mbi {x}) . For any error \mbi {e} and information \mbi {y} , the fraction of \mbi {x} that masks the error \mbi {e} is less than 1. In this paper, we describe lower and upper bounds on the proposed codes and show that the presented constructions can generate optimal or close to optimal codes. An efficient encoding and decoding method for the codes minimizing the number of multipliers using the multivariate Horner scheme is presented.