dataesr/scientific-paragraphs-categorization huggingface dataset:
2. We extend the Jasmin programming language [ABB + 17, ABB + 20] with local functions, sub-arrays, pointer types required for call-by-reference, and system calls to obtain randomness. We communicated these extensions to the Jasmin developers and they have meanwhile been adopted upstream. 3. We present two implementations of Kyber-768 in Jasmin targeting the AMD64 architecture: one reference implementation and one optimized implementation using the AVX2 vector instruction set. We use the automated extraction provided by the Jasmin compiler to obtain EasyCrypt models of the two Jasmin implementations. 4. We extend EasyCrypt's standard library with new features required by Kyber, such as support for polynomial rings, signed representations of field elements, dealing with sub-arrays, etc. We created a library that specifies and validates several optimizations of NTT computations used in Kyber, but which is of interest for other post-quantum cryptosystems.
What does our result mean? The use of the formally verified Jasmin compiler guarantees correct translation to assembly, so the behavior of the assembly code is guaranteed to match the behavior of the source Jasmin code. The computer-verified proofs of functional correctness establish the link between the implementations and the specification of Kyber and, ultimately, guarantee that the assembly code is indeed performing the computations specified by the Kyber specification. However, there are two aspects that still require careful manual inspection by expert auditors: the formal specification of Kyber in EasyCrypt and the statements of the theorems that we prove. We therefore dedicate most of the paper to explaining our formalization choices with respect to these two aspects, and present only a summarized view of the proof itself, focusing on the most innovative aspects and documenting lessons learned for the future.
With regards to verification of implementation security, we refer to [ASBG + 23], which reports formally proven protection against classical timing attacks and Spectre v1 attacks [KHF + 19] for Jasmin implementations of multiple cryptographic routines, including Kyber. The implementations of Kyber considered in that paper are very close to the ones proven correct here. We are confident that we can use the same approach to prove constant-timeness and protect against Spectre v1, once the security type system in the Jasmin compiler from [ASBG + 23] is integrated into the main branch. Also, we are confident that the performance overhead for Spectre v1 protections will be just as low (i. e. , < 1%) as reported in [ASBG + 23]. Limitations and TCB. Our computer-verified proofs rely on a trusted code base (TCB) and are limited in scope to the Kyber specification.
The correctness proofs of the Jasmin compiler rely on the assumption that the semantics of individual machine instructions are correctly formalized in Coq and EasyCrypt. The mechanism that extracts EasyCrypt code from Jasmin code is also part of the TCB. Finally, the EasyCrypt tool itself is part of the TCB. In terms of scope, our proofs do not cover the correctness of the SHA3 implementations, which come from the libjade library 1. Some of this code has been verified in [ABB + 19], but we do not establish a formal connection to this work. We note also that the correctness theorem for the Jasmin compiler and the extraction to EasyCrypt only apply to memory-safe programs. However, automatically proving memory safety of our Kyber implementations is currently out of scope for the static safety analyzer in the Jasmin compiler.
For this reason, we check memory safety using a combination of static analysis and dynamic analysis: the functional correctness proof guarantees that the memory accesses which are relevant for the computation of the scheme are safe, but they do not exclude accesses that cause unsafety due to, e. g. , misalignment or simply accessing memory that is subsequently not used. For this reason we use the Jasmin interpreter and valgrind to reinforce the memory-safety guarantees. The bigger picture. As the subtitle of this paper suggests, formally verifying the functional correctness and certain aspects of implementation security of Kyber is only part of the whole story. The use of EasyCrypt as specification language and verification tool allows us to also conduct mechanized reductionist proofs of security, i.
Related Work. While this paper is the first to present a fully computer-verified implementation of a post-quantum crypto scheme, it is not the first to present verification efforts in the realm of post-quantum cryptography. Hwang et al. [HLS + 22] use CryptoLine 2 to formally verify the AVX2 implementation of the NTT transform used in the Kyber NIST submission. This is essentially the same code used for NTT in our AVX2 implementation, so our results corroborate the findings in [HLS + 22]. However, our proof goes beyond NTT and covers two full Kyber implementations. We further discuss [HLS + 22] in the concluding remarks of the paper. Kreuzer  [Kre23]  focuses on machine-checking the correctness of the Kyber specification as a cryptographic construction, i. e. , a proof that encryption and decryption commute.
Specification of Kyber in EasyCrypt The EasyCrypt specification of Kyber closely follows the description in the latest version (3. 02) of the CRYSTALS-Kyber proposal [ABD + 21], omitting some features that are not relevant for Kyber-768, namely noise sampling and compression algorithms that are only used for other Kyber parameter sets 3. We will gradually introduce the various definitions and intermediate results leading to the full code in Figures 2 to 5. This section was written so that it is easy to match our code to the pseudocode specification of Kyber in [ABD + 21, Sec. 1].
Algebraic Structure Operations over values in field F q. We begin by fixing the prime q = 3329 and instantiating the EasyCrypt theory ZModField with this parameter to obtain type Fq 2 CryptoLine is a formal-verification framework that takes low-level code with user annotations for pre-conditions, post-conditions and intermediate assertions, and generates inputs for SMT solvers and computer algebra systems that can then be used to automatically check correctness. It is available from https://github. com/fmlab-iis/cryptoline. 3 Extending the specification for other variants is straightforward. that represents elements in the finite field F q. We extend this theory with an operator as_sint that maps elements in Fq to integers in the range [-(q -1)/2, (q -1)/2] and define compression and decompression operators as follows: op as_sint(x : Fq) = if (q-1) / 2 < asint x then asint xq else asint x.
op compress(d : int, x : Fq) : int = round (asint x * 2 d / R q) % 2 d. op decompress(d : int, x : int) : Fq = inFq (round (x * q / R 2 d )). Here, asint is the operator that takes a field element and returns an integer in the range [0, q). We use / R to denote real division, use / for integer division and % for the mod operation. round denotes rounding to the closest integer with ties being rounded up, as indicated in the Kyber specification. Compression and decompression map field elements into integers in the range [0, 2 d ) and back, with a loss that is captured by the following lemma stated and proved in EasyCrypt. 0 < d ⇒ 2 d < q ⇒ | as_sint (compress_err d c) | ≤ round (q / R (2 d+1 )). We pave the way to connecting the Kyber specification to Jasmin code by giving alternative definitions of compress and decompress-these match what is done in code using machine instructions-and prove that these are equivalent to the specifications above.
The code computes compress using compress_alt for d = 1 and d = 4, and it uses compress_alt_large for d = 10. op compress_alt(d : int, c : Fq) : int = (asint c * 2 d + (q+1)/2) * (2 28 /q) / 2 28 % 2 d. op compress_alt_large(c : Fq) : int = (asint c * 2 10 + (q+1)/2) * (2 32 /q) / 2 32 % 2 10. op decompress_alt(d : int, c : int) : Fq = inFq ((c * q + 2 d-1 ) / 2 d ). Using these operators we can also capture the encoding/decoding of bits as finite-field  The next step is to specify the distributions over field elements that are used by Kyber. We define the Binomial distribution and the uniform distribution over field elements by declaring them as follows, and then deriving auxiliary lemmas that describe the mass function of each of them in an explicit way (this is important for proving correctness of the sampling procedures used by the implementation).
Algorithmic Sampling, Encoding and Decoding The Kyber specification relies on a number of auxiliary algorithms. We follow the same structure and define them as independent EasyCrypt modules used by the main Kyber specification in EasyCrypt. In this section we mention SHA3 algorithms several times, when the specification refers to it. By this we mean algorithms in the SHA-3 standard, including the SHA3 hash functions and the SHAKE extendable-output functions. In Section 7 we further discuss how our formalization and an ongoing machine-checked security proof of the specification clarify the assumptions that Kyber makes about SHA3 algorithms. Rejection sampling a uniform ring element. The first auxiliary algorithm used by Kyber is a rejection sampling procedure called Parse, which we give in Figure  4.
t list) : bool list = flatten (map W8. w2bits bytes). op decode(l i : int, bits : bool list) = l j=0 b2i (nth false bits (i * l+j)) * 2 j. op sem_decode4(a : W8. t Array128. t) : ipoly = Array256. init (fun i ⇒ decode 4 i (BytesToBits (to_list a))). The Kyber specification [ABD + 21] leaves encoding implicitly defined as the inverse of the decoding operation. We rely on a new EasyCrypt feature to lift our imperative versions of the encoding and decoding operations to functional operators, prove that decoding matches the Kyber specification, and finally prove that encoding inverts decoding. We discuss this in more detail in Section 3. 2. The full specification. The code given in Figures 2 to 5 and the code snippets we provide throughout this section closely match the pseudo-code and definitions in the Kyber specification [ABD + 21].
Also, in a deterministic setting, results in HL can be proven using results in pHL, as well as the other way around. The proof of correctness for the Kyber Jasmin code relies on these two mechanisms. In particular, the game-hopping strategy allows us to build intermediate programs between the EasyCrypt code produced by Jasmin and our desired specification. We use it to remove optimizations and to abstract operations on algebraic structures. EasyCrypt also features a standard library formalizing some basic algebraic structures, which we use to capture the algebraic structure underlying Kyber. This library is based on the EasyCrypt cloning mechanism, originally introduced to manage abstract types in cryptographic primitives. One thing that became clear during this project is that cloning has proven to be a source of complexity and limitations as more algebraic structures were added to the hierarchy, namely polynomial rings, vectors and matrices thereof needed for Kyber.
Automatic inference of functional specifications. One of the tedious aspects of some EasyCrypt proofs arises from the fact that some parts of the proofs are easier to do with functional specifications, whereas other parts are easier to do with imperative specifications. The sweet spot usually resides in using both approaches at the same time, which means writing both specifications by hand and proving that they are equivalent. In Kyber, a number of simple procedures are used to encode and decode data into byte arrays, so applying this approach would be quite time consuming. To avoid this, a new mechanism was developed that can automatically infer a functional specification from an imperative program, provided that the latter has as reasonably simple control flow. Dealing with nested for loops in EasyCrypt.
Implementation This paper presents two different implementations of Kyber-768, a reference implementation and an optimized implementation using AVX2 vector instructions. Those implementations follow largely the structure and implementation strategies of the ref and avx2 implementations by the Kyber team 6  , which are also included in the submission package to NIST and integrated into PQClean 7. Reference implementation. The structure of the reference implementation largely follows the specification. On the lowest level they implement arithmetic in F q , i. e. on integers modulo the prime q; these are represented as signed 16-bit integers. The most interesting routines on this level are Montgomery and Barrett reductions. The Montgomery reduction takes as input a signed 32-bit integer a and produces a signed 16-bit output r with r ≡ a • 2 16 (mod q).
Proof of functional correctness The strategy we adopted for the functional correctness proof divided the effort into a first phase, in which we constructed a proof for the reference implementation, and a second phase where we addressed the AVX2 implementation. The first phase included the development of a number of EasyCrypt libraries to deal with various data structures and operators used by the EasyCrypt code extracted from the Jasmin implementations, namely distributions over arrays, conversions between arrays of field elements and their representations, etc. One important library that may be reused in future developments establishes results for field elements in Montgomery representation, including not only the expected congruence relations, but also the ranges of the representations of these elements when stored as microprocessor words by the implementation.
In the same figure we also show that we have proved as important side-results that, should the XOF and PRF modules we show above be replaced with purely random coins, then the noise sampling and matrix sampling procedures in the Kyber specification produce the correct output distribution. The top-level IND-CPA proof then proceeds by connecting our intermediate implementation to the Kyber specification by using the lower level results described above for ring elements and vectors thereof. The proof boils down to guaranteeing that plugging the outputs of one function into the next always satisfies the contracts that constrain the ranges of the representations. When it comes to noise sampling and matrix sampling, we first replace the extracted code with the mock implementation, which allows us to conclude the equivalence proof in a trivial way.
This is natural, since the AVX2 implementation is meant to be a drop-in replacement, whenever the target platform supports the necessary extensions. The proof is by transitivity: we have that the reference implementation is correct with respect to the Kyber specification, so it suffices to prove that the AVX2 implementation is equivalent to the reference implementation. We propagate this transitivity argument using relational Hoare logic down to lower level operations, as far as the structure of the code allows. For example, it is straightforward to prove that the IND-CPA encryption operations are equivalent, assuming that the intermediate level operations over vectors and ring elements on each side are, in turn, equivalent. We end up with a series of proof goals that look like the statement below.
Again, the most challenging cases were the NTT-related operations, where the proof effort was divided into three additional steps: i. defining an intermediate EasyCrypt implementation that performs field operation in the same order as the AVX implementation; ii. proving that this code is equivalent to the AVX implementation by excluding the possibility of representation errors; and iii. proving that the resulting sequence of field operations is indeed computing the NTT as prescribed by the specification. Our NTT library was extended with additional variants of the NTT computation, all proved equivalent to the specification, to facilitate the connection to the AVX implementation, as we describe next.
The proof is again done by game-hopping and its structure is summed up in Figure  9. The thin double arrow represents step 1) discussed above. The thick double arrows correspond to pRHL equivalence proofs. The dashed double arrow corresponds to the final HL correctness proof, where the EasyCrypt program NTTnaive is proven to implement the EasyCrypt functional specification of the NTT, described in Section 2. This proof is then lifted to pHL and carried by transitivity to all the other versions of the NTT via the other equivalence proofs. The intermediate NTTs are characterized by the following: • NTT Fq replaces the calls to auxiliary functions in NTT Jasmin by their mathematical specification • NTTAVX2 Fq replaces the calls to auxiliary functions in NTTAVX2 Jasmin by their mathematical specification • NTTopt splits the NTT into several small functions to allow for modular reasoning • NTTbsrev replaces the incremental computation of the index used to access the array of roots of unity by the computation of it's value from the loop indexes, and the index variable of the innermost loop by it's final value when it's used after the innermost loop • NTTnaive has it's two innermost loops in reverse bit order when compared to NTTbsrev, and the accesses to the array of roots of the unity are replaced by the computation of the value of the desired root • NTTAVX2 Fun replaces the two innermost loops by the evaluation of a function, and is designed to be easy to be shown equivalent to both NTTbsrev and NTTAVX2 The most challenging proof was the equivalence between NTTbsrev and NTTnaive, as it is in this transformation that the loops on both sides do not have the same order.
Benchmarks In this Section we present benchmark results of our Jasmin implementations and compare to the original implementations written in C and assembly. We benchmark on three different generations of Intel CPUs that all implement the AMD64 architecture and support the AVX2 instruction set. Specifically, we benchmark on an Intel Core i7-6500U (Skylake), an Intel Core i7-4770K (Haswell) and on an Intel Core i7-10700K (Comet Lake) CPU. All benchmarks are using only a single core of these CPUs; we followed the standard practice of disabling Hyperthreading and TurboBoost; the C compiler used for all benchmarks was Clang, version 14. 8 Table  1  reports the results of these benchmarks. All cycle counts in this table are the median of 10 000 runs with different inputs. All implementations used the same implementation of randombytes, which is implemented through the Linux getrandom system call.
We see that the Jasmin reference implementation is considerably slower than the C reference implementation. This is expected, because the Jasmin compiler, unlike C compilers, does not optimize the code: this is by design the job of the programmer. The goal of this implementation was not to achieve high performance, but rather to facilitate the EasyCrypt proof of correctness. More relevant is the performance comparison of the optimized AVX2 implementations. We first comment that, for the same C/asm implementation and very similar CPUs, SUPERCOP  [BL]  reports somewhat lower cycle counts. The main reason for this difference is that our benchmarks obtain random bytes through a system call, while SUPERCOP uses a fast userspace randomness generator. We see that the fully optimized Jasmin code is within about 10% of the performance of the optimized C and assembly implementation by the Kyber team.
The approach in [HLS + 22] is promising but, at the moment, there are significant differences in the level of assurance that our work provides in comparison, namely: (1) our coverage of the implementation (excluding SHA3) is complete, whereas in [HLS + 22] only the NTT transform is covered; and (2) the trusted computing base (TCB) for the tooling in our development is arguably smaller, since EasyCrypt has been around for a long time and is reasonably self-contained, and the Jasmin compiler is verified in Coq. Nevertheless, like in [HLS + 22], our TCB includes hand-written semantics for assembly operations and the part of the Jasmin compiler that extracts Jasmin code to EasyCrypt. In any case, future research will certainly include an effort to integrate the ideas of [HLS + 22] (or even the tooling) into the current toolchain.
3. The proof highlights sub-optimal parts of the code, e. g. , the fact that bounds are explicitly stated and proved at the function level permit identifying the points where these bounds are too tight for what is needed, and hence can be relaxed by removing unnecessary computations. This was indeed the case in this development, where the final version of the AVX2 code is faster because we were able to eliminate redundant reduction steps that became evident when formally proving the ranges of intermediate computations. As an example of the importance of point (1) above, which is perhaps the less obvious one, let us consider the declarations in Figure  10 , which pinpoint how SHA3 algorithms are used in Kyber. We note that a total of 9 different types of calls to the SHA3 library are performed: these are declared as operators, which we axiomatize as the semantics of the corresponding functions in the SHA3 library for concrete input and output sizes.
Acknowledgments This research was supported by  Deutsche Forschungsgemeinschaft (DFG, German research Foundation)  as part of the  Excellence Strategy   of the German Federal and State Governments  - EXC 2092 CASA -390781972 ; by the  European Commission  through the  ERC Starting Grant   805031  (EPOQUE); by the  German Federal Ministry of Education and Research (BMBF)  in the course of the 6GEM research hub under grant number  16KISK038 ; and by the  Agence Nationale de la Recherche (French National Research Agency)  as part of the  France 2030 programme  - ANR-22-PECY-0006. This work was supported by  European Structural and Investment Funds  in the  FEDER component , and through the  Operational Competitiveness and Internationalization Programme (COMPETE 2020)  (Project No. 047264 ; Funding Reference:  POCI-01-0247-FEDER-047264 ).
1  and Supplementary Table  1 ). Such systematic biases and limitations can allow the model to discriminate classes based on differences in background noise, which are likely much easier patterns to exploit and would thus result in seemingly excellent predictive performances. Indeed, studies on this data set report extremely high performances of 99% sensitivity when discriminating healthy from pathological breathing  16  and 92% for the detection of Chronic Obstructive Pulmonary Disease (COPD)  17. Other studies not using the ICBHI dataset tend to be limited to specific diseases, or single geographic locations, which risks poor generalizabilty. These examples highlight the crucial importance of external validation and model interpretability to assess predictive robustness and rule out the possibility of confounding factors being exploited for classification.
To our knowledge, no prior studies proposing diagnostic deep learning models on DLA recordings have been externally validated on independently collected data, nor has there been an effort to verify that their predictions align to physiological signals. The concept of dataset shift is becoming increasingly recognized as a practical concern with dramatic effects in performance  18. Such as in an analogous example of diagnostic models for automated X-ray interpretation, where the performance on external test data proved to be significantly lower than that originally reported  19. In this study, we have made a specific effort to generate a pathologically diverse data set of auscultation recordings, that are acquired from a systematically recruited patient cohort, with standardized inclusion criteria and diagnostic protocols as well as broad geographic representation.