So far, most of the Identity-Based Encryption (IBE) schemes have been realized by employing bilinear pairings, lattices, trapdoor discrete logarithm, or based on the quadratic residue problem. Among the IBE schemes, only pairing-based methods seem to be practical. Previously published non-pairing-based schemes are generally inefficient in encryption, decryption, key generation, ciphertext size or key size. In this paper, we propose an IBE scheme based on a hybrid of Diffie-Hellman and RSA-like hardness assumption. The computational cost of the proposed scheme is lower than the previous schemes and the ciphertext size for an $l$-bit plaintext is only $2l$ bits. The proposed scheme is similar to the well-known ElGamal encryption algorithm; therefore it might be used in applications such as oblivious computation.

In this work, we are concerned with the hardening of post-quantum key encapsulation mechanisms (KEM) against side-channel attacks, with a focus on the comparison operation required for the Fujisaki-Okamoto (FO) transform. We identify critical vulnerabilities in two proposals for masked comparison and successfully attack the masked comparison algorithms from TCHES 2018 and TCHES 2020. To do so, we use first-order side-channel attacks and show that the advertised security properties do not hold. Additionally, we break the higher-order secured masked comparison from TCHES 2020 using a collision attack, which does not require side-channel information. To enable implementers to spot such flaws in the implementation or underlying algorithms, we propose a framework that is designed to test the re-encryption step of the FO transform for information leakage. Our framework relies on a specifically parametrized $t$-test and would have identified the previously mentioned flaws in the masked comparison. Our framework can be used to test both the comparison itself and the full decapsulation implementation.

ForkAE is a family of authenticated encryption (AE) schemes using a forkcipher as a building block. ForkAE was published in Asiacrypt'19 and is a second-round candidate in the NIST lightweight cryptography process. ForkAE comes in several modes of operation: SAEF, PAEF, and rPAEF. SAEF is optimized for authenticated encryption of short messages and processes the message blocks in a sequential and online manner. SAEF requires a smaller internal state than its parallel sibling PAEF and is better fitted for devices with smaller footprint. At SAC 2020 it was shown that SAEF is also an online nonce misuse-resistant AE (OAE) and hence offers enhanced security against adversaries that make blockwise adaptive encryption queries. It has remained an open question if SAEF resists attacks against blockwise adaptive decryption adversaries, or more generally when the decrypted plaintext is released before the verification (RUP). RUP security is a particularly relevant security target for lightweight (LW) implementations of AE schemes on memory-constrained devices or devices with stringent real-time requirements. Surprisingly, very few NIST lightweight AEAD candidates come with any provable guarantees against RUP. In this work, we show that the SAEF mode of operation of the ForkAE family comes with integrity guarantees in the RUP setting. The RUP integrity (INT-RUP) property was defined by Andreeva et~al.~in Asiacrypt'14. Our INT-RUP proof is conducted using the coefficient H technique and it shows that, without any modifications, SAEF is INT-RUP secure up to the birthday bound, i.e., up to $2^{n/2}$ processed data blocks, where $n$ is the block size of the forkcipher. The implication of our work is that SAEF is indeed RUP secure in the sense that the release of unverified plaintexts will not impact its ciphertext integrity.

Advanced Encryption Standard used with Galois Counter Mode, mode of operation is one of the the most secure modes to use the AES. This paper represents an overview of the AES modes focusing the AES-GCM mode and its particularities. Moreover, after a detailed analysis of the possibility of enhancement for the encryption and authentication phase, a method of generating custom encryption schemes based on GF($2^8$) irreducible polynomials different from the standard polynomial used by the AES-GCM mode is provided. Besides the polynomial customization, the solution proposed in this paper offers the possibility to determine, for each polynomial, the constants that can be used in order to keep all the security properties of the algorithm. Using this customization method, allows changing the encryption schemes over a period of time without interfering with the process, bringing a major improvement from the security point of view by avoiding pattern creation. Furthermore, this paper sets the grounds for implementing authentication enhancement using a similar method to determine the polynomials that can be used instead of the default authentication polynomial, without changing the algorithm strength at all.

The progress on constructing quantum computers and the ongoing standardization of post-quantum cryptography (PQC) have led to the development and refinement of promising new digital signature schemes and key encapsulation mechanisms (KEM). Especially lattice-based schemes have gained some popularity in the research community, presumably due to acceptable key, ciphertext, and signature sizes as well as good performance results and cryptographic strength. However, in some practical applications like smart cards, it is also crucial to secure cryptographic implementations against side-channel and fault attacks. In this work, we analyze the so-called redundant number representation (RNR) that can be used to counter side-channel attacks. We show how to avoid security issues with the RNR due to unexpected de-randomization and we apply it to the Kyber KEM and show that the RNR has a very low overhead. We then verify the RNR methodology by practical experiments, using the non-specific t-test methodology and the ChipWhisperer platform. Furthermore, we present a novel countermeasure against fault attacks based on the Chinese remainder theorem (CRT). On an ARM Cortex-M4, our implementation of the RNR and fault countermeasure offers better performance than masking and redundant calculation. Our methods thus have the potential to expand the toolbox of a defender implementing lattice-based cryptography with protection against two common physical attacks.

Having shared access to high-quality random numbers is essential in many important applications. Yet, existing constructions of distributed random beacons still have limitations such as imperfect security guarantees, strong setup or network assumptions, or high costs. In this paper, we present SPURT, an efficient distributed randomness beacon protocol that does not require any trusted or expensive setup and is secure against a malicious adversary that controls up to one-third of the nodes in a partially synchronous network. We formally prove that each output of SPURT is unpredictable, bias-resistant, and publicly verifiable. SPURT has an amortized total communication cost of $O(\lambda n^2)$ per beacon output where $\lambda$ is the security parameter. While designing SPURT, we also design a publicly verifiable secret sharing (PVSS) scheme whose security is based on the standard Decisional Bilinear Diffie-Hellman assumption and does not require a Random Oracle. We implement SPURT and evaluate it using a network of up to 128 nodes running in geographically distributed AWS instances. Our evaluation shows that SPURT can produce about 84 beacon outputs per minute in a network of 32 nodes and is comparable to systems with stronger assumptions or weaker security.

A major concern in training and releasing machine learning models is to what extent the model contains sensitive information that the data holders do not want to reveal. Property inference attacks consider an adversary who has access to the trained model and tries to extract some global statistics of the training data. In this work, we study property inference in scenarios where the adversary can maliciously control part of the training data (poisoning data) with the goal of increasing the leakage. Previous work on poisoning attacks focused on trying to decrease the accuracy of models either on the whole population or on specific sub-populations or instances. Here, for the first time, we study poisoning attacks where the goal of the adversary is to increase the information leakage of the model. Our findings suggest that poisoning attacks can boost the information leakage significantly and should be considered as a stronger threat model in sensitive applications where some of the data sources may be malicious. We first describe our property inference poisoning attack that allows the adversary to learn the prevalence in the training data of any property it chooses: it chooses the property to attack, then submits input data according to a poisoned distribution, and finally uses black box queries (label-only queries) on the trained model to determine the frequency of the chosen property. We theoretically prove that our attack can always succeed as long as the learning algorithm used has good generalization properties. We then verify effectiveness of our attack by experimentally evaluating it on two datasets: a Census dataset and the Enron email dataset. In the first case we show that classifiers that recognizes whether an individual has high income (Census data) also leak information about the race and gender ratios of the underlying dataset. In the second case, we show classifiers trained to detect spam emails (Enron data) can also reveal the fraction of emails which show negative sentiment (according to a sentiment analysis algorithm); note that the sentiment is not a feature in the training dataset, but rather some feature that the adversary chooses and can be derived from the existing features (in this case the words). Finally, we add an additional feature to each dataset that is chosen at random, independent of the other features, and show that the classifiers can also be made to leak statistics about this feature; this shows that the attack can target features completely uncorrelated with the original training task. We were able to achieve above $90\%$ attack accuracy with $9-10\%$ poisoning in all of these experiments.

We consider image sets of $d$-uniform maps of finite fields. We present a lower bound on the image size of such maps and study their preimage distribution, by extending methods used for planar maps. We apply the results to study $d$-uniform Dembowsi-Ostrom polynomials. Further, we focus on a particularly interesting case of APN maps on binary fields $\F_{2^n}$. For these maps our lower bound coincides with previous bounds. We show that APN maps fulfilling the lower bound have a very special preimage distribution. We observe that for an even $n$ the image sets of several well-studied families of APN maps are minimal. In particular, for $n$ even, a Dembowski-Ostrom polynomial of form $f(x) =f'(x^3)$ is APN if and only if $f$ is almost-3-to-1, that is when its image set is minimal. Also, any almost-3-to-1 component-wise plateaued map is necessarily APN, if $n$ is even. For $n$ odd, we believe that the lower bound is not sharp. For $n$ odd, we present APN Dembowski-Ostrom polynomials of form $f'(x^3)$ on $\F_{2^n}$ with image sizes $ 2^{n-1}$ and $5\cdot 2^{n-3}$. We present results connecting the image sets of special APN maps with their Walsh spectrum. Especially, we show that a large class of APN maps has the classical Walsh spectrum. Finally, we present upper bounds on the image size of APN maps. In particular, we show that the image set of a non-bijective almost bent map contains at most $2^n-2^{(n-1)/2}$ elements.

The prefix-free PRF (pseudorandom function) security of a cascade function based on a compression function $f$ against a $q$-query distinguisher is reduced to a $q$-query PRF security of $f$ with a tightness gap $lq$ where $l$ represents the length of the longest query among all $q$ queries. In this paper, we have shown a reduction which is also applicable to multiuser setup and improves the tightness gap for both adaptive and non-adaptive distinguishers. As an immediate application of our result, we have shown multiuser security of NMAC, HMAC and many other MACs for the first time. Moreover, the tightness gap is improved in comparison with known single-user analysis. We also have shown a similar tightness gap for single-keyed NMAC. As a result, the constants ipad and opad used in HMAC and existing PRB (pseudorandom bit) assumption on the underlying compression function become redundant.

Standard hybrid encryption schemes based on the KEM-DEM framework are hard to implement efficiently in a distributed manner whilst maintaining the CCA security property of the scheme. This is because the DEM needs to be decrypted under the key encapsulated by the KEM, before the whole ciphertext is declared valid. In this paper we present a new variant of the KEM-DEM framework, closely related to Tag-KEMs, which sidesteps this issue. We then present a post-quantum KEM for this framework based on Learning-with-Rounding, which is designed specifically to have fast distributed decryption. Our combined construction of a hybrid encryption scheme with Learning-with-Rounding based KEM, called Gladius, is closely related to the NIST Round 3 candidate called Saber. Finally, we give a prototype distributed implementation that achieves a decapsulation time of 4.99 seconds for three parties.

An information escrow (IE) service allows its users to encrypt a message such that the message is unlocked only when a user-specified condition is satisfied. Its instantiations include timed-release encryption and allegation escrows with applications ranging from e-auctions to the #metoo movement. The proposed IE systems typically employ threshold cryptography towards mitigating the single-point-of-failure problem. Here, a set of escrow agents securely realize the IE functionality as long as a threshold or more agents behave honestly. Nevertheless, these threshold information escrow (TIE) protocols are vulnerable to premature and undetectable unlocking of messages through collusion among rational agents offering the IE service. This work presents a provably secure TIE scheme in the mixed-behavior model consisting of rational and malicious escrow agents.; any collusion attempt among the agents towards premature decryption results in penalization through a loss of (crypto-)currency and getting banned from the system. The proposed collusion-deterrent escrow (CDE) scheme introduces a novel incentive-penalty mechanism among the agents to stay honest until the user-specified decryption condition is met. In particular, each agent makes a cryptocurrency deposit before the start of the protocol instance such that the deposit amount is returned to the agent when the user-specified condition is met or can be transferred by anyone who holds a secret key corresponding to a public key associated with the instance. Using a novel combination of oblivious transfer, robust bit watermarking, and secure multi-party computation, CDE ensures that whenever the agents collude to decrypt the user data prematurely, one or more whistle-blower agents can withdraw/transfer the deposits of all other agents, thereby penalizing them. We model collusion as a game induced among rational agents offering the CDE service and show that the agents do not collude at equilibrium in game-theoretic terms. We also present a prototype implementation of the CDE protocol and demonstrate its efficiency towards use in practice. While this work does not aim to solve the collusion problem fully, it significantly raises the bar for collusion. It offers an important step towards weakening the strong non-collusion assumption pervasive across multi-party computation applications.

Credit and debit-card payments are typically authenticated with PINs. Once entered into a terminal, the PIN is sent as an encrypted \emph{PIN block} across a payments network to the destination bank, which decrypts and verifies the PIN block. Each node in the payments network routes the PIN block to the next node by decrypting the block with its own key, and then re-encrypting the PIN block with the next node's key; nodes establish shared secret keys with their neighbors to do so. This decrypt-then-encrypt operation over PIN blocks is known as \emph{PIN translation}, and it is currently performed in Hardware Security Modules (HSMs) to avoid possible PIN exposure. However, HSMs incur heavy acquisition and operational expenses. Introduced at EUROCRYPT'98, proxy re-encryption (PRE) is a cryptographic primitive which can re-encrypt without exposing sensitive data. We perform an extensive study of PRE as applied to PIN translation, and show through formalization, security analysis, and an implementation study that PRE is a practical alternative to HSMs. With PRE, we eliminate the need for HSMs during re-encryption of a PIN, thus greatly reducing the number of HSMs needed by each participant in the payments ecosystem. Along the way we conduct practice-oriented PRE research, with novel theoretical contributions to resolve issues in comparing so-called honest re-encryption to chosen-ciphertext PRE security, and a new efficient PRE scheme achieving a type of chosen-ciphertext security.

Despite a growing body of work on leakage-abuse attacks for encrypted databases, attacks on practical response-hiding constructions are yet to appear. Response-hiding constructions are superior in that they nullify access-pattern based attacks by revealing only the search token and the result size of each query. Response-hiding schemes are vulnerable to existing volume attacks, which are, however, based on strong assumptions such as the uniform query assumption or the dense database assumption. More crucially, these attacks only apply to schemes that cannot be deployed in practice (ones with quadratic storage and increased leakage) while practical response-hiding schemes (Demertzis et al. [SIGMOD’16] and Faber et al. [ESORICS’15]) have linear storage and less leakage. Due to these shortcomings, the value of existing volume attacks on response-hiding schemes is unclear. In this work, we close the aforementioned gap by introducing a parametrized leakage-abuse attack that applies to practical response-hiding structured encryption schemes. The use of non-parametric estimation techniques makes our attack agnostic to both the data and the query distribution. At the very core of our technique lies the newly defined concept of a counting function with respect to a range scheme. We propose a two-phase framework to approximate the counting function for any range scheme. By simply switching one counting function for another, i.e., the so-called “parameter” of our modular attack, an adversary can attack different encrypted range schemes. We propose a constrained optimization formulation for the attack algorithm that is based on the counting functions. We demonstrate the effectiveness of our leakage-abuse attack on synthetic and real-world data under various scenarios.

In this article, we propose a new public key cryptosystem, called \textbf{NAB}. The most important features of NAB are that its security strength is no easier than the security issues of the NTRU cryptosystem~\cite{Hoffstein96} and the encryption/decryption process is very fast compared to the previous public key cryptosystems RSA~\cite{Rivest78amethod}, Elgamal~\cite{ElGamal85}, NTRU~\cite{Hoffstein96}. Since the NTRU cryptosystem~\cite{Hoffstein96} is still not known to be breakable using quantum computers, NAB is also the same. In addition, the expansion of the ciphertext is barely greater than the plaintext and the ratio of the bit-size of the ciphertext to the bit-size of the plaintext can be reduced to just over one. We suggest that NAB is an alternative to RSA~\cite{Rivest78amethod}, Elgamal~\cite{ElGamal85} and NTRU~\cite{Hoffstein96} cryptosystems.

In many cases, machine learning and privacy are perceived to be at odds. Privacy concerns are especially relevant when the involved data are sensitive. This paper deals with the privacy-preserving inference of deep neural networks. We report on first experiments with a new library implementing a variant of the TFHE fully homomorphic encryption scheme. The underlying key technology is the programmable bootstrapping. It enables the homomorphic evaluation of any function of a ciphertext, with a controlled level of noise. Our results indicate for the first time that deep neural networks are now within the reach of fully homomorphic encryption. Importantly, in contrast to prior works, our framework does not necessitate re-training the model.

We focus on exploring more potential of Longa and Sica's algorithm (ASIACRYPT 2012), which is an elaborate iterated Cornacchia algorithm that can compute short bases for 4-GLV decompositions. The algorithm consists of two sub-algorithms, the first one in the ring of integers $\mathbb{Z}$ and the second one in the Gaussian integer ring $\mathbb{Z}[i]$. We observe that $\mathbb{Z}[i]$ in the second sub-algorithm can be replaced by another Euclidean domain $\mathbb{Z}[\omega]$ $(\omega=\frac{-1+\sqrt{-3}}{2})$. As a consequence, we design a new twofold Cornacchia-type algorithm with a theoretic upper bound of output $C\cdot n^{1/4}$, where $C=\frac{3+\sqrt{3}}{2}\sqrt{1+|r|+|s|}$ with small values $r, s$ given by the curves. The new twofold algorithm can be used to compute $4$-GLV decompositions on two classes of curves. First it gives a new and unified method to compute all $4$-GLV decompositions on $j$-invariant $0$ elliptic curves over $\mathbb{F}_{p^2}$. Second it can be used to compute the $4$-GLV decomposition on the Jacobian of the hyperelliptic curve defined as $\mathcal{C}/\mathbb{F}_{p}:y^{2}=x^{6}+ax^{3}+b$, which has an endomorphism $\phi$ with the characteristic equation $\phi^2+\phi+1=0$ (hence $\mathbb{Z}[\phi]=\mathbb{Z}[\omega]$). As far as we know, none of the previous algorithms can be used to compute the $4$-GLV decomposition on the latter class of curves.

Many privacy-preserving protocols employ a primitive that allows a sender to "flag" a message to a recipient's public key, such that only the recipient (who possesses the corresponding secret key) can detect that the message is intended for their use. Examples of such protocols include anonymous messaging, privacy-preserving payments, and anonymous tracing. A limitation of the existing techniques is that recipients cannot easily outsource the detection of messages to a remote server, without revealing to the server the exact set of matching messages. In this work we propose a new class of cryptographic primitives called fuzzy message detection schemes. These schemes allow a recipient to derive a specialized message detection key that can identify correct messages, while also incorrectly identifying non-matching messages with a specific and chosen false positive rate $p$. This allows recipients to outsource detection work to an untrustworthy server, without revealing precisely which messages belong to the receiver. We show how to construct these schemes under a variety of assumptions; describe several applications of the new technique; and show that our schemes are efficient enough to use in real applications.

The hybrid argument is a fundamental and well-established proof technique of modern cryptography for showing the indistinguishability of distributions. As such, its details are often glossed over and phrases along the line of "this can be proven via a standard hybrid argument" are common in the cryptographic literature. Yet, the hybrid argument is not always as straightforward as we make it out to be, but instead comes with its share of intricacies. For example, a commonly stated variant says that if one has a sequence of hybrids $H_0,...,H_t$, and each pair $H_i$, $H_{i+1}$ is computationally indistinguishable, then so are the extreme hybrids $H_0$ and $H_t$. We iterate the fact that, in this form, the statement is only true for constant $t$, and we translate the common approach for general $t$ into a rigorous statement. The paper here is not a research paper in the traditional sense. It mainly consists of an excerpt from the book "The Theory of Hash Functions and Random Oracles - An Approach to Modern Cryptography" (Information Security and Cryptography, Springer, 2021), providing a detailed discussion of the intricacies of the hybrid argument that we believe is of interest to the broader cryptographic community. The excerpt is reproduced with permission of Springer.

We present ZEN, the first optimizing compiler that generates efficient verifiable, zero-knowledge neural network inference schemes. ZEN generates two schemes: ZEN$_{acc}$ and ZEN$_{infer}$. ZEN$_{acc}$ proves the accuracy of a committed neural network model; ZEN$_{infer}$ proves a specific inference result. Used in combination, these verifiable computation schemes ensure both the privacy of the sensitive user data as well as the confidentiality of the neural network models. However, directly using these schemes on zkSNARKs requires prohibitive computational cost. As an optimizing compiler, ZEN introduces two kinds of optimizations to address this issue: first, ZEN incorporates a new neural network quantization algorithm that incorporate two R1CS friendly optimizations which makes the model to be express in zkSNARKs with less constraints and minimal accuracy loss; second, ZEN introduces a SIMD style optimization, namely stranded encoding, that can encoding multiple 8bit integers in large finite field elements without overwhelming extraction cost. Combining these optimizations, ZEN produces verifiable neural network inference schemes with ${\bf 5.43} \sim {\bf 22.19} \times$ ($15.35 \times$ on average) less R1CS constraints.

Proof of Elapsed Time (PoET) is a Nakamoto-style consensus algorithm where proof of work is replaced by a wait time randomly generated by a trusted execution environment (TEE). PoET was originally developed by Intel engineers and contributed to Hyperledger Sawtooth, but has never been formally defined or analyzed. In particular, PoET enables consensus on a bitcoin-like scale without having to resort to mining. Proof of Luck (PoL), designed by Milutinovic et. al., is a similar (but not identical) protocol that also builds a Nakamoto-style consensus algorithm using a TEE. Like PoET, it also lacks a formal proof. In this work, we formally define a simplified version of PoET and Proof of Luck, which we call elapsed time (ET) consensus with a trusted timer. We prove the security of our ET consensus protocol with a trusted gimer given an honest majority assumption in a model very similar to the bitcoin backbone model proposed by Garay et al. which we call the elapsed time backbone model. Our model and protocol aims to capture the essence of PoeT and PoL while ignoring some of the more practical difficulties associated with such protocols, such as bootstrapping and setting up the TEE. The PoET protocol also contains a function called the $z$-test that limits the number of blocks a player can publish in any particular larger set of blocks. Surprisingly, by improving this $z$-test a little bit we can prove the security of our ET consensus protocol without any TEEs with a (slightly stronger) honest majority assumption. This implies that Nakamoto-style consensus with rate limiting and no proofs of work can be used to obtained scalable consensus in a permissioned setting: in other words, ``bitcoin without proofs of work'' can be made secure without a TEE for private blockchains!

In this paper, we present the analysis of Huff curves for implementing isogeny-based cryptography. In this regard, we first investigate the computational cost of the building blocks when compression functions are used for Huff curves. We also apply the square-root V\'elu formula on Huff curves and present a new formula for recovering the coefficient of the curve, from a given point on a Huff curve. From our implementation, the performance of Huff-SIDH and Montgomery-SIDH is almost the same, and the performance of Huff-CSIDH is 6\% faster than Montgomery-CSIDH. We further optimized Huff-CSIDH by exploiting Edwards curves for computing the coefficient of the image curve and present the Huff-Edwards hybrid model. As a result, the performance of Huff-Edwards CSIDH is almost the same as Montgomery-Edwards CSIDH. The result of our work shows that Huff curves can be quite practical for implementing isogeny-based cryptography but has some limitations.

In this paper, we present two new perturbations for the design of multivariate schemes that we call ``Ariadne Thread'' and ``Pepper''. From these ideas, we present some efficient multivariate encryption and signature schemes with explicit parameters that resist all known attacks. In particular they resist the two main (and often very powerful) attacks in this area: the Gröbner attacks (to compute a cleartext from a ciphertext) and the MinRank attacks (to recover the secret key). Ariadne Threat and Pepper can also be seen as new ``perturbations'' that we can use to enforce many multivariate schemes. The ``Pepper'' perturbation works only for public key equations of degree (at least) 3. Similarly at present the ``Ariadne Thread'' perturbation seems to be particularly powerful with public keys of degree 3. Despite this, the size of the public key may still be reasonable since we can use larger fields (and also maybe non dense equations). Ariadne Thread perturbation seems to be particularly interesting for encryption. This is unusual since in multivariate cryptography encryption is generally more difficult than signatures.

In this paper, we computationally analyze Passkey Entry in its entirety as a cryptographic authenticated key exchange (AKE) - including user-protocol interactions that are typically ignored as out-of-band. To achieve this, we model the user-to-device channels, as well as the typical device-to-device channel, and adversarial control scenarios in both cases. In particular, we separately capture adversarial control of device displays on the initiating and responding devices as well as adversarial control of user input mechanisms using what we call a CYBORG model. The CYBORG model enables realistic real-world security analysis in light of published attacks on user-mediated protocols such as Bluetooth that leverage malware and device displays. In light of this, we show that all versions of Passkey Entry fail to provide security in our model. Finally, we demonstrate how slight modications to the protocol would allow it to achieve stronger security guarantees for all current variants of passkey generation, as well as a newly proposed twofold mode of generation we term Dual Passkey Entry. These proof-of-concept modications point to improved design approaches for user-mediated protocols. Finally, this work points to categories of vulnerabilities, based on compromise type, that could be exploited in Bluetooth Passkey Entry.

Secure Multiparty Computation involves a protocol between parties with an aim to produce a computed result just as a trusted party would produce if the parties provided their inputs to it. The trusted party in conventional computation is replaced with "un-trusted" parties in Secure Multiparty Computation. We first show that this existing binary definition of trust is inadequate. Real world is rife with disparities, that which produce a perceivable trust gradient between the participants. Conventional MPC models do not take this into account and rather provide security guarantees based on the thresholds of the number of corrupted parties. The thresholds are supposed to cover for some of the parties turning out to be corrupt. Often, with the knowledge of prior probability of a party being corrupt, we can do better if we allot weight to each party based on how trusted we perceive it to be. Our paper explores this idea and our contributions towards it are three folds. First, we introduce the Graded Trust model where each party essentially has a "trust grade" assigned to it in the protocol based on the prior of it being corrupt. Second, we present a method for protocol translation and execution by by simulating players. Lastly, we present a discussion on the philosophy behind graded trust, and the potential benefits for large scale public MPC systems.

The concept of private stream aggregation (PSA) has been proposed by Shi et al. (NDSS 2011) to allow for data analysis in a privacy-preserving manner. In this work, we introduce the notion of labeled secret sharing (LaSS) schemes and show how to use it to construct PSA schemes. We also show how to realize LaSS using pseudorandom functions or alternatively with a hash function modeled as a random oracle and how it can be used to construct PSA schemes. Additionally, we revisit the security model of Becker et al. (NDSS 2018) and describe stronger security notions for PSA. We then present additional constructions achieving the stronger security notions by relying on recent results on multi-client functional encryption. For all of our constructions, we present implementations to show their practicality and the performance gains over existing solutions.

Chosen ciphertext security for lattice based encryption schemes is generally achieved through a generic transformation such as the Fujisaki-Okamoto transformation. This method requires full re-encryption of the plaintext during decapsulation, which typically dominates the cost of the latter procedure. In this work we show that it is possible to develop alternative transformations specifically designed for lattice based encryption schemes. We propose two novel chosen ciphertext transformations, $\mathtt{ETC1}$ and $\mathtt{ETC2}$, in which re-encryption is replaced by checking the error term of the input ciphertext. We show that our new ciphertext validity check can be securely applied to lattice based encryption schemes under specific conditions. For the NIST post-quantum standardization candidate Threebears we show a speed-up for decapsulation of up to $37.4\%$. Moreover, as our method only changes the validation check during decapsulation, it is fully backwards compatible with existing implementations of the Fujisaki-Okamoto transformation.

In this paper, we present the first side-channel attack on a first-order masked implementation of IND-CCA secure Saber KEM. We show how to recover both the session key and the long-term secret key from 16 traces by deep learning-based power analysis without explicitly extracting the random mask at each execution. Since the presented method is not dependent on the mask, we can improve success probability by combining score vectors of multiple traces captured for the same ciphertext. This is an important advantage over previous attacks on LWE/LWR-based KEMs, which must rely on a single trace. Another advantage is that the presented method does not require a profiling device with deactivated countermeasure, or known secret key. Thus, if a device under attack is accessible, it can be used for profiling. This typically maximizes the classification accuracy of deep learning models. In addition, we discovered a leakage point in the primitive for masked logical shifting on arithmetic shares which has not been known before. We also present a new approach for secret key recovery, using maps from error-correcting codes. This approach can compensate for some errors in the recovered message.

We propose a smart contract that allows two mutually distrusting parties to transact any non-digital good or service on a blockchain. The contract acts as an escrow and settles disputes by letting parties wager that they can convince an arbiter they were the honest party. We analyze the contract as an extensive-form game and prove that the contract is secure in a strong game-theoretic sense if and only if the arbiter is biased in favor of honest parties. We show this is inherent to any contract that achieves game-theoretic security for interesting trades. We consider a generalization of the contract with different ways of paying back the wagers, and we can instantiate it to make a tradeoff between security and the size of the wager. By relaxing the security notion such that parties have only weak incentive to behave honestly, we can replace the arbiter by a random coin toss protocol. We implement the contract in Ethereum and estimate the amortized cost of running the contract as 2-3 USD for the seller and 4-5 USD for the buyer.

In a recent paper Géraud-Stewart and Naccache \cite{gsn2021} (GSN) described an non-interactive process allowing a prover $\mathcal P$ to convince a verifier $\mathcal V$ that a modulus $n$ is the product of two randomly generated primes ($p,q$) of about the same size. A heuristic argument conjectures that $\mathcal P$ cannot control $p,q$ to make $n$ easy to factor. GSN's protocol relies upon elementary number-theoretic properties and can be implemented efficiently using very few operations. This contrasts with state-of-the-art zero-knowledge protocols for RSA modulus proper generation assessment. This paper proposes an alternative process applicable in settings where $\mathcal P$ co-generates a modulus $n=p_1q_1p_2q_2$ with a certification authority $\mathcal V$. If $\mathcal P$ honestly cooperates with $\mathcal V$, then $\mathcal V$ will only learn the sub-products $n_1=p_1q_1$ and $n_2=p_2q_2$. A heuristic argument conjectures that at least two of the factors of $n$ are beyond $\mathcal P$'s control. This makes $n$ appropriate for cryptographic use provided that \emph{at least one party} (of $\mathcal P$ and $\mathcal V$) is honest. This heuristic argument calls for further cryptanalysis.

Zero-knowledge (ZK) proofs with an optimal memory footprint have attracted a lot of attention, because such protocols can easily prove very large computation with a small memory requirement. Such ZK protocol only needs O(M) memory for both parties, where M is the memory required to verify the statement in the clear. In this paper, we propose several new ZK protocols in this setting, which improve the concrete efficiency and, at the same time, enable sublinear amortized communication for circuits with some notion of relaxed uniformity. 1. In the circuit-based model, where the computation is represented as a circuit over a field, our ZK protocol achieves a communication complexity of 1 field element per non-linear gate for any field size while keeping the computation very cheap. We implemented our protocol, which shows extremely high efficiency and affordability. Compared to the previous best-known implementation, we achieve 6×–7× improvement in computation and 3×– 7× improvement in communication. When running on intro-level AWS instances, our protocol only needs one US dollar to prove one trillion AND gates (or 2.5 US dollars for one trillion multiplication gates over a 61-bit field). 2. In the setting where part of the computation can be represented as a set of polynomials, we can achieve communication sublinear to the polynomial size: the communication only depends on the input size and the highest degree of all polynomials, independent of the number of polynomials and the number of multiplications in the polynomials. Using the improved ZK protocol, we can prove matrix multiplication with communication proportional to the input size, rather than the number of multiplications. Proving the multiplication of two 1024 × 1024 matrices, our implementation, with one thread and 1 GB of memory, only needs 10 seconds and communicates 25 MB, 35× faster than the state-of-the-art protocol Virgo that would need more than 140 GB of memory for the same task.

The subfield construction is one of the most promising methods to construct maximum distance separable (MDS) diffusion layers for block ciphers and cryptographic hash functions. In this paper, we give a generalization of this method and investigate the efficiency of our generalization. As a result, we provide several best MDS diffusions with respect to the number of XORs that the diffusion needs. For instance, we give (i) an involutory MDS diffusion $\mathbb{F}_{2^8}^{3} \rightarrow \mathbb{F}_{2^8}^{3}$ by 85 XORs and (ii) an involutory MDS diffusion $\mathbb{F}_{2^8}^{4} \rightarrow \mathbb{F}_{2^8}^{4}$ by 122 XORs, and hence present new records to the literature. Furthermore, we interpret the coding theoretical background of our generalization.

Logic access control enforces who can read and write data; the enforcement is typically performed by a fully trusted entity. At TCC 2016, Damg\aa rd et al. proposed Access Control Encryption (ACE) schemes where a predicate function decides whether or not users can read (decrypt) and write (encrypt) data, while the message secrecy and the users' anonymity are preserved against malicious parties. Subsequently, several ACE constructions with an arbitrary identity-based access policy have been proposed, but they have huge ciphertext and key sizes and/or rely on indistinguishability obfuscation. At IEEE S&P 2021, Wang and Chow proposed a Cross-Domain ACE scheme with constant-size ciphertext and arbitrary identity-based policy; the key generators are separated into two distinct parties, called Sender Authority and Receiver Authority. In this paper, we improve over their work with a novel construction that provides a more expressive access control policy based on attributes rather than on identities, the security of which relies on standard assumptions. Our generic construction combines Structure-Preserving Signatures, Non-Interactive Zero-Knowledge proofs, and Re-randomizable Ciphertext-Policy Attribute-Based Encryption schemes. Moreover, we propose an efficient scheme in which the sizes of ciphertexts and encryption and decryption keys are constant and thus independent of the number of receivers and their attributes. Our experiments demonstrate that not only is our system more flexible, but it also is more efficient and results in shorter decryption keys (reduced from about 100 to 47 bytes) and ciphertexts (reduced from about 1400 to 1047 bytes).

In 2020 Bernstein, De Feo, Leroux, and Smith presented a new odd-degree $\ell$-isogeny computation method called Velusqrt. This method has complexity $\tilde{O}(\sqrt{\ell})$, compared to the complexity of $\tilde{O}(\ell)$ of the classical Vélu method. In this paper application of the Velusqrt method to Huff's and general Huff's curves is presented. It is showed how to compute odd-degree isogeny on Huff's and general Huff's curves using Velusqrt algorithm and $x$-line arithmetic for different compression functions.

This paper introduces a practical evaluation procedure based on autoencoders for profiled side-channel analysis evaluations. An autoencoder is a learning model able to pre-process leakage traces improving in this way the guessing entropy. Nevertheless, this learning model's design should aim to code the leakage distribution to avoid relevant information being removed. For this reason, we propose an autoencoder built upon dilated convolutions. When using these learning models, the evaluation produces new assets, e.g., new versions of the dataset and new models based on learning algorithms. Our procedure comprises meaningful metrics and visualization techniques, namely signal-to-noise ratio and weight visualization, to evaluate those assets' effectiveness. After applying our procedure and our new autoencoder architecture to the ASCAD random key database, our results outperform state-of-the-art.

Deep learning represents a powerful set of techniques for profiling side-channel analysis. The results in the last few years show that neural network architectures like multilayer perceptron and convolutional neural networks give strong attack performance where it is possible to break targets protected with various countermeasures. Considering that deep learning techniques commonly have a plethora of hyperparameters to tune, it is clear that such top attack results can come with a high price in preparing the attack. This is especially problematic as the side-channel community commonly uses random search or grid search techniques to look for the best hyperparameters. In this paper, we propose to use reinforcement learning to tune the convolutional neural network hyperparameters. In our framework, we investigate the Q-Learning paradigm and develop two reward functions that use side-channel metrics. We mount an investigation on three commonly used datasets and two leakage models where the results show that reinforcement learning can find convolutional neural networks exhibiting top performance while having small numbers of trainable parameters. We note that our approach is automated and can be easily adapted to different datasets. Several of our newly developed architectures outperform the current state-of-the-art results. Finally, we make our source code publicly available. https://github.com/AISyLab/Reinforcement-Learning-for-SCA

Relay attacks pose a serious security threat to wireless systems, such as, contactless payment systems, keyless entry systems, or smart access control systems. Distance bounding protocols, which allow an entity to not only authenticate another entity but also determine whether it is physically close by, effectively mitigate relay attacks. However, secure implementation of distance bounding protocols, especially of the time critical challenge-response phase, has been a challenging task. In this paper, we design and implement a secure and accurate distance bounding protocol based on Narrow-Band signals, such as Bluetooth Low Energy (BLE), to particularly mitigate relay attacks. Narrow-Band ranging, specifically, phase-based ranging, enables accurate distance measurement, but it is vulnerable to phase rollover attacks. In our solution, we mitigate phase rollover attacks by also measuring time-of-flight (ToF) to detect the delay introduced by such attacks. Therefore, our protocol effectively combines the best of both worlds: phase-based ranging for accuracy and time-of-flight (ToF) measurement for security. To demonstrate the feasibility and practicality of our solution, we prototype it on NXP KW36 BLE chips and evaluate its performance and relay attack resistance. The obtained precision and accuracy of the presented ranging solution are 2.5 cm and 30 cm, respectively, in wireless measurements.

We propose a privacy-preserving Naive Bayes classifier and apply it to the problem of private text classification. In this setting, a party (Alice) holds a text message, while another party (Bob) holds a classifier. At the end of the protocol, Alice will only learn the result of the classifier applied to her text input and Bob learns nothing. Our solution is based on Secure Multiparty Computation (SMC). Our Rust implementation provides a fast and secure solution for the classification of unstructured text. Applying our solution to the case of spam detection (the solution is generic, and can be used in any other scenario in which the Naive Bayes classifier can be employed), we can classify an SMS as spam or ham in less than 340ms in the case where the dictionary size of Bob's model includes all words ($n = 5200$) and Alice's SMS has at most $m = 160$ unigrams. In the case with $n = 369$ and $m = 8$ (the average of a spam SMS in the database), our solution takes only 21ms.

In this work we introduce Banquet, a digital signature scheme with post-quantum security, constructed using only symmetric-key primitives. The design is based on the MPC-in-head paradigm also used by Picnic (CCS 2017) and BBQ (SAC 2019). Like BBQ, Banquet uses only standardized primitives, namely AES and SHA-3, but signatures are more than 50% shorter, making them competitive with Picnic (which uses a non-standard block cipher to improve performance). The MPC protocol in Banquet uses a new technique to verify correctness of the AES S-box computations, which is efficient because the cost is amortized with a batch verification strategy. Our implementation and benchmarks also show that both signing and verification can be done in under 10ms on a current x64 CPU. We also explore the parameter space to show the range of trade-offs that are possible with the Banquet design, and show that Banquet can nearly match the signature sizes possible with Picnic (albeit with slower, but still practical run times) or have speed within a factor of two of Picnic (at the cost of larger signatures).

Masking is a popular technique to protect cryptographic implementations against side-channel attacks and comes in several variants including Boolean and arithmetic masking. Some masked implementations require conversion between these two variants, which is increasingly the case for masking of post-quantum encryption and signature schemes. One way to perform Arithmetic to Boolean (A2B) mask conversion is a table-based approach first introduced by Coron and Tchulkine, and later corrected and adapted by Debraize in CHES 2012. In this work, we show both analytically and experimentally that the table-based A2B conversion algorithm proposed by Debraize does not achieve the claimed resistance against differential power analysis due to a non-uniform masking of an intermediate variable. This non-uniformity is hard to find analytically but leads to clear leakage in experimental validation. To address the non-uniform masking issue, we propose two new A2B conversions: one that maintains efficiency at the cost of additional memory and one that trades efficiency for a reduced memory footprint. We give analytical and experimental evidence for their security, and will make their implementations, which are shown to be free from side-channel leakage in 100.000 power traces collected on the ARM Cortex-M4, available online. We conclude that when designing side-channel protection mechanisms, it is of paramount importance to perform both a theoretical analysis and an experimental validation of the method.

Block cipher resistance against differential cryptanalysis is commonly assessed by counting the number of active substitution boxes (S-boxes) using search algorithms or mathematical solvers that incur high computational costs. In this paper, we propose an alternative approach using deep neural networks to predict the number of active S-boxes, trading off exactness for real-time efficiency as the bulk of computational work is brought over to pre-processing (training). Active S-box prediction is framed as a regression task whereby neural networks are trained using features such as input and output differences, number of rounds, and permutation pattern. We first investigate the feasibility of the proposed approach by applying it on a reduced (4-branch) generalized Feistel structure (GFS) cipher. Apart from optimizing a neural network architecture for the task, we also explore the impact of each feature and its representation on prediction error. We then extend the idea to 64-bit GFS ciphers by first training neural networks using data from five different ciphers before using them to predict the number of active S-boxes for TWINE, a lightweight block cipher. The best performing model achieved the lowest root mean square error of 1.62 and R$^2$ of 0.87, depicting the feasibility of the proposed approach.

Cryptographic offloading to hardware is a hot research topic promising accelerated execution time and improved security compared to the software counterpart. However, hardware design and production is a lengthy process which enquires significant financial resources and technical expertise. Our research paper focuses on elliptic curve cryptography, specifically Diffie-Hellman, and on minimizing these deficiencies by highlighting solutions to map this class of algorithms to hardware description. The insights are not limitative and can be equally applied to other cryptographic primitives. The resulting design uses few hardware resources, has low power consumption, is easy to interface with the software and can be implemented on cheap FPGAs. Index Terms—elliptic curves, cryptography, diffie-hellman, FPGA, hardware security, high level synthesis

NIST's post-quantum standardization effort very recently entered its final round. This makes studying the implementation-security aspect of the remaining candidates an increasingly important task, as such analyses can aid in the final selection process and enable appropriately secure wider deployment after standardization. However, lattice-based key-encapsulation mechanisms (KEMs), which are prominently represented among the finalists, have thus far received little attention when it comes to fault attacks. Interestingly, many of these KEMs exhibit structural similarities. They can be seen as variants of the encryption scheme of Lyubashevsky, Peikert, and Rosen, and employ the Fujisaki-Okamoto transform (FO) to achieve CCA2 security. The latter involves re-encrypting a decrypted plaintext and testing the ciphertexts for equivalence. This corresponds to the classic countermeasure of computing the inverse operation and hence prevents many fault attacks. In this work, we show that despite this inherent protection, practical fault attacks are still possible. We present an attack that requires a single instruction-skipping fault in the decoding process, which is run as part of the decapsulation. After observing if this fault actually changed the outcome (effective fault) or if the correct result is still returned (ineffective fault), we can set up a linear inequality involving the key coefficients. After gathering enough of these inequalities by faulting many decapsulations, we can solve for the key using a bespoke statistical solving approach. As our attack only requires distinguishing effective from ineffective faults, various detection-based countermeasures, including many forms of double execution, can be bypassed. We apply this attack to Kyber and NewHope, both of which belong to the aforementioned class of schemes. Using fault simulations, we show that, e.g., 6,500 faulty decapsulations are required for full key recovery on Kyber512. To demonstrate practicality, we use clock glitches to attack Kyber running on a Cortex M4. As we argue that other schemes of this class, such as Saber, might also be susceptible, the presented attack clearly shows that one cannot rely on the FO transform's fault deterrence and that proper countermeasures are still needed.

Cryptography is used since the Antiquity to securely transmit messages. Thanks to a key that is shared between parties, the armies have been able to securely send commands and information to a distant unit. In the middle of the Twentieth Century, cryptography has experienced a drastic evolution and has become even more widespread, thanks to the development of computer science and the democratization of the digitization of the data transmitted between people. In particular, cryptologists Whitfield Diffie and Martin Hellman invented in 1976 the concept of public key cryptography, revolutionizing the way data can be protected, and paving the way to a new kind of cryptography that can be used for much more than data confidentiality. CYBERCRYPT is a collaborative and educational game that allows people to understand basic cryptographic mechanisms. It allows to discover from the oldest techniques (Scytale, Caesar and Vernam's encryption, Enigma machine) to most recent ones, currently implemented in our daily transactions (electronic signature, key exchange, etc.). CYBERCRYPT allows, through several rich and comprehensive workshops, to discover the different techniques used in cryptography, and also highlights the crucial importance of cryptography to protect our digital daily life.

We generalize Zhandry's compressed oracle technique to invertible random permutations. (That is, to a quantum random oracle where the adversary has access to a random permutation and its inverse.) This enables security proofs with lazy sampling, i.e., where oracle outputs are chosen only when needed. As an application of our technique, we show the collision-resistance of the sponge construction based on invertible permutations. In particular, this shows the collision-resistance of SHA3 (in the random oracle model).

Every user can be identified online by a unique string used for email or nickname on some of the many platforms out there. IBE systems propose a simple cryptosystem in which the public key system can be omitted by using the unique string as public identification. In this paper we present a minimal email application that uses Clifford Cocks’ proposed IBE scheme. We analyze the impact of using it inside our application and how it can be improved to better fit the need of nowadays applications.

Building on the Gennaro & Goldfeder and Lindell & Nof protocols (CCS '18), we present threshold ECDSA protocols, for any number of signatories and any threshold, that improve as follows over the state of the art: * Only the last round of our protocols requires knowledge of the message, and the other rounds can take place in a preprocessing stage, lending to a non-interactive threshold ECDSA protocol. * Our protocols withstand adaptive corruption of signatories. Furthermore, they include a periodic refresh mechanism and offer full proactive security. * Our protocols realize an ideal threshold signature functionality within the UC framework, in the global random oracle model, assuming Strong RSA, DDH, semantic security of the Paillier encryption, and a somewhat enhanced variant of existential unforgeability of ECDSA. * Both protocols achieve accountability by identifying corrupted signatories in case of failure to generate a valid signature. The protocols provide a tradeoff between the number of rounds to generate a signature and the computational and communication overhead for the identification of corrupted signatories. Namely: * For one protocol, signature generation takes only 4 rounds (down from the current state of the art of 8 rounds), but the identification process requires computation and communication that is quadratic in the number of parties. * For the other protocol, the identification process requires computation and communication that is only linear in the number of parties, but signature generation takes 7 rounds. These properties (low latency, compatibility with cold-wallet architectures, proactive security, identifiable abort and composable security) make the two protocols ideal for threshold wallets for ECDSA-based cryptocurrencies.

The security of cryptographic primitives and protocols against adversaries that are allowed to make adaptive choices (e.g., which parties to corrupt or which queries to make) is notoriously difficult to establish. A broad theoretical framework was introduced by Jafargholi et al. [Crypto'17] for this purpose. In this paper we initiate the study of lower bounds on loss in adaptive security for certain cryptographic protocols considered in the framework. We prove lower bounds that almost match the upper bounds (proven using the framework) for proxy re-encryption, prefix-constrained PRFs and generalized selective decryption, a security game that captures the security of certain group messaging and broadcast encryption schemes. Those primitives have in common that their security game involves an underlying graph that can be adaptively built by the adversary. Some of our lower bounds only apply to a restricted class of black-box reductions which we term "oblivious" (the existing upper bounds are of this restricted type), some apply to the broader but still restricted class of non-rewinding reductions, while our lower bound for proxy re-encryption applies to all black-box reductions. The fact that some of our lower bounds seem to crucially rely on obliviousness or at least a non-rewinding reduction hints to the exciting possibility that the existing upper bounds can be improved by using more sophisticated reductions. Our main conceptual contribution is a two-player multi-stage game called the Builder-Pebbler Game. We can translate bounds on the winning probabilities for various instantiations of this game into cryptographic lower bounds for the above-mentioned primitives using oracle separation techniques.

In this paper, we contribute a comprehensive resource analysis for widely used cryptographic primitives across different off-the-shelf IoT platforms, and quantify the performance impact of crypto-hardware. This work builds on the newly designed crypto-subsystem of the IoT operating system RIOT, which provides seamless crypto support across software and hardware components. Our evaluations show that (i) hardware-based crypto outperforms software by considerably over 100 %, which is crucial for nodal lifetime. Despite, the memory consumption typically increases moderately. (ii) Hardware diversity, driver design, and software implementations heavily impact resource efficiency. (iii) External crypto-chips operate slowly on symmetric crypto-operations, but provide secure write-only memory for private credentials, which is unavailable on many platforms.

Correlation intractability is an important cryptographic notion that is used for establishing soundness of Fiat-Shamir over public-coin protocols. In this work, we show that symmetric-key cryptography is neither sufficient nor essential for obtaining correlation intractability. Specifically, we prove a bidirectional fully black-box separation between one-way functions (OWFs) and correlation-intractable hash (CIH). In the first direction, we show that CIH for relations as simple as degree-3 polynomials cannot be based solely on OWFs. In the other direction, we show that there exists no fully black-box construction of OWF from CIH for all sparse relations. Consequently, we infer that computationally sound Fiat-Shamir over any specific constant-round proof system does not necessarily require one-way functions.

In this paper, we present a new concept named the basic function. By the study of the basic function, we find the $O(n)$-time algorithm to calculate the probability or correlation for some property of Modulo $2^n$, including the difference-linear connective correlation coefficients, the linear approximation correlation coefficients, the differential probability, difference-boomerange connective probability, boomerange connective probability, boomerange-difference connective probability, etc.

In this tech report, we introduce a novel countermeasure against physical attacks: Inertial hardware security modules (iHSMs). Conventional systems have in common that they try to detect attacks by crafting sensors responding to increasingly minute manipulations of the monitored security boundary or volume. Our approach is novel in that we reduce the sensitivity requirement of security meshes and other sensors and increase the complexity of any manipulations by rotating the security mesh or sensor at high speed—thereby presenting a moving target to an attacker. Attempts to stop the rotation are easily monitored with commercial MEMS accelerometers and gyroscopes. Our approach leads to a HSM that can easily be built from off-the-shelf parts by any university electronics lab, yet offers a level of security that is comparable to commercial HSMs.

Programmers are used to the rounding and error properties of IEEE double precision arithmetic, however in secure computing paradigms, such as provided by Multi-Party Computation (MPC), usually a different form of approximation is provided for real number arithmetic. We compare the two standard variants using for LSSS-based MPC, with an implementation of IEEE compliant double precision using binary circuit-based MPC. We compare the relative performance, and conclude that the addition cost of IEEE compliance maybe too great for some applications. Thus in the secure domain standards bodies may wish to examine a different form of real number approximations.

Lattice-based cryptography, the study of cryptographic primitives whose security is based on the hardness of so-called lattice problems, has taken center stage in cryptographic research in recent years. It potentially offers favorable security features, even against quantum algorithms. One of the main obstacles for wide adoption of this type of cryptography is its unsatisfactory efficiency. To address this point, efficient lattice-based cryptography usually relies on the intractability of problems on lattices with additional algebraic structure (such as so-called ideal-lattices or module-lattices). It is an important open question to evaluate the hardness of such lattice problems, and their relation to the hardness of problems on unstructured lattices. It is a known fact that an unstructured lattice, which is simply an additive discrete group in Euclidean space, can be cast as an ideal-lattice in some \emph{order} of a number field (and thus, in a rather trivial sense, that ideals in orders are as general as unstructured lattices). However, it is not known whether this connection can be used to imply useful hardness results for structured lattices, or alternatively new algorithmic techniques for unstructured lattices. In this work we establish a gradient of hardness for the Order-LWE problem (a generalization of the well known Ring-LWE problem), as it varies over orders in a number field. Furthermore, we show that, in every number field, there are certain orders such that the corresponding Order-LWE problem is at least as hard as the (unstructured) LWE problem. So in general one should not hope to solve (any) Order-LWE more efficiently than LWE. However, we show that this connection holds in orders that are very ``skewed'' and hence, perhaps, irrelevant for improving efficiency in cryptographic applications. We further improve the hardness result for Order-LWE, to include \textit{all} ideal lattices, closing a gap left in prior work. This establishes a direct connection between problems on unstructured lattices and the structured problem of Order-LWE.

This paper describes a non-interactive process allowing a prover to convince a verifier that a modulus $n$ is the product of two primes ($p,q$) of about the same size. A further heuristic argument conjectures that $p-1$ and $q-1$ have sufficiently large prime factors for cryptographic applications. The new protocol relies upon elementary number-theoretic properties and can be implemented efficiently using very few operations. This contrasts with state-of-the-art zero-knowledge protocols for RSA modulus proper generation assessment. The heuristic argument at the end of our construction calls for further cryptanalysis by the community and is, as such, an interesting research question in its own right.

Our purpose is to compare how much the F5 algorithm can gain in efficiency compared to the F4 algorithm. This can be achieve as the F5 algorithm uses the concept of signatures to foresee potential useless computation which the F4 algorithm might make represented by zero rows in the reduction of a large matrix. We experimentally show that this is a modest increase in efficiency for the parameters we tested.

Often times, the ability to distinguish between random data and a public key can leads to an attack against the cryptosystem itself. In this paper, we will show experimentally a very efficient distinguisher based on the distribution of ranks of the symmetric matrices associated with the central map in the multivariate cryptosystem HFE when the degree D of the central map is very small.

This report presents area, throughput, and energy results for synthesizing the NIST Lightweight Cryptography Round 2 candidates on five ASIC cell libraries using two different synthesis tool suites.

A gadget decomposition algorithm is commonly used in many advanced lattice cryptography applications which support homomorphic operation over ciphertexts to control the noise growth. For a special structure of a gadget, the algorithm is digit decomposition. If such algorithm samples from a subgaussian distribution, that is, the output is randomized, it gives more benefits on output quality. One of important advantages is Pythagorean additivity which makes resulting noise contained in a ciphertext grow much less than naive digit decomposition. Therefore, the error analysis becomes cleaner and tighter than the use of other measures like $\ell_2$ and $\ell_\infty$. Even though such advantage can also be achieved by the use of discrete Gaussian sampling, it is not preferable for practical performance due to large factor in resulting noise and the complex computation of exponential function, whereas more relaxed probability condition is required for subgaussian distribution. Nevertheless, subgaussian sampling has barely received an attention so far, thus no practical algorithms was implemented before an efficient algorithm is presented by Genis et al., recently. In this paper, we present a practically efficient gadget decomposition algorithm where output follows a subgaussian distribution. We parallelize the existing practical subgaussian gadget decomposition algorithm, using bounded uniform distribution. Our algorithm is divided into two independent subalgorithms and only one algorithm depends on input. Therefore, the other algorithm can be considered as pre-computation. As an experimental result, our algorithm performs over 50\% better than the existing algorithm.

The voting process is fundamental to any democratic system – be it a country or a company's boardroom. Nearly forty years ago, e-voting was theoretically perceived as a more efficient replacement of the widely existing paper-based traditional voting system. Several research works have been carried out to ensure more security and efficiency in different settings for e-voting schemes. One of the fundamental building blocks of e-voting systems is the public Bulletin Board through which several security properties are achieved. After introducing Blockchain technology, the bulletin board has found a new meaningful and concrete way of distributed way of implementation. Before Blockchain technology, either such a system was theoretically assumed or perceived as a public broadcast channel with memory. In this survey, we present a concise survey of bulletin boards' evolution with a typical application to the e-voting systems. We note that bulletin boards have other applications in other joint computation areas. Still, we are interested in evolving e-voting systems based on bulletin board and how several desired security properties are realized through bulletin boards.

In the recent years, many research lines on Functional Encryption (FE) have been suggested and studied regarding the functionality, security, or efficiency. Nevertheless, an open problem on a basic functionality, the single-input inner-product (IPFE), remains: can IPFE be instantiated based on the Ring Learning With Errors (RLWE) assumption? The RLWE assumption provides quantum-resistance security while in comparison with LWE assumption gives significant performance and compactness gains. In this paper we present the first RLWE-based IPFE scheme. We carefully choose strategies in the security proofs to optimize the size of parameters. More precisely, we develop two new results on ideal lattices. The first result is a variant of Ring-LWE, that we call multi-hint extended Ring-LWE, where some hints on the secret and the noise are given. We present a reduction from RLWE problem to this variant. The second tool is a special form of Leftover Hash Lemma (LHL) over rings, known as Ring-LHL. To demonstrate the efficiency of our scheme we provide an optimized implementation of RLWE-based IPFE scheme and show its performance on a practical use case. We further present new compilers that, combined with some existing ones, can transfer a single-input FE to its (identity-based, decentralized) multi-client variant with linear size of the ciphertext (w.r.t the number of clients).

Binarized Neural Networks (BNN) provide efficient implementations of Convolutional Neural Networks (CNN). This makes them particularly suitable to perform fast and memory-light inference of neural networks running on resource-constrained devices. Motivated by the growing interest in CNN-based biometric recognition on potentially insecure devices, or as part of strong multi-factor authentication for sensitive applications, the protection of BNN inference on edge devices is rendered imperative. We propose a new method to perform secure inference of BNN relying on secure multiparty computation. While preceding papers offered security in a semi-honest setting for BNN or malicious security for standard CNN, our work yields security with abort against one malicious adversary for BNN by leveraging on Replicated Secret Sharing (RSS) for an honest majority with three computing parties. Experimentally, we implement BaNNeRS on top of MP-SPDZ and compare it with prior work over binarized models trained for MNIST and CIFAR10 image classification datasets. Our results attest the efficiency of BaNNeRS as a privacy-preserving inference technique.

Metadata from voice calls, such as the knowledge of who is communicating with whom, contains rich information about people’s lives. Indeed, it is a prime target for powerful adversaries such as nation states. Existing systems that hide voice call metadata either require trusted intermediaries in the network or scale to only tens of users. This paper describes the design, implementation, and evaluation of Addra, the first system for voice communication that hides metadata over fully untrusted infrastructure and scales to tens of thousands of users. At a high level, Addra follows a template in which callers and callees deposit and retrieve messages from private mailboxes hosted at an untrusted server. However, Addra improves message latency in this architecture, which is a key performance metric for voice calls. First, it enables a caller to push a message to a callee in two hops, using a new way of assigning mailboxes to users that resembles how a post office assigns PO boxes to its customers. Second, it innovates on the underlying cryptographic machinery and constructs a new private information retrieval scheme, FastPIR, that reduces the time to process oblivious access requests for mailboxes. An evaluation of Addra on a cluster of 80 machines on AWS demonstrates that it can serve 32K users with a 99-th percentile message latency of 726 ms—a 7× improvement over a prior system for text messaging in the same threat model.

In this paper, we show how to apply Montgomery multiplication to the tag tracing variant of the Pollard's rho algorithm applied to prime order fields. This combines the advantages of tag tracing with those of Montgomery multiplication. In particular, compared to the previous version of tag tracing, the use of Montgomery multiplication entirely eliminates costly modular reductions and replaces these with much more efficient divisions by a suitable power of two.

The random oracle methodology has proven to be a powerful tool for designing and reasoning about cryptographic schemes. In this paper, we focus on the basic problem of correcting faulty—or adversarially corrupted—random oracles, so that they can be confidently applied for such cryptographic purposes. We prove that a simple construction can transform a “subverted” random oracle—which disagrees with the original one at a small fraction of inputs—into an object that is indifferentiable from a random function, even if the adversary is made aware of all randomness used in the transformation. Our results permit future designers of cryptographic primitives in typical kleptographic settings (i.e., those permitting adversaries that subvert or replace basic cryptographic algorithms) to use random oracles as a trusted black box.

The potential development of large-scale quantum computers is raising concerns among IT and security research professionals due to their ability to solve (elliptic curve) discrete logarithm and integer factorization problems in polynomial time. This would jeopardize IT security as we know it. In this work, we investigate two quantum-safe, hash-based signature schemes published by the Internet Engineering Task Force and submitted to the National Institute of Standards and Technology for use in secure boot. We evaluate various parameter sets for the use-case in question and we prove that post-quantum signatures with less than one second signing and less than 10ms verification would not have material impact (less than1‰) on secure boot. We evaluate the hierarchical design of these signatures in hardware-based and virtual secure boot. In addition, we develop Hardware Description Language code and show that the code footprint is just a few kilobytes in size which would fit easily in almost all modern FPGAs. We also analyze and evaluate potential challenges for integration in existing technologies and we discuss considerations for vendors embarking on a journey of image signing with hash-based signatures.

Tropical linear algebra has been recently put forward by Grigoriev and Shpilrain ~\cite{grigoriev2014tropical,grigoriev2018tropical} as a promising platform for the implementation of protocols of Diffie-Hellman and Stickel type. Based on the CSR expansion of tropical matrix powers, we suggest a simple algorithm for the following tropical discrete logarithm problem: ``Given that $A=V\otimes F^{\otimes t}$ for a unique $t$ and matrices $A$, $V$, $F$ of appropriate dimensions, find this $t$.'' We then use this algorithm to suggest a simple attack on a protocol based on the tropical semidirect product. The algorithm and the attack are guaranteed to work in some important special cases and are shown to be efficient in our numerical experiments.

We give secure parameter suggestions to use sparse secret vectors in LWE based encryption schemes. This should replace existing security parameters, because homomorphic encryption(HE) schemes use quite different variables from the existing parameters. In particular HE schemes using sparse secrets should be supported by experimental analysis, here we summarize existing attacks to be considered and security levels for each attacks. Based on the analysis and experiments, we compute optimal scaling factors for CKKS.

We describe the binary numeral tree—a type of binary tree uniquely suited to processing unbounded streams of data—and present a number of algorithms for efficiently constructing and verifying Merkle proofs within such trees. Specifically, we present existence proofs for single leaves, for a contiguous range of leaves, and for multiple disjoint ranges. We also introduce Merkle "diff" proofs, which assert that an arbitrary modification was correctly applied to an existing tree. Each algorithm, operating on a tree with $n$ leaves and $k$ disjoint proof ranges, requires $\mathcal{O}(\log_2(n))$ space and $\mathcal{O}(n)$ time, and yields proofs of size $\mathcal{O}(k\log_2 (n))$. Furthermore, each algorithm operates in streaming fashion, requiring only a single in-order pass over the leaf data.

Being based on a sound theoretical basis, masking schemes are commonly applied to protect cryptographic implementations against Side-Channel Analysis (SCA) attacks. Constructing SCA-protected AES, as the most widely deployed block cipher, has been naturally the focus of several research projects, with a direct application in industry. The majority of SCA-secure AES implementations introduced to the community opted for low area and latency overheads considering Application-Specific Integrated Circuit (ASIC) platforms. Albeit a few, those which particularly targeted Field Programmable Gate Arrays (FPGAs) as the implementation platform yield either a low throughput or a not-highly secure design. In this work, we fill this gap by introducing first-order glitch-extended probing secure masked AES implementations highly optimized for FPGAs, which support both encryption and decryption. Compared to the state of the art, our designs efficiently map the critical non-linear parts of the masked S-box into the built-in Block RAMs (BRAMs). The most performant variant of our constructions accomplishes five first-order secure AES encryptions/decryptions simultaneously in 50 clock cycles. Compared to the equivalent state-of-the-art designs, this leads to at least 70% reduction in utilization of FPGA resources (slices) at the cost of occupying BRAMs. Last but not least, we provide a wide range of such secure and efficient implementations supporting a large set of applications, ranging from low-area to high-throughput.

The modern financial world has seen a significant rise in the use of cryptocurrencies in recent years, partly due to the convincing lures of anonymity promised by these schemes. Bitcoin, despite being considered as the most widespread among all, is claimed to have significant lapses in relation to its anonymity. Unfortunately, studies have shown that many cryptocurrency transactions can be traced back to their corresponding participants through the analysis of publicly available data, to which the cryptographic community has responded by proposing new constructions with improved anonymity claims. Nevertheless, the absence of a common metric for evaluating the level of anonymity achieved by these schemes has led to a number of disparate ad hoc anonymity definitions, making comparisons difficult. The multitude of these notions also hints at the surprising complexity of the overall anonymity landscape. In this study, we introduce such a common framework to evaluate the nature and extent of anonymity in (crypto)currencies and distributed transaction systems, irrespective of their implementation. As such, our work lays the foundation for formalising security models and terminology across a wide range of anonymity notions referenced in the literature, while showing how ``anonymity'' itself is a surprisingly nuanced concept.

Blockchains suffer from a critical scalability problem where traditionally each network node maintains all network state, including records since the establishment of the blockchain. Sketches are popular hash-based data structures used to represent a large amount of data while supporting particular queries such as on set membership, cardinality estimation and identification of large elements. Often, to achieve time and memory savings, sketches allow potential inaccuracies in answers to the queries. The design of popular blockchain networks such as Bitcoin and Ethereum makes use of sketches for various tasks such as summarization of transaction blocks or declaring the interests of light nodes. Similarly, they seem natural to deal with the size of the state in blockchains. In this paper, we study existing and potential future applications of sketches in blockchains. We first summarize current blockchain use cases of sketches. Likewise, we explore how this coupling can be generalized to a wider range of sketches and additional functionalities. In particular, we explain how sketches can detect anomalies based on efficient an summary of the state or traffic.

In $2$-party Circuit-based Private Set Intersection (Circuit-PSI), $P_0$ and $P_1$ hold sets $\mathsf{S}_{0}$ and $\mathsf{S}_{1}$ respectively and wish to securely compute a function $f$ over the set $\mathsf{S}_{0} \cap \mathsf{S}_{1}$ (e.g., cardinality, sum over associated attributes, or threshold intersection). Following a long line of work, Pinkas et al. ($\mathsf{PSTY}$, Eurocrypt 2019) showed how to construct a concretely efficient Circuit-PSI protocol with linear communication complexity. However, their protocol requires super-linear computation. In this work, we construct concretely efficient Circuit-PSI protocols with linear computational and communication cost. Further, our protocols are more performant than the state-of-the-art, $\mathsf{PSTY}$ -- we are $\approx 2.3\times$ more communication efficient and are up to $2.8\times$ faster. We obtain our improvements through a new primitive called Relaxed Batch Oblivious Programmable Pseudorandom Functions ($\mathsf{RBOPPRF}$) that can be seen as a strict generalization of Batch $\mathsf{OPPRF}$s that were used in $\mathsf{PSTY}$. We believe that this primitive could be of independent interest.

Identity-based encryption (IBE), introduced by Shamir, eliminates the need for public-key infrastructure. The sender can simply encrypt a message by using the recipient's identity (such as email or IP address) without needing to look up the public key. In particular, when ciphertexts of an IBE do not reveal recipient's identity, this scheme is known as an anonymous IBE scheme. Recently, Blazy et al. (ARES '19) analyzed the trade-off between public safety and unconditional privacy in anonymous IBE and introduced a new notion that incorporates traceability into anonymous IBE, called anonymous IBE with traceable identities (AIBET). However, their construction is based on the discrete logarithm assumption, which is insecure in the quantum era. In this paper, we first formalize the consistency of tracing key of the AIBET scheme to ensure that a ciphertext cannot be traced with the use of wrong tracing keys. Subsequently, we present a generic formulation concept that can be used to transform structure-specific lattice-based anonymous IBE schemes into an AIBET. Finally, we apply this concept to Katsumata and Yamada's compact anonymous IBE scheme (Asiacrypt '16) to obtain the first quantum-resistant AIBET scheme that is adaptively secure under the ring learning with errors assumption without random oracle.

Protecting secrets is a key challenge in our contemporary information-based era. In common situations, however, revealing secrets appears unavoidable, for instance, when identifying oneself in a bank to retrieve money. In turn, this may have highly undesirable consequences in the unlikely, yet not unrealistic, case where the bank’s security gets compromised. This naturally raises the question of whether disclosing secrets is fundamentally necessary for identifying oneself, or more generally for proving a statement to be correct. Developments in computer science provide an elegant solution via the concept of zero-knowledge proofs: a prover can convince a verifier of the validity of a certain statement without facilitating the elaboration of a proof at all. In this work, we report the experimental realisation of such a zero-knowledge protocol involving two separated verifier-prover pairs. Security is enforced via the physical principle of special relativity, and no computational assumption (such as the existence of one-way functions) is required. Our implementation exclusively relies on off-the-shelf equipment and works at both short (60 m) and long distances (400 m) in about one second. This demonstrates the practical potential of multi-prover zero-knowledge protocols, promising for identification tasks and blockchain-based applications such as cryptocurrencies or smart contracts.

Key distribution protocols deal with generating, exchanging, and storing information (especially shared keys). In this paper, we compare three different types of protocols: classical, quantum key distribution, and blockchain-based protocols, with examples from each category, presenting the particularities and challenges of each one, including solutions and the impact of these protocols.

This paper studies zero-knowledge SNARKs for NP, where the prover incurs $O(N)$ finite field operations to prove the satisfiability of an $N$-sized R1CS instance. We observe that recent work of Bootle, Chiesa, and Groth (BCG, TCC 20) provides a polynomial commitment scheme that, when combined with the linear-time interactive proof system of Spartan~(CRYPTO 20), yields linear-time IOPs and SNARKs for R1CS. Specifically, for security parameter $\lambda$, and for an $N$-sized R1CS instance over a field of size $\exp(\lambda)$ and fixed $\epsilon > 0$, the prover incurs $O(N)$ finite field operations to produce a proof of size $O_\lambda(N^\epsilon)$ that can be verified in $O_\lambda(N^\epsilon)$---after a one-time preprocessing step, which requires $O(N)$ finite field operations. This reestablishes the main result of BCG. Arguably, our approach is conceptually simpler and more direct. Additionally, the polynomial commitment scheme that we distill from BCG is of independent interest; it improves over the prior state of the art by offering the first scheme where the time to commit to an $N$-sized polynomial is $O(N)$ finite field operations. We further observe that one can render the aforementioned SNARK zero knowledge and reduce the proof size and verifier time to polylogarithmic---while maintaining a linear-time prover---by outsourcing the verifier's work via one layer of proof composition with an existing zkSNARK as the ``outer'' proof system. A similar result can be derived from recent work of Bootle, Chiesa, and Liu (ePrint 2020/1527). We implement the aforementioned polynomial commitment scheme with $\epsilon = 1/2$ and combine it with Spartan’s interactive proof system to obtain a SNARK for R1CS. We refer to this combination as Cerberus. It uses Reed-Solomon codes in the polynomial commitment scheme, and hence the prover is not asymptotically linear-time. Nonetheless, Cerberus features the fastest known prover (the only exception is Spartan when proving large instances over 256-bit fields), and is plausibly post-quantum secure.

Nowadays, genomic sequencing has become much more affordable for many people and, thus, many people own their genomic data in a digital format. Having paid for genomic sequencing, they want to make use of their data for different tasks that are possible only using genomics, and they share their data with third parties to achieve these tasks, e.g., to find their relatives in a genomic database. As a consequence, more genomic data get collected worldwide. The upside of the data collection is that unique analyses on these data become possible. However, this raises privacy concerns because the genomic data uniquely identify their owner, contain sensitive data about his/her risk for getting particular diseases, and even sensitive information about his/her family members. In this paper, we introduce EPISODE - a highly efficient privacy-preserving protocol for Similar Sequence Queries (SSQs), which can be used for finding genetically similar individuals in an outsourced genomic database, i.e., securely aggregated from data of multiple institutions. Our SSQ protocol is based on the edit distance approximation by Asharov et al. (PETS'18), which we further optimize and extend to the outsourcing scenario. We improve their protocol by using more efficient building blocks and achieve a 5-6x run-time improvement compared to their work in the same two-party scenario. Recently, Cheng et al. (ASIACCS'18) introduced protocols for outsourced SSQs that rely on homomorphic encryption. Our new protocol outperforms theirs by more than factor 24000x in terms of run-time in the same setting and guarantees the same level of security. In addition, we show that our algorithm scales for practical database sizes by querying a database that contains up to a million short sequences within a few minutes, and a database with hundreds of whole-genome sequences containing 75 million alleles each within a few hours.

The Google Titan Security Key is a FIDO U2F hardware device proposed by Google (available since July 2018) as a two-factor authentication token to sign in to applications (e.g. your Google account). We present here a side-channel attack that targets the Google Titan Security Key’s secure element (the NXP A700X chip) by the observation of its local electromagnetic radiations during ECDSA signatures (the core cryptographic operation of the FIDO U2F protocol). This work shows that an attacker can clone a legitimate Google Titan Security Key. To understand the NXP ECDSA implementation, find a vulnerability and design a key-recovery attack, we had to make a quick stop on Rhea (NXP J3D081 JavaCard smartcard). Freely available on the web, this product looks very much like the NXP A700X chip and uses the same cryptographic library. Rhea, as an open JavaCard platform, gives us more control to study the ECDSA implementation. We could then show that the electromagnetic side-channel signal bears partial information about the ECDSA ephemeral key. The sensitive information is recovered with a non-supervised machine learning method and plugged into a customized lattice-based attack scheme. Finally, 4000 ECDSA observations were enough to recover the (known) secret key on Rhea and validate our attack process. It was then applied on the Google Titan Security Key with success (this time with 6000 observations) as we were able to extract the long term ECDSA private key linked to a FIDO U2F account created for the experiment. Cautionary Note: Two-factor authentication tokens (like FIDO U2F hardware devices) primary goal is to fight phishing attacks. Our attack requires physical access to the Google Titan Security Key, expensive equipment, custom software, and technical skills. Thus, as far as the work presented here goes, it is still safer to use your Google Titan Security Key or other impacted products as FIDO U2F two-factor authentication token to sign in to applications rather than not using one. Nevertheless, this work shows that the Google Titan Security Key (and other impacted products) would not avoid unnoticed security breach by attackers willing to put enough effort into it. Users that face such a threat should probably switch to other FIDO U2F hardware security keys, where no vulnerability has yet been discovered.

Electronic voting consists of the methods that use an electronic system in the process of recording, counting or transmitting votes. It is relatively a new concept used in the democratic processes and especially in the context of COVID19. It’s aim is to reduce errors and to improve the integrity of the election process. In this paper, we provide a review of the existing systems used in Europe. Initially, we mention the factors that influence the adoption of such systems at a large scale. We further describe the systems used in Russia (Moscow’s primary) and in Romania (for counting the ballots). These systems are analyzed in order to find out if they respect technical challenges such as verifiability, dependability, security, anonymity and trust.

Cramer and Shoup introduced at Eurocrypt’02 the concept of hash proof system, also designated as smooth projective hash functions. Since then, they have found several applications, from building CCA-2 encryption as they were initially created for, to being at the core of several authenticated key exchange or even allowing witness encryption. In the post-quantum setting, the very few candidates use a language based on ciphertexts to build their hash proof system. This choice seems to inherently introduce a gap, as some elements outside the language could not be distinguish from those in the language. This creates a lawless zone, where an adversary can possibly mount an undetectable attack, particularly problematic when trying to prove security in the UC framework. We show that this gap could be completely withdrawn using code-based cryptography. Starting from RQC, a candidate selected for the second round of the National Institute of Standards and Technology (NIST) post-quantum cryptography standardization project, we show how to build such a hash proof system from code-based cryptography and present a way, based on a proof of knowledge, to fully negate the gap. We propose two applications of our construction, a witness encryption scheme and a password authenticated key exchange (PAKE).

Federated Learning (FL) is a collaborative machine learning approach allowing participants to jointly train a model without having to share their private, potentially sensitive local datasets with others. Despite its benefits, FL is vulnerable to so-called backdoor attacks, in which an adversary injects manipulated model updates into the federated model aggregation process so that the resulting model will provide targeted false predictions for specific adversary-chosen inputs. Proposed defenses against backdoor attacks based on detecting and filtering out malicious model updates consider only very specific and limited attacker models, whereas defenses based on differential privacy-inspired noise injection significantly deteriorate the benign performance of the aggregated model. To address these deficiencies, we introduce FLAME, a defense framework that estimates the sufficient amount of noise to be injected to ensure the elimination of backdoors. To minimize the required amount of noise, FLAME uses a model clustering and weight clipping approach. This ensures that FLAME can maintain the benign performance of the aggregated model while effectively eliminating adversarial backdoors. Our evaluation of FLAME on several datasets stemming from application areas including image classification, word prediction, and IoT intrusion detection demonstrates that FLAME removes backdoors effectively with a negligible impact on the benign performance of the models.

Post-quantum cryptography (PQC) is a trend that has a deserved NIST status, and which aims to be resistant to quantum computer attacks like Shor and Grover algorithms. NIST is currently leading the third-round search of a viable set of standards, all based on traditional approaches as code-based, lattice-based, multi quadratic-based, or hash-based cryptographic protocols [1]. We choose to follow an alternative way of replacing all numeric field arithmetic with GF(2^8) field operations [2]. By doing so, it is easy to implement R-propped asymmetric systems as the present paper shows [3,4]. Here R stands for Rijndael as we work over the AES field. This approach yields secure post-quantum protocols since the resulting multiplicative monoid is immune against quantum algorithms and resist classical linearization attacks like Tsaban’s Algebraic Span [5] or Roman’kov linearization attacks [6]. The Burmester-Desmedt (B-D) conference key distribution protocol [7] has been proved to be secure against passive adversaries if the computational Diffie-Hellman problem remains hard. The authors refer that the proposed scheme could also be secure against active adversaries under the same assumptions as before if an authentication step is included to foil attacks like MITM (man in the middle). Also, this protocol proved to be semantical secure against adaptative IND-CPA2 [8, 9] if the discrete log problem is intractable. We discuss the features of our present work and a practical way to include an authentication step. Classical and quantum security levels are also discussed. Finally, we present a numerical example of the proposed R-Propped protocol.

The term permissionless has established itself within the context of blockchain and distributed ledger research to characterize protocols and systems that exhibit similar properties to Bitcoin. However, the notion of what is meant by permissionlessness is often vague or left implicit within the various literature, rendering it imprecise and hard to compare. We hereby shed light onto this topic by revising research that either incorporates or defines the term permissionless and systematically expose the properties and characteristics that its utilization intends to capture. Based on this review, we highlight current shortcomings and blind spots within the available definitions. In particular, the ability to freely perform transactions between users is often not adequately incorporated and different actor roles are left unspecified. Furthermore, the topics of privacy and governance appear to be largely overlooked.

In this paper we propose new techniques related to division property. We describe for the first time a practical algorithm for computing the propagation tables of 16-bit Super-Sboxes, increasing the precision of the division property by removing a lot of false division trails. We also improve the complexity of the procedure introduced by Lambin et al. (Design, Codes and Cryptography, 2020) to extend a cipher with linear mappings and show how to decrease the number of transitions to look for. While search procedures for integral distinguishers most often rely on MILP or SAT solvers for their ease of programming the propagation constraints, such generic solvers can only handle small 4/8-bit Sboxes. Thus we developed an ad-hoc tool handling larger Sboxes and all the improvements described in the paper. As a result, we found new integral distinguishers on SKINNY-64, HIGHT and Midori-64.

Fast Near collision attacks on the stream ciphers Grain v1 and A5/1 were presented at Eurocrypt 2018 and Asiacrypt 2019 respectively. They use the fact that the entire internal state can be split into two parts so that the second part can be recovered from the first one which can be found using the keystream prefix and some guesses of the key materials. In this paper we reevaluate the complexity of these attacks and show that actually they are inferior to previously known results. Basically, we show that their complexity is actually much higher and we point out the main problems of these papers based on information theoretic ideas. We also check that some distributions do not have the predicted entropy loss claimed by the authors. Checking cryptographic attacks with galactic complexity is difficult in general. In particular, as these attacks involve many steps it is hard to identify precisely where the attacks are flawed. But for the attack against A5/1, it could have been avoided if the author had provided a full experiment of its attack since the overall claimed complexity was lower than 232 in both time and memory

In this paper we describe a new tool to search for boomerang distinguishers. One limitation of the MILP model of Liu et al. is that it handles only one round for the middle part while Song et al. have shown that dependencies could affect much more rounds, for instance up to 6 rounds for SKINNY. Thus we describe a new approach to turn an MILP model to search for truncated characteristics into an MILP model to search for truncated boomerang characteristics automatically handling the middle rounds. We then show a new CP model to search for the best possible instantiations to identify good boomerang distinguishers. Finally we systematized the method initiated by Song et al. to precisely compute the probability of a boomerang. As a result, we found many new boomerang distinguishers up to 24 rounds in the TK3 model. In particular, we improved by a factor $2^{30}$ the probability of the best known distinguisher against 18-round SKINNY-128/256.

This paper makes a comprehensive comparison of the efficiencies of vectorized implementations of Kummer lines and Montgomery curves at various security levels. For the comparison, nine Kummer lines are considered, out of which eight are new, and new assembly implementations of all nine Kummer lines have been made. Seven previously proposed Montgomery curves are considered and new vectorized assembly implementations have been made for five of them. Our comparisons show that for all security levels, Kummer lines are consistently faster than Montgomery curves, though the speed-up gap is not much.

To maintain the secure information sharing among vehicles in the Internet of Vehicles, various message authentication schemes were proposed. Recently, Sutrala et al. proposed a conditional privacy preserving authentication scheme (``On the Design of Conditional Privacy Preserving Batch Verification-Based Authentication Scheme for Internet of Vehicles Deployment,'' IEEE Trans. Veh. Technol., vol. 69, no. 5, pp. 5535-5548, May 2020.) to against various potential attacks. However, our observations show that, contrary to what is claimed, the scheme is insecure. Any (malicious) vehicle can forge signature for any message, which can be validated successfully and cannot be traceable. Our observations also show that, the security proof based on the standard random oracle model is wrong.

This paper presents Poplar, a new system for solving the private heavy-hitters problem. In this problem, there are many clients and a small set of data-collection servers. Each client holds a private bitstring. The servers want to recover the set of all popular strings, without learning anything else about any client’s string. A web-browser vendor, for instance, can use Poplar to figure out which homepages are popular, without learning any user’s homepage. We also consider the simpler private subset-histogram problem, in which the servers want to count how many clients hold strings in a particular set without revealing this set to the clients. Poplar uses two data-collection servers and, in a protocol run, each client send sends only a single message to the servers. Poplar protects client privacy against arbitrary misbehavior by one of the servers and our approach requires no public-key cryptography (except for secure channels), nor general-purpose multiparty computation. Instead, we rely on incremental distributed point functions, a new cryptographic tool that allows a client to succinctly secret-share the labels on the nodes of an exponentially large binary tree, provided that the tree has a single non-zero path. Along the way, we develop new general tools for providing malicious security in applications of distributed point functions. A limitation of Poplar is that it reveals to the servers slightly more information than the set of popular strings itself. We precisely define and quantify this leakage and explain how to ameliorate its effects. In an experimental evaluation with two servers on opposite sides of the U.S., the servers can find the 200 most popular strings among a set of 400,000 client-held 256-bit strings in 54 minutes. Our protocols are highly parallelizable. We estimate that with 20 physical machines per logical server, Poplar could compute heavy hitters over ten million clients in just over one hour of computation.

Black-box separations have been successfully used to identify the limits of a powerful set of tools in cryptography, namely those of black-box reductions. They allow proving that a large set of techniques are not capable of basing one primitive $\mathcal{P}$ on another $\mathcal{Q}$. Such separations, however, do not say anything about the power of the combination of primitives $\mathcal{Q}_1,\mathcal{Q}_2$ for constructing $\mathcal{P}$, even if $\mathcal{P}$ cannot be based on $\mathcal{Q}_1$ or $\mathcal{Q}_2$ alone. By introducing and formalizing the notion of black-box uselessness, we develop a framework that allows us to make such conclusions. At an informal level, we call primitive $\mathcal{Q}$ black-box useless (BBU) for primitive $\mathcal{P}$ if $\mathcal{Q}$ cannot help constructing $\mathcal{P}$ in a black-box way, even in the presence of another primitive $\mathcal{Z}$. This is formalized by saying that $\mathcal{Q}$ is BBU for $\mathcal{P}$ if for any auxiliary primitive $\mathcal{Z}$, whenever there exists a black-box construction of $\mathcal{P}$ from $(\mathcal{Q},\mathcal{Z})$, then there must already also exist a black-box construction of $\mathcal{P}$ from $\mathcal{Z}$ alone. We also formalize various other notions of black-box uselessness, and consider in particular the setting of efficient black-box constructions when the number of queries to $\mathcal{Q}$ is below a threshold. Impagliazzo and Rudich (STOC'89) initiated the study of black-box separations by separating key agreement from one-way functions. We prove a number of initial results in this direction, which indicate that one-way functions are perhaps also black-box useless for key agreement. In particular, we show that OWFs are black-box useless in any construction of key agreement in either of the following settings: (1) the key agreement has perfect correctness and one of the parties calls the OWF a constant number of times; (2) the key agreement consists of a single round of interaction (as in Merkle-type protocols). We conjecture that OWFs are indeed black-box useless for general key agreement protocols. We also show that certain techniques for proving black-box separations can be lifted to the uselessness regime. In particular, we show that known lower bounds for assumptions behind black-box constructions of indistinguishability obfuscation (IO) can be extended to derive black-box uselessness of a variety of primitives for obtaining (approximately correct) IO. These results follow the so-called "compiling out" technique, which we prove to imply black-box uselessness. Eventually, we study the complementary landscape of black-box uselessness, namely black-box helpfulness. Formally, we call primitive $\mathcal{Q}$ black-box helpful (BBH) for $\mathcal{P}$, if there exists an auxiliary primitive $\mathcal{Z}$ such that there exists a black-box construction of $\mathcal{P}$ from $(\mathcal{Q},\mathcal{Z})$, but there exists no black-box construction of $\mathcal{P}$ from $\mathcal{Z}$ alone. We put forth the conjecture that one-way functions are black-box helpful for building collision-resistant hash functions. We define two natural relaxations of this conjecture, and prove that both of these conjectures are implied by a natural conjecture regarding random permutations equipped with a collision finder oracle, as defined by Simon (Eurocrypt'98). This conjecture may also be of interest in other contexts, such as hardness amplification.

In recent years, numerous attacks have appeared that aim to steal secret information from their victim using the power side-channel vector, yet without direct physical access. These attacks are called Remote Power Attacks or Remote Power Analysis, utilizing resources that are natively present inside the victim environment. However, there is no unified definition about the limitations that a power attack requires to be defined as remote. This paper aims to propose a unified definition and concrete threat models to clearly differentiate remote power attacks from non-remote ones. Additionally, we collect the main remote power attacks performed so far from the literature, and the principal proposed countermeasures to avoid them. The search of such countermeasures denoted a clear gap in preventing remote power attacks at the technical level. Thus, the academic community must face an important challenge to avoid this emerging threat, given the clear room for improvement that should be addressed in terms of defense and security of devices that work with private information.

Though the multilinear maps have many cryptographic applications, secure and efficient construction of such maps is an open problem. Many multilinear maps like GGH, GGH15, CLT, and CLT15 have been and are being proposed, while none of them is both secure and efficient. The construction of some multilinear maps is based on the Graded Encoding Scheme (GES), where, the necessity of announcing zero-testing parameter and encoding of zero has destroyed the security of the multilinear map. Attempt is made to propose a new GES, where, instead of encoding an element, the users can obtain the encoding of an associated but unknown random element. In this new setting, there is no need to publish the encodings of zero and one. This new GES provides the actual functionality of the usual GES and can be applied in constructing a secure and efficient multilinear map and a multi-party non-interactive key exchange (MP-NIKE) scheme. We also improve the MP-NIKE scheme and turn it into an ID-based MP-NIKE scheme.

We describe and illustrate the local neighbourhoods of vertices and edges in the (2, 2)-isogeny graph of principally polarized abelian surfaces, considering the action of automorphisms. Our diagrams are intended to build intuition for number theorists and cryptographers investigating isogeny graphs in dimension/genus 2, and the superspecial isogeny graph in particular.

We investigate special structures due to automorphisms in isogeny graphs of principally polarized abelian varieties, and abelian surfaces in particular. We give theoretical and experimental results on the spectral and statistical properties of (2, 2)-isogeny graphs of superspecial abelian surfaces, including stationary distributions for random walks, bounds on eigenvalues and diameters, and a proof of the connectivity of the Jacobian subgraph of the (2, 2)-isogeny graph. Our results improve our understanding of the performance and security of some recently-proposed cryptosystems, and are also a concrete step towards a better understanding of general superspecial isogeny graphs in arbitrary dimension.

The problem of solving explicitly the equation $P_a(X):=X^{q+1}+X+a=0$ over the finite field $\GF{Q}$, where $Q=p^n$, $q=p^k$ and $p$ is a prime, arises in many different contexts including finite geometry, the inverse Galois problem \cite{ACZ2000}, the construction of difference sets with Singer parameters \cite{DD2004}, determining cross-correlation between $m$-sequences \cite{DOBBERTIN2006} and to construct error correcting codes \cite{Bracken2009}, cryptographic APN functions \cite{BTT2014,Budaghyan-Carlet_2006}, designs \cite{Tang_2019}, as well as to speed up the index calculus method for computing discrete logarithms on finite fields \cite{GGGZ2013,GGGZ2013+} and on algebraic curves \cite{M2014}. Subsequently, in \cite{Bluher2004,HK2008,HK2010,BTT2014,Bluher2016,KM2019,CMPZ2019,MS2019,KCM19}, the $\GF{Q}$-zeros of $P_a(X)$ have been studied. In \cite{Bluher2004}, it was shown that the possible values of the number of the zeros that $P_a(X)$ has in $\GF{Q}$ is $0$, $1$, $2$ or $p^{\gcd(n, k)}+1$. Some criteria for the number of the $\GF{Q}$-zeros of $P_a(x)$ were found in \cite{HK2008,HK2010,BTT2014,KM2019,MS2019}. However, while the ultimate goal is to explicit all the $\GF{Q}$-zeros, even in the case $p=2$, it was solved only under the condition $\gcd(n, k)=1$ \cite{KM2019}. In this article, we discuss this equation without any restriction on $p$ and $\gcd(n,k)$. In \cite{KCM19}, for the cases of one or two $\GF{Q}$-zeros, explicit expressions for these rational zeros in terms of $a$ were provided, but for the case of $p^{\gcd(n, k)}+1$ $\GF{Q}-$ zeros it was remained open to explicitly compute the zeros. This paper solves the remained problem, thus now the equation $X^{p^k+1}+X+a=0$ over $\GF{p^n}$ is completely solved for any prime $p$, any integers $n$ and $k$.

Compression is widely used in Internet communication to save communication time and bandwidth. Recently invented by Jarek Duda asymmetric numeral system (ANS) offers an improved efficiency and a close to optimal compression. The ANS algorithm has been deployed by major IT companies such as Facebook, Google and Apple. Compression by itself does not provide any security (such as confidentiality or authentication of transmitted data). An obvious solution to this problem is an encryption of compressed bitstream. However, it requires two algorithms: one for compression and the other for encryption. In this work, we investigate natural properties of ANS that allow to incorporate authenticated encryption using as little cryptography as possible. We target low-level security communication such as transmission of data from IoT devices/sensors. In particular, we propose three solutions for joint compression and encryption (compcrypt). All of them use a pseudorandom bit generator (PRGB) based on lightweight stream ciphers. The first solution applies state jumps controlled by PRGB. The second one employs two ANS algorithms, where compression switches between the two. The switch is controlled by a PRGB bit. The third compcrypt modifies the encoding function of ANS depending on PRGB bits. Security and efficiency of the proposed compcrypt algorithms are evaluated.

Abstract: Off-chain is a common approach to deal with the scalability problem of blockchain networks. It enables users toexecute multiple payments without committing each of them to the blockchain by relying on predefined payment channels. Apair of users can employ a payment even without a direct channel between them, via routing the payment through off-chainchannels involving other intermediate users. Users together with the off-chain channels form a graph, known as the off-chainnetwork topology. The off-chain topology and the payment characteristics affect network performance such as the averagenumber of intermediate users a payment is routed through, the amount of fees, or channel capacities needed to successfullyroute payments. In this paper, we study two basic problems in off-chain network design. First, efficiently mapping users toan off-chain topology with a known structure. Second, constructing a topology of a bounded number of channels that canserve well users with associated payments. We design algorithms for both problems and evaluate them based on real datafrom Raiden, the off-chain extension for Ethereum. Keywors:

Nonlinear diffusion layers are less studied in cryptographic literature, up to now. In 2018, Liu, Rijmen and Leander studied nonlinear non-MDS diffusion layers and mentioned some advantages of them. As they stated, nonlinear diffusion layers could make symmetric ciphers more resistant against statistical and algebraic cryptanalysis. In this paper, with the aid of some special maps over the finite field $\mathbb{F}_{2^n}$, we examine nonlinear MDS mappings and present a family of $4 \times 4$ nonlinear MDS diffusion layers. Next, we determine the Walsh and differential spectrum as well as the algebraic degree of the proposed diffusion layers.

Zhang et al. recently proposed a lattice-based proxy-oriented identity-based encryption with keyword search (PO-IBEKS) at Information Sciences in 2019. They claimed that their scheme can resist insider keyword guessing attacks by preventing cloud server from generating ciphertext. In this note, we provide a cryptanalysis of their PO-IBEKS and demonstrate that their scheme cannot resist outsider/insider keyword guessing attacks, even though they satisfy unforgeability requirement. Furthermore, we uncover the root cause of the attack and provide a possible solution for Zhang et al.'s scheme to aid future designs of secure PO-IBEKS schemes.

Many web-based and mobile applications and services allow users to indicate their preferences regarding whether and how their personal information can be used or reused by the application itself, by the service provider, and/or by third parties. The number of possible configurations that constitute a user's preference profile can be overwhelming to a typical user. This report describes a practical, privacy-preserving technique for reducing the burden users face when specifying their preferences by offering users data-driven recommendations for fully-specified preference profiles based on their inputs for just a few settings. The feasibility of the approach is demonstrated by a browser-based prototype application that relies on secure multi-party computation and uses the web-compatible JIFF library as the backbone for managing communications between the client application and the recommendation service. The principal algorithms used for generating proposed preference profiles are $k$-means clustering (for privacy-preserving analysis of preference profile data across multiple users) and $k$-nearest neighbors (for selecting a proposed preference profile to recommend to the user).