International Association
for Cryptologic Research

In this work, we present a primary construction of bent functions based on cellular automata (CA). We consider the well-known characterization of bent functions in terms of Hadamard matrices and employ some recent results about mutually orthogonal Latin squares (MOLS) based on linear bipermutive CA (LBCA) to design families of Hadamard matrices of the form required for bent functions. In particular, the main question to address in this construction can be reduced to finding a large enough set of coprime polynomials over $\mathbb{F}_q$, which are used to define a set of MOLS via LBCA. This set of MOLS is, in turn, used to define a Hadamard matrix of the specific structure characterizing a bent function. We settle the existence question of such bent functions by proving that the required coprime sets exist if and only if the degree of the involved polynomials is either $1$ or $2$, and we count the resulting sets. Next, we check if the functions of $8$ variables arising from our construction are EA-equivalent to Maiorana-McFarland functions, observing that most of them are not. Finally, we show how to represent the support of these bent functions as a union of the kernels of the underlying linear CA. This allows us, in turn, to prove that the functions generated by our construction belong to the partial spread class $\mathcal{PS}^-$. In particular, we remark that for degree $1$ our construction is a particular case of the Desarguesian spread construction.

Functional Encryption (FE) allows users who hold a specific secret key (known as the functional key) to learn a specific function of encrypted data whilst learning nothing about the content of the underlying data. Considering this functionality and the fact that the field of FE is still in its infancy, we sought a route to apply this potent tool to solve the existing problem of designing decentralised additive reputation systems. To this end, we first built a symmetric FE scheme for the $\ell_1$ norm of a vector space, which allows us to compute the sum of the components of an encrypted vector (i.e. the votes). Then, we utilized our construction, along with functionalities offered by Intel SGX, to design the first FE-based decentralized additive reputation system with Multi-Party Computation. While our reputation system faces certain limitations, this work is amongst the first attempts that seek to utilize FE in the solution of a real-life problem.

In this paper, we study relationship between security of cryptographic schemes in the random oracle model (ROM) and quantum random oracle model (QROM). First, we introduce a notion of a proof of quantum access to a random oracle (PoQRO), which is a protocol to prove the capability to quantumly access a random oracle to a classical verifier. We observe that a proof of quantumness recently proposed by Brakerski et al. (TQC '20) can be seen as a PoQRO. We also give a construction of a publicly verifiable PoQRO relative to a classical oracle. Based on them, we construct digital signature and public key encryption schemes that are secure in the ROM but insecure in the QROM. In particular, we obtain the first examples of natural cryptographic schemes that separate the ROM and QROM under a standard cryptographic assumption.

On the other hand, we give lifting theorems from security in the ROM to that in the QROM for certain types of cryptographic schemes and security notions. For example, our lifting theorems are applicable to Fiat-Shamir non-interactive arguments, Fiat-Shamir signatures, and Full-Domain-Hash signatures etc. We also discuss applications of our lifting theorems to quantum query complexity.

In this work, we propose tweaks to the PRINCE block cipher that help us to increase its security without changing the number of rounds or round operations. We get substantially higher security for the same complexity. From an implementation perspective, PRINCEv2 comes at an extremely low overhead compared to PRINCE in all key categories, such as area, latency and energy. We expect, as it is already the case for PRINCE, that the new cipher PRINCEv2 will be deployed in various settings.

The Statistical Ineffective Fault Analysis, SIFA, is a recent addition to the family of fault based cryptanalysis techniques. SIFA based attack is shown to be formidable and is able to bypass virtually all the conventional fault attack countermeasures. Reported countermeasures to SIFA incur overheads of the order of at least thrice the unprotected cipher. We propose a novel countermeasure that reduces the overhead (compared to all existing countermeasures) as we rely on a simple duplication based technique. In essence, our countermeasure eliminates the observation that enables the attacker to perform SIFA. The core idea we use here is to choose the encoding for the state bits randomly. In this way, each bit of the state is free from statistical bias, which renders SIFA unusable. Our approach protects against stuck-at faults and also does not rely on any side channel countermeasure. We show the effectiveness of the countermeasure through an open source gate-level fault attack simulation tool. Our approach is probably the simplest and the most cost effective.

Fault attacks are among the well-studied topics in the area of cryptography. These attacks constitute a powerful tool to recover the secret key used in the encryption process. Fault attacks work by forcing a device to work under non-ideal environmental conditions (such as high temperature) or external disturbances (such as glitch in the power supply) while performing a cryptographic operation. The recent trend shows that the amount of research in this direction; which ranges from attacking a particular primitive, proposing a fault countermeasure, to attacking countermeasures; has grown up substantially and going to stay as an active research interest for a foreseeable future. Hence, it becomes apparent to have a comprehensive yet compact study of the (major) works. This work, which covers a wide spectrum in the present day research on fault attacks that fall under the purview of the symmetric key cryptography, aims at fulfilling the absence of an up-to-date survey. We present mostly all aspects of the topic in a way which is not only understandable for a non-expert reader, but also helpful for an expert as a reference.

We initiate the study of multi-party functional encryption (MPFE) which unifies and abstracts out various notions of functional encryption which support distributed ciphertexts or secret keys, such as multi-input FE, multi-client FE, decentralized multi-client FE, multi-authority ABE, multi-authority FE and such others. We provide a unifying framework to capture existing multi-party FE primitives, define new, natural primitives that emerge from the framework, provide a feasibility result assuming general multi-input functional encryption (MIFE), and also provide constructions for restricted function families from standard assumptions. In more detail, we provide the following new constructions:

1. Two Input Quadratic Functional Encryption: We provide the first two input functional encryption scheme for quadratic functions from the SXDH assumption on bilinear groups. To the best of our knowledge, this is the first construction of MIFE from standard assumptions that goes beyond the inner product functionality.

2. Decentralized Inner Product Functional Encryption: We provide the first decentralized version of an inner product functional encryption scheme, generalizing the recent work of Michalevsky and Joye (ESORICS'18). Our construction supports access policies C that are representable as inner product predicates, and is secure based on the k-linear assumption, in the random oracle model.

3. Distributed Ciphertext-Policy Attribute Based Encryption. We provide a decentralized variant of the recent ciphertext-policy attribute based encryption scheme, constructed by Agrawal and Yamada (Eurocrypt'20). Our construction supports NC1 access policies, and is secure based on Learning With Errors and relies on the generic bilinear group model as well as the random oracle model.

Our new abstraction predicts meaningful new primitives for multi-party functional encryption which we describe but do not instantiate — these may be constructed in future work.

Modern public-key cryptography is a crucial part of our contemporary life where a secure communication channel with another party is needed. With the advance of more powerful computing architectures – especially Graphics Processing Units (GPUs) – traditional approaches like RSA and Diffie-Hellman schemes are more and more in danger of being broken.

We present a highly optimized implementation of Lenstra’s ECM algorithm customized for GPUs. Our implementation uses state-of-the-art elliptic curve arithmetic and optimized integer arithmetic while providing the possibility of arbitrarily scaling ECM’s parameters allowing an application even for larger discrete logarithm problems. Furthermore, the proposed software is not limited to any specific GPU generation and is to the best of our knowledge the first implementation supporting multiple device computation. To this end, for a bound of B1=8,192 and a modulus size of 192 bit, we achieve a throughput of 214 thousand ECM trials per second on a modern RTX 2080 Ti GPU considering only the first stage of ECM. To solve the Discrete Logarithm Problem for larger bit sizes, our software can easily support larger parameter sets such that a throughput of 2,781 ECM trials per second is achieved using B1=50,000, B2=5,000,000, and a modulus size of 448 bit.

For safe resource management - an effective mechanism/system is necessary that identifies a person and his rights to these resources, using an appropriate key, and its degree of security determines not only the property, but sometimes even the life of its owner. For several decades, it has been based on the security of (bio)material keys, which only guarantee their own authenticity, but not their owner, due to weak of static password protection. The development of an effective SecHCI (Secure Human-Computer Identification) system is becoming an increasingly urgent problem in modern civilization. In the article will be presented an innovative challenge-response protocol, that requires only 1 image to be remember by an user, showing the structure of a virtual microchip, and a mental simulation of the operation of its components, thanks to which reverse engineering of the virtual structure is as difficult as such operation on a physical microchip, and their diversity is limited only by the fantasy of the user, inspired by the analogous features of the physical elements. It will be shown how the i-Chip generates the one-time password (OTP) or whole digital signature, also offline on paper documents, or acts as a virtual key for an electronic lock opened with OTP.

The advances of the Internet of Things (IoT) have had a fundamental impact and influence in sharping our rich living experiences. However, since IoT devices are usually resource-constrained, lightweight block ciphers have played a major role in serving as a building block for secure IoT protocols. In CHES 2015, SIMECK, a family of block ciphers, was designed for resource-constrained IoT devices. Since its publication, there have been many analyses on its security. In this paper, under the one bit-flip model, we propose a new efficient fault analysis attack on SIMECK ciphers. Compared to those previously reported attacks, our attack can recover the full master key by injecting faults into only a single round of all SIMECK family members. This property is crucial, as it is infeasible for an attacker to inject faults into different rounds of a SIMECK implementation on IoT devices in the real world. Specifically, our attack is characterized by exercising a deep analysis of differential trail between the correct and faulty immediate ciphertexts. Extensive simulation evaluations are conducted, and the results demonstrate the effectiveness and correctness of our proposed attack.

In this paper, we analyze permissionless blockchain protocols, whose distributed consensus algorithm lies on a Proof-of-Work composed of $k \geq 1$ sequential hash-puzzles. We put our focus in a restricted scenario, widely used in the blockchain literature, in which the number of miners, their hash rates, and the difficulty values of the hash-puzzles are constant throughout time. Our main contribution is a closed-form expression for the mining probability of a miner, that is, the probability the miner completes the Proof-of-Work of the next block to be added to the blockchain before every other miner does. Our theoretical results can be applied to existing Proof-of-Work based blockchain protocols, such as Bitcoin or Ethereum. We also point out some security issues implied by our findings, which makes not trivial at all the design of multi-stage (i.e. $k \geq 2$) Proof-of-Work blockchain protocols.

Multi-signatures enable a group of signers to produce a single signature on a given message. Recently, Drijvers et al. (S&P'19) showed that all thus far proposed two-round multi-signature schemes in the DL setting (without pairings) are insecure under concurrent sessions, i.e., if a single signer participates in multiple signing sessions concurrently. While Drijvers et al. improve the situation by constructing a secure two-round scheme, saving a round comes with the price of having less compact signatures. In particular, the signatures produced by their scheme are more than twice as large as Schnorr signatures, which arguably are the most natural and compact among all practical DL signatures and are therefore becoming popular in cryptographic applications (e.g., support for Schnorr signature verification has been proposed to be included in Bitcoin). If one needs a multi-signature scheme that can be used as a drop-in replacement for Schnorr signatures, then one is either forced to resort to a three-round scheme such as MuSig (Maxwell et al., DCC 2019) or MSDL-pop (Boneh, Drijvers, and Neven, ASIACRYPT 2018), or to accept that signing sessions are only secure when run sequentially, which may be hard to enforce in practice, e.g., when the same signing key is used by multiple devices.

In this work, we propose MuSig2, a novel and simple two-round multi-signature scheme variant of the MuSig scheme. Our scheme is the first multi-signature scheme that simultaneously i) is secure under concurrent signing sessions, ii) supports key aggregation, iii) outputs ordinary Schnorr signatures, iv) needs only two communication rounds, and v) has similar signer complexity as regular Schnorr signatures. Furthermore, our scheme is the first multi-signature scheme in the DL setting that supports preprocessing of all but one rounds, effectively enabling a non-interactive signing process, without forgoing security under concurrent sessions. The combination of all these features makes MuSig2 highly practical. We prove the security of MuSig2 under the one-more discrete logarithm (OMDL) assumption in the random oracle model, and the security of a more efficient variant in the combination of the random oracle and algebraic group models.

This work provides a systematic investigation of the use of approximate enumeration oracles in BKZ, building on recent technical progress on speeding-up lattice enumeration: relaxing (the search radius of) enumeration and extended preprocessing which preprocesses in a larger rank than the enumeration rank. First, we heuristically justify that relaxing enumeration with certain extreme pruning asymptotically achieves an exponential speed-up for reaching the same root Hermite factor (RHF). Second, we perform simulations/experiments to validate this and the performance for relaxed enumeration with numerically optimised pruning for both regular and extended preprocessing. Upgrading BKZ with such approximate enumeration oracles gives rise to our main result, namely a practical and faster (compared to previous work) polynomial-space lattice reduction algorithm for reaching the same RHF in practical and cryptographic parameter ranges. We assess its concrete time/quality performance with extensive simulations and experiments. As a consequence, we update the extrapolation of the crossover rank between a square-root cost estimate for quantum enumeration using our algorithm and the Core-SVP cost estimate for quantum sieving to 547.

With the advancement of the trusted execution environment (TEE) technologies, hardware-supported secure computing becomes increasingly popular due to its efficiency. During the protocol execution, typically, the players need to contact a third-party server for remote attestation, ensuring the validity of the involved trusted hardware component, such as Intel SGX, as well as the integrity of the computation result. When the hardware manufacturer is not fully trusted, sensitive information may be leaked to the third-party server through backdoors, side-channels, steganography, and kleptography, etc. In this work, we introduce a new security notion called semi-trusted hardware model, where the adversary is allowed to passively and/or maliciously corrupt the hardware component. Therefore, she can learn the input of the hardware component and might also tamper the output. We show that two-party computation can still be significantly sped up in this new model. When the semi-trusted hardware is instantiated by Intel SGX, to generate 10k random OT's, our protocol is 50X and 270X faster than the EMP-ROT in the LAN and WAN setting, respectively. For the AES, SHA-1, and SHA-256 evaluation, our protocol is 4-5X and 40-50X faster than the EMP-SH2PC in the LAN and WAN setting, respectively.

Side-channel analysis (SCA) utilizing the power consumption of a device has proved to be an efficient technique for recovering secret keys exploiting the implementation vulnerability of mathematically secure cryptographic algorithms. Recently, Deep Learning-based profiled SCA (DL-SCA) has gained popularity, where an adversary trains a deep learning model using profiled traces obtained from a dummy device (a device that is similar to the target device) and uses the trained model to retrieve the secret key from the target device. \emph{However, for efficient key recovery from the target device, training of such a model requires a large number of profiled traces from the dummy device and extensive training time}. In this paper, we propose \emph{TranSCA}, a new DL-SCA strategy that tries to address the issue. \emph{TranSCA} works in three steps -- an adversary (1) performs a one-time training of a \emph{base model} using profiled traces from \emph{any} device, (2) fine-tunes the parameters of the \emph{base model} using significantly less profiled traces from a dummy device with the aid of \emph{transfer learning} strategy in lesser time than training from scratch, and (3) uses the fine-tuned model to attack the target device. We validate \emph{TranSCA} on simulated power traces created to represent different FPGA families. Experimental results show that the transfer learning strategy makes it possible to attack a new device from the knowledge of another device even if the new device belongs to a different family. Also, \emph{TranSCA} requires very few power traces from the dummy device compared to when applying DL-SCA without any previous knowledge.

Lattice-based cryptographic scheme is constructed based on hard problems on a structured lattice such as the short integer solution (SIS) problem and the learning with error (LWE), called ring-SIS (R-SIS), ring-LWE (R-LWE), module-SIS (M-SIS), and module-LWE (M-LWE). Generally, it has been considered that problems defined on the module-lattice are more difficult than the problems defined on the ideal-lattices. However, Albrecht and Deo showed that there is a reduction from M-LWE to R-LWE in the polynomial ring by handling the error rate and modulus. Also, Koo, No, and Kim showed that there is a reduction from M-SIS$_{q^{k},m^{k},\beta'}$ to R-SIS$_{q,m,\beta}$ under some norm constraint of R-SIS, where $k > 1$. In this paper, we propose the improved reductions related to M-SIS and R-SIS compared to the previous work. To show the improved reduction, we propose the three novel reductions related to M-SIS to R-SIS on the polynomial ring. First, we propose the reduction from R-SIS$_{q^{k},m,\beta'}$ to R-SIS$_{q^{k},m^{k},\beta^{k}}$. Combining one of the previous works, we obtain the reduction between R-SIS problems with distinct parameters preserving the number of samples of R-SIS. Second, we propose the improved reduction from M-SIS$_{q^{k},m,\beta'}$ to R-SIS$_{q^{k},m,\beta}$ with $k \ge 1$ under some norm constraint of R-SIS. Comparing to the previous work, the upper bound of the norm of the solution of M-SIS is decreased. Finally, we propose a reduction between M-SIS with different moduli. Combining these three results implies that R-SIS$_{q,m,\beta}$ is more difficult than M-SIS$_{C,m,\beta'}$, where $C$ is a multiple of $q^{k}$ for some $k \ge 1$ under some norm constraint of R-SIS, which provides a double extension of the possible range of module ranks for M-SIS compared to the previous work.

We study information-theoretic multiparty computation (MPC) protocols over rings $\mathbb{Z}/p^k \mathbb{Z}$ that have good asymptotic communication complexity for a large number of players. An important ingredient for such protocols is arithmetic secret sharing, i.e., linear secret-sharing schemes with multiplicative properties. The standard way to obtain these over fields is with a family of linear codes $C$, such that $C$, $C^\perp$ and $C^2$ are asymptotically good (strongly multiplicative). For our purposes here it suffices if the square code $C^2$ is not the whole space, i.e., has codimension at least 1 (multiplicative).

Our approach is to lift such a family of codes defined over a finite field $\mathbb F$ to a Galois ring, which is a local ring that has $\mathbb F$ as its residue field and that contains $\mathbb{Z}/p^k \mathbb{Z}$ as a subring, and thus enables arithmetic that is compatible with both structures. Although arbitrary lifts preserve the distance and dual distance of a code, as we demonstrate with a counterexample, the multiplicative property is not preserved. We work around this issue by showing a dedicated lift that preserves \emph{self-orthogonality} (as well as distance and dual distance), for $p \geq 3$. Self-orthogonal codes are multiplicative, therefore we can use existing results of asymptotically good self-dual codes over fields to obtain arithmetic secret sharing over Galois rings. For $p = 2$ we obtain multiplicativity by using existing techniques of secret-sharing using both $C$ and $C^\perp$, incurring a constant overhead. As a result, we obtain asymptotically good arithmetic secret-sharing schemes over Galois rings.

With these schemes in hand, we extend existing field-based MPC protocols to obtain MPC over $\mathbb{Z}/p^k \mathbb{Z}$, in the setting of a submaximal adversary corrupting less than a fraction $1/2 - \varepsilon$ of the players, where $\varepsilon > 0$ is arbitrarily small. We consider 3 different corruption models. For passive and active security with abort, our protocols communicate $O(n)$ bits per multiplication. For full security with guaranteed output delivery we use a preprocessing model and get $O(n)$ bits per multiplication in the online phase and $O(n \log n)$ bits per multiplication in the offline phase. Thus, we obtain true linear bit complexities, without the common assumption that the ring size depends on the number of players.

This paper considers multivariate polynomial equation systems over GF(2) that have a small number of solutions. This paper gives a new method EGHAM2 for solving such systems of equations that uses the properties of the Boolean quotient ring to potentially reduce memory and time complexity relative to existing XL-type or Groebner basis algorithms applied in this setting. This paper also establishes a direct connection between solving such a multivariate polynomial equation system over GF(2), an MQ problem, and an instance of the LPN problem.

This paper closes the question of the possibility of two-round MPC protocols achieving different security guarantees with and without the availability of broadcast in any given round. Cohen et al. [CGZ20] study this question in the dishonest majority setting; we complete the picture by studying the honest majority setting. In the honest majority setting, given broadcast in both rounds, it is known that the strongest guarantee — guaranteed output delivery — is achievable [GLS15]. We show that in this setting, given broadcast in the first round only, guaranteed output delivery is still achievable. Given broadcast in the second round only, identifiable abort and all weaker guarantees are achievable, but fairness — and thus guaranteed output delivery — are not. Finally, using only peer-to-peer channels, for corruption thresholds $t > 1$ we show that the weakest guarantee — selective abort — is the only one achievable. For $t = 1$ and $n \geq 4$, it is known [IKP10,IKKP15] that guaranteed output delivery (and thus all weaker guarantees) are possible. We show that for $t = 1$ and $n = 3$ the strongest achievable guarantee is selective abort, resolving the question of best achievable guarantees in two-round secure computation protocols.

In this paper we present a new representation of the AES key schedule, with some implications to the security of AES-based schemes. In particular, we show that the AES-128 key schedule can be split into four independent parallel computations operating on 32 bits chunks, up to linear transformation. Surprisingly, this property has not been described in the literature after more than 20 years of analysis of AES. We show two consequences of our new representation, improving previous cryptanalysis results of AES-based schemes. First, we observe that iterating an odd number of key schedule rounds results in a function with short cycles. This explains an observation of Khairallah on mixFeed, a second-round candidate in the NIST lightweight competition. Our analysis actually shows that his forgery attack on mixFeed succeeds with probability 0.44 (with data complexity 220GB), breaking the scheme in practice. The same observation also leads to a novel attack on ALE, another AES-based AEAD scheme. Our new representation also gives efficient ways to combine information from the first sub-keys and information from the last sub-keys, in order to reconstruct the corresponding master keys. In particular we improve previous impossible-differential attacks against AES-128.