Side channel attacks have demonstrated in the past that it is possible to break cryptographic algorithms by attacking the implementation rather than the algorithm. This paper compares an adaptation of Paul Kocher's Differential Power Analysis (DPA) for AES with a multi-bit variant by attacking an AES128 implementation for an ATmega328P microcontroller board. The results show that the use of multi-bit DPA can significantly reduce ghost peaks and allow for the recovery of a key with far fewer traces.

As one of the most efficient lattice-based signature schemes, and one of the only ones to have seen deployment beyond an academic setting (e.g., as part of the VPN software suite strongSwan), BLISS has attracted a significant amount of attention in terms of its implementation security, and side-channel vulnerabilities of several parts of its signing algorithm have been identified in previous works. In this paper, we present an even simpler timing attack against it. The bimodal Gaussian distribution that BLISS is named after is achieved using a random sign flip during signature generation, and neither the original implementation of BLISS nor strongSwan ensure that this sign flip is carried out in constant time. It is therefore possible to recover the corresponding sign through side-channel leakage (using, e.g., cache attacks or branch tracing). We show that obtaining this single bit of leakage (for a moderate number of signatures) is in fact sufficient for a full key recovery attack. The recovery is carried out using a maximum likelihood estimation on the space of parameters, which can be seen as a statistical manifold. The analysis of the attack thus reduces to the computation of the Fisher information metric.

Non-commutative cryptography studies cryptographic primitives and systems which are based on algebraic structures like groups, semigroups and noncommutative rings. We con-tinue to investigate inverse protocols of Non-commutative cryptography defined in terms of subsemigroups of Affine Cremona Semigroups over finite fields or arithmetic rings $Z_m$ and homomorphic images of these semigroups as possible instruments of Post Quantum Cryptography. This approach allows to construct cryptosystems which are not public keys, as outputs of the protocol correspondents receive mutually inverse transformations on affine space $K^n$ or variety $(K^*)^n$, where $K$ is a field or an arithmetic ring. The security of such inverse protocol rests on the complexity of word problem to decompose element of Affine Cremona Semigroup given in its standard form into composition of given generators. We discuss the idea of the usage of combinations of two cryptosystems with cipherspaces $(K^*)^n$ and $K^n$ to form a new cryptosystem with the plainspace $(K^*)^n$, ciphertext $K^n$ and nonbijective highly nonlinear encryption map.

Atomic Swap enables two parties to atomically exchange their own cryptocurrencies without trusted third parties. This paper provides the first quantitative analysis on the fairness of the Atomic Swap protocol, and proposes the first fair Atomic Swap protocol with implementations. In particular, we model the Atomic Swap as the American Call Option, and prove that an Atomic Swap is equivalent to an American Call Option without the premium. Thus, the Atomic Swap is unfair to the swap participant. Then, we quantify the fairness of the Atomic Swap and compare it with that of conventional financial assets (stocks and fiat currencies). The quantification results show that the the Atomic Swap is much more unfair on cryptocurrencies than on stocks and fiat currencies in the same setting. Moreover, we use the conventional Cox-Ross-Rubinstein option pricing model in Finance to estimate the premium, and show that the estimated premium for cryptocurrencies is 2% ∼ 3% of the asset value, while the premium for stocks and fiat currencies is approximately 0.3%. Furthermore, we propose two fair Atomic Swap protocols, one is for currency exchange and the other is for American Call Options. Our protocols are based on the original Atomic Swap protocol, but implement the premium mechanism. Blockchains supporting smart contracts such as Ethereum support our protocols directly. Blockchains only supporting scripts such as Bitcoin can support our protocols by adding a simple opcode. Finally, we provide the reference implementation of our protocols in Solidity, and give detailed instructions on implementing our protocols with Bitcoin script.

In 2017 Kyung-Ah Shim et al proposed a multivariate signature scheme called Himq-3 which is a submission to National Institute of Standards and Technology (NIST) standardization process of post-quantum cryptosystems. The Himq-3 signature scheme can be classified into oil vinegar signature scheme family. It has a multilayer structure but it uses a cycle system to invert the central map. The signing process of Himq-3 is very fast, and it has small signatures. In this paper we present a cryptanalysis of Himq-3. We show that inherent to the signing process is a leakage of information of the private key. Using this information one can forge a signature.

We design a suite of protocols so that a small tamper-resistant device can be used as a biometric identity document which can be scanned by authorized terminals. We target both strongly secure identification and strong privacy. Unlike biometric passports, our protocols leak no digital evidence and are essentially deniable. Besides, getting the identity information from the device requires going through access control. Access control can follow either a strong PKI-based path or a weak password-based path which offer different functionalities. We implemented our protocols on JavaCard using finger-vein recognition as a proof of concept.

A new implementation of Falcon is presented. It solves longstanding issues in the existing reference code: the new implementation is constant-time, it does not require floating-point hardware (though it can use such hardware for better performance), it uses less RAM, and achieves much better performance on both large systems (x86 with Skylake cores, POWER8,...) and small microcontrollers (ARM Cortex M4). In particular, signature generation with Falcon-512 takes less than 470k cycles on a Skylake (82k cycles only for verification), and about 21.2 million cycles on an ARM Cortex M4.

We propose a new nonce-misuse-resistant authenticated encryption scheme, which instantiates the SIV paradigm of Rogaway and Shrimpton. In contrast to the GCM-SIV approach proposed by Gueron and Lindell, we do only use a single type of cryptographic primitive, which can be advantageous in restricted embedded devices. Furthermore, we use three independent and fixed subkeys derived from a single master key. Similar to the CCM mode, our scheme uses a combination of the CTR mode for the symmetric encryption and a MAC based on the CBC construction and is therefore called CCM-SIV. We provide a detailed security proof for our scheme. Furthermore, we outline its extension to a nonce-based key derivation as the AES-GCM-SIV approach.

In this work, we consider executions of smart contracts for implementing secure multi-party computation (MPC) protocols on forking blockchains (e.g., Ethereum), and we study security and delay issues due to forks. In this setting, the classical double-spending problem tells us that messages of the MPC protocol should be confirmed on-chain before playing the next ones, thus slowing down the entire execution. Our contributions are twofold: - For the concrete case of fairly tossing multiple coins with penalties, we notice that the lottery protocol of Andrychowicz et al. (S&P '14) becomes insecure if players do not wait for the confirmations of several transactions. In addition, we present a smart contract that instead retains security even when all honest players immediately answer to transactions appearing on-chain. We analyze the performance using Ethereum as testbed. - We design a compiler that takes any ``digital and universally composable'' MPC protocol (with or without honest majority), and transforms it into another one (for the same task and same setup) which maintains security even if all messages are played on-chain without delays. The special requirements on the starting protocol mean that messages consist only of bits (e.g., no hardware token is sent) and security holds also in the presence of other protocols. We further show that our compiler satisfies fairness with penalties as long as honest players only wait for confirmations once. By reducing the number of confirmations, our protocols can be significantly faster than natural constructions.

We present a polynomial-time adaptive attack on the 2-SIDH protocol. The 2-SIDH protocol is a special instance of the countermeasure proposed by Azarderakhsh, Jao and Leonardi to perform isogeny-based key exchange with static keys in the presence of an adaptive attack. This countermeasure has also been recently explicitly proposed by Kayacan. Our attack extends the adaptive attack by Galbraith, Petit, Shani and Ti (GPST) to recover a static secret key using malformed points. The extension of GPST is non-trivial and requires learning additional information. In particular, the attack needs to recover intermediate elliptic curves in the isogeny path, and points on them. We also discuss how to extend the attack to k-SIDH when k > 2 and explain that the attack complexity is exponential in k.

Deployment of DNSSEC, although increasing, still suffers from many practical issues that results in a false sense of security. While many domains outsource zone management, they also have to outsource DNSSEC key management to the DNS operator, making the operator an attractive target for attackers. Moreover, DNSSEC does not provide any sort of protection in the case the operator itself decides to serve false information, for example, if it gets compromised. In this work, we show how to use techniques from threshold ECDSA: (1) to protect keys such that domains do not reveal their signing keys to a DNS operator, and (2) to protect the operational integrity of DNS operator. As a result of being highly specialized, prior work on threshold ECDSA has focused on a limited set of threat models, and none have so far considered techniques to amortize signature generation.creation. Our work takes a different approach and presents a generic technique for obtaining a threshold ECDSA protocol from any secure multiparty computation protocol that works over an appropriate finite field. We show how this technique lends itself to very efficient threshold signing protocols by comparing it against state-of-the-art protocols from both academia and industry. For similar threat models, our protocols are as fast as the previous best protocol in terms of signing, and up to an order of magnitude faster for key generation on a fast network. Finally, we show how to integrate our application into a widely used DNS management software and demonstrate through experiments the overhead compared to traditional DNSSECs.

In this paper, we study a group of AEAD schemes that use rekeying as a technique to increase efficiency by reducing the state size of the algorithm. We provide a unified model to study the behavior of the keys used in these schemes, called Rekey-and-Chain (RaC). This model helps understand the design of several AEAD schemes. We show generic attacks on these schemes based on the existence of certain types of weak keys. We also show that the borderline between multi-key and single-key analyses of these schemes is not solid and the analysis can be performed independent of the master key, leading sometimes to practical attacks in the multi-key setting. More importantly, the multi-key analysis can be applied in the single key setting, since each message is encrypted with a different key. Consequently, we show gaps in the security analysis of COMET and mixFeed in the single key setting, which led the designers to provide overly optimistic security claims. In the case of COMET, full key recovery can be performed with 2^64 online queries and 2^64 offline queries in the single-key setting, or 2^40 online queries per user and 2^64 offline queries in the multi-key setting with 2^24 users. In the case of mixFeed, we enhance the forgery adversarial advantage in the single-key setting with a factor of 2^67 compared to what the designers claim. More importantly, our result is just a lower bound of this advantage, since we show that the gap in the analysis of mixFeed depends on properties of the AES Key Schedule that are not well understood and require more cryptanalytic efforts to find a more tight advantage. After reporting these findings, the designers updated their security analyses and accommodated the proposed attacks.

The increasing communication capabilities of vehicles are paving the way for promising road safety and traffic management applications. But the rise of connected vehicles also potentially introduces many security and privacy concerns. Thus, a vision of a successful cooperative vehicular network relies on strong security properties. Proposals such as the Security Credential Management System (SCMS) fulfil these security requirements with the concept of pseudonym certificates, relying on large-scale PKI. But since the on-board units performing these cryptographic operations are usually resource-constrained devices, it is important to consider ways to optimize and devise efficient implementations of the proposed algorithms. In this work, we study optimizations on the mathematical and algorithmic aspects of the validation of implicit certificates and the verification of ECDSA signatures used in the SCMS. We propose efficient algorithms to validate batches of implicit certificates, providing significant savings compared to the sequential validation of the individual certificates. We also propose optimizations to the verification of ECDSA signatures when the verification is performed with an implicit certificate. Although we focus our work on the SCMS and V2X communications, our contributions are more general and apply to every system combining ECQV and ECDSA.

Although Byzantine Agreement (BA) has been studied for three decades, perhaps somewhat surprisingly, there still exist significant gaps in our understanding regarding its round complexity. First, although expected constant-round protocols are known in the honest majority setting, it is unclear whether one has to settle for expected constant-round or whether there exist better protocols that are worst-case constant-round. Second, for the corrupt majority setting, the existence of sublinear-round BA protocols continues to ellude us except for the narrow regime when only sublinearly more than a half are corrupt. In this paper, we make a couple important steps forward in bridging this gap. We show two main results: - No (even randomized) protocol that completes in worst-case $o\left(\log(1/\delta)/\log \log(1/\delta)\right)$ rounds can achieve BA with $1-\delta$ probability, even when only 1% of the nodes are corrupt. In comparison, known expected constant-round, honest-majority protocols complete in $O(\log(1/\delta))$ rounds in the worst-case. Therefore, our lower bound is tight upto a $\log\log$ factor for the honest majority setting. - There exists a corrupt-majority BA protocol that terminates in $O(\log(1/\delta)/\epsilon)$ rounds in the worst case and tolerates $(1-\epsilon)$ fraction of corrupt nodes. Our upper bound is optimal upto a logarithmic factor in light of the elegant $\Omega(1/\epsilon)$ lower bound by Garay et al. (FOCS'07).

In this paper, we provide a notable step towards filling the gap between theory (estimates of running-time) and practice (a discrete logarithm record computation) for the Tower Number Field Sieve (TNFS) algorithm. We propose a generalisation of ranking formula for selecting the polynomials used in the very first step of TNFS algorithm. For this we provide a definition and an exact implementation (Magma and SageMath) of the alpha function. This function measures the bias in the smoothness probability of norms in number fields compared to random integers of the same size. We use it to estimate the yield of polynomials, that is the expected number of relations, as a generalisation of Murphy's E function, and finally the total amount of operations needed to compute a discrete logarithm with TNFS algorithm in the targeted fields. This is an improvement of the earlier work of Barbulescu and Duquesne on estimating the running-time of the algorithm. We apply our estimates to a wide size range of finite fields GF(p^n), for small composite n = 12, 16, 18, 24, that are target fields of pairing-friendly curves.

In this paper, we present new preimage attacks on KECCAK-384 and KECCAK-512 for 2, 3 and 4 rounds. The attacks are based on non-linear structures (structures that contain quadratic terms). These structures were studied by Guo et al. and Li et al. to give preimage attacks on round reduced KECCAK. We carefully construct non-linear structures such that the quadratic terms are not spread across the whole state. This allows us to create more linear equations between the variables and hash values, leading to better preimage attacks. As a result, we present the best theoretical preimage attack on KECCAK-384 and KECCAK-512 for 2 and 3-rounds and also KECCAK-384 for 4-rounds.

Multiparty computation as a service (MPSaaS) is a promising approach for building privacy-preserving communication systems.However, in this paper, we argue that existing MPC implementations are inadequate for this application as they do not address fairness, let alone robustness. Even a single malicious server can cause the protocol to abort while seeing the output for itself, which in the context of an anonymous communication service would create a vulnerability to censorship and deanonymization attacks. To remedy this we propose a new MPC implementation, HoneyBadgerMPC, that combines a robust online phase with an optimistic offline phase that is efficient enough to run continuously alongside the online phase. We use HoneyBadgerMPC to develop an application case study, called AsynchroMix, that provides an anonymous broadcast functionality. AsynchroMix features a novel MPC program that trades off between computation and communication, allowing for low-latency message mixing in varying settings. In a cloud-based distributed benchmark with 100 nodes, we demonstrate mixing a batch of 512 messages in around 20 seconds and up to 4096 messages in around two minutes.

A tropical version of Stickel’s key exchange protocol was suggested by Grigoriev and Sphilrain [2] and successfully attacked by Kotov and Ushakov [5]. We suggest some modifications of this scheme that use commuting matrices in tropical algebra and discuss some possibilities of attacks on these new modifications. We suggest some simple heuristic attacks on one of our new protocols, and then we generalize the Kotov and Ushakov attack on Stickel’s protocol and discuss the application of that generalised attack to all our new protocols

The boomerang attack, introduced by Wagner in 1999, is a cryptanalysis technique against block ciphers based on differential cryptanalysis. In particular it takes into consideration two differentials, one for the upper part of the cipher and one for the lower part, and it exploits the dependency of these two differentials. At Eurocrypt'18, Cid et al. introduced a new tool, called the Boomerang Connectivity Table (BCT) that permits to simplify this analysis. Next, Boura and Canteaut introduced an important parameter for cryptographic S-boxes called boomerang uniformity, that is the maximum value in the BCT. Very recently, the boomerang uniformity of some classes of permutations (in particular quadratic functions) have been studied by Li, Qu, Sun and Li, and by Mesnager, Chunming and Maosheng. In this paper we further study the boomerang uniformity of some non-quadratic differentially 4-uniform functions. In particular, we consider the case of the Bracken-Leander cubic function and three classes of 4-uniform functions constructed by Li, Wang and Yu, obtained from modifying the inverse functions.

At present, the access control schemes in the power grid are centralized. In the centralized system, the data of the network sensor nodes is transmitted by centralized nodes, and the data itself may be illegally tamped with or lost, which can lead to reduced system reliability. For this feature, we apply blockchain technology to the design of access control schemes. In this paper, we propose a blockchain-based access control scheme that is suitable for multiple scenarios in the smart grid. Our access control scheme is based on an identity-based combined encryption, signature and signcryption scheme. In addition, we design a consensus algorithm in the power system for the consortium blockchain architecture to solve the key escrow problem of the untrusted third parties. Our scheme also ensures the confidentiality, integrity, authentication and non-repudiation of the data. Compared with the existing work, our scheme can use the same key pair to encrypt, sign and signcrypt the message, which has lower computation and communication costs in multiple scenarios of smart grids.

Subterranean 2.0 designed by Daemen, Massolino and Rotella is a Round 2 candidate of the NIST Lightweight Cryptography Standardization process. In the official document of Subterranean 2.0, the designers have analyzed the state collisions in unkeyed absorbing by reducing the number of rounds to absorb the message from 2 to 1. However, little cryptanalysis of the authenticated encryption scheme Subterranean-SAE is made. For Subterranean-SAE, the designers introduce 8 blank rounds to separate the controllable input and output, and expect that 8 blank rounds can achieve a sufficient diffusion. Therefore, it is meaningful to investigate the security by reducing the number of blank rounds. Moreover, the designers make no security claim but expect a non-trivial effort to achieve full-state recovery in a nonce-misuse scenario. In this paper, we present the first practical full-state recovery attack in a nonce-misuse scenario with data complexity of $2^{13}$ 32-bit blocks. In addition, in a nonce-respecting scenario and if the number of blank rounds is reduced to 4, we can mount a key-recovery attack with $2^{122}$ calls to the internal permutation of Subterranean-SAE and $2^{69.5}$ 32-bit blocks. A distinguishing attack with $2^{33}$ calls to the internal permutation of Subterranean-SAE and $2^{33}$ 32-bit blocks is achieved as well. Our cryptanalysis does not threaten the security claim for Subterranean-SAE and we hope it can enhance the understanding of Subterranean-SAE.

In recent years, there has been a proliferation of *algebraically structured* Learning With Errors (LWE) variants, including Ring-LWE, Module-LWE, Polynomial-LWE, Order-LWE, and Middle-Product LWE, and a web of reductions to support their hardness, both among these problems themselves and from related worst-case problems on structured lattices. However, these reductions are often difficult to interpret and use, due to the complexity of their parameters and analysis, and most especially their (frequently large) blowup and distortion of the error distributions. In this paper we unify and simplify this line of work. First, we give a general framework that encompasses *all* proposed LWE variants (over commutative base rings), and in particular unifies all prior ``algebraic'' LWE variants defined over number fields. We then use this framework to give much simpler, more general, and tighter reductions from Ring-LWE to other algebraic LWE variants, including Module-LWE, Order-LWE, and Middle-Product LWE. In particular, all of our reductions have easy-to-analyze and frequently small error expansion; in most cases they even leave the error unchanged. A main message of our work is that it is straightforward to use the hardness of the original Ring-LWE problem as a foundation for the hardness of all other algebraic LWE problems defined over number fields, via simple and rather tight reductions.

The Schnorr blind signing protocol allows blind issuing of Schnorr signatures, one of the most widely used signatures. Despite its practical relevance, its security analysis is unsatisfactory. The only known security proof is rather informal and in the combination of the generic group model (GGM) and the random oracle model (ROM) assuming that the ``ROS problem'' is hard. The situation is similar for (Schnorr-)signed ElGamal encryption, a simple CCA2-secure variant of ElGamal. We analyze the security of these schemes in the algebraic group model (AGM), an idealized model closer to the standard model than the GGM. We first prove tight security of Schnorr signatures from the discrete logarithm assumption (DL) in the AGM+ROM. We then give a rigorous proof for blind Schnorr signatures in the AGM+ROM assuming hardness of the one-more discrete logarithm problem and ROS. As ROS can be solved in sub-exponential time using Wagner's algorithm, we propose a simple modification of the signing protocol, which leaves the signatures unchanged. It is therefore compatible with systems that already use Schnorr signatures, such as blockchain protocols. We show that the security of our modified scheme relies on the hardness of a problem related to ROS that appears much harder. Finally, we give tight reductions, again in the AGM+ROM, of the CCA2 security of signed ElGamal encryption to DDH and signed hashed ElGamal key encapsulation to DL.

In order to propagate transactions and blocks, today’s blockchain systems rely on unstructured peer-to-peer overlay networks. In such networks, broadcast is known to be an inefficient operation in terms of message complexity and overhead. In addition to the impact on the system performance, inefficient or delayed block propagation may have severe consequences regarding security and fairness of the consensus layer. Therefore, we introduce Kadcast, a novel peer-to-peer protocol for block propagation in blockchain networks. Kadcast utilizes the well-known structured overlay topology of Kademlia to realize an efficient broadcast operation with tunable overhead. As our protocol is based on UDP, we incorporate forward error correction (FEC) to increase reliability while still maintaining its lightweight protocol architecture. To this end, we build a probabilistic model to analyze Kadcast’s resilience to packet losses as well as random and adversarial node failures. Moreover, we evaluate Kadcast’s block delivery performance, broadcast reliability, efficiency, and security based on advanced network simulations, which confirm the merits of the Kadcast protocol.

We introduce a Quantum Key Recycling (QKR) protocol that needs no classical communication from Alice to Bob. Alice sends only a cipherstate, which consists of qubits that are individually measured by Bob. Bob merely has to respond with an authenticated one-bit accept/reject classical message. Compared to Quantum Key Distribution (QKD), QKR has reduced round complexity. Compared to other qubit-wise QKR protocols, our scheme has far less classical communication. We provide a security proof in the universal composability framework and find that the communication rate is asymptotically the same as for QKD with one-way postprocessing.

Attribute-based encryption with keyword search (ABKS) achieves both fine-grained access control and keyword search. However, in the previous ABKS schemes, the search algorithm requires that each keyword between the target keyword set and the ciphertext keyword set be the same, otherwise the algorithm doesn't output any search result, which is not conducive to use. Moreover, the previous ABKS schemes are vulnerable to what we call a \emph{peer-decryption attack}, that is, the ciphertext may be eavesdropped and decrypted by an adversary who has sufficient authorities but no information about the ciphertext keywords. In this paper, we provide a new system in fog computing, the ciphertext-policy attribute-based encryption with dynamic keyword search (ABDKS). In ABDKS, the search algorithm requires only \emph{one} keyword to be identical between the two keyword sets and outputs the corresponding correlation which reflects the number of the same keywords in those two sets. In addition, our ABDKS is resistant to peer-decryption attack, since the decryption requires not only sufficient authority but also at least one keyword of the ciphertext. Beyond that, the ABDKS shifts most computational overheads from resource constrained users to fog nodes. The security analysis shows that the ABDKS can resist Chosen-Plaintext Attack (CPA) and Chosen-Keyword Attack (CKA).

Counting the Boolean functions having specific cryptographic features is an interesting problem in combinatorics and cryptography. Count of bent functions for more than eight variables is unexplored. In this paper, we propose an upper bound for the count of rotational symmetric bent Boolean functions and characterize its truth table representation from the necessary condition of a rotational symmetric bent Boolean function.

At CRYPTO 2018, Cramer et al. introduced a secret-sharing based protocol called SPD$\mathbb{Z}_{2^k}$ that allows for secure multiparty computation (MPC) in the dishonest majority setting over the ring of integers modulo $2^k$, thus solving a long-standing open question in MPC about secure computation over rings in this setting. In this paper we study this problem in the information-theoretic scenario. More specifically, we ask the following question: Can we obtain information-theoretic MPC protocols that work over rings with comparable efficiency to corresponding protocols over fields? We answer this question in the affirmative by presenting an efficient protocol for robust Secure Multiparty Computation over $\mathbb{Z}/p^{k}\mathbb{Z}$ (for \emph{any} prime $p$ and positive integer $k$) that is perfectly secure against active adversaries corrupting a fraction of at most $1/3$ players, and a robust protocol that is statistically secure against an active adversary corrupting a fraction of at most $1/2$ players.

The foundation of zero-knowledge is the simulator: a weak machine capable of pretending to be a weak verifier talking with all-powerful provers. To achieve this, simulators need some kind of advantage such as the knowledge of a trapdoor. In existing zero-knowledge multi-prover protocols, this advantage is essentially signalling, something that the provers are explicitly forbidden to do. In most cases, this advantage is stronger than necessary as it is possible to define a sense in which simulators need much less to simulate. We define a framework in which we can quantify the simulators’ non-local advantage and exhibit examples of zero-knowledge protocols that are sound against local or entangled provers but that are not sound against no-signalling provers precisely because the no-signalling simulation strategy can be adopted by malicious provers.

This paper presents an efficient algorithm for computing $11^{\mathrm{th}}$-power residue symbols in the cyclotomic field $\mathbb{Q}(\zeta_{11})$, where $\zeta_{11}$ is a primitive $11^{\mathrm{th}}$ root of unity. It extends an earlier algorithm due to Caranay and Scheidler (Int. J. Number Theory, 2010) for the $7^{\mathrm{th}}$-power residue symbol. The new algorithm finds applications in the implementation of certain cryptographic schemes.

Security and safety-critical remote applications such as e-voting, online banking, industrial control systems and medical devices rely upon user interaction that is typically performed through web applications. Trusted path to such remote systems is critical in the presence of an attacker that controls the computer that the user operates. Such an attacker can observe and modify any IO data without being detected by the user or the server. We investigate the security of previous research proposals and observe several drawbacks that make them vulnerable to attacks. Based on these observations we identify novel requirements for secure IO operation in the presence of a compromised host. As a solution, we propose ProtectIOn, a system that ensures IO integrity using a trusted low-TCB device that sits between the attacker-controlled host and the IO devices. ProtectIOn intercepts the display signal and user inputs from the keyboard and mouse, and overlays secure UI on top of the HDMI frames generated by the untrusted host. The guiding design principles of ProtectIOn are that (i) integrity of user input and output cannot be considered separately, (ii) all user input modalities need to be protected simultaneously, and (iii) integrity protection should not rely on error prone user tasks like checking the presence of security indicators. By following these guidelines, ProtectIOn achieves strong protection for IO integrity. We also propose an extension of ProtectIOn for IO confidentiality and implement a plug-and-play prototype and evaluate its performance.

We prove lower bounds on the round complexity of randomized Byzantine agreement (BA) protocols, bounding the halting probability of such protocols after one and two rounds. In particular, we prove that: (1) BA protocols resilient against $n/3$ [resp., $n/4$] corruptions terminate (under attack) at the end of the first round with probability at most $o(1)$ [resp., $1/2+ o(1)$]. (2) BA protocols resilient against a fraction of corruptions greater than $1/4$ terminate at the end of the second round with probability at most $1-\Theta(1)$. (3) For a large class of protocols (including all BA protocols used in practice) and under a plausible combinatorial conjecture, BA protocols resilient against a fraction of corruptions greater than $1/3$ [resp., $1/4$] terminate at the end of the second round with probability at most $o(1)$ [resp., $1/2 + o(1)$]. The above bounds hold even when the parties use a trusted setup phase, e.g., a public-key infrastructure (PKI). The third bound essentially matches the recent protocol of Micali (ITCS'17) that tolerates up to $n/3$ corruptions and terminates at the end of the third round with constant probability.

Lilliput-AE is a tweakable block cipher submitted as a candidate to the NIST lightweight cryptography standardization process. It is based upon the lightweight block cipher Lilliput, whose cryptanalysis so far suggests that it has a large security margin. In this note we present an extremely efficient forgery attack on Lilliput-AE: Given a single arbitrary message of length about 2^36 bytes, we can instantly produce another valid message that leads to the same tag, along with the corresponding ciphertext. The attack uses a weakness in the tweakey schedule of Lilliput-AE which leads to the existence of a related tweak differential characteristic with probability 1 in the underlying block cipher. The weakness we exploit, which does not exist in Lilliput, demonstrates the potential security risk in using a very simple tweakey schedule in which the same part of the key/tweak is re-used in every round, even when round constants are employed to prevent slide attacks. Following this attack, the Lilliput-AE submission to NIST was tweaked.

Semi-invasive fault injection attacks are powerful techniques well-known by attackers and secure embedded system designers. When performing such attacks, the selection of the fault injection parameters is of utmost importance and usually based on the experience of the attacker. Surprisingly, there exists no formal and general approach to characterize the target behavior under attack. In this work, we present a novel methodology to perform a fast characterization of the fault injection impact on a target, depending on the possible attack parameters. We experimentally show our methodology to be a successful one when targeting different algorithms such as DES and AES encryption and then extend to the full characterization with the help of deep learning. Finally, we show how the characterization results are transferable between different targets.

SipHash is a family of ARX-based MAC algorithms optimized for short inputs. Already, a lot of implementations and applications for SipHash have been proposed, whereas the cryptanalysis of SipHash still lags behind. In this paper, we study the property of truncated differential in SipHash and find out the output bits with the most imbalanced differential biases. Making use of these results, we construct distinguishers with practical complexity $2^{10}$ for SipHash-2-1 and $2^{36}$ for SipHash-2-2. We further reveal the relations between the value of output bias and the difference after first modular addition step, which is directly determined by corresponding key bits. Based on these relations, we propose a key recovery method for SipHash-2-1 that can obtain a nonuniform distribution of the 128-bit key through several bias tests. It is found that the highest probability can reach $2^{-41}$ and the nonuniform distribution can lead to a $2^{29}$ gain of search cost in average.

We review several solutions for the Byzantine Fault Tolerance (BFT) problem and discuss some aspects that are frequently overlooked by existing literatures. For example, PBFT and HotStuff BFT protocols (HotStuff has been adopted by Facebook Libra) require a reliable broadcast primitive. We show that if the broadcast primitive is not reliable then the PBFT and HotStuff BFT protocols could not achieve the liveness property (that is, the system will never reach an agreement on a proposal). Though these BFT protocols have been developed for partial synchronous networks, we show that they cannot achieve consensus in partial synchronous networks since the participants do not know what is the Global Stabilization Time (GST) and broadcast channels before GST are defined to be unreliable (e.g., DoS attacks on certain participants). Thus it is important for developers to be aware of these issues when developing applications (such as blockchains) using these BFT protocols.

Secure Multi-party Computation (MPC) with small population and honest majority has drawn focus specifically due to customization in techniques and resulting efficiency that the constructions can offer. In this work, we investigate a wide range of security notions in the five-party setting, tolerating two active corruptions. Being constant-round, our protocols are best suited for real-time, high latency networks such as the Internet. In a minimal setting of pairwise-private channels, we present efficient instantiations with unanimous abort (where either all honest parties obtain the output or none of them do) and fairness (where the adversary obtains its output only if all honest parties also receive it). With the presence of an additional broadcast channel (known to be necessary), we present a construction with guaranteed output delivery (where any adversarial behaviour cannot prevent the honest parties from receiving the output). The broadcast communication is minimal and independent of circuit size. In terms of performance (communication and run time), our protocols incur minimal overhead over the best known protocol of Chandran et al. (ACM CCS 2016) that achieves the least security notion of selective abort. Further, our protocols for fairness and unanimous abort can be extended to n-parties with at most $\sqrt{n}$ corruptions, similar to Chandran et al. Going beyond the most popular honest-majority setting of three parties with one corruption, our results demonstrate feasibility of attaining stronger security notions at an expense not too far from the least desired security of selective abort.

We show that Legendre PRF, recently suggested as an MPC-friendly primitive in a prime field $Z_p$, admits key recovery attacks of complexity $O(\sqrt{p})$ rather than previously assumed $O(p)$. We also demonstrate new attacks on high-degree versions of this PRF, improving on the previous results by Russell and Shparlinski.

One way of attacking ECDSA with wNAF implementation for the scalar multiplication is to perform a side-channel analysis to collect information, then use a lattice based method to recover the secret key. In this paper, we reinvestigate the construction of the lattice used in one of these methods, the Extended Hidden Number Problem (EHNP). We find the secret key with only 3 signatures, thus reaching the theoretical bound given by Fan, Wang and Cheng, whereas best previous methods required at least 4 signatures in practice. Our attack is more efficient than previous attacks, in particular compared to times reported by Fan et al. at CCS 2016 and for most cases, has better probability of success. To obtain such results, we perform a detailed analysis of the parameters used in the attack and introduce a preprocessing method which reduces by a factor up to 7 the overall time to recover the secret key for some parameters. We perform an error resilience analysis which has never been done before in the setup of EHNP. Our construction is still able to find the secret key with a small amount of erroneous traces, up to 2% of false digits, and 4% with a specific type of error. We also investigate Coppersmith's methods as a potential alternative to EHNP and explain why, to the best of our knowledge, EHNP goes beyond the limitations of Coppersmith's methods.

Machine learning is nowadays supplanting or extending human expertise in many domains ranging from board games to text translation. Correspondingly, the use of such tools is also on the rise in computer security. Alongside CHES 2018, a side channel challenge was organised under the theme of ’Deep Learning vs Classical SCA’ to test whether Deep Learning is presently widely used in the SCA community and whether it yields competitive results. The competition had 58 participants, it ran for three months, and a quantity of 35GB of data was used as a test sample. This paper presents the solutions of the teams that captured a flag and then discusses the results. While deep learning was used by neither team, other machine learning methods turned out to be very useful. The first contribution is a snapshot in time of the expertise in the community and shows a clear bias towards classic SCA. The second contribution is the presentation of novel techniques for key extraction for the challenges proposed and a reference for a black-box evaluation of crypto primitives by experts in the field. The third contribution is a baseline which can be used to further improve upon. Based on the results of this competition, we conclude that human expertise remains very important in the design of successful SCA attacks and machine learning can be a useful tool. Section 2,3 and 4 of this report have been directly contributed by the winning teams; as a consequence, section 3 is essentially identical to the previous eprint https://eprint.iacr.org/2019/094/20190131:230649 [8] authored by A. Gohr, S. Jacob and W. Schindler.

After the work of Impagliazzo and Rudich (STOC, 1989), the black box framework has become one of the main research domain of cryptography. However black box techniques say nothing about non-black box techniques such as making use of zero-knowledge proofs. Brakerski et al. introduced a new black box framework named augmented black box framework, in which they gave a zero-knowledge proof oracle in addition to a base primitive oracle (TCC, 2011). They showed a construction of a non-interactive zero knowledge proof system based on a witness indistinguishable proof system oracle. They presented augmented black box construction of chosen ciphertext secure public key encryption scheme based on chosen plaintext secure public key encryption scheme and augmented black box separation between one-way function and key agreement. In this paper we simplify the work of Brakerski et al. by introducing a proof system oracle without witness indistinguishability, named coin-free proof system oracle, that aims to give the same construction and separation results of previous work. As a result, the augmented black box framework becomes easier to handle. Since our oracle is not witness indistinguishable, our result encompasses the result of previous work.

Once algorithms for quantum-resistant key exchange and digital signature schemes are selected by standards bodies, adoption of post-quantum cryptography will depend on progress in integrating those algorithms into standards for communication protocols and other parts of the IT infrastructure. In this paper, we explore how two major Internet security protocols, the Transport Layer Security (TLS) and Secure Shell (SSH) protocols, can be adapted to use post-quantum cryptography. First, we examine various design considerations for integrating post-quantum and hybrid key exchange and authentication into communications protocols generally, and in TLS and SSH specifically. These include issues such as how to negotiate the use of multiple algorithms for hybrid cryptography, how to combine multiple keys, and more. Subsequently, we report on several implementations of post-quantum and hybrid key exchange in TLS 1.2, TLS 1.3, and SSHv2. We also report on work to add hybrid authentication in TLS 1.3 and SSHv2. These integrations are in Amazon s2n and forks of OpenSSL and OpenSSH; the latter two rely on the liboqs library from the Open Quantum Safe project.

In this paper we propose Bitcontracts, a novel solution that enables secure and efficient execution of generic smart contracts on top of unmodified legacy cryptocurrencies like Bitcoin that do not support contracts natively. The starting point of our solution is an off-chain execution model, where the contract's issuers appoints a set of service providers to execute the contract's code. The contract's execution results are accepted if a quorum of service providers reports the same result and clients are free to choose which such contracts they trust and use. The main technical contribution of this paper is how to realize such a trust model securely and efficiently without modifying the underlying blockchain. We also identify a set of generic properties that a blockchain system must support so that expressive smart contracts can be added safely, and analyze popular existing blockchains based on these criteria.

At the FSE conference of ToSC 2018, Kranz et al. presented their results on shortest linear programs for the linear layers of several well known block ciphers in literature. Shortest linear programs are essentially the minimum number of 2-input xor gates required to completely describe a linear system of equations. In the above paper the authors showed that the commonly used metrics like d-xor/s-xor count that are used to judge the ``lightweightedness'' do not represent the minimum number of xor gates required to describe a given MDS matrix. In fact they used heuristic based algorithms of Boyar/Peralta and Paar to find implementations of MDS matrices with even fewer xor gates than was previously known. They proved that the AES mixcolumn matrix can be implemented with as little as 97 xor gates. In this paper we show that the values reported in the above paper are not optimal. By suitably including random bits in the instances of the above algorithms we can achieve implementations of almost all matrices with lesser number of gates than were reported in the above paper. As a result we report an implementation of the AES mixcolumn matrix that uses only 95 xor gates. In the second part of the paper, we observe that most standard cell libraries contain both 2 and 3-input xor gates, with the silicon area of the 3-input xor gate being smaller than the sum of the areas of two 2-input xor gates. Hence when linear circuits are synthesized by logic compilers (with specific instructions to optimize for area), most of them would return a solution circuit containing both 2 and 3-input xor gates. Thus from a practical point of view, reducing circuit size in presence of these gates is no longer equivalent to solving the shortest linear program. In this paper we show that by adopting a graph based heuristic it is possible to convert a circuit constructed with 2-input xor gates to another functionally equivalent circuit that utilizes both 2 and 3-input xor gates and occupies less hardware area. As a result we obtain more lightweight implementations of all the matrices listed in the ToSC paper.

We introduce the WIDESEAS protocol for lattice-based Private Information Retrieval (PIR), and we give performance numbers for its recent implementation in the EncryptedQuery open-source PIR software. This protocol uses the fully homomorphic Brakerski--Fan--Vercauteren (BFV) encryption scheme, as opposed to the Paillier scheme, which is used in all earlier versions of EncryptedQuery. We show that the homomorphic capabilities of BFV result in smaller query sizes (due to a query-shrinking technique based on batching and ciphertext multiplication), higher response generation rates (due to using relinearization to keep ciphertexts small; due to caching certain products of query elements in the NTT domain; due to using the distributive law to achieve a quadratic reduction in the total number of ciphertext multiplications; due to using lazy reduction to speed up modular multiplies; and, due to exploiting properties of inverse NTTs over periodic data, and forward NTTs over sparse data, for the purpose of accelerating plain multiplications), and comparable response sizes (due to using modulus switching to discard redundant ciphertext information prior to transmitting the response). For instance, running a single thread (with Turbo Boost disabled) on a MacBook Pro equipped with a 2.8 GHz Intel core i7, and using a $20$-bit hash and a $2^{15}$-byte data chunk size (which allows us to search for a single targeted selector), our implementation can (i) generate a query of size $64\ \mathrm{MiB}$ in around $0.41\ {\rm seconds,}$ (ii) process a query against a $1\ \mathrm{TiB}$ database (comprised of $2^{20}$-many $1\ \mathrm{MiB}$ records) at a rate of $23.67\ \mathrm{MiB/s}$ (which is at least two orders of magnitude faster than the Paillier-based version of EncryptedQuery), and (iii) generate a response of size $4\ \mathrm{MiB}$ in around $0.51\ \mathrm{days}{\rm .}$ We expect a speed up on server class machines. Our implementation uses the Microsoft SEAL library along with a small amount of custom code.

To quantify security levels in a post-quantum scenario, it is common to use the quantum resources needed to attack AES as a reference value. Specifically, in NIST’s ongoing post-quantum standardization effort, different security categories are defined that reflect the quantum resources needed to attack AES-128, AES-192, and AES-256. This paper presents a quantum circuit to implement the S-box of AES. Leveraging also an improved implementation of the key expansion, we identify new quantum circuits for all three AES key lengths. For AES-128, the number of Toffoli gates can be reduced by more than 88% compared to Almazrooie et al.'s and Grassl et al.'s estimates, while simultaneously reducing the number of qubits. Our circuits can be used to simplify a Grover-based key search for AES.

We analyse three game-based definitions of receipt-freeness; uncovering soundness issues with two of the definitions and completeness issues with all three. Hence, two of the definitions are too weak, i.e., satisfiable by voting schemes that are not intuitively receipt-free. More precisely, those schemes need not even satisfy ballot secrecy. Consequently, the definitions are satisfiable by schemes that reveal how voters' vote. Moreover, we find that each definition is limited in scope. Beyond soundness and completeness issues, we show that each definition captures a different attacker model and we examine some of those differences.

In this paper, we analyze the security of AES in the case in which the whitening key is a weak key. After a systematization of the classes of weak-keys of AES, we perform an extensive analysis of weak-key distinguishers (in the single-key setting) for AES instantiated with the original key-schedule and with the new key-schedule proposed at ToSC/FSE'18 (which is faster than the standard key schedule and ensures a higher number of active S-Boxes). As one of the main results, we show that (almost) all the secret-key distinguishers for round-reduced AES currently present in the literature can be set up for a higher number of rounds of AES if the whitening key is a weak-key. Using these results as starting point, we describe a property for 9-round AES-128 and 12-round AES-256 in the chosen-key setting with complexity 264 without requiring related keys. These new chosen-key distinguishers -- set up by exploiting a variant of the multiple-of-8 property introduced at Eurocrypt'17 -- improve all the AES chosen-key distinguishers in the single-key setting. The entire analysis has been performed using a new framework that we introduce here -- called "weak-key subspace trails", which is obtained by combining invariant subspaces (Crypto'11) and subspace trails (FSE'17) into a new, more powerful, attack. Weak-key subspace trails are defined by extending the invariant subspace approach to allow for different subspaces in every round, something that so far only the subspace trail approach and a generalization for invariant subspace and invariant set attacks (Asiacrypt'18) were able to do. For an easier detection, we also provide an algorithm which finds these weak-key subspace trails.

Recently, in IEEE Transactions on Industrial Informatics, Fan et al. proposed a lightweight RFID protocol which has been suggested to be employed for protecting the Medical Privacy in an IoT system. However, the protocol has trivial flaws, as it is shown recently by Aghili et al., in Future Generation Computer Systems. Aghili et al. also proposed an improved version of the protocol, based on the similar designing paradigm, called SecLAP. Although the protocol's designers claimed full security against all attacks, we show that the proposed protocol has serious security flaws, by presenting traceability and passive secret disclosure attacks against this protocol. More precisely, we present passive partial secret disclosure attack with the complexity of eavesdropping one session of the protocol and success probability of `1'. The disclosed parameters can be used to trace the tag/reader in any later session which compromises the tag/reader privacy. In addition, we present a passive full secret disclosure attack against SecLAP which can disclose $2n$-bit secret key, $n$-bit $TID$ and $n$-bit $RID$ with the computational complexity of $27n^7$. In addition, we show that, as it is expected, Fan et al.'s protocol has security flaws in random oracle model, where the adversary's advantage after $q$ queries to distinguish the protocol from a random oracle is $1- 2^{-q} $. We also evaluate the security of SecLAP in the random oracle model and show that it is as insecure as its predecessor.

Internet of Things (IoT) has various applications such as healthcare, supply chain, agriculture, etc. Using the Internet of Vehicles(IoV) to control traffic of the cities is one of the IoT applications to construct smart cities. Recently Fan et al. proposed an authentication protocol to provide security of the IoV networks. They claimed that their scheme is secure and can resist against various known attacks. In this paper, we analyze more deeply the proposed scheme and show that their scheme is vulnerable against disclosure and desynchronization attacks. In disclosure attack, we disclose unique identification of the tag $ID$, secret key $S$, encryption matrix $M_2$ and half rows of encryption matrix $M_1$. Furthermore, we proposed an improved authentication scheme based on Maximum Distance Separable(MDS) matrices that is resistance against various attacks while maintaining low computational cost.

IoT systems are vulnerable to various cyber attacks as they form a subset of the In- ternet. Insider attacks find more significance since many devices are configured to access the Internet without intrusion detection systems or firewalls in place. The current work focuses on three insider attacks, namely, blackhole attack, sinkhole attack and wormhole attack. A distrib - uted trust based intrusion detection system is proposed to detect these attacks. The trust scores are compared with those existing in immutable distributed ledger and used to arrive at a deci- sion to include or exclude a node.

Recently Bar-On et al. proposed the DLCT for a tighter analysis of probabilities for differential-linear distinguishers. We extend the analysis of the DLCT, and gain new insights about this notion. The DLCT entries correspond to the autocorrelation spectrum of the component functions and thus the DLCT is nothing else as the ACT. We note that the ACT spectrum is invariant under some equivalence relations. Interestingly the ACT spectrum is not invariant under inversion (and thus not under CCZ equivalence), implying that it might be beneficial to look at the decryption for a differential-linear cryptanalysis. Furthermore, while for Boolean functions a lower bound for the maximal absolute autocorrelation, the absolute indicator, is not known, the case for vectorial Boolean functions is different. Here, we prove that for any vectorial Boolean function, its absolute indicator is lower bounded by $2^{n/2}$. Eventually, for APN functions we show a connection of the absolute indicator to the linearity of balanced Boolean functions, and exhibit APN permutations with absolute indicator bounded by $2^{(n+1)/2}$.

In this article, we propose new heuristics for minimizing the amount of XOR gates required to compute a system of linear equations in GF(2). We first revisit the well known Boyar-Peralta strategy and argue that a proper randomization process during the selection phases can lead to great improvements. We then propose new selection criteria and explain their rationale. Our new methods outperform state-of-the-art algorithms such as Paar or Boyar-Peralta (or open synthesis tools such as Yosys) when tested on random matrices with various densities. They can be applied on matrices of reasonable sizes (up to about 32 x 32). Notably, we provide a new implementation record for the matrix underlying the MixColumns function of the AES block cipher, requiring only 94 XORs.

Functional encryption (FE) that bases on user attributes has many useful practical applications. For example, a company may only authorize department heads of other sections to query the average sale figures of the sales department from the encrypted sales amounts of all sales. However, FE schemes that can solve this problem are based on new, but not well-studied assumptions (such as indistinguishable obfuscation or multilinear maps). It is not clear if these FE schemes are secure. In this paper, we develop the first functional encryption scheme (ABFE) from simple and well-studied assumptions that can authorize a user base on the user's attributes to obtain a functional value of the encrypted data.

Rank metric is a very promising research direction for code-based cryptography. In fact, thanks to the high complexity of generic decoding attacks against codes in this metric, it is possible to easily select parameters that yield very small data sizes. In this paper we analyze cryptosystems based on Low-Rank Parity-Check (LRPC) codes, one of the classes of codes that are efficiently decodable in the rank metric. We show how to exploit the decoding failure rate, which is an inherent feature of these codes, to devise a reaction attack aimed at recovering the private key. As a case study, we cryptanalyze the recent McNie submission to NIST’s Post-Quantum Standardization process. Additionally, we provide details of a simple implementation to validate our approach.

This paper presents pqm4 – a testing and benchmarking framework for the ARM Cortex-M4. It makes use of a widely available discovery board with 196 KiB of memory and 1 MiB flash ROM. It currently includes 10 key encapsulation mechanisms and 5 signature schemes of the NIST PQC competition. For the remaining 11 schemes, the available implementations do require more than the available memory or they depend on external libraries which makes them arguably unsuitable for embedded devices.

CSIDH is an isogeny-based key exchange protocol proposed by Castryck \textit{et al.} in 2018. It is based on the ideal class group action on $\mathbb{F}_p$-isomorphism classes of Montgomery curves. The original CSIDH algorithm requires a calculation over $\mathbb{F}_p$ by representing points as $x$-coordinate over Montgomery curves. There is a special coordinate on Edwards curves (the $w$-coordinate) to calculate group operations and isogenies. If we try to calculate the class group action on Edwards curves by using the $w$-coordinate in a similar way on Montgomery curves, we have to consider points defined over $\mathbb{F}_{p^4}$. Therefore, it is not a trivial task to calculate the class group action on Edwards curves with $w$-coordinates over only $\mathbb{F}_p$. In this paper, we prove some theorems about the properties of Edwards curves. By these theorems, we construct the new CSIDH algorithm on Edwards curves with $w$-coordinates over $\mathbb{F}_p$. This algorithm is as fast as (or a little bit faster than) the algorithm proposed by Meyer and Reith. This paper is an extend version of [25]. We added the construction of a technique similar to Elligator on Edwards curves. This technique contributes the efficiency of the constant-time CSIDH algorithm. We also added the construction of new formulas to compute isogenies in $\tilde{O}(\sqrt{\ell})$ times on Edwards curves. It is based on formulas on Montgomery curves proposed by Bernstein \textit{et al.} ($\sqrt{\vphantom{2}}$élu's formulas). In our analysis, these formulas on Edwards curves is a little bit faster than those on Montgomery curves.

Poly1305 is a polynomial hash function designed by Bernstein in 2005. Presently, it is part of several major platforms including the Transport Layer Security protocol. Vectorised implementation of Poly1305 has been proposed by Goll and Gueron in 2015. We provide some simple algorithmic improvements to the Goll-Gueron vectorisation strategy. Implementation of the modified strategy on modern Intel processors shows marked improvements in speed for short messages.

Recently, an article by Felke appeared in Cryptography and Communications discussing the security of biquadratic C* and a further generalization, k-ary C*. The article derives lower bounds for the complexity of an algebraic attack, directly inverting the public key, under an assumption that the first-fall degree is a good approximation of the solving degree, an assumption that the paper notes requires ``greater justification and clarification." In this work, we provide a practical attack breaking all k-ary C* schemes. The attack is based on differential techniques and requires nothing but the ability to evaluate the public key and solve linear systems. In particular, the attack breaks the parameters provided in CryptoChallenge11 by constructing and solving linear systems of moderate size in a few minutes.

The Tire Pressure Monitoring System (TPMS) is used to monitor the pressure of the tires and to inform the driver of it. This equipment is mandatory for vehicles in US and EU. To ensure the security of TPMS, it is important to reduce the cost of the cryptographic mechanisms implemented in resourced-constrained devices. To address this problem, previous work has proposed countermeasures employing lightweight block ciphers such as PRESENT, SPECK, or KATAN. However, it is not clear to us that any of these works have addressed the issues of software optimization that considers TPMS-packet protection as well as session key updates for architectures consisting of the vehicle TPMS ECU and four low-cost TPM sensors equipped with the tires. In this paper, we propose to application of the ISO/IEC 29192-5 lightweight hash function Lesamnta-LW to address this issue. Our approach is to apply the known method of converting Lesamnta-LW to multiple independent pseudo-random functions (PRFs) in TPMS. In our case, we generate five PRFs this way and then use one PRF for MAC-generation and four for key derivation. Although we follow the NIST SP 800-108 framework of converting PRFs to key derivation functions, we confirm the significant advantage of Lesamnta-LW-based PRFs over HMAC-SHA-256 by evaluating the performance on AVR 8-bit micro-controllers, on which we consider simulating TPMS sensors. We expect that our method to achieve multiple-purposes with a single cryptographic primitive will help to reduce the total implementation cost required for TPMS security.

We give the first construction of statistical Zaps. Our construction satisfies computational soundness and relies on the quasi-polynomial hardness of learning with errors assumption.

Clock synchronization allows parties to establish a common notion of global time by leveraging a weaker synchrony assumption, i.e., local clocks with approximately the same speed. The problem has long been a prominent goal for fault-tolerant distributed computing with a number of ingenious solutions in various settings. However, despite intensive investigation, the existing solutions do not apply to common blockchain protocols, which are designed to tolerate variable---and potentially adversarial---participation patterns, e.g., sleepiness and dynamic availability. Furthermore, because such blockchain protocols rely on freshly joining (or re-joining) parties to have a common notion of time, e.g., a global clock which allows knowledge of the current protocol round, it is not clear if or how they can operate without such a strong synchrony assumption. In this work, we show how to solve the global synchronization problem by leveraging proof of stake (PoS). Concretely, we design and analyze a PoS blockchain protocol in the above dynamic-participation setting, that does not require a global clock but merely assumes that parties have local clocks advancing at approximately the same speed. Central to our construction is a novel synchronization mechanism that can be thought as the blockchain-era analogue of classical synchronizers: It enables joining parties---even if upon joining their local time is off by an arbitrary amount---to quickly calibrate their local clocks so that they all show approximately the same time. As a direct implication of our blockchain construction---since the blockchain can be joined and observed by any interested party---we obtain a permissionless PoS implementation of a global clock that may be used by higher level protocols that need access to global time.

CSIDH is a recent quantum-resistant primitive based on the difficulty of finding isogeny paths between supersingular curves. Recently, two constant-time versions of CSIDH have been proposed: first by Meyer, Campos and Reith, and then by Onuki, Aikawa, Yamazaki and Takagi. While both offer protection against timing attacks and simple power consumption analysis, they are vulnerable to more powerful attacks such as fault injections. In this work, we identify and repair two oversights in these algorithms that compromised their constant-time character. By exploiting Edwards arithmetic and optimal addition chains, we produce the fastest constant-time version of CSIDH to date. We then consider the stronger attack scenario of fault injection, which is relevant for the security of CSIDH static keys in embedded hardware. We propose and evaluate a dummy-free CSIDH algorithm. While these CSIDH variants are slower, their performance is still within a small constant factor of less-protected variants. Finally, we discuss derandomized CSIDH algorithms.

We explore two main issues in the performance of Secure Two- Party Computation (2PC): (1) interaction of 2PC with the transport layer and (2) evaluation of 2PC implementations. Transport layer: Although significantly improved, the performance of 2PC is still prohibitive for practical systems. Contrary to the common belief that bandwidth is the remaining bottleneck for 2PC implementation, we show that the network is under-utilised due to the use of standard TCP sockets. Nevertheless, using other sockets is a nontrivial task: the developers of secure computation need to integrate them into the operating systems, which is challenging even for systems experts. To resolve this issue, and break the efficiency barrier of 2PC, we design and develop a framework, we call Transputation, which automates the integration of transport layer sockets into 2PC implementations. The goal of Transputation is to enable developers of 2PC protocols to easily identify and use the optimal transport layer protocol for the given computation task and network conditions and hence to improve performance of secure computation. We integrated selected transport layer protocols into Transputation and evaluated the performance for a number of computational tasks. As a highlight, even a general purpose transport layer protocol, such as SABUL, improves the run-time of 2PC over TCP on EU-Australia connection for circuits with $ > 10^6 $ Boolean gates by a factor of $ 8 $. Evaluations of 2PC: Evaluations of 2PC implementations do not reflect performance in real networks since they are typically done on simulated environments and even more often on a single host. To address this issue, we provide a testbed platform for evaluation of 2PC implementations in real life settings on the Internet.

Smart contracts are programmable, decentralized and transparent financial applications. Because smart contract platforms typically support Turing-complete programming languages, such systems are often said to enable arbitrary applications. However, the current permissionless smart contract systems impose heavy restrictions on the types of computations that can be implemented. For example, the globally-replicated and sequential execution model of Ethereum requires low gas limits that make many computations infeasible. In this paper, we propose a novel system called ACE whose main goal is to enable more complex smart contracts on permissionless blockchains. ACE is based on an off-chain execution model where the contract issuers appoint a set of service providers to execute the contract code independent from the consensus layer. The primary advantage of ACE over previous solutions is that it allows one contract to safely call another contract that is executed by a different set of service providers. Thus, ACE is the first solution to enable off-chain execution of interactive smart contracts with flexible trust assumptions. Our evaluation shows that ACE enables several orders of magnitude more complex smart contracts than standard Ethereum.

Succinct non-interactive arguments (SNARGs) are highly efficient certificates of membership in non-deterministic languages. Constructions of SNARGs in the random oracle model are widely believed to be post-quantum secure, provided the oracle is instantiated with a suitable post-quantum hash function. No formal evidence, however, supports this belief. In this work we provide the first such evidence by proving that the SNARG construction of Micali is unconditionally secure in the *quantum* random oracle model. We also prove that, analogously to the classical case, the SNARG inherits the zero knowledge and proof of knowledge properties of the PCP underlying the Micali construction. We thus obtain the first zero knowledge SNARG of knowledge (zkSNARK) that is secure in the quantum random oracle model. Our main tool is a new lifting lemma that shows how, for a rich class of oracle games, we can *generically* deduce security against quantum attackers by bounding a natural classical property of these games. This means that in order to prove our theorem we only need to establish *classical* properties about the Micali construction. This approach not only lets us prove post-quantum security but also enables us to prove explicit bounds that are tight up to small factors. We additionally use our techniques to prove that SNARGs based on interactive oracle proofs (IOPs) with round-by-round soundness are unconditionally secure in the quantum random oracle model. This result establishes the post-quantum security of many SNARGs of practical interest.

In this short report we present a short linear program for AES MixColumn with 92 XOR gates and depth 6.

This paper studies information-theoretically secure multiparty computation (MPC) over rings $\Z/p^{\ell}\Z$. In the work of [ACD+, TCC'19], a protocol based on the Shamir secret sharing over $\Z/p^{\ell}\Z$ was presented. As in the field case, its limitation is that the share size grows as the number of players increases. Then several MPC protocols were developed in [ACD+, Asiacrypt'20] to overcome this limitation. However, (i) their offline multiplication gate has super-linear communication complexity in the number of players; (ii) the share size is doubled for the most important case, namely over $\Z/2^{\ell}\Z$ due to infeasible lifting of self-orthogonal codes from fields to rings; (iii) most importantly, the BGW model could not be applied via the secret sharing given in [Asiacrypt'20] due to lack of strong multiplication. In this paper we overcome all the drawbacks mentioned above. Of independent interest, we establish an arithmetic secret sharing with strong multiplication, which is the most important primitive in the BGW model. Of independent interest, the new multiplicative triples check, introduced to solve (i), compares to [GSZ, Crypto'20] in that it has constant latency and a different complexity trade-off, both in the particular case of finite fields and when lifted over rings $\Z/p^{\ell}\Z$. Finally, we lift Reverse Multiplication Friendly Embeddings (RMFE) from fields to rings, with same (linear) complexity. Note that RMFE has become a standard amortization technique for communication complexity in MPC in the regime over many instances of the same circuit, as in [CCXY, Crypto'18] and [DLN, Crypto'19]. We can thus compile existing MPC protocols over fields, including [PS, EC'21], into ones over rings $\Z/2^{\ell}\Z$ with same complexities. To obtain our theoretical results, we use the existence of lifts of curves over rings, then use the known results stating that Riemann-Roch spaces are free modules. To make our scheme practical, we start from good algebraic geometry codes over finite fields obtained from existing computational techniques. Then we present, and implement, an efficient algorithm to Hensel-lift the generating matrix of the code, such that the multiplicative conditions are preserved over rings. On the other hand, a random lifting of codes over rings does not preserve multiplicativity in general. Finally we provide efficient methods for sharing and reconstruction over rings.

There is a major interest in designing RFID schemes based on symmetric-key cryptography and ensuring efficient tag identification. These requirements taken together often lead to a decrease in the degree of privacy provided by the scheme. This issue, as we know, has been treated in an ad-hoc manner so far. In this paper, we introduce the class of stateful RFID schemes with constant tag identifiers, that ensure tag identification in no more than logarithmic time. In order to study their privacy, we propose an appropriate general model obtained by constraining Vaudenay's model. We then propose two symmetric-key cryptography based RFID schemes in this class that achieve weak and destructive privacy, respectively, in addition to mutual authentication. We also discuss on the degree of privacy provided by other schemes proposed in the literature, that fall in this class.

We consider the problem of outsourcing computation on data authenticated by different users. Our aim is to describe and implement the simplest possible solution to provide data integrity in cloud-based scenarios. Concretely, our multi-key linearly homomorphic signature scheme (mklhs) allows users to upload signed data on a server, and at any later point in time any third party can query the server to compute a linear combination of data authenticated by different users and check the correctness of the returned result. Our construction generalizes Boneh et al.'s linearly homomorphic signature scheme (PKC'09) to the multi-key setting and relies on basic tools of pairing-based cryptography. Compared to existing multi-key homomorphic signature schemes, our mklhs is a conceptually simple and elegant direct construction, which trades-off privacy for efficiency. The simplicity of our approach leads us to a very efficient construction that enjoys significantly shorter signatures and higher performance than previous proposals. Finally, we implement mklhs using two different pairing-friendly curves at the 128-bit security level, a Barreto-Lynn-Scott curve and a Barreto-Naehrig curve. Our benchmarks illustrate interesting performance trade-offs between these parameters, involving the cost of exponentiation and hashing in pairing groups. We provide a discussion on such trade-offs that can be useful to other implementers of pairing-based protocols.

Bitslicing is a programming technique that offers several attractive features, such as timing attack resistance, high amortized performance in batch computation, and architecture independence. On the symmetric crypto side, this technique sees wide real-world deployment, in particular for block ciphers with naturally parallel modes. However, the asymmetric side lags in application, seemingly due to the rigidity of the batch computation requirement. In this paper, we build on existing bitsliced binary field arithmetic results to develop a tool that optimizes performance of binary fields at any size on a given architecture. We then provide an ECC layer, with support for arbitrary binary curves. Finally, we integrate into our novel dynamic OpenSSL engine, transparently exposing the batch results to the OpenSSL library and linking applications to achieve significant performance and security gains for key pair generation, ECDSA signing, and (half of) ECDH across a wide range of curves, both standardized and non-standard.

Collision side-channel attacks are efficient attacks against cryptographic implementations, however, optimal collision side-channel attacks and how to compute them efficiently is an open question. In this paper, we show that collision side-channel attacks can be derived using the maximum likelihood principle when the distribution of the values of the leakage function is known. This allows us to exhibit the optimal collision side-channel attack and its efficient computation. Finally, we are able to compute an upper bound for the success rate of the optimal post-processing strategy, and we show that our method and the optimal strategy have success rates close to each other. Attackers can benefit from our method as we present an efficient collision side-channel attack. Evaluators can benefit from our method as we present a tight upper bound for the success rate of the optimal strategy.

Blockchains such as the bitcoin blockchain depend on reaching a global consensus on the distributed ledger; therefore, they suffer from well know scalability problems. This paper proposes an algorithm that avoids double-spending in the short term with just O(√n) messages instead of O(n); each node receiving money off-chain performs the due diligence of consulting k√n random nodes to check if any of them is aware of double-spending. Two nodes receiving double-spent money will in this way consult at least one common node with very high probability, due to the ‘birthday paradox’, and any common honest node consulted will detect the fraud. Since the velocity of money in the real world has coins circulating through at most a few wallets per day, the size of the due diligence communication is small in the short term. This `k-root-n’ algorithm is suitable for an environment with synchronous or asynchronous (but with fairly low latency) communication and with Byzantine faults. The presented k-root-n algorithm should be practical to avoid double-spending with arbitrarily high probability, while feasibly coping with the throughput of all world commerce. It is resistant to Sybil attacks even beyond 50% of nodes. In the long term, the k-root-n algorithm is less efficient. Therefore, it should preferably be used as a complement, and not a replacement, to a global distributed ledger technology.

Modular multiplication is one of the most compute-intensive arithmetic operations. Most public-key cryptosytems utilize modular multiplications of integers of various lengths, depending on security requirements. Efficient algorithms and implementations are required to realize a practical public-key cryptosystem. Different parameters, such as area, power and time, can be optimized for different implementation requirements. Low latency was not as important as high throughput requirement for modular multiplication implementations before. However, with recent work on Verifiable Delay Functions (VDFs), a necessity for lowest possible latency for modular multiplication implementations emerged. VDFs are designed to take a prescribed time to realize the underlying computation that can be publicly verified. VDF constructions are required to utilize inherently sequential arithmetic operations. Efficient VDF constructions have been proposed recently, based on time-lock puzzles constructed by Rivest, Shamir and Wagner. An exponentiation operation in an RSA group needs to be realized for these VDF constructions. For these VDF constructions to be practical, low-latency modular multiplication algorithms and implementations are required. In this paper, a modular multiplication algorithm suitable for low-latency circuit implementations is proposed and an FPGA-optimized variant of this algorithm is presented.

XTS is an encryption scheme for storage devices standardized by IEEE and NIST. It is based on Rogaway's XEX tweakable block cipher and is known to be secure up to the collisions between the blocks, thus up to around $2^{n/2}$ blocks for $n$-bit blocks. However this only implies that the theoretical indistinguishability notion is broken with $O(2^{n/2})$ queries and does not tell the practical risk against the plaintext recovery if XTS is targeted. We show several plaintext recovery attacks against XTS beyond collisions, and evaluate their practical impacts.

Achieving security in the Internet of Things (IoT) is challenging. The need for lightweight yet robust cryptographic solutions suitable for the IoT calls for improved design and implementation of constructs such as authenticated encryption with associated data (AEAD) which can ensure confidentiality, integrity, and authenticity of data in one algorithm. The U.S. National Institute of Standards and Technology (NIST) has embarked on a multi-year effort called the lightweight cryptography (LWC) standardization process to evaluate lightweight AEAD and optional hash algorithms for inclusion in U.S. federal standards. As candidates are evaluated for many characteristics including hardware resources and performance, obtaining results of hardware implementations as early as possible is preferable. In this work, we implement six NIST LWC Round 2 candidate ciphers, SpoC, GIFT-COFB, COMET-AES, COMET-CHAM, Ascon, and Schwaemm and Esch, in the Artix-7, Spartan-6, and Cyclone-V FPGAs. Implementations are compliant with the newly-released hardware (HW) applications programming interface (API) for lightweight cryptography and are tested in actual hardware. We also provide the average power and energy per bit of our implementations at 40 MHz. Results indicate that SpoC has the smallest area and power, while Ascon has the highest throughput-to-area (TPA) ratio.

We design an efficient method for sampling a large batch of $d$ independent coins with a given bias $p \in [0,1]$. The folklore secure computation method for doing so requires $O(\lambda + \log d)$ communication and computation per coin to achieve total statistical difference $2^{-\lambda}$. We present an exponential improvement over the folklore method that uses just $O(\log(\lambda+\log d))$ gates per coin when sampling $d$ coins with total statistical difference $2^{-\lambda}$. We present a variant of our work that also concretely beats the folklore method for $\lambda \geq 60$ which are parameters that are often used in practice. Our new technique relies on using specially designed oblivious data structures to achieve biased coin samples that takean expected $2$ random bits to sample. Using our new sampling technique, we present an implementation of the differentially private report-noisy-max mechanism (a more practical implementation of the celebrated exponential mechanism) as a secure multi-party computation. Our benchmarks show that one can run this mechanism on a domain of size $d=2^{12}$ in 6 seconds and up to $d=2^{19}$ in 14 minutes. As far as we know, this is the first complete distributed implementation of either of these mechanisms.

We explore formal definitions of coercion resistance (WPES'05, FC'09, CRYPTO'10, and CSF'10), conceived to capture the strongest privacy notions achievable by voting systems. We find all but one is unsuitable, demonstrating difficulties faced by our community in formalising this property and raising questions over the security of schemes striving to deliver coercion resistance. We find the remaining definition to be reliant on burdensome combinatorial analysis, prohibiting immediate application. We propose a variant that simplifies application. We also patch an unsuitable definition and introduce sufficient conditions to simplify proofs.

Forward Secrecy (FS) is a security property in key-exchange algorithms which guarantees that a compromise in the secrecy of a long-term private-key does not compromise the secrecy of past session keys. With a growing awareness of long-term mass surveillance programs by governments and others, FS has become widely regarded as a highly desirable property. This is particularly true in the TLS protocol, which is used to secure Internet communication. In this paper, we investigate FS in pre-TLS 1.3 protocols, which do not mandate FS, but still widely used today. We conduct an empirical analysis of over 10 million TLS servers from three different datasets using a novel heuristic approach. Using a modern TLS client handshake algorithms, our results show 5.37% of top domains, 7.51% of random domains, and 26.16% of random IPs do not select FS key-exchange algorithms. Surprisingly, 39.20% of the top domains, 24.40% of the random domains, and 14.46% of the random IPs that do not select FS, do support FS. In light of this analysis, we discuss possible paths toward forward secure Internet traffic. As an improvement of the current state, we propose a new client-side mechanism that we call "Best Effort Forward Secrecy" (BEFS), and an extension of it that we call "Best Effort Forward Secrecy and Authenticated Encryption" (BESAFE), which aims to guide (force) misconfigured servers to FS using a best effort approach. Finally, within our analysis, we introduce a novel adversarial model that we call "discriminatory" adversary, which is applicable to the TLS protocol.

Location data is an important piece of contextual information in location-driven features for geosocial and pervasive computing applications. In this paper, we propose to geo-hash locations using space-filling curves, which are dimension reduction techniques that preserve locality. The proposed location referencing method is agnostic to specific maps or precoded location models and can effectively preserve users’ location privacy based on user preferences. We employ post-quantum-secure encryption on location data and privacy preferences to minimize the risk of data leakage. We also design three algorithms to homomorphically compute geospatial queries on the encrypted location data without revealing either user locations or user preferences. One of the three proposed algorithms reduces the multiplicative depth by more than half; thus, significantly speeding up homomorphic computations. We then present a prototype of the proposed system and algorithms using a somewhat homomorphic encryption scheme and our optimization techniques. A systematic evaluation of the prototype demonstrates its utility in spatial cloaking.

Decision tree and its generalization of random forests are a simple yet powerful machine learning model for many classification and regression problems. Recent works propose how to privately evaluate a decision tree in a two-party setting where the feature vector of the client or the decision tree model (such as the threshold values of its nodes) is kept a secret from another party. However, these works cannot be extended trivially to support the outsourcing setting where a third-party who should not have access to the model or the query. Furthermore, their use of an interactive comparison protocol does not support branching program, hence requires interactions with the client to determine the comparison result before resuming the evaluation task. In this paper, we propose the first secure protocol for collaborative evaluation of random forests contributed by multiple owners. They outsource evaluation tasks to a third-party evaluator. Upon receiving the client’s encrypted inputs, the cloud evaluates obliviously on individually encrypted random forest models and calculates the aggregated result. The system is based on our new secure comparison protocol, secure counting protocol, and a multi-key somewhat homomorphic encryption on top of symmetric-key encryption. This allows us to reduce communication overheads while achieving round complexity lower than existing work.

This article, for the first time, demonstrates Cross-device Deep Learning Side-Channel Attack (X-DeepSCA), achieving an accuracy of $>99.9\%$, even in presence of significantly higher inter-device variations compared to the inter-key variations. Augmenting traces captured from multiple devices for training and with proper choice of hyper-parameters, the proposed 256-class Deep Neural Network (DNN) learns accurately from the power side-channel leakage of an AES-128 target encryption engine, and an N-trace ($N\leq10$) X-DeepSCA attack breaks different target devices within seconds compared to a few minutes for a correlational power analysis (CPA) attack, thereby increasing the threat surface for embedded devices significantly. Even for low SNR scenarios, the proposed X-DeepSCA attack achieves $\sim10\times$ lower minimum traces to disclosure (MTD) compared to a traditional CPA.

Non-zero inner product encryption (NIPE) allows a user to encrypt a message with its attribute vector and decryption is possible using a secret-key associated with a predicate vector if the inner product of the vectors is non-zero. The concept of NIPE was put forth by Katz, Sahai and Waters (EUROCRYPT 2008). Following that many NIPE constructions were proposed along with interesting applications. The security of all these works is based on hardness assumptions in pairing-friendly groups. Recently, Katsumata and Yamada (PKC 2019) built a NIPE relying on the Learning-with-Errors (LWE) problems, however, their system practically lags behind for providing only selective security with significantly large sizes of master public-key, secret-keys and ciphertexts. Despite its cryptographic importance, past history of NIPE is not convincing in terms of both security and practical efficiency as the schemes are either selectively secure or depend on bilinear maps. In this paper, our goal is to construct adaptively secure efficient NIPEs. Firstly, we provide adaptively secure public-key NIPE under the standard Decision Diffie-Hellman (DDH) assumption that enables one to encrypt messages of sufficiently small length. To overcome this limitation we rely on the Decision Diffie-Hellman-f (DDH-f) and the Hard Subgroup Membership (HSM) assumptions proposed by Castagnos et al. in ASIACRYPT 2018. Consequently, we construct two pNIPEs, adaptively secure under the DDH-f and HSM assumptions respectively, both are capable of encrypting large messages with inner products over integers. We upgrade these two pNIPEs so that it can encrypt messages with unbounded inner products modulo an arbitrary large prime p. In addition, utilizing inner product functional encryptions we provide attribute-hiding public-key NIPEs depending on the DDH, DDH-f, HSM, LWE, Decision Composite Reciprocity assumptions and establish full-hiding private-key NIPEs based on the Decision linear and Symmetric External Diffie-Hellman assumptions.

A framework for asynchronous, signature free, fully local and probabilistically converging total order algorithms is developed, that may survive in high entropy, unstructured Peer-to-Peer networks with near optimal communication efficiency. Regarding the natural boundaries of the CAP-theorem, the protocol chooses different compromises for consistency and availability, depending on the severity of the attack. The family is parameterized by a few constants and external functions called voting-weight, incentivation and punishement, difficulty oracle and quorum-selector. These functions are necessary to fine tune the dynamics and very different long term behavior might appear, depending on any actual choice.

The basic Supersingular Isogeny Diffie-Hellman (SIDH) key agreement protocol is insecure due to an attack described by Galbraith, Petit, Shani and Ti. In this note we present two variants of SIDH that are immune to this attack.

Pairing-friendly elliptic curve constructions provide two elliptic curve groups which are both of prime order $q$ and usually each have a nontrivial cofactor $h$. Due to the way these curves are typically constructed, endomorphisms can be applied to perform fast cofactor multiplication. However, cofactor multiplication is sometimes insufficient for dealing with cofactors, such as with malleability attacks. In this brief note, we describe efficient techniques for checking that points exist within the correct $q$-order subgroups of the BLS12-381 elliptic curve construction, which is the focus of standardization for pairing-based protocols. Instead of multiplying by $q$ and comparing the point with the identity, we use endomorphisms to eliminate the $q$-torsion while modifying (but not killing) the $h$-torsion components. The result can then be compared against the identity.

Symmetric Searchable encryption (SSE) is an encryption technique that allows users to search directly on their outsourced encrypted data, in a way that the privacy of both the files and the search queries is preserved. Naturally, with every search query, some information is leaked. The leakage becomes even bigger when the scheme is dynamic (i.e. supports file insertions and deletions). To deal with this problem we design a forward private dynamic SSE scheme where file insertions do not leak any information about previous queries. Moreover, our construction supports the multi-client model, in the sense that every user that holds the secret key can perform search queries. Finally, our scheme also focuses on the problem of synchronization by utilizing the functionality offered by Intel SGX.

Symmetric cryptographic primitives with low multiplicative complexity have been proposed to improve the performance of emerging applications such as secure Multi-Party Computation. However, primitives composed of round functions with low algebraic degree require a careful evaluation to assess their security against algebraic cryptanalysis, and in particular interpolation attacks. This paper proposes new low-memory interpolation attacks on symmetric key primitives of low degree. Moreover, we present generic attacks on block ciphers with a simple key schedule; our attacks require either constant memory or constant data complexity. The improved attack is applied to the block cipher MiMC which aims to minimize the number of multiplications in large finite fields. As a result, we can break MiMC-$129/129$ with $38$ rounds with time and data complexity $2^{65.5}$ and $2^{60.2}$ respectively and with negligible memory; this attack invalidates one of the security claims of the designers. Our attack indicates that for MiMC-$129/129$ the full $82$ rounds are necessary even with restrictions on the memory available to the attacker. For variants of MiMC with larger keys, we present new attacks with reduced complexity. Our results do not affect the security claims of the full round MiMC.

Building expressive encrypted databases that can scale to large volumes of data while enjoying formal security guarantees has been one of the holy grails of security and cryptography research. Searchable Encryption (SE) is considered to be an attractive implementation choice for this goal: It naturally supports basic database queries such as point, join and range, and is very practical at the expense of well-defined leakage such as search and access pattern. Nevertheless, recent attacks have exploited these leakages to recover the plaintext database or the posed queries, casting doubt to the usefulness of SE in encrypted systems. Defenses against such leakage-abuse attacks typically require the use of Oblivious RAM or worst-case padding---such countermeasures are however quite impractical. In order to efficiently defend against leakage-abuse attacks on SE-based systems, we propose SEAL, a family of new SE schemes with adjustable leakage. In SEAL, the amount of privacy loss is expressed in leaked bits of search or access pattern and can be defined at setup. As our experiments show, when protecting only a few bits of leakage (e.g., three to four bits of access pattern), enough for existing and even new more aggressive attacks to fail, SEAL query execution time is within the realm of practical for real-world applications (a little over one order of magnitude slowdown compared to traditional SE-based encrypted databases). Our findings therefore show that SEAL could be a promising approach for building efficient and robust encrypted databases.

In an article from CHES 2015, which appears in extended form in the Journal of Cryptology in 2019, Bernard, Haddad, Fischer, and Nicolai modeled the physical behavior of a transient effect ring oscillator (TERO), thereby providing a means to certify its operation as a true random number generator (TRNG). In this work, we disprove the physical assumption on which the whole model is based. Moreover, we show that the convenient use of tractable, closed-form equations stems from a mathematical error. On a more constructive note, we are the first to point out that TEROs and Bistable Ring physically unclonable functions (PUFs) are closely related, thereby not only laying the foundations of a more accurate physical model but also revealing a new design trade-off between throughput, entropy, and reliability. Furthermore, we demonstrate that most TERO implementations in the literature are prone to counter value corruptions, and propose a solution to this problem. Measurements performed on a field-programmable gate array (FPGA) substantiate our claims.

Many cryptographers have focused on lightweight cryptography, and a huge number of lightweight block ciphers have been proposed. On the other hand, designing lightweight stream ciphers is a challenging task due to the well-known security criteria, i.e., the state size of stream ciphers must be at least twice the key size. The designers of Sprout addressed this issue by involving the secret key not only in the initialization but also in the keystream generation, and the state size of such stream ciphers can be smaller than twice the key size. After the seminal work, some small-state stream ciphers have been proposed such as Fruit, Plantlet, and LIZARD. Unlike conventional stream ciphers, these small-state stream ciphers have the limitation of keystream bits that can be generated from the same key and IV pair. In this paper, our motivation is to show whether the data limitation claimed by the designers is proper or not. The correlation attack is one of the attack methods exploiting many keystream bits generated from the same key and IV pair, and we apply it to Fruit-80 and Plantlet. As a result, we can break the full Fruit-80, i.e., the designers' data limitation is not sufficient. We can also recover the secret key of Plantlet if it allows about $2^{53}$ keystream bits from the same key and IV pair.

We construct a 2-message publicly verifiable witness indistinguishable argument system for NP assuming that the Learning with Errors (LWE) problem is subexponentially hard. Moreover, the protocol is ``delayed input''; that is, the verifier message in this protocol does not depend on the instance. This means that a single verifier message can be reused many times. We construct two variants of this argument system: one variant is adaptively sound, while the other is public-coin (but only non-adaptively sound). We obtain our result via a generic transformation showing that the correlation intractable hash families constructed by Canetti et al. (STOC 2019) and Peikert and Shiehian (CRYPTO 2019) suffice to construct such 2-message WI arguments when combined with an appropriately chosen ``trapdoor Sigma-protocol.'' Our construction can be seen as an adaptation of the Dwork-Naor ``reverse randomization'' paradigm (FOCS '00) for constructing ZAPs to the setting of computational soundness rather than statistical soundness. Our adaptation of the Dwork-Naor transformation crucially relies on complexity leveraging to prove that soundness is preserved.

PKI schemes provide a critical foundation for applied cryptographic protocols. However, there are no rigorous security specifications for realistic PKI schemes, and therefore, no PKI schemes were proven secure. Cryptographic systems that use PKI are analyzed by adopting overly simplified models of the PKI, often, simply assuming securely-distributed public keys. This is problematic given the extensive reliance on PKI, the multiple failures of PKI systems, and the complexity of both proposed and deployed systems, which involve complex requirements and models. We present game-based security specifications for PKI schemes, and analyze important and widely deployed PKIs: PKIX and two variants of Certificate Transparency (CT). All PKIs are based on the X.509v3 standard and its CRL revocation mechanism. Our analysis identified few subtle vulnerabilities, and provides reduction-based proofs showing that the PKIs ensure specific requirements under specific models (assumptions). To our knowledge, this is the first reduction-based proof of security for a realistic PKI scheme, e.g., supporting certificate chains.

Rapid advances in Internet technologies have fostered the emergence of the “software as a service” model for enterprise computing. The “Database as a Service” model provides users with the power to create, store, modify, and retrieve data from any location, as long as they have access to the Internet. As more and more datasets (including those containing private and sensitive data) are outsourced to remote / cloud storage providers, the data owner, firstly, needs to be certain of the security of data against thefts by outsiders and, secondly, the data owner needs to secure the data not only against external threats but also from untrusted service providers. The same is true for distributed applications with complex microservice architectures. However, the use of standard encryption schemes for data protection also effectively eliminates the search capability of the database service which, in turn, severely constrains the ability of the service to manage large volumes of data. Searchable encryption (SE) is a class of cryptographic techniques that addresses these issues. SE allows a user to write encrypted data to an untrusted storage provider while retaining the ability to perform queries without decrypting the data. This can be achieved by either encrypting the data in a special way that enables queries to be executed directly on the ciphertext or by introducing a searchable encrypted index which is stored together with the encrypted data on the storage provider. All reasonably efficient SE schemes have a common problem. They leak the search pattern that reveals whether two search queries were performed for the same keyword or not. Hence, the search pattern provides the information on the frequency of occurrence for each query. This information can be further exploited by statistical analysis, allowing an adversary to gain full knowledge about the plaintext keywords, which significantly decreases the security benefits of encrypting the data. There is no single best publicly known secure search system or a set of such techniques. The design of SE schemes is a balancing act between security, functionality, performance, and usability. This is especially true since different users will want different database architecture (SQL, NoSQL, NewSQL). Most progress in the area of SE has been made in the setting of keyword search on encrypted documents. While this has many practical applications (i.e. email, desktop search engines, cloud document storage), much of the data produced and consumed is stored and processed in relational databases queried using SQL. In this paper, we propose Acra Searchable Encryption (Acra SE) – a solution for secure search in an encrypted SQL database based on the blind indexing approach developing and evolving the original idea of the CipherSweet project.

Data minimization has become a paradigm to address privacy concerns when collecting and storing personal data. In this paper we present two new approaches, RSTxFM and RRTxFM, to estimate the cardinality of a dataset while ensuring differential privacy. We argue that privacy-preserving cardinality estimators are able to realize strong privacy requirements. Both approaches are based on a probabilistic counting algorithm which has a logarithmic space complexity. We combine this with a randomization technique to provide differential privacy. In our analysis, we detail the privacy and utility guarantees and expose the impact of the various parameters. Moreover, we discuss workforce analytics as application area where strong privacy is paramount.

For enabling post-quantum cryptanalytic experiments on a meaningful scale, there is a strong need for low-memory algorithms. We show that the combination of techniques from representations, multiple collision finding, and the Schroeppel-Shamir algorithm leeds to improved low-memory algorithms. For random subset sum instances $(a_1, \ldots, a_n,t)$ defined modulo $2^n$, our algorithms improve over the Dissection technique for small memory $M < 2^{0.02n}$ and in the mid-memory regime $2^{0.13n} < M < 2^{0.2n}$. An application of our technique to LPN of dimension $k$ and constant error $p$ yields significant time complexity improvements over the Dissection-BKW algorithm from Crypto 2018 for all memory parameters $M< 2^{0.35 \frac{k}{\log k}}$.

The side-channel community recently investigated a new approach, based on deep learning, to significantly improve profiled attacks against embedded systems. Previous works have shown the benefit of using convolutional neural networks (CNN) to limit the effect of some countermeasures such as desynchronization. Compared with template attacks, deep learning techniques can deal with trace misalignment and the high dimensionality of the data. Pre-processing is no longer mandatory. However, the performance of attacks depends to a great extent on the choice of each hyperparameter used to configure a CNN architecture. Hence, we cannot perfectly harness the potential of deep neural networks without a clear understanding of the network’s inner-workings. To reduce this gap, we propose to clearly explain the role of each hyperparameters during the feature selection phase using some specific visualization techniques including Weight Visualization, Gradient Visualization and Heatmaps. By highlighting which features are retained by filters, heatmaps come in handy when a security evaluator tries to interpret and understand the efficiency of CNN. We propose a methodology for building efficient CNN architectures in terms of attack efficiency and network complexity, even in the presence of desynchronization. We evaluate our methodology using public datasets with and without desynchronization. In each case, our methodology outperforms the previous state-of-the-art CNN models while significantly reducing network complexity. Our networks are up to 25 times more efficient than previous state-of-the-art while their complexity is up to 31810 times smaller. Our results show that CNN networks do not need to be very complex to perform well in the side-channel context.

In this paper we consider various methods and techniques to find the smallest circuit realizing a given linear transformation on $n$ input signals and $m$ output signals, with a constraint of a maximum depth, $maxD$, of the circuit. Additional requirements may include that input signals can arrive to the circuit with different delays, and output signals may be requested to be ready at a different depth. We apply these methods and also improve previous results in order to find hardware circuits for forward, inverse, and combined AES SBoxes, and for each of them we provide the fastest and smallest combinatorial circuits. Additionally, we propose a novel technique with ``floating multiplexers'' to minimize the circuit for the combined SBox, where we have two different linear matrices (forward and inverse) combined with multiplexers. The resulting AES SBox solutions are the fastest and smallest to our knowledge.

SAE (Simultaneous Authentication of Equals), is a password authenticated key exchange protocol, which is designed to replace the WPA2-PSK based authentication. The SAE Authentication Protocol supports the peer to peer (P2P) authentication, and is a major authentication mechanism of the Authentication and Key Management Suite (AKM). The SAE key exchange protocol and its variants, i.e, the Dragonfly key exchange protocol, have previously received some cryptanalysis, in which the authors pointed out Dragonfly protocol is vulnerable to the sub-group attack. This paper investigates some further vulnerabilities using impersonation attacks and suggests some protocol amendments for protection. It is recommended that SAE implementations should be upgraded to ensure protection against these attacks.

We give a 4-list algorithm for solving the Elliptic Curve Discrete Logarithm (ECDLP) over some quadratic field $\mathbb{F}_{p^2}$. Using the representation technique, we reduce ECDLP to a multivariate polynomial zero testing problem. Our solution of this problem using bivariate polynomial multi-evaluation yields a $p^{1.314}$-algorithm for ECDLP. While this is inferior to Pollard's Rho algorithm with square root (in the field size) complexity $\mathcal{O}(p)$, it still has the potential to open a path to an $o(p)$-algorithm for ECDLP, since all involved lists are of size as small as $p^{\frac 3 4}$, only their computation is yet too costly.