In the present paper we describe the technology for translating algorithmic descriptions of discrete functions to SAT. The proposed technology is aimed at applications in algebraic cryptanalysis. We describe how cryptanalysis instances are reduced to SAT in such a way that it should be perceived as natural by the cryptographic community. Therefore, in the theoretical part of the paper we justify the main principles of general reduction to SAT for discrete functions from a class containing the majority of functions employed in cryptography. Based on these principles we describe the Transalg software system, developed with SAT-based cryptanalysis specifics in mind. We show the results of applications of Transalg to construction of a number of attacks on various cryptographic functions. Some of the corresponding attacks are state of the art. We also compare the functional capabilities of the proposed system with that of other software systems that can be used to reduce cryptanalysis instances to SAT, and also with the CBMC system widely employed in symbolic verification. In the paper we also present vast experimental data, obtained using the SAT-solvers that took first places at the SAT-competitions in the recent several years.
The software system @cite_51 @cite_91 @cite_28 was developed by Galois inc. In 2010 there appeared the system @cite_1 . Approximately at this time we started the development of the software system, which we describe in the present paper ( was first mentioned in papers in Russian in 2011). In 2012 there appeared the system @cite_113 , aimed at reducing to SAT various constraint programming problems. It can be applied to construct encodings for cryptographic functions as well. Note that , and can encode to SAT algorithmic descriptions of a very wide class of functions working with binary data. Meanwhile, is designed to work only with keystream generators based on shift registers. We considered the pros and cons of all mentioned systems in detail in Section 4.
@cite_91 @cite_28 @cite_1 @cite_113 @cite_51
2101207956 2049051506 1637999745 1550483759
Polar codes, as the first provable capacity-achieving error-correcting codes, have received much attention in recent years. However, the decoding performance of polar codes with traditional successive-cancellation (SC) algorithm cannot match that of the low-density parity-check or Turbo codes. Because SC list (SCL) decoding algorithm can significantly improve the error-correcting performance of polar codes, design of SCL decoders is important for polar codes to be deployed in practical applications. However, because the prior latency reduction approaches for SC decoders are not applicable for SCL decoders, these list decoders suffer from the long-latency bottleneck. In this paper, we propose a multibit-decision approach that can significantly reduce latency of SCL decoders. First, we present a reformulated SCL algorithm that can perform intermediate decoding of 2 b together. The proposed approach, referred as 2-bit reformulated SCL ( 2b-rSCL ) algorithm , can reduce the latency of SCL decoder from ( @math ) to ( @math ) clock cycles without any performance loss. Then, we extend the idea of 2-b-decision to general case, and propose a general decoding scheme that can perform intermediate decoding of any @math bits simultaneously. This general approach, referred as @math -bit reformulated SCL ( @math b-rSCL ) algorithm , can reduce the overall decoding latency to as short as @math cycles. Furthermore, on the basis of the proposed algorithms, very large-scale integration architectures for 2b-rSCL and 4b-rSCL decoders are synthesized. Compared with a prior SCL decoder, the proposed (1024, 512) 2b-rSCL and 4b-rSCL decoders can achieve 21 and 60 reduction in latency, 1.66 and 2.77 times increase in coded throughput with list size 2, and 2.11 and 3.23 times increase in coded throughput with list size 4, respectively. This paper describes a new method for efficient implementation of the Galois Counter Mode on general purpose processors. Our approach is based on three concepts: a) having a 64-bit carry-less multiplication instruction in the processor; b) a method for using this instruction to efficiently multiply binary polynomials of degree 127; c) a method for efficient reduction of a binary polynomial of degree 254, modulo the polynomial x^1^2^8+x^7+x^2+x+1 (which defines the finite field of the Galois Counter Mode). The two latter concepts can be used for writing an efficient and lookup-table free software implementation of the Galois Counter Mode, for processors that have a carry-less multiplication instruction. Our approach uses only a generic carry-less multiplication instruction, without any field-specific reduction logic, making the instruction applicable to multiple use cases, and therefore an appealing addition to the instruction set of a general purpose processor. This research played a significant role in the process that eventually led to adding a carry-less multiplication instruction (called PCLMULQDQ) to the Intel Architecture. PCLMULQDQ and six AES instructions are introduced in the new 2010 Intel Core processor family, based on the 32 nm Intel microarchitecture codename ''Westmere''. On the new Westmere processors, the software that implements the methods described here, computes AES-GCM more than six times faster than the current, lookup table-based, state-of-the-art implementation. This new capability adds motivation to using AES-GCM for high performance secure networking. We describe a new class of list decodable codes based on Galois extensions of function fields and present a list decoding algorithm. These codes are obtained as a result of folding the set of rational places of a function field using certain elements (automorphisms) from the Galois group of the extension. This work is an extension of Folded Reed Solomon codes to the setting of Algebraic Geometric codes. We describe two constructions based on this framework depending on if the order of the automorphism used to fold the code is large or small compared to the block length. When the automorphism is of large order, the codes have polynomially bounded list size in the worst case. This construction gives codes of rate @math over an alphabet of size independent of block length that can correct a fraction of @math errors subject to the existence of asymptotically good towers of function fields with large automorphisms. The second construction addresses the case when the order of the element used to fold is small compared to the block length. In this case a heuristic analysis shows that for a random received word, the expected list size and the running time of the decoding algorithm are bounded by a polynomial in the block length. When applied to the Garcia-Stichtenoth tower, this yields codes of rate @math over an alphabet of size @math , that can correct a fraction of @math errors. I describe and study the 'support encoding' of binary constraint satisfaction problems (CSP's) into boolean satisfiability (SAT). This is based on work by Kasif in 1990, in which clauses encode support information, rather than the encoding of conflicts in the standard 'direct encoding'. This enables arc consistency in the original CSP to be established by propagation in the translated SAT instance, providing an optimal worst case time algorithm for arc consistency [14]. I prove that the DP algorithm in SAT applied to the suport encoding behaves exactly like the MAC algorithm in CSP's. Using the SAT solver Chaff, I show that the support encoding can be used effectively to solve hard instances of random binary CSP's, and more effectively than the direct encoding on hard instances. Finally, I show that the local search algorithm WalkSAT can perform many times better on the support encoding than on the direct encoding.