Lattice-based encryption schemes are often subject to the possibility of decryption failures, in which valid encryptions are decrypted incorrectly. Such failures, in large number, leak information about the secret key, enabling an attack strategy alternative to pure lattice reduction. Extending the "failure boosting'' technique of D'Anvers et al. in PKC 2019, we propose an approach that we call "directional failure boosting'' that uses previously found "failing ciphertexts'' to accelerate the search for new ones. We analyse in detail the case where the lattice is defined over polynomial ring modules quotiented by <X^N + 1> and demonstrate it on a simple Mod-LWE-based scheme parametrized à la Kyber768/Saber. We show that, using our technique, for a given secret key (single-target setting), the cost of searching for additional failing ciphertexts after one or more have already been found, can be sped up dramatically. We thus demonstrate that, in this single-target model, these schemes should be designed so that it is hard to even obtain one decryption failure. Besides, in a wider security model where there are many target secret keys (multi-target setting), our attack greatly improves over the state of the art.

The inconsistency of Nash equilibrium of rational delegated computation scheme in the UC framework will lead to the lack of strict security proof of the protocols fundamentally. The consistency proof of Nash equilibrium between the ideal world and the real world has always been a challenge in the research field. In this paper, we analyze the Nash equilibrium according to the game model of rational delegated computation, and the ideal functionality for rational delegation of computation based on incentive-driven adversary is proposed, then we construct a rational delegated computation protocol for UC-realizing the ideal functionality. In a word, the proposed rational delegated computing protocol based on incentive-driven adversary has been proven to be secure in the universally composable framework, furthermore, we effectively solve the inconsistency problem of Nash equilibrium between the real world and the ideal world.

Secret sharing splits a secret $s$ into $\ell$ shares in such a way that $k\leq \ell$ shares suffice to reconstruct $s$. Let $\rho_{i,j}$ be the probability that shareholder $i$ disclose their share to shareholder $j$, with $0 \leq i,j < n$. Given $k \leq \ell \leq n$, to whom $\ell$ individuals should we hand shares, if we wish to minimize the probability that one of them reconstitutes $s$?

A new multivariate cryptosystem based on a linear code was proposed by Smith-Tone and Tone quite recently. This short note points out that it is a variant of UOV.

Recent results have shown that some post-quantum cryptographic systems have encryption and decryption performance comparable to fast elliptic-curve cryptography (ECC) or even better. However, this performance metric is considering only CPU time and ignoring bandwidth and storage. High-confidence post-quantum encryption systems have much larger keys than ECC. For example, the code-based cryptosystem recommended by the PQCRYPTO project uses public keys of 1MB. Fast key erasure (to provide ``forward secrecy'') requires new public keys to be constantly transmitted. Either the server needs to constantly generate, store, and transmit large keys, or it needs to receive, store, and use large keys from the clients. This is not necessarily a problem for overall bandwidth, but it is a problem for storage and computation time on tiny network servers. All straightforward approaches allow easy denial-of-service attacks. This paper describes a protocol, suitable for today's networks and tiny servers, in which clients transmit their code-based one-time public keys to servers. Servers never store full client public keys but work on parts provided by the clients, without having to maintain any per-client state. Intermediate results are stored on the client side in the form of encrypted cookies and are eventually combined by the server to obtain the ciphertext. Requirements on the server side are very small: storage of one long-term private key, which is much smaller than a public key, and a few small symmetric cookie keys, which are updated regularly and erased after use. The protocol is highly parallel, requiring only a few round trips, and involves total bandwidth not much larger than a single public key. The total number of packets sent by each side is 971, each fitting into one IPv6 packet of less than 1280 bytes. The protocol makes use of the structure of encryption in code-based cryptography and benefits from small ciphertexts in code-based cryptography.

FPGAs are increasingly used in cloud applications and being integrated into Systems-on-Chip (SoCs). For these systems, various side-channel attacks on cryptographic implementations have been reported, motivating to apply proper countermeasures. Beyond cryptographic implementations, maliciously introduced covert channel receivers and transmitters can allow to exfiltrate other secret information from the FPGA. In this paper, we present a fast covert channel on FPGAs, which exploits the on-chip power distribution network. This can be achieved without any logical connection between the transmitter and receiver blocks. Compared to a recently published covert channel with an estimated 4.8 Mbit/s transmission speed, we show 8 Mbit/s transmission and reduced errors from around 3% to less than 0.003%. Furthermore, we demonstrate proper transmissions of word-size messages and test the channel in the presence of noise generated from other residing tenants' modules in the FPGA. When we place and operate other co-tenant modules that require 85% of the total FPGA area, the error rate increases to 0.02%, depending on the platform and setup. This error rate is still reasonably low for a covert channel. Overall, the transmitter and receiver work with less than 3-5% FPGA LUT resources together. We also show the feasibility of other types of covert channel transmitters, in the form of synchronous circuits within the FPGA.

Computer-aided cryptography is an active area of research that develops and applies formal, machine-checkable approaches to the design, analysis, and implementation of cryptography. We present a cross-cutting systematization of the computer-aided cryptography literature, focusing on three main areas: (i) design-level security (both symbolic security and computational security), (ii) functional correctness and efficiency, and (iii) implementation-level security (with a focus on digital side-channel resistance). In each area, we first clarify the role of computer-aided cryptography---how it can help and what the caveats are---in addressing current challenges. We next present a taxonomy of state-of-the-art tools, comparing their accuracy, scope, trustworthiness, and usability. Then, we highlight their main achievements, trade-offs, and research challenges. After covering the three main areas, we present two case studies. First, we study efforts in combining tools focused on different areas to consolidate the guarantees they can provide. Second, we distill the lessons learned from the computer-aided cryptography community's involvement in the TLS 1.3 standardization effort. Finally, we conclude with recommendations to paper authors, tool developers, and standardization bodies moving forward.

The user of an imperfectly correct lattice-based public-key encryption scheme leaks information about their secret key with each decryption query that they answer---even if they answer all queries successfully. Through a refinement of the D'Anvers--Guo--Johansson--Nilsson--Vercauteren--Verbauwhede failure boosting attack, we show that an adversary can use this information to improve his odds of finding a decryption failure. We also propose a new definition of $\delta$-correctness, and we re-assess the correctness of several submissions to NIST's post-quantum standardization effort.

Using a set of pairing product equations (PPEs) to verify the correctness of an untrusted set of pairing elements with respect to another set of trusted elements has numerous cryptographic applications. These include the design of basic and structure-preserving signature schemes, building oblivious transfer schemes from “blind” IBE, finding new verifiable random functions and keeping the IBE/ABE authority “accountable” to the user. A natural question to ask is: are all trusted-untrusted pairing element groups in the literature PPE testable? We provide original observations demonstrating that the answer is no, and moreover, it can be non-trivial to determine whether or not there exists a set of PPEs that can verify some pairing elements with respect to others. Many IBE schemes have PPE-testable private keys (with respect to the public parameters), while others, such as those based on dual-system encryption, provably do not. To aid those wishing to use PPE-based element verification in their cryptosystems, we devised rules to systematically search for a set of PPEs that can verify untrusted elements with respect to a set of trusted elements. We prove the correctness of each rule and combine them into a main searching algorithm for which we also prove correctness. We implemented this algorithm in a new software tool, called AutoPPE. Tested on over two dozen case studies, AutoPPE found a set of PPEs (on schemes where they exist) usually in just a matter of seconds. This work represents an important step towards the larger goal of improving the speed and accuracy of pairing-based cryptographic design via computer automation.

Secure multiparty computation enables a set of parties to securely carry out a joint computation on their private inputs without revealing anything but the output. A particularly motivated setting is that of three parties with a single corruption (hereafter denoted 3PC). This 3PC setting is particularly appealing for two main reasons: (1) it admits more efficient MPC protocols than in other standard settings; (2) it allows in principle to achieve full security (and fairness). Highly efficient protocols exist within this setting with security against a semi-honest adversary; however, a significant gap remains between these and protocols with stronger security against a malicious adversary. In this paper, we narrow this gap within concretely efficient protocols. More explicitly, we have the following contributions: * Concretely Efficient Malicious 3PC. We present an optimized 3PC protocol for arithmetic circuits over rings with (amortized) communication of 1 ring element per multiplication gate per party, matching the best semi-honest protocols. The protocol applies also to Boolean circuits, significantly improving over previous protocols even for small circuits. Our protocol builds on recent techniques of Boneh et al.\ (Crypto 2019) for sublinear zero-knowledge proofs on distributed data, together with an efficient semi-honest protocol based on replicated secret sharing (Araki et al., CCS 2016). We present a concrete analysis of communication and computation costs, including several optimizations. For example, for 40-bit statistical security, and Boolean circuit with a million (nonlinear) gates, the overhead on top of the semi-honest protocol can involve less than 0.5KB of communication {\em for the entire circuit}, while the computational overhead is dominated by roughly 30 multiplications per gate in the field $F_{2^{47}}$. In addition, we implemented and benchmarked the protocol for varied circuit sizes. * Full Security. We augment the 3PC protocol to further provide full security (with guaranteed output delivery) while maintaining amortized 1 ring element communication per party per multiplication gate, and with hardly any impact on concrete efficiency. This is contrasted with the best previous 3PC protocols from the literature, which allow a corrupt party to mount a denial-of-service attack without being detected.

Tweakable block ciphers are increasingly becoming a common primitive to build new resilient modes as well as a concept for multiple dedicated designs. While regular block ciphers define a family of permutations indexed by a secret key, tweakable ones define a family of permutations indexed by both a secret key and a public tweak. In this work we formalize and study a generic framework for building such a tweakable block cipher based on regular block ciphers, the iterated tweakable FX construction, which includes many such previous constructions of tweakable block ciphers. Then we describe a cryptanalysis from which we can derive a provable security upper-bound for all constructions following this tweakable iterated FX strategy. Concretely, the cryptanalysis of r rounds of our generic construction based on n-bit block ciphers with \kap-bit keys requires O(2^{r(n + \kap)/(r+1)}) online and offline queries. For r = 2 rounds this interestingly matches the proof of the particular case of XHX2 by Lee and Lee (ASIACRYPT 2018) thus proving for the first time its tightness. In turn, the XHX and XHX2 proofs show that our generic cryptanalysis is information theoretically optimal for 1 and 2 rounds.

Code-based public key cryptosystems have been found to be an interesting option in the area of Post-Quantum Cryptography. In this work, we present a key encapsulation mechanism (KEM) using a parity check matrix of the Generalized Srivastava code as the public key matrix. Generalized Srivastava codes are privileged with the decoding technique of Alternant codes as they belong to the family of Alternant codes. We exploit the dyadic structure of the parity check matrix to reduce the storage of the public key. Our encapsulation leads to a shorter ciphertext as compared to DAGS proposed by Banegas et al. in Journal of Mathematical Cryptology which also uses Generalized Srivastava code. Our KEM provides IND-CCA security in the random oracle model. Also, our scheme can be shown to achieve post-quantum security in the quantum random oracle model.

Let $A/\overline{\mathbb{F}}_p$ and $A'/\overline{\mathbb{F}}_p$ be supersingular principally polarized abelian varieties of dimension $g>1$. For any prime $\ell \ne p$, we give an algorithm that finds a path $\phi : A \rightarrow A'$ in the $(\ell, \dots , \ell)$-isogeny graph in $\widetilde{O}(p^{g-1})$ group operations on a classical computer, and $\widetilde{O}(\sqrt{p^{g-1}})$ calls to the Grover oracle on a quantum computer. The idea is to find paths from $A$ and $A'$ to nodes that correspond to products of lower dimensional abelian varieties, and to recurse down in dimension until an elliptic path-finding algorithm (such as Delfs--Galbraith) can be invoked to connect the paths in dimension $g=1$. In the general case where $A$ and $A'$ are any two nodes in the graph, this algorithm presents an asymptotic improvement over all of the algorithms in the current literature. In the special case where $A$ and $A'$ are a known and relatively small number of steps away from each other (as is the case in higher dimensional analogues of SIDH), it gives an asymptotic improvement over the quantum claw finding algorithms and an asymptotic improvement over the classical van Oorschot--Wiener algorithm.

Three-party key exchange, where two clients aim to agree a session key with the help of a trusted server, is prevalent in present-day systems. In this paper, we present a practical and secure three-party password-based authenticated key exchange protocol over ideal lattices. Aside from hash functions our protocol does not rely on external primitives in the construction and the security of our protocol is directly relied on the Ring Learning with Errors (RLWE) assumption. Our protocol attains provable security. A proof-of-concept implementation shows our protocol is indeed practical.

The Lighting Network (LN) is a network of micropayment channels that runs on top of Bitcoin. The balances of payment channels are not broadcasted to the LN network to preserve the privacy of the nodes participating in the network. A balance disclosure attack (BDA) has been proven to be successful in determining the balance of large amount of channels in the network. In this paper we propose an improved algorithm for the BDA as well as a new type of attack that leverages the differences between LN client software implementations. Our improved algorithm extends the original BDA by performing payments from both sides of the channel. The new attack uses malformed payments to shutdown payment channels an adversary isn't part of.

The key escrow problem is one of the main barriers to the widespread real-world use of identity-based encryption (IBE). Specifically, a key generation center (KGC), which generates secret keys for a given identity, has the power to decrypt all ciphertexts. At PKC 2009, Chow defined a notion of security against the KGC, that relies on assuming that it cannot discover the underlying identities behind ciphertexts. However, this is not a realistic assumption since, in practice, the KGC manages an identity list, and hence it can easily guess the identities corresponding to given ciphertexts. Chow later amended this issue by introducing a new entity called an identity-certifying authority (ICA) and proposed an anonymous key-issuing protocol. Essentially, this allows the users, KGC, and ICA to interactively generate secret keys without users ever having to reveal their identities to the KGC. Unfortunately, since Chow separately defined the security of IBE and that of the anonymous key-issuing protocol, his IBE definition did not provide any formal treatment when the ICA is used to authenticate the users. Effectively, all of the subsequent works following Chow lack the formal proofs needed to determine whether or not it delivers a secure solution to the key escrow problem. In this paper, based on Chow's work, we formally define an IBE scheme that resolves the key escrow problem and provide formal definitions of security against corrupted users, KGC, and ICA. Along the way, we observe that if we are allowed to assume a fully trusted ICA, as in Chow's work, then we can construct a trivial (and meaningless) IBE scheme that is secure against the KGC. Finally, we present two instantiations in our new security model: a lattice-based construction based on the Gentry--Peikert--Vaikuntanathan IBE scheme (STOC 2008) and R{ü}ckert's lattice-based blind signature scheme (ASIACRYPT 2010), and a pairing-based construction based on the Boneh--Franklin IBE scheme (CRYPTO 2001) and Boldyreva's blind signature scheme (PKC 2003).

In standard Secret Sharing (SS), a dealer shares a secret $s$ among $n$ parties such that an adversary corrupting no more than $t$ parties does not learn $s$, while any $t+1$ parties can efficiently recover $s$. Proactive Secret Sharing (PSS) retains confidentiality of $s$ even when a mobile adversary corrupts all parties over the lifetime of the secret, but no more than a threshold $t$ in each epoch (called a refresh period). Withstanding such adversaries has become of increasing importance with the emergence of settings where private keys are secret shared and used to sign cryptocurrency transactions, among other applications. Feasibility of single-secret PSS for static groups with dishonest majorities was demonstrated but with a protocol that requires inefficient communication of $O(n^4)$. In this work, we improve over prior work in three directions: batching without incurring a linear loss in corruption threshold, communication efficiency, and handling dynamic groups. While each of properties we improve upon appeared independently in the context of PSS and in other previous work, handling them simultaneously (and efficiently) in a single scheme faces non-trivial challenges. Some PSS protocols can handle batching of $\ell \sim n$ secrets, but all of them are for the honest majority setting. Techniques typically used to accomplish such batching decrease the tolerated corruption threshold bound by a linear factor in $\ell$, effectively limiting the number of elements that can be batched with dishonest majority. We solve this problem by reducing the threshold decrease to $\sqrt{\ell}$ instead, allowing us to deal with the dishonest majority setting when $\ell \sim n$. This is accomplished based on new bivariate-polynomials-based techniques for sharing, and refreshing and recovering of shares, that allow batching of up to $n-2$ secrets in our PSS. To tackle the efficiency bottleneck the constructed PSS protocol requires only $O(n^3/\ell)$ communication for $\ell$ secrets, i.e., an amortized communication complexity of $O(n^2)$ when the maximum batch size is used. To handle dynamic groups we develop three new sub-protocols to deal with parties joining and leaving the group.

An exciting new development in differential privacy is the shuffled model, in which an anonymous channel enables non-interactive, differentially private protocols with error much smaller than what is possible in the local model, while relying on weaker trust assumptions than in the central model. In this paper, we study basic counting problems in the shuffled model and establish separations between the error that can be achieved in the single-message shuffled model and in the shuffled model with multiple messages per user. For the problem of frequency estimation for $n$ users and a domain of size $B$, we obtain: - A nearly tight lower bound of $\tilde{\Omega}( \min(\sqrt[4]{n}, \sqrt{B}))$ on the error in the single-message shuffled model. This implies that the protocols obtained from the amplification via shuffling work of Erlingsson et al.~(SODA 2019) and Balle et al.~(Crypto 2019) are essentially optimal for single-message protocols. A key ingredient in the proof is a lower bound on the error of locally-private frequency estimation in the low-privacy (aka high $\epsilon$) regime. For this we develop new techniques to extend the results of Duchi et al.~(FOCS 2013; JASA 2018) and Bassily \& Smith~(STOC 2015), whose techniques were restricted to the high-privacy case. - Protocols in the multi-message shuffled model with $\poly(\log{B}, \log{n})$ bits of communication per user and $\poly\log{B}$ error, which provide an exponential improvement on the error compared to what is possible with single-message algorithms. This implies protocols with similar error and communication guarantees for several well-studied problems such as heavy hitters, $d$-dimensional range counting, M-estimation of the median and quantiles, and more generally sparse non-adaptive statistical query algorithms. For the related selection problem on a domain of size $B$, we prove: - A nearly tight lower bound of $\Omega(B)$ on the number of users in the single-message shuffled model. This significantly improves on the $\Omega(B^{1/17})$ lower bound obtained by Cheu et al.~(Eurocrypt 2019), and when combined with their $\tilde{O}(\sqrt{B})$-error multi-message protocol, implies the first separation between single-message and multi-message protocols for this problem.

Given the links between nonlinearity properties and the related tables such as LAT, DDT, BCT and ACT that have appeared in the literature, the boomerang connectivity table BCT seems to be an outlier as it cannot be derived from the others using Walsh-Hadamard transform. In this paper, a brief unified summary of the existing links for general vectorial Boolean functions is given first and then a link between the autocorrelation and boomerang connectivity tables is established.

In 2008, Drimer et al. proposed different AES implementations on a Xilinx Virtex-5 FPGA, making efficient use of the DSP slices and BRAM tiles available on the device. Inspired by their work, in this paper, we evaluate the feasibility of extending AES with the popular GCM mode of operation, still concentrating on the optimal use of DSP slices and BRAM tiles. We make use of a Xilinx Zynq UltraScale+ MPSoC FPGA with improved DSP features. For the AES part, we implement Drimer’s round-based and unrolled pipelined architectures differently, still using DSPs and BRAMs efficiently based on the AES Tbox approach. On top of AES, we append the GCM mode of operation, where we use DSP slices to support the GCM finite field multiplication. This allows us to implement AES-GCM with a small amount of FFs and LUTs. We propose two implementations: a relatively compact round-based design and a faster unrolled design.

Obtaining compact, while cryptographically strong, S-boxes is a challenging task required for hardware implementations of lightweight cryptography. Contrarily to 4-bit permutations design which is somewhat well understood, 8-bit permutations have mainly been investigated only through structured S-boxes built from 4-bit ones by means of Feistel, MISTY or SPN schemes. In this paper, we depart from this common habit and search for compact designs directly in the space of 8-bit permutations. We propose two methods for searching good and compact 8-bit S-boxes. One is derived from an adaptation to 8-bit circuits of a systematic bottom-up exploration already used in previous works for 4-bit permutations. The other is the use of a genetic algorithm that samples solutions in the 8-bit permutations space and makes them evolve toward predefined criteria. Contrarily to similar previous attempts, we chose to encode permutations by their circuits rather than by their tables, which allows to optimize non only w.r.t the cryptographic quality but also w.r.t. compactness. We obtain results which show competitive compared to structured designs and we provide an overview of the relation between quality and compactness in the range of rather small 8-bit circuits. Beside, we also exhibit a 8-gate circuit made of only AND and XOR gates that represents a 4-bit permutation belonging to an optimal equivalence class. This shows that such optimal class can be instantiated by threshold implementation friendly circuits with no extra cost compared to previous works.

S-boxes are the only source of non-linearity in many symmetric primitives. While they are often defined as being functions operating on a small space, some recent designs propose the use of much larger ones (e.g., 32 bits). In this context, an S-box is then defined as a subfunction whose cryptographic properties can be estimated precisely. We present a 64-bit ARX-based S-box called Alzette, which can be evaluated in constant time using only 12 instructions on modern CPUs. Its parallel application can also leverage vector (SIMD) instructions. One iteration of Alzette has differential and linear properties comparable to those of the AES S-box, and two are at least as secure as the AES super S-box. As the state size is much larger than the typical 4 or 8 bits, the study of the relevant cryptographic properties of Alzette is not trivial. We further discuss how such wide S-boxes could be used to construct round functions of 64-, 128- and 256-bit (tweakable) block ciphers with good cryptographic properties that are guaranteed even in the related-tweak setting. We use these structures to design a very lightweight 64-bit block cipher (CRAX) which outperforms SPECK-64/128 for short messages on micro-controllers, and a 256-bit tweakable block cipher (TRAX) which can be used to obtain strong security guarantees against powerful adversaries (nonce misuse, quantum attacks).

Abstract. We present a construction for hash-based one-time group signature schemes, and develop a traceable post-quantum multi-time group signature upon it. A group signature scheme allows group members to anonymously sign a message on behalf of the whole group. The signatures are unforgeable and the scheme enables authorized openers to trace the signature back to the original signer when needed. Our construction utilizes three nested layers to build the group signature scheme. The first layer is key management; it deploys a transversal design to assign keys to the group members and the openers, providing the construction with traceability. The second layer utilizes hash pools to build the group public verification key, to connect group members together, and to provide anonymity. The final layer is a post-quantum hash-based signature scheme, that adds unforgeability to our construction. We extend our scheme to multi-time signatures by using Merkle trees, and show that this process keeps the scalability property of Merkle-based signatures, while it supports the group members signing any number of messages. Keywords: Post Quantum Signatures, Hash-based Signatures, Group Signatures, Transversal Designs, Multi-opener Signatures

Revocable identity-based encryption (RIBE) is an extension of IBE which can support a key revocation mechanism, and it is important when deploying an IBE system in practice. Boneh and Franklin (Crypto'01) presented the first generic construction of RIBE, however, their scheme is not scalable where the size of key updates is linear in the number of users in the system. The first generic construction of RIBE is presented by Ma and Lin with complete subtree (CS) method by combining IBE and hierarchical IBE (HIBE) schemes. Recently, Lee proposed a new generic construction using the subset difference (SD) method by combining IBE,identity-based revocation (IBR), and two-level HIBE schemes. In this paper, we present a new primitive called Identity-Based Encryption with Ciphertext Delegation (CIBE) and propose a generic construction of RIBE scheme via subset difference method using CIBE and HIBE as building blocks. CIBE is a special type of Wildcarded IBE (WIBE) and Identity-Based Broadcast Encryption (IBBE). Furthermore, we show that CIBE can be constructed from IBE in a black-box way. Instantiating the underlying building blocks with different concrete schemes, we can obtain a RIBE scheme with constant-size public parameter, ciphertext, private key and $O(r)$ key updates in the selective-ID model. Additionally, our generic RIBE scheme can be easily converted to a sever-aided RIBE scheme which is more suitable for lightweight devices.

We design a very simple private-key encryption scheme whose decryption function is a rational function. This scheme is not born naturally homomorphic. To get homomorphic properties, a nonlinear additive homomorphic operator is specifically developed. The security analysis is based on symmetry considerations and we prove some formal results under the factoring assumption. In particular, we prove IND-CPA security in the generic ring model. Even if our security proof is not complete, we think that it is convincing and that the technical tools considered in this paper are interesting by themselves. Moreover, the factoring assumption is just needed to ensure that solving nonlinear equations or finding non-null polynomials with many roots is difficult. Consequently, the ideas behind our construction could be re-used in rings satisfying these properties. As motivating perspectives, we then propose to develop a simple multiplicative operator. To achieve this, randomness is added in our construction giving hope to remove the factoring assumption in order to get a pure multivariate encryption scheme.

Public key cryptography is threatened by the advent of quantum computers. Using Shor's algorithm on a large-enough quantum computer, an attacker can cryptanalyze any RSA/ECC public key, and generate fake digital signatures in seconds. If this vulnerability is left unaddressed, digital communications and electronic transactions can potentially be without the assurance of authenticity and non-repudiation. In this paper, we study the use of digital signatures in 14 real-world applications across the financial, critical infrastructure, Internet, and enterprise sectors. Besides understanding the digital signing usage, we compare the applications' signing requirements against all 6 NIST's post-quantum cryptography contest round 3 candidate algorithms. This is done through a proposed framework where we map out the suitability of each algorithm against the applications' requirements in a feasibility matrix. Using the matrix, we identify improvements needed for all 14 applications to have a feasible post-quantum secure replacement digital signing algorithm.

Finding an isogenous supersingular elliptic curve of a prescribed odd degree is an important building block for all the isogeny-based protocols proposed to date. In this note we present several strategies for the efficient construction of odd degree isogenies, which outperform previously reported methods when dealing with isogeny degrees in the range $[7, 2^{20}].$

AEGIS is one of the authenticated encryption designs selected for the final portfolio of the CAESAR competition. It combines the AES round function and simple Boolean operations to update its large state and extract a keystream to achieve an excellent software performance. In 2014, Minaud discovered slight biases in the keystream based on linear characteristics. For family member AEGIS-256, these could be exploited to undermine the confidentiality faster than generic attacks, but this still requires very large amounts of data. For final portfolio member AEGIS-128, these attacks are currently less efficient than generic attacks. We propose improved keystream approximations for the AEGIS family, but also prove upper bounds below $2^{-128}$ for the squared correlation contribution of any single suitable linear characteristic.

There have been notable improvements in discrete logarithm computations in finite fields since 2015 and the introduction of the Tower Number Field Sieve algorithm (TNFS) for extension fields. The Special TNFS is very efficient in finite fields that are target groups of pairings on elliptic curves, where the characteristic is special (e.g.~sparse). The key sizes for pairings should be increased, and alternative pairing-friendly curves can be considered. We revisit the Special variant of TNFS for pairing-friendly curves. In this case the characteristic is given by a polynomial of moderate degree (between 4 and 38) and tiny coefficients, evaluated at an integer (a seed). We present a polynomial selection with a new practical trade-off between degree and coefficient size. As a consequence, the security of curves computed by Barbulescu, El~Mrabet and Ghammam in 2019 should be revised: we obtain a smaller estimated cost of STNFS for all curves except BLS12 and BN. To obtain TNFS-secure curves, we reconsider the Brezing--Weng generic construction of families of pairing-friendly curves and estimate the cost of our new Special TNFS algorithm for these curves. This improves on the work of Fotiadis and Konstantinou, Fotiadis and Martindale, and Barbulescu, El~Mrabet and Ghammam. We obtain a short-list of interesting families of curves that are resistant to the Special TNFS algorithm, of embedding degrees 10 to 16 for the 128-bit security level. We conclude that at the 128-bit security level, BLS-12 and Fotiadis--Konstantinou--Martindale curves with $k=12$ over a 440 to 448-bit prime field seem to be the best choice for pairing efficiency. We also give hints at the 192-bit security level.

ASCON is an authenticated encryption, selected as the first choice for a lightweight use case in the CAESAR competition in February 2019. In this work, we investigate vulnerabilities of ASCON against fault analysis. We observe that the use of 128-bit random nonce makes it resistant against many cryptanalysis techniques like differential, linear, etc. and their variants. However, XORing the key just before releasing the tag T (a public value) creates a trivial attack path. Also, the S-Box demonstrates a non-random behavior towards subset cryptanalysis. We observe that if the 3rd bit of the S-box input is set to zero, then XoR of the last two output bits is zero, with a probability of $0.625$, i.e., this characteristic is present in 10 out of 16 cases. Our subset fault analysis(SSFA) attack uses this property to retrieve the 128-bit secret key. The SSFA attack can uniquely retrieve the key of full-round ASCON with the complexity of $2^{64}$.

Protection against active physical attacks is of serious concerns of cryptographic hardware designers. Introduction of SIFA invalidating several previously-thought-effective countermeasures, made this challenge even harder. Here in this work we deal with error correction, and introduce a methodology which shows, depending on the selected adversary model, how to correctly embed error-correcting codes in a cryptographic implementation. Our construction guarantees the correction of faults, in any location of the circuit and at any clock cycle, as long as they fit into the underlying adversary model. Based on case studies evaluated by open-source fault diagnostic tools, we claim protection against SIFA.

Post-quantum cryptography has received increased attention in recent years, in particular, due to the standardization effort by NIST. One of the second-round candidates in the NIST post-quantum standardization project is Picnic, a post-quantum secure signature scheme based on efficient zero-knowledge proofs of knowledge. In this work, we present the first FPGA implementation of Picnic. We show how to efficiently calculate LowMC, the block cipher used as a one-way function in Picnic, in hardware despite the large number of constants needed during computation. We then combine our LowMC implementation and efficient instantiations of Keccak to build the full Picnic algorithm. Additionally, we conform to recently proposed hardware interfaces for post-quantum schemes to enable easier comparisons with other designs. We provide evaluations of our Picnic implementation for both, the standalone design and a version wrapped with a PCIe interface, and compare them to the state-of-the-art software implementations of Picnic and similar hardware designs. Concretely, signing messages on our FPGA takes 0.25 ms for the L1 security level and 1.24 ms for the L5 security level, beating existing optimized software implementations by a factor of 4.

Certificateless signature was proposed by Al-Riyami and Paterson to eliminate the certificate management in the public-key infrastructures and solve the key escrow problem in the identity-based signature. In 2007, Hu et al. proposed a generic construction of certificateless signature. They construct certificateless signature scheme from any standard identity-based signature and signature scheme.However, their security reduction is loose; the security of the constructed scheme depends on the number of users. In this paper, we give the tight reduction for their construction and instantiate a tightly-secure certificateless signature scheme without pairing from DDH assumption. Best of our knowledge, this scheme is the first tightly-secure certificateless signature scheme.

The Enhanced Privacy ID (EPID) scheme is currently used for hardware enclave attestation by an increasingly large number of platforms that implement Intel Software Guard Extensions (SGX). However, the scheme currently deployed by Intel is supported on Elliptic Curve Cryptography (ECC), and will become insecure should a large quantum computer become available. As part of National Institute of Standards and Technology (NIST)'s effort for the standardisation of post-quantum cryptography, there has been a great boost in research on lattice-based cryptography. As this type of cryptography is more widely used, one expects that hardware platforms start integrating specific instructions that accelerate its execution. In this article, a new EPID scheme is proposed, supported on lattice primitives, that may benefit not only from future research developments in post-quantum cryptography, but also from instructions that may extend Intel's Instruction Set Architecture (ISA) in the future. This paper presents a new security model for EPID in the Universal Composability (UC) framework. The proposed Lattice-based EPID (LEPID) scheme is proved secure under the new model. Experimentally compared with a closely related Lattice-based Direct Anonymous Attestation (DAA) (LDAA) scheme from related art, it is shown that the private-key size is reduced 1.5 times, and that signature and verification times are sped up up to 1.4 and 1.1 times, respectively, for the considered parameters, when LEPID is compared with LDAA. Moreover, the signature size compares favourably to LDAA for small and medium-sized communities.

Privacy-preserving machine learning (PPML) via Secure Multi-party Computation (MPC) has gained momentum in the recent past. Assuming a minimal network of pair-wise private channels, we propose an efficient four-party PPML framework over rings $\Z{\ell}$, FLASH, the first of its kind in the regime of PPML framework, that achieves the strongest security notion of Guaranteed Output Delivery (all parties obtain the output irrespective of adversary's behaviour). The state of the art ML frameworks such as ABY3 by {\em Mohassel et.al} (ACM CCS'18) and SecureNN by {\em Wagh et.al} (PETS'19) operate in the setting of $3$ parties with one malicious corruption but achieve the {\em weaker} security guarantee of {\em abort}. We demonstrate PPML with real-time efficiency, using the following custom-made tools that overcome the limitations of the aforementioned state-of-the-art-- (a) {\em dot product}, which is independent of the vector size unlike the state-of-the-art ABY3, SecureNN and ASTRA by {\em Chaudhari et.al} (ACM CCSW'19), all of which have linear dependence on the vector size. (b) {\em Truncation}, which is constant round and free of circuits like Ripple Carry Adder (RCA), unlike ABY3 which uses these circuits and has round complexity of the order of depth of these circuits. We then exhibit the application of our FLASH framework in the secure server-aided prediction of vital algorithms-- Linear Regression, Logistic Regression, Deep Neural Networks, and Binarized Neural Networks. We substantiate our theoretical claims through improvement in benchmarks of the aforementioned algorithms when compared with the current best framework ABY3. All the protocols are implemented over a 64-bit ring in LAN and WAN. Our experiments demonstrate that, for MNIST dataset, the improvement (in terms of throughput) ranges from $11\times$ to $1395\times$ over LAN and WAN together.

Multiplicative complexity (MC) is defined as the minimum number of AND gates required to implement a function with a circuit over the basis (AND, XOR, NOT). Boolean functions with MC 1 and 2 have been characterized in Fischer and Peralta ( 2002) and Find et al. (2017), respectively. In this work, we identify the affine equivalence classes for functions with MC 3 and 4. In order to achieve this, we utilize the notion of the dimension $dim(f)$ of a Boolean function in relation to its linearity dimension, and provide a new lower bound suggesting that multiplicative complexity of $f$ is at least $\ceil{dim(f)/2}$. For MC 3, this implies that there are no equivalence classes other than those $24$ identified in Calik et al (2018). Using the techniques from Calik et al. (2018) and the new relation between dimension and MC, we identify the 1277 equivalence classes having MC 4. We also provide a closed formula for the number of $n$-variable functions with MC 3 and 4. The techniques allow us to construct MC-optimal circuits for Boolean functions that have MC 4 or less, independent of the number of variables they are defined on.

Nowadays, we spend our life juggling with many devices such as smartphones, tablets or laptops, and we expect to easily and efficiently switch between them without losing time or security. However, most applications have been designed for single device usage. This is the case for secure instant messaging (SIM) services based on the Signal protocol, that implements the Double Ratchet key exchange algorithm. While some adaptations, like the Sesame protocol released by the developers of Signal, have been proposed to fix this usability issue, they have not been designed as specific multi-device solutions and no security model has been formally defined either. In addition, even though the group key exchange problematic appears related to the multi-device case, group solutions are too generic and do not take into account some properties of the multi-device setting.Indeed, the fact that all devices belong to a single user can be exploited to build more efficient solutions. In this paper, we propose a Multi-Device Instant Messaging protocol based on Signal, ensuring all the security properties of the original Signal.

Forward security ensures that compromise of entities today does not impact the security of cryptographic primitives employed in the past. Such a form of security is regarded as increasingly important in the modern world due to the existence of adversaries with mass storage capabilities and powerful infiltration abilities. Although the idea of forward security has been known for over 30 years, current understanding of what it really should mean is limited due to the prevalence of new techniques and inconsistent terminology. We survey existing methods for achieving forward security for different cryptographic primitives and propose new definitions and terminology aimed at a unified treatment of the notion.

In this paper we introduce new Montgomery and Edwards form elliptic curve targeted at the 256-bit security level. To this end, we work with three primes, namely $p_1:=2^{506}-45$, $p_2=2^{510}-75$ and $p_3:=2^{521}-1$. While $p_3$ has been considered earlier in the literature, $p_1$ and $p_2$ are new. We define a pair of birationally equivalent Montgomery and Edwards form curves over all the three primes. Efficient 64-bit assembly implementations targeted at Skylake and later generation Intel processors have been made for the shared secret computation phase of the Diffie-Hellman key agreement protocol for the new Montgomery curves. Curve448 of the Transport Layer Security, Version 1.3 is a Montgomery curve which provides security at the 224-bit security level. Compared to the best publicly available 64-bit implementation of Curve448, the new Montgomery curve over $p_1$ leads to a $3\%$-$4\%$ slowdown and the new Montgomery curve over $p_2$ leads to a $4.5\%$-$5\%$ slowdown; on the other hand, 29 and 30.5 extra bits of security respectively are gained. For designers aiming for the 256-bit security level, the new curves over $p_1$ and $p_2$ provide an acceptable trade-off between security and efficiency.

We present the first actively secure variant of a distributed signature scheme based on isogenies. The protocol produces signatures from the recent CSI-FiSh signature scheme. Our scheme works for any access structure, as we use a replicated secret sharing scheme to define the underlying secret sharing; as such it is only practical when the number of maximally unqualified sets is relatively small. This, however, includes the important case of full threshold, and $(n,t)$-threshold schemes when $n$ is small.

Authenticated encryption (AE) schemes are widely used to secure communications because they can guarantee both confidentiality and authenticity of a message. In addition to the standard AE security notion, some recent schemes offer extra robustness, i.e. they maintain security in some misuse scenarios. In particular, Ashur, Dunkelman and Luykx proposed a generic AE construction at CRYPTO'17 that is secure even when releasing unverified plaintext (the RUP setting), and a concrete instantiation, GCM-RUP. The designers proved that GCM-RUP is secure up to the birthday bound in the nonce-respecting model. In this paper, we perform a birthday-bound universal forgery attack against GCM-RUP, matching the bound of the proof. While there are simple distinguishing attacks with birthday complexity on GCM-RUP, our attack is much stronger: we have a partial key recovery leading to universal forgeries. For reference, the best known universal forgery attack against GCM requires $2^{2n/3}$ operations, and many schemes do not have any known universal forgery attacks faster than $2^n$. This suggests that GCM-RUP offers a different security trade-off than GCM: stronger protection in the RUP setting, but more fragile when the data complexity reaches the birthday bound. In order to avoid this attack, we suggest a minor modification of GCM-RUP that seems to offer better robustness at the birthday bound.

Functional Encryption (FE) has been widely studied in the last decade, as it provides a very useful tool for restricted access to sensitive data: from a ciphertext, it allows specific users to learn a function of the underlying plaintext. In practice, many users may be interested in the same function on the data, say the mean value of the inputs, for example. The conventional definition of FE associates each function to a secret decryption functional key and therefore all the users get the same secret key for the same function. This induces an important problem: if one of these users (called a traitor) leaks or sells the decryption functional key to be included in a pirate decryption tool, then there is no way to trace back its identity. Our objective is to solve this issue by introducing a new primitive, called Traceable Functional Encryption: the functional decryption key will not only be specific to a function, but to a user too, in such a way that if some users collude to produce a pirate decoder that successfully evaluates a function on the plaintext, from the ciphertext only, one can trace back at least one of them. We propose a concrete solution for Inner Product Functional Encryption (IPFE). We first remark that the ElGamal-based IPFE from Abdalla et. al. in PKC '15 shares many similarities with the Boneh-Franklin traitor tracing from CRYPTO '99. Then, we can combine these two schemes in a very efficient way, with the help of pairings, to obtain a Traceable IPFE with black-box confirmation.

The Legendre PRF relies on the conjectured pseudorandomness properties of the Legendre symbol with a hidden shift. Originally proposed as a PRG by Damgård at CRYPTO 1988, it was recently suggested as an efficient PRF for multiparty computation purposes by Grassi et al. at CCS 2016. Moreover, the Legendre PRF is being considered for usage in the Ethereum 2.0 blockchain. This paper improves previous attacks on the Legendre PRF and its higher-degree variant due to Khovratovich by reducing the time complexity from $O(p\log{p}/M)$ to $O(p\log^2{p}/M^2)$ Legendre symbol evaluations when $M \le \sqrt[4]{p \log^2 p}$ queries are available. The practical relevance of our improved attack is demonstrated by breaking three concrete instances of the PRF proposed by the Ethereum foundation. Furthermore, we generalize our attack in a nontrivial way to the higher-degree variant of the Legendre PRF and we point out a large class of weak keys for this construction. Lastly, we provide the first security analysis of two additional generalizations of the Legendre PRF originally proposed by Damgård in the PRG setting, namely the Jacobi PRF and the power residue PRF.

Modern key exchange protocols are usually based on the Diffie-Hellman (DH) primitive. The beauty of this primitive, among other things, is its potential reusage of key shares: DH shares can be either used a single time or in multiple runs. Since DH-based protocols are insecure against quantum adversaries, alternative solutions have to be found when moving to the post-quantum setting. However, most post-quantum candidates, including schemes based on lattices and even supersingular isogeny DH, are not known to be secure under key reuse. In particular, this means that they cannot be necessarily deployed as an immediate DH substitute in protocols. In this paper, we introduce the notion of a split key encapsulation mechanism (split KEM) to translate the desired key-reusability of a DH-based protocol to a KEM-based flow. We provide the relevant security notions of split KEMs and show how the formalism lends itself to lifting Signal's X3DH handshake to the post-quantum KEM setting without additional message flows. Although the proposed framework conceptually solves the raised issues, instantiating it securely from post-quantum assumptions proved to be non-trivial. We give passively secure instantiations from (R)LWE, yet overcoming the above-mentioned insecurities under key reuse in the presence of active adversaries remains an open problem. Approaching one-sided key reuse, we provide a split KEM instantiation that allows such reuse based on the KEM introduced by Kiltz (PKC 2007), which may serve as a post-quantum blueprint if the underlying hardness assumption (gap hashed Diffie-Hellman) holds for the commutative group action of CSIDH (Asiacrypt 2018). The intention of this paper hence is to raise awareness of the challenges arising when moving to KEM-based key exchange protocols with key-reusability, and to propose split KEMs as a specific target for instantiation in future research.

We introduce a new technique for building multivariate encryption schemes based on random linear codes. The construction is versatile, naturally admitting multiple modifications. Among these modifications is an interesting embedding modifier--- any efficiently invertible multivariate system can be embedded and used as part of the inversion process. In particular, even small scale secure multivariate signature schemes can be embedded producing reasonably efficient encryption schemes. Thus this technique offers a bridge between multivariate signatures, many of which have remained stable and functional for many years, and multivariate encryption, a historically more troubling area.

The disruptive blockchain technology is expected to have broad applications in many areas due to its advantages of transparency, fault tolerance, and decentralization, but the open nature of blockchain also introduces severe privacy issues. Since anyone can deduce private information about relevant accounts, different privacy-preserving techniques have been proposed for cryptocurrencies under the UTXO model, e.g., Zerocash and Monero. However, it is more challenging to protect privacy for account-model blockchains (e.g., Ethereum) since it is much easier to link accounts in the account-model blockchain. In this paper, we propose BlockMaze, an efficient privacy-preserving account-model blockchain based on zk-SNARKs. Along with dual-balance model, BlockMaze achieves strong privacy guaran- tees by hiding account balances, transaction amounts, and linkage between senders and recipients. Moreover, we provide formal security definitions and prove the security of BlockMaze. Finally, we implement a prototype of BlockMaze based on Libsnark and Go-Ethereum, and conduct extensive experiments to evaluate its performance. Our 300-node experiment results show that BlockMaze has high efficiency in computation and transaction throughput: one transaction verification takes about 13.8 ms, one transaction generation takes 4.6-18.2 seconds, and its throughput is around 20 TPS.

In a Conditional Disclosure of Secrets (CDS) a verifier V wants to reveal a message m to a prover P conditioned on the fact that x is an accepting instance of some NP-language L. An honest prover (holding the corresponding witness w) always obtains the message m at the end of the interaction. On the other hand, if x is not in L we require that no PPT P* can learn the message m. We introduce laconic CDS, a two round CDS protocol with optimal computational cost for the verifier V and optimal communication cost. More specifically, the verifier's computation and overall communication grows with poly(|x|,\lambda,log(T)), where \lambda is the security parameter and T is the verification time for checking that x is in L (given w). We obtain constructions of laconic CDS under standard assumptions, such as CDH or LWE. Laconic CDS serves as a powerful tool for "maliciousifying" semi-honest protocols while preserving their computational and communication complexities. To substantiate this claim, we consider the setting of non-interactive secure computation: Alice wants to publish a short digest corresponding to a private large input x on her web page such that (possibly many) Bob, with a private input y, can send a short message to Alice allowing her to learn C(x,y) (where C is a public circuit). The protocol must be reusable in the sense that Bob can engage in arbitrarily many executions on the same digest. In this context we obtain the following new implications. (1) UC Secure Bob-optimized 2PC: We obtain a UC secure protocol where Bob's computational cost and the communication cost of the protocol grows with poly(|x|,|y|,\lambda, d), where d is the depth of the computed circuit C. (2) Malicious Laconic Function Evaluation: Next, we move on to the setting where Alice's input x is large. For this case, UC secure protocols must have communication cost growing with x. Thus, with the goal of achieving better efficiency, we consider a weaker notion of malicious security. For this setting, we obtain a protocol for which Bob's computational cost and the communication cost of the protocol grows with poly(|y|,\lambda, d), where d is the depth of the computed circuit C.

In this paper we develop a number of generic techniques and algorithms in spectral analysis of large linear approximations for use in cryptanalysis. We apply the developed tools for cryptanalysis of ZUC-256 and give a distinguishing attack with complexity around $2^{236}$. Although the attack is only $2^{20}$ times faster than exhaustive key search, the result indicates that ZUC-256 does not provide a source with full 256-bit entropy in the generated keystream, which would be expected from a 256-bit key. To the best of our knowledge, this is the first known academic attack on full ZUC-256 with a computational complexity that is below exhaustive key search.

Particular instantiations of the Offset Merkle Damgaard authenticated encryption scheme (OMD) represent highly secure alternatives for AES-GCM. It is already a fact that OMD can be efficiently implemented in software. Given this, in our paper we focus on speeding-up OMD in hardware, more precisely on FPGA platforms. Thus, we propose a new OMD instantiation based on the compression function of BLAKE2b. Moreover, to the best of our knowledge, we present the first FPGA implementation results for the SHA-512 instantiation of OMD as well as the first architecture of an online authenticated encryption system based on OMD.

Secure distance measurement and therefore secure Time-of-Arrival (ToA) measurement is critical for applications such as contactless payments, passive-keyless entry and start systems, and navigation systems. This paper initiates the study of Message Time of Arrival Codes (MTACs) and their security. MTACs represent a core primitive in the construction of systems for secure ToA measurement. By surfacing MTACs in this way, we are able for the first time to formally define the security requirements of physical-layer measures that protect ToA measurement systems against attacks. Our viewpoint also enables us to provide a unified presentation of existing MTACs (such as those proposed in distance-bounding protocols and in a secure distance measurement standard) and to propose basic principles for protecting ToA measurement systems against attacks that remain unaddressed by existing mechanisms. We also use our perspective to systematically explore the tradeoffs between security and performance that apply to all signal modulation techniques enabling ToA measurements.

Mobile autonomous systems, robots, and cyber-physical systems rely on accurate positioning information. To conduct distance-measurement, two devices exchange signals and, knowing these signals propagate at the speed of light, the time of arrival is used for distance estimations. Existing distance- measurement techniques are incapable of protecting against adversarial distance enlargement—a highly devastating tactic in which the adversary reissues a delayed version of the signals transmitted between devices, after distorting the authentic signal to prevent the receiver from identifying it. The adversary need not break crypto, nor compromise any upper- layer security protocols for mounting this attack. No known solution currently exists to protect against distance enlargement. We present Ultra-Wideband Enlargement Detection (UWB-ED), a new modulation technique to detect distance enlargement attacks, and securely verify distances between two mutually trusted devices. We analyze UWB-ED under an adversary that injects signals to block/modify authentic signals. We show how UWB-ED is a good candidate for 802.15.4z Low Rate Pulse and the 5G standard.

Decentralized protocols which require synchronous communication usually achieve it with the help of the time that computer clocks show. These clocks are mostly adjusted by centralized systems such as Network Time Protocol (NTP) because these adjustments are indispensable to reduce the effects of random drifts on clocks. On the other hand, an attack on these systems (which has happened in the past) can cause corruption of the protocols which rely on the time data that they provide to preserve synchronicity. So, we are facing the dilemma of relying on a centralized solution to adjust our timers or risking the security of our decentralized protocols. In this paper, we propose a Global Universal Composable (GUC) model for the physical clock synchronization problem in the decentralized systems by modeling the notion of consensus on clocks. Consensus on clocks is agreed upon considering the local clocks of all parties in a protocol which are possibly drifted. In this way, we model the functionality that e.g. NTP provides in a decentralized manner. In the end, we give a simple but useful protocol relying on a blockchain network that realizes our model. Our protocol can be used by the full nodes of a blockchain that need synchronous clocks in the real world to preserve the correctness and the security of the blockchain protocol. One advantage of our protocol is that it does not cause any extra communication overhead on the underlying blockchain protocol.

In this work, we study message authentication code (MAC) schemes supporting variable tag lengths. We provide a formalisation of such a scheme. Several variants of the classical Wegman- Carter MAC scheme are considered. Most of these are shown to be insecure by pointing out detailed attacks. One of these schemes is highlighted and proved to be secure. We further build on this scheme to obtain single-key variable tag length MAC schemes utilising either a stream cipher or a short-output pseudo-random function. These schemes can be efficiently instantiated using practical well known primitives.

With the proliferation of data and emerging data-driven applications, how to perform data analytical operations while respecting privacy concerns has become a very interesting research topic. With the advancement of communication and computing technologies, e.g. the FoG computing concept and its associated Edge computing technologies, it is now appealing to deploy decentralized data-driven applications. Following this trend, in this paper, we investigate privacy-preserving singular value decomposition (SVD) solutions tailored for these new computing environments. We first analyse a privacy-preserving SVD solution by Chen et al., which is based on the Paillier encryption scheme and some heuristic randomization method. We show that (1) their solution leaks statistical information to an individual player in the system; (2) their solution leaks much more information when more than one players collude. Based on the analysis, we present a new solution, which distributes the SVD results into two different players in a privacy-preserving manner. In comparison, our solution minimizes the information leakage to both individual player and colluded ones, via randomization and threshold homomorphic encryption techniques.

The cloud changed the way we manage and store data. Today, cloud storage services offer clients an infrastructure that allows them a convenient source to store, replicate, and secure data online. However, with these new capabilities also come limitations, such as lack of transparency, limited decentralization, and challenges with privacy and security. And, as the need for more agile, private and secure data solutions continues to grow exponentially, rethinking the current structure of cloud storage is mission-critical for enterprises. By leveraging and building upon blockchain’s unique attributes, including immutability, security to the data element level, distributed (no single point of failure), we have developed a solution prototype that allows data to be reliably stored while simultaneously being secured, with tamper-evident auditability, via blockchain. The result, Audita, is a flexible solution that assures data protection and solves challenges such as scalability and privacy. Audita works via an augmented blockchain network of participants that include storage-nodes and block-creators. In addition, it provides an automatic and fair challenge system to assure that data is distributed and reliably and provably stored. While the prototype is built on Quorum, the solution framework can be used with any blockchain platform. The benefit is a system that is built to grow along with the data needs of enterprises, while continuing to build the network via incentives and solving for issues such as auditing and outsourcing.

In the setting of secure multiparty computation (MPC), a set of mutually distrusting parties wish to jointly compute a function, while guaranteeing the privacy of their inputs and the correctness of the output. An MPC protocol is called fully secure if no adversary can prevent the honest parties from obtaining their outputs. A protocol is called fair if an adversary can prematurely abort the computation, however, only before learning any new information. We present highly efficient transformations from fair computations to fully secure computations, assuming the fraction of honest parties is constant (e.g., 1% of the parties are honest). Compared to previous transformations that require linear invocations (in the number of parties) of the fair computation, our transformations require super-logarithmic, and sometimes even super-constant, such invocations. The main idea is to delegate the computation to chosen random committees that invoke the fair computation. Apart from the benefit of uplifting security, the reduction in the number of parties is also useful, since only committee members are required to work, whereas the remaining parties simply "listen" to the computation over a broadcast channel. One application of these transformations is a new $\delta$-bias coin-flipping protocol, whose round complexity has a super-logarithmic dependency on the number of parties, improving over the protocol of Beimel, Omri, and Orlov (Crypto 2010) that has a linear dependency. A second application is a new fully secure protocol for computing the Boolean OR function, with a super-constant round complexity, improving over the protocol of Gordon and Katz (TCC 2009) whose round complexity is linear in the number of parties. Finally, we show that our positive results are in a sense optimal, by proving that for some functionalities, a super-constant number of (sequential) invocations of the fair computation is necessary for computing the functionality in a fully secure manner.

Kyber is a KEM based their security on the Modular Learning with Errors problem and was selected in the second round of NIST Post-quantum standardization process. Before we put Kyber into practical application, it is very important to assess its security in hard practical conditions especially when the Fujisaki-Okamoto transformations are neglected. In this paper, we propose an efficient key mismatch attacks on Kyber, which can recover one participant's secret key if the public key is reused. We first define the oracles in which the adversary is able to launch the attacks. Then, we show that by accessing the oracle multiple times, the adversary is able to recover the coefficients in the secret key. Furthermore, we propose two strategies to reduce the queries and time in recovering the secret key. It turns out that it is actually much easier to use key mismatch attacks to break Kyber than NewHope, another NIST second round candidate, due to their different design structures. Our implementations have demonstrated the efficiency of the proposed attacks and verified our findings. Another interesting observation from the attack is that in the most powerful Kyber-1024, it is easier to recover each coefficient compared with that in Kyber-512 and Kyber-768. Specifically, for Kyber-512 on average we recover each coefficient with $2.7$ queries, while in Kyber-1024 and 768, we only need $2.4$ queries. This demonstrates further that implementations of LWE based schemes in practice is very delicate.

Wildcard identity-based encryption (WIBE) allows a sender to simultaneously encrypt messages to a group of users matching a certain pattern, defined as a sequence of identifiers and wildcards. We propose a novel scalable wildcarded identity-based encryption, called SWIBE, which reduces the ciphertext size to be constant. To the best of our knowledge, SWIBE is the first wildcard identity-based encryption scheme that generates a constant size ciphertext regardless of the depth of the identities with fast decryption. The proposed scheme improves the decryption time. According to our experiment results, decryption of the SWIBE scheme is 3, 10, and 650 times faster than existing WIBE, WW-IBE, and CCP-ABE schemes. The SWIBE scheme also subsumes the generalized key derivation naturally by allowing wildcards in the key delegation process. We prove CPA security of the proposed scheme and extend it to be CCA secure.

We present the first maliciously secure protocol for succinct non-interactive secure two-party computation (SNISC): Each player sends just a single message whose length is (essentially) independent of the running time of the function to be computed. The protocol does not require any trusted setup, satisfies superpolynomial-time simulation-based security (SPS), and is based on (subexponential) security of the Learning With Errors (LWE) assumption. We do not rely on SNARKs or "knowledge of exponent"-type assumptions. Since the protocol is non-interactive, the relaxation to SPS security is needed, as standard polynomial-time simulation is impossible; however, a slight variant of our main protocol yields a SNISC with polynomial-time simulation in the CRS model.

Generating secret shares of a shuffled dataset - such that neither party knows the order in which it is permuted - is a fundamental building block in many protocols, such as secure collaborative filtering, oblivious sorting, and secure function evaluation on set intersection. Traditional approaches to this problem either involve expensive public-key based crypto or using symmetric crypto on permutation networks. While public-key based solutions are bandwidth efficient, they are computation-bound. On the other hand, permutation network based constructions are communication-bound, especially when the elements are long, for example feature vectors in an ML context. We design a new 2-party protocol for this task of computing secret shares of shuffled data, which we refer to as secret-shared shuffle. Our protocol is secure against static semi-honest adversary. At the heart of our approach is a new method of obtaining two sets of pseudorandom shares which are ``correlated via the permutation'', which can be implemented with low communication using GGM puncturable PRFs. This gives a new protocol for secure shuffle which is concretely more efficient than the existing techniques in the literature. In particular, we are three orders of magnitude faster than public key based approach and one order of magnitude faster compared to the best known symmetric-key cryptography approach based on permutation network when the elements are moderately large.

We revisit the well-studied problem of extracting nearly uniform randomness from an arbitrary source of sufficient min-entropy. Strong seeded extractors solve this problem by relying on a public random seed, which is unknown to the source. Here, we consider a setting where the seed is reused over time and the source may depend on prior calls to the extractor with the same seed. Can we still extract nearly uniform randomness? In more detail, we assume the seed is chosen randomly, but the source can make arbitrary oracle queries to the extractor with the given seed before outputting a sample. We require that the sample has entropy and differs from any of the previously queried values. The extracted output should look uniform even to a distinguisher that gets the seed. We consider two variants of the problem, depending on whether the source only outputs the sample, or whether it can also output some correlated public auxiliary information that preserves the sample's entropy. Our results are: * Without Auxiliary Information: We show that every pseudo-random function (PRF) with a sufficiently high security level is a good extractor in this setting, even if the distinguisher is computationally unbounded. We further show that the source necessarily needs to be computationally bounded and that such extractors imply one-way functions. * With Auxiliary Information: We construct secure extractors in this setting, as long as both the source and the distinguisher are computationally bounded. We give several constructions based on different intermediate primitives, yielding instantiations based on the DDH, DLIN, LWE or DCR assumptions. On the negative side, we show that one cannot prove security against computationally unbounded distinguishers in this setting under any standard assumption via a black-box reduction. Furthermore, even when restricting to computationally bounded distinguishers, we show that there exist PRFs that are insecure as extractors in this setting and that a large class of constructions cannot be proven secure via a black-box reduction from standard assumptions.

We construct new protocols for two parties to securely compute on the items in their intersection. Our protocols make use of an untrusted third party that has no input. The use of this party allows us to construct highly efficient protocols that are secure against a single malicious corruption.

The first construction of Witness Encryption (WE) by Garg et al. (STOC 2013) has led to many exciting avenues of research in the past years. A particularly interesting variant is Offline WE (OWE) by Abusalah et al. (ACNS 2016), as the encryption algorithm uses neither obfuscation nor multilinear maps. Current OWE schemes provide only selective security. That is, the adversary must commit to their challenge messages $m_0$ and $m_1$ before seeing the public parameters. We provide a new, generic framework to construct OWE, which achieves adaptive security in the sense that the adversary may choose their challenge messages adaptively. We call this semi-adaptive security, because - as in prior work - the instance of the considered NP language that is used to create the challenge ciphertext must be fixed before the parameters are generated in the security proof. We show that our framework gives the first OWE scheme with constant ciphertext overhead even for messages of polynomially-bounded size. We achieve this by introducing a new variant of puncturable encryption defined by Green and Miers (S&P 2015) and combining it with the iO-based approach of Abusalah et al. Finally, we show that our framework can be easily extended to construct the first Extractable Offline Witness Encryption (EOWE), by using extractability obfuscation of Boyle et al. (TCC 2014) in place of iO, opening up even more possible applications. The obfuscation is needed only for our public parameters, but its functionality can be realised with a Trusted Execution Environment (TEE), which means we have a very efficient scheme with ciphertexts consisting of only 5 group elements.

We give an overview of our critiques of “proofs” of security and a guide to our papers on the subject that have appeared over the past decade and a half. We also provide numerous additional examples and a few updates and errata.

Verifiable random functions (VRFs) are essentially digital signatures with additional properties, namely verifiable uniqueness and pseudorandomness, which make VRFs a useful tool, e.g., to prevent enumeration in DNSSEC Authenticated Denial of Existence and the CONIKS key management system, or in the random committee selection of the Algorand blockchain. Most standard-model VRFs rely on admissible hash functions (AHFs) to achieve security against adaptive attacks in the standard model. Known AHF constructions are based on error-correcting codes, which yield asymptotically efficient constructions. However, previous works do not clarify how the code should be instantiated concretely in the real world. The rate and the minimal distance of the selected code have significant impact on the efficiency of the resulting cryptosystem, therefore it is unclear if and how the aforementioned constructions can be used in practice. First, we explain inherent limitations of code-based AHFs. Concretely, we show that even if we were given codes that achieve the well-known Gilbert-Varshamov or McEliece-Rodemich-Rumsey-Welch bounds, existing AHF-based constructions of VRFs can only be instantiated quite inefficiently. Then we introduce and construct computational AHFs (cAHFs). While classical AHFs are information-theoretic, and therefore work even in presence of computationally unbounded adversaries, cAHFs provide only security against computationally bounded adversaries. However, we show that cAHFs can be instantiated significantly more efficiently. Finally, we present a new VRF scheme using cAHFs and show that it is currently the most efficient verifiable random function with full adaptive security in the standard model.

Machine Learning has been widely applied in practice, such as disease diagnosis, target detection. Commonly, a good model relies on massive training data collected from different sources. However, the collected data might expose sensitive information. To solve the problem, researchers have proposed many excellent methods that combine machine learning with privacy protection technologies, such as secure multiparty computation(MPC), homomorphic encryption(HE), and differential privacy. In the meanwhile, some other researchers proposed distributed machine learning which allows the clients to store their data locally but train a model collaboratively. The first kind of method focuses on security, but the performance and accuracy remain to be improved, while the second provides higher accuracy and better performance but weaker security, for instance, the adversary can launch membership attacks from the gradients' updates in plaintext. In this paper, we join secret sharing to distributed machine learning to achieve reliable performance, accuracy and high-level security. Next, we design, implement, and evaluate a practical system to jointly learn an accurate model under semi-honest and servers-only malicious adversary security, respectively. And the experiments show our protocols achieve the best overall performance as well.

Many isogeny-based cryptosystems are believed to rely on the hardness of the Supersingular Decision Diffie-Hellman (SSDDH) problem. However, most cryptanalytic efforts have treated the hardness of this problem as being equivalent to the more generic supersingular $\ell^e$-isogeny problem --- an established hard problem in number theory. In this work, we shine some light on the possibility that the combination of two additional pieces of information given in practical SSDDH instances --- the image of the torsion subgroup, and the starting curve's endomorphism ring --- can lead to better attacks cryptosystems relying on this assumption. We show that SIKE/SIDH are secure against our techniques. However, in certain settings, e.g., multi-party protocols, our results may suggest a larger gap between the security of these cryptosystems and the $\ell^e$-isogeny problem. Our analysis relies on the ability to find many endomorphisms on the base curve that have special properties. To the best of our knowledge, this class of endomorphisms has never been studied in the literature. We informally discuss the parameter sets where these endomorphisms should exist. We also present an algorithm which may provide information about additional torsion points under the party's private isogeny, which is of independent interest. Finally, we present a minor variation of the SIKE protocol that avoids exposing a known endomorphism ring.

We propose the first auctioneer-free sealed-bid auction protocol with a linear computation and communication complexity $O(c)$, $c$ being the bit length of the bid price. Our protocol, called Self-Enforcing Auction Lot (SEAL), operates in a decentralized setting, where bidders jointly compute the maximum bid while preserving the privacy of losing bids. In our protocol, we do not require any secret channels between participants. All operations are publicly verifiable; everyone including third-party observers is able to verify the integrity of the auction outcome. Upon learning the highest bid, the winner comes forward with a proof to prove that she is the real winner. Based on the proof, everyone is able to check if there is only one winner or there is a tie. While our main protocol works with the first-price sealed-bid, it can be easily extended to support the second-price sealed-bid (also known as the Vickrey auction), revealing only the winner and the second highest bid, while keeping the highest bid and all other bids secret. To the best of our knowledge, this work establishes to date the best computation and communication complexity for sealed-bid auction schemes without involving any auctioneer.

In this work, we formulate and investigate a pragmatic question related to practical side-channel attacks complemented with key enumeration. In a real attack scenario, after an attacker has extracted side-channel information, it is possible that despite the entropy of the key has been signicantly reduced, she cannot yet achieve a direct key recovery. If the correct key lies within a sufficiently small set of most probable keys, it can then be recovered with a plaintext and the corresponding ciphertext, by performing enumeration. Our proposal relates to the following question: how does an attacker know when to stop acquiring side-channel observations and when to start enumerating with a given computational effort? Since key enumeration is an expensive (i.e. time-consuming) task, this is an important question from an adversarial viewpoint. To answer this question, we present an efficient (heuristic) way to perform key-less rank estimation, based on simple entropy estimations using histograms.

Selling digital commodities securely over the Internet is a challenging task when Seller and Buyer do not trust each other. With the advent of cryptocurrencies, one prominent solution for digital exchange is to rely on a smart contract as a trusted arbiter that fairly resolves disputes when Seller and Buyer disagree. Such protocols have an optimistic mode, where the digital exchange between the parties can be completed with only minimal interaction with the smart contract. In this work we present OptiSwap, a new smart contract based fair exchange protocol that significantly improves the optimistic case of smart contract based fair exchange protocols. In particular, OptiSwap has almost no overhead in communication complexity, and improves on the computational overheads of the parties compared to prior solutions. An additional feature of OptiSwap is a protection mechanism against so-called grieving attacks, where an adversary attempts to violate the financial fairness of the protocol by forcing the honest party to pay fees. We analyze OptiSwap's security in the UC model and provide benchmark results over Ethereum.

Elliptic curves play a prominent role in cryptography. For instance, the hardness of the elliptic curve discrete logarithm problem is a foundational assumption in public key cryptography. Drinfeld modules are positive characteristic function field analogues of elliptic curves. It is natural to ponder the existence/security of Drinfeld module analogues of elliptic curve cryptosystems. But the Drinfeld module discrete logarithm problem is easy even on a classical computer. Beyond discrete logarithms, elliptic curve isogeny based cryptosystems have have emerged as candidates for post-quantum cryptography, including supersingular isogeny Diffie-Hellman (SIDH) and commutative supersingular isogeny Diffie-Hellman (CSIDH) protocols. We formulate Drinfeld module analogues of these elliptic curve isogeny based cryptosystems and devise classical polynomial time algorithms to break these Drinfeld analogues catastrophically.

Proactive security is the notion of defending a distributed system against an attacker who compromises different devices through its lifetime, but no more than a threshold number of them at any given time. The emergence of threshold wallets for more secure cryptocurrency custody warrants an efficient proactivization protocol tailored to this setting. While many proactivization protocols have been devised and studied in the literature, none of them have communication patterns ideal for threshold wallets. In particular a $(t,n)$ threshold wallet is designed to have $t$ parties jointly sign a transaction (of which only one may be honest) whereas even the best current proactivization protocols require at least an additional $t-1$ honest parties to come online simultaneously to refresh the system. In this work we formulate the notion of refresh with offline devices, where any $\rho$ parties may proactivize the system at any time and the remaining $n-\rho$ offline parties can non-interactively "catch up'' at their leisure. However, many subtle issues arise in realizing this pattern. We identify that this problem is divided into two settings: $(2,n)$ and $(t,n)$ where $t>2$. We develop novel techniques to address both settings as follows: - We show that the $(2,n)$ setting permits a tight $\rho$ for refresh. In particular we give a highly efficient $\rho=2$ protocol to upgrade a number of standard $(2,n)$ threshold signature schemes to proactive security with offline refresh. This protocol can augment existing implementations of threshold wallets for immediate use- we show that proactivization does not have to interfere with their native mode of operation. This technique is compatible with Schnorr, EdDSA, and even sophisticated ECDSA protocols. By implementation we show that proactivizing two different recent $(2,n)$ ECDSA protocols incurs only 14% and 24% computational overhead respectively, less than 200 bytes, and no extra round of communication. - For the general $(t,n)$ setting we prove that it is impossible to construct an offline refresh protocol with $\rho<2(t-1)$, i.e. tolerating a dishonest majority of online parties. Our techniques are novel in reasoning about the message complexity of proactive security, and may be of independent interest. Our results are positive for small-scale decentralization (such as 2FA with threshold wallets), and negative for large-scale distributed systems with higher thresholds. We thus initiate the study of proactive security with offline refresh, with a comprehensive treatment of the dishonest majority case.

In this paper, we present a selfish mining attack on the multi-stage blockchain proposed by Palash Sarkar. We provide detailed analysis of computational wastage of honest miners and biased rewards achieved by the selfish pool. In our analysis, we introduce a spy inside an honest pool which is a trivial task. Our spy is responsible for leaking the information of the stage mining from the honest pool to the selfish pool. In our analysis, we consider all the possible configurations of mining namely sequential, parallel and pipelining. In all of these configurations, we show through our mathematical equations as to how a selfish miner can succeed in wasting the computation power of the honest miner and how he can influence the reward of mining. For completeness, we provide an algorithm for performing a selfish mining attack on all the scenarios on multi-stage blockchain. To thwart selfish mining on multi-stage blockchain we redesign the original verification algorithm by introducing a new parameter called the crypto-stamp. We present a new algorithm that uses crypto-stamp during the verification process of the mined stages or blocks and is able to detect with high probability whether the stages or blocks were kept private or not.

Authenticated encryption schemes are usually expected to offer confidentiality and authenticity. In case of release of unverified plaintext (RUP), an adversary gets separated access to the decryption and verification functionality, and has more power in breaking the scheme. Andreeva et al. (ASIACRYPT 2014) formalized RUP security using plaintext awareness, informally meaning that the decryption functionality gives no extra power in breaking confidentiality, and INT-RUP security, covering authenticity in case of RUP. We describe a single, unified model, called AERUP security, that ties together these notions: we prove that an authenticated encryption scheme is AERUP secure if and only if it is conventionally secure, plaintext aware, and INT-RUP secure. We next present ANYDAE, a generalization of SUNDAE of Banik et al. (ToSC 2018/3). ANYDAE is a lightweight deterministic scheme that is based on a block cipher with block size $n$ and arbitrary mixing functions that all operate on an $n$-bit state. It is particularly efficient for short messages, it does not rely on a nonce, and it provides maximal robustness to a lack of secure state. Whereas SUNDAE is not secure under release of unverified plaintext (a fairly simple attack can be mounted in constant time), ANYDAE is. We make handy use of the AERUP security model to prove that ANYDAE achieves both conventional security as RUP security, provided that certain modest conditions on the mixing functions are met. We describe two simple instances, called MONDAE and TUESDAE, that conform to these conditions and that are competitive with SUNDAE, in terms of efficiency and optimality.

Attribute-based proxy re-encryption (ABPRE) allows a semi-trusted proxy to transform an encryption under an access-policy into an encryption under a new access policy, without revealing any information about the underlying message. Such a primitive facilitates fine-grained secure sharing of encrypted data in the cloud. In its key-policy flavor, the re-encryption key is associated with an access structure that specifies which type of ciphertexts can be re-encrypted. Only two attempts have been made towards realising key-policy ABPRE (KP-ABPRE), one satisfying replayable chosen ciphertext security (RCCA security) and the other claiming to be chosen ciphertext secure (CCA secure). We show that both the systems are vulnerable to RCCA and CCA attacks respectively. We further propose a selective CCA secure KP-ABPRE scheme in this work. Since we demonstrate attacks on the only two existing RCCA secure and CCA secure schemes in the literature, our scheme becomes the first KP-ABPRE scheme satisfying selective CCA security. Moreover, our scheme has an additional attractive property, namely collusion resistance. A proxy re-encryption scheme typically consists of three parties: a delegator who delegates his decryption rights, a proxy who performs re-encryption, and a delegatee to whom the decryption power is delegated to. When a delegator wishes to share his data with a delegatee satisfying an access-policy, the proxy can collude with the malicious delegatee to attempt to obtain the private keys of the delegator during delegation period. If the private keys are exposed, security of the delegator's data is completely compromised. The proxy or the delegatee can obtain all confidential data of the delegator at will at any time, even after the delegation period is over. Hence, achieving collusion resistance is indispensable to real-world applications. In this paper, we show that our construction satisfies collusion resistance. Our scheme is proven collusion resistant and selective CCA secure in the random oracle model, based on Bilinear Diffie-Hellman exponent assumption.

\textsf{HCTR}, proposed by Wang et al., is one of the most efficient candidates of tweakable enciphering schemes that turns an $n$-bit block cipher into a variable input length tweakable block cipher. Wang et al. have shown that \textsf{HCTR} offers a cubic security bound against all adaptive chosen plaintext and chosen ciphertext adversaries. Later in FSE 2008, Chakraborty and Nandi have improved its bound to $O(\sigma^2 / 2^n)$, where $\sigma$ is the total number of blocks queried and $n$ is the block size of the block cipher. In this paper, we propose \textbf{tweakable \textsf{HCTR}} that turns an $n$-bit tweakable block cipher to a variable input length tweakable block cipher by replacing all the block cipher calls of \textsf{HCTR} with tweakable block cipher. We show that when there is no repetition of the tweak, tweakable \textsf{HCTR} enjoys the optimal security against all adaptive chosen plaintext and chosen ciphertext adversaries. However, if the repetition of the tweak is limited, then the security of the construction remains close to the security bound in no repetition of the tweak case. Hence, it gives a graceful security degradation with the maximum number of repetition of tweaks.

Knowledge extraction, typically studied in the classical setting, is at the heart of several cryptographic protocols. The prospect of quantum computers forces us to revisit the concept of knowledge extraction in the presence of quantum adversaries. We introduce the notion of secure quantum extraction protocols. A secure quantum extraction protocol for an NP relation R is a classical interactive protocol between a sender and a receiver, where the sender gets as input the instance z and witness w while the receiver only gets the instance z as input. There are two properties associated with a secure quantum extraction protocol: (a) Extractability: for any efficient quantum polynomial-time (QPT) adversarial sender, there exists a QPT extractor that can extract a witness w' such that (z,w') \in R and, (b) Zero-Knowledge: a malicious receiver, interacting with the sender, should not be able to learn any information about w. We study and construct two flavors of secure quantum extraction protocols. - Security against QPT malicious receivers: First we consider the setting when the malicious receiver is a QPT adversary. In this setting, we construct a secure quantum extraction protocol for NP assuming the existence of quantum fully homomorphic encryption satisfying some mild properties (already satisfied by existing constructions [Mahadev, FOCS'18, Brakerski CRYPTO'18]) and quantum hardness of learning with errors. The novelty of our construction is a new non black box technique in the quantum setting. All previous extraction techniques in the quantum setting were solely based on quantum rewinding. - Security against classical PPT malicious receivers: We also consider the setting when the malicious receiver is a classical probabilistic polynomial time (PPT) adversary. In this setting, we construct a secure quantum extraction protocol for NP solely based on the quantum hardness of learning with errors. Furthermore, our construction satisfies quantum-lasting security: a malicious receiver cannot later, long after the protocol has been executed, use a quantum computer to extract a valid witness from the transcript of the protocol. Both the above extraction protocols are constant round protocols. We present an application of secure quantum extraction protocols to zero-knowledge (ZK). Assuming quantum hardness of learning with errors, we present the first construction of ZK argument systems for NP in constant rounds based on the quantum hardness of learning with errors with: (a) zero-knowledge against QPT malicious verifiers and, (b) soundness against classical PPT adversaries. Moreover, our construction satisfies the stronger (quantum) auxiliary-input zero knowledge property and thus can be composed with other protocols secure against quantum adversaries.

Blockchain protocols for cryptocurrencies offer secure payment transactions, yet their throughput pales in comparison to centralized payment systems such as VISA. Moreover, transactions incur fees that relatively hinder the adoption of cryptocurrencies for simple daily payments. Micropayment channels are second layer protocols that allow efficient and nearly unlimited number of payments between parties at the cost of only two transactions, one to initiate it and the other one to close it. Typically, the de-facto approach for micropayment channels on Ethereum is to utilize digital signatures which incur a constant gas cost but still relatively high due to expensive elliptic curve operations. Recently, ElSheikh et al. have proposed a protocol that utilizes hash chain which scales linearly with the channel capacity and has a lower cost compared to the digital signature based channel up to a capacity of 1000 micropayments. In this paper, we improve even more and propose a protocol that scales logarithmically with the channel capacity. Furthermore, by utilizing a variant of Merkle tree, our protocol does not require the payer to lock the entire balance at the channel creation which is an intrinsic limitation with the current alternatives. To assess the efficiency of our protocol, we carried out a number of experiments, and the results prove a positive efficiency and an overall low cost. Finally, we release the source code for prototype on GitHub.

This is an informal tutorial on the supersingular isogeny Diffie-Hellman protocol aimed at non-isogenists.

A reliable source of randomness is a critical element in many cryptographic systems. A public randomness beacon is a randomness source generated in a distributed manner that satisfies the following requirements: Liveness, Unpredictability, Unbiasability and Public Verifiability. In this work we introduce HERB: a new randomness beacon protocol based on additively homomorphic encryption. We show that this protocol meets the requirements listed above and additionaly provides Guaranteed Output Delivery. HERB has a modular structure with two replaceable modules: an homomorphic cryptosystem and a consensus algorithm. In our analysis we instantiate HERB using ElGamal encryption and a public blockchain. We implemented a prototype using Cosmos SDK to demonstrate the simplicity and efficiency of our approach. HERB allows splitting all protocol participants into two groups that can relate in any way. This property can be used for building more complex participation and reward systems based on the HERB solution.

Linear cryptanalysis is an important evaluation method for cryptographic primitives against key recovery attack. In this paper, we revisit the Walsh transformation for linear correlation calculation of modular addition, and an efficient algorithm is proposed to construct the input-output mask space of specified correlation weight. By filtering out the impossible large correlation weights in the first round, the search space of the first round can be substantially reduced. We introduce a new construction of combinational linear approximation table (cLAT) for modular addition with two inputs. When one input mask is fixed, another input mask and the output mask can be obtained by the \textit{Spliting-Lookup-Recombination} approach. We first split the $n$-bit fixed input mask into several sub-vectors, then, to find the corresponding bits of other masks, and in the recombination phase, pruning conditions can be used. By this approach, a large number of search branches in the middle rounds can be pruned. With the combination of the optimization strategies and the branch-and-bound search algorithm, we can improve the search efficiency for linear characteristics on ARX ciphers. The linear hulls for SPECK32/48/64 with higher average linear potential ($ALP$) than existing results have been obtained. For SPARX variants, a 11-round linear trail and a 10-round linear hull have been found for SPARX-64, a 10-round linear trail and a 9-round linear hull are obtained for SPARX-128. For Chaskey, a 5-round linear trail with correlation of $2^{-61}$ have been obtained. For CHAM-64, the 34/35-round optimal linear characteristics with correlation of $2^{-31}$/$2^{-33}$ are found.

Motivated by the algorithm of differential probability calculation of Lipmaa and Moriai, we revisit the differential properties of modular addition. We propose an efficient approach to generate the input-output difference tuples with non-zero probabilities. A novel construction of combinational DDT, which makes it possible to obtain all valid output differences for fixed input differences. According to the upper bound of differential probability of modular addition, combining the optimization strategies with branch and bound search algorithm, we can reduce the search space of the first round and prune the invalid difference branches of the middle rounds. Applying this tool, the provable optimal differential trails covering more rounds for SPECK32/48/64 with tight probabilities can be found, and the differentials with larger probabilities are also obtained. In addition, the optimal differential trails cover more rounds than exisiting results for SPARX variants are obtained. A 12-round differential with a probability of $2^{-54.83}$ for SPARX-64, and a 11-round differential trail with a probability of $2^{-53}$ for SPARX-128 are found. For CHAM-64/128 and CHAM-128/*, the 39/63-round differential characteristics we find cover 3/18 rounds more than the known results respectively.

Reverse firewalls were introduced at Eurocrypt 2015 by Mironov and Stephens-Davidowitz, as a method for protecting cryptographic protocols against attacks on the devices of the honest parties. In a nutshell: a reverse firewall is placed outside of a device and its goal is to ``sanitize'' the messages sent by it, in such a way that a malicious device cannot leak its secrets to the outside world. It is typically assumed that the cryptographic devices are attacked in a ``functionality-preserving way'' (i.e. informally speaking, the functionality of the protocol remains unchanged under this attacks). In their paper, Mironov and Stephens-Davidowitz construct a protocol for passively-secure two-party computations with firewalls, leaving extension of this result to stronger models as an open question. In this paper, we address this problem by constructing a protocol for secure computation with firewalls that has two main advantages over the original protocol from Eurocrypt 2015. Firstly, it is a multiparty computation protocol (i.e. it works for an arbitrary number $n$ of the parties, and not just for $2$). Secondly, it is secure in much stronger corruption settings, namely in the actively corruption model. More precisely: we consider an adversary that can fully corrupt up to $n-1$ parties, while the remaining parties are corrupt in a functionality-preserving way. Our core techniques are: malleable commitments and malleable non-interactive zero-knowledge, which in particular allow us to create a novel protocol for multiparty augmented coin-tossing into the well with reverse firewalls (that is based on a protocol of Lindell from Crypto 2001).

Gaudry and Lubicz introduced the idea of Kummer line in 2009, and Karati and Sarkar proposed three Kummer lines over prime fields in 2017. In this work, we explore the problem of secure and efficient scalar multiplications on binary field using Kummer line and investigate the possibilities of speedups using Kummer line compared to Koblitz curves, binary Edwards curve and Weierstrass curves. We propose a binary Kummer line $\mathsf{BKL}251$ over binary field $\mathbb{F}_{2^{251}}$ where the associated elliptic curve satisfies the required security conditions and offers 124.5-bit security which is the same as that of Binary Edwards curve $\mathsf{BEd251}$ and Weierstrass curve $\mathsf{CURVE2251}$. $\mathsf{BKL}251$ has small curve parameter and small base point. We implement our software of $\mathsf{BKL}l251$ using the instruction ${\tt PCLMULQDQ}$ of modern Intel processors and batch software $\mathsf{BBK251}$ using bitslicing technique. For fair comparison, we also implement the software $\mathsf{BEd}251$ for binary Edwards curve. In both the implementations, scalar multiplications take constant time which use Montgomery ladders. In case of left-to-right Montgomery ladder, both the Kummer line and Edwards curve have almost the same number of field operations. For right-to-left Montgomery ladder scalar multiplication, each ladder step of binary Kummer line needs less number of field operations compared to Edwards curve. Our experimental results show that left-to-right Montgomery scalar multiplications of $\mathsf{BKL}251$ are $9.63\%$ and $0.52\%$ faster than those of $\mathsf{BEd}251$ for fixed-base and variable-base, respectively. Left-to-right Montgomery scalar multiplication for variable-base of $\mathsf{BKL}251$ is 39.74\%, 23.25\% and 32.92\% faster than those of the curves $\mathsf{CURVE2251}$, K-283 and B-283 respectively. Using right-to-left Montgomery ladder with precomputation, $\mathsf{BKL}251$ achieves 17.84\% speedup over $\mathsf{BEd}251$ for fixed-base scalar multiplication. For batch computation, $\mathsf{BBK251}$ has comparatively the same (slightly faster) performance as $\mathsf{BBE251}$ and $\mathsf{sect283r1}$. Also it is clear from our experiments that scalar multiplications on $\mathsf{BKL}251$ and $\mathsf{BEd251}$ are (approximately) 65\% faster than one scalar multiplication (after scaling down) of batch software $\mathsf{BBK251}$ and $\mathsf{BBE251}$.

Machine learning has started to be deployed in fields such as healthcare and finance, which involves dealing with a lot of sensitive data. This propelled the need for and growth of privacy-preserving machine learning (PPML). We propose an actively secure four-party protocol (4PC), and a framework for PPML, showcasing its applications on four of the most widely-known machine learning algorithms -- Linear Regression, Logistic Regression, Neural Networks, and Convolutional Neural Networks. Our 4PC protocol tolerating at most one malicious corruption is practically efficient as compared to Gordon et al. (ASIACRYPT 2018) as the 4th party in our protocol is not active in the online phase, except input sharing and output reconstruction stages. Concretely, we reduce the online communication as compared to them by 1 ring element. We use the protocol to build an efficient mixed-world framework (Trident) to switch between the Arithmetic, Boolean, and Garbled worlds. Our framework operates in the offline-online paradigm over rings and is instantiated in an outsourced setting for machine learning, where the data is secretly shared among the servers. Also, we propose conversions especially relevant to privacy-preserving machine learning. With the privilege of having an extra honest party, we outperform the current state-of-the-art ABY3 (for three parties), in terms of both rounds as well as communication complexity. The highlights of our framework include using a minimal number of expensive circuits overall as compared to ABY3. This can be seen in our technique for truncation, which does not affect the online cost of multiplication and removes the need for any circuits in the offline phase. Our B2A conversion has an improvement of $\mathbf{7} \times$ in rounds and $\mathbf{18} \times$ in the communication complexity. The practicality of our framework is argued through improvements in the benchmarking of the aforementioned algorithms when compared with ABY3. All the protocols are implemented over a 64-bit ring in both LAN and WAN settings. Our improvements go up to $\mathbf{187} \times$ for the training phase and $\mathbf{158} \times$ for the prediction phase when observed over LAN and WAN.

Searchable encryption can provide secure search over encrypted cloud-based data without infringing data confidentiality and data searcher privacy. In this work, we focus on a secure search service providing fine-grained and expressive search functionality, which can be seen as a general extension of searchable encryption and called attribute-based multi-keyword search (ABMKS). In most of the existing ABMKS schemes, the ciphertext size of keyword index (encrypted index) grows linearly with the number of the keyword associated with a file, so that the computation and communication complexity of keyword index is limited to O(m) , where m is the number of the keyword. To address this shortage, we propose the first ABMKS scheme through utilizing keyword dictionary tree and the subset cover, in such a way that the ciphertext size of keyword index is not dependent on the number of underlying keyword in a file. In our design, the complexity of computation and the complexity of the keyword index are at most O ( 2· log (n/2) ) for the worst case, but O(1) for the best case, where n is the number of keyword in a keyword dictionary. We also present the security and the performance analysis to demonstrate that our scheme is both secure and efficient in practice.

We consider the problem of amplifying two-party coin-tossing protocols: given a protocol where it is possible to bias the common output by at most $\rho$, we aim to obtain a new protocol where the output can be biased by at most $\rho^\star<\rho$. We rule out the existence of a natural type of amplifiers called oblivious amplifiers for every $\rho^\star<\rho$. Such amplifiers ignore the way that the underlying $\rho$-bias protocol works and can only invoke an oracle that provides $\rho$-bias bits. We provide two proofs of this impossibility. The first is by a reduction to the impossibility of deterministic randomness extraction from Santha-Vazirani sources. The second is a direct proof that is more general and also rules outs certain types of asymmetric amplification. In addition, it gives yet another proof for the Santha-Vazirani impossibility.

Historically, fault diagnosis for integrated circuits has singularly dealt with reliability concerns. In contrast, a cryptographic circuit needs to be primarily evaluated concerning information leakage in the presence of maliciously crafted faults. While Differential Fault Attacks (DFAs) on symmetric ciphers have been known for over 20 years, recent developments have tried to structurally classify the attackers’ capabilities as well as the properties of countermeasures. Correct realization of countermeasures should still be manually verified, which is error-prone and infeasible for even moderate-size real-world designs. Here, we introduce the concept of Cryptographic Fault Diagnosis, which revises and shapes the notions of fault diagnosis in reliability testing to the needs of evaluating cryptographic implementations. Additionally, we present VerFI, which materializes the idea of Cryptographic Fault Diagnosis. It is a fully automated, open-source fault detection tool processing the gate-level representation of arbitrary cryptographic implementations. By adjusting the bounds of the underlying adversary model, VerFI allows us to rapidly examine the desired fault detection/correction capabilities of the given implementation. Among several case studies, we demonstrate its application on an implementation of LED cipher with combined countermeasures against side-channel analysis and fault-injection attacks (published at CRYPTO 2016). This experiment revealed general implementation flaws and undetectable faults leading to successful DFA on the protected design with full-key recovery.

In public key broadcast encryption, anyone can securely transmit a message to a group of receivers such that privileged users can decrypt it. The three important parameters of the broadcast encryption scheme are the length of the ciphertext, the size of private/public key, and the performance of encryption/decryption. It is suggested to decrease them as much as possible, however, it turns out that decreasing one increases the other in most schemes. This paper proposes a new broadcast encryption scheme for tiny IoT equipments (BESTIE), minimizing the private key size in each user. In the proposed scheme, the private key size is O(log n), the public key size is O(log n), the encryption time per subset is O(log n), the decryption time is O(log n), and the ciphertext text size is O(r), where n denotes the maximum number of users and r indicates the number of revoked users. The proposed scheme is the first subset difference based broadcast encryption scheme to reduce the private size O(log n) without sacrificing the other parameters. We prove that our proposed scheme is secure under q-Simplified Multi-Exponent Bilinear Diffie-Hellman (q-SMEBDH) in the standard model.

As perfect building blocks for the diffusion layers of many symmetric-key primitives, the construction of MDS matrices with light-weight circuits has received much attention from the symmetric-key community. One promising way of realizing low-cost MDS matrices is based on the iterative construction: a low-cost matrix becomes MDS after rising it to a certain power. To be more specific, if $A^t$ is MDS, then one can implement $A$ instead of $A^t$ to achieve the MDS property at the expense of an increased latency with $t$ clock cycles. In this work, we identify the exact lower bound of the number of nonzero blocks for a $4 \times 4$ block matrix to be potentially iterative-MDS. Subsequently, we show that the theoretically lightest $4 \times 4$ iterative MDS block matrix (whose entries or blocks are $4 \times 4$ binary matrices) with minimal nonzero blocks costs at least 3 XOR gates, and a concrete example achieving the 3-XOR bound is provided. Moreover, we prove that there is no hope for previous constructions (GFS, LFS, DSI, and spares DSI) to beat this bound. Since the circuit latency is another important factor, we also consider the lower bound of the number of iterations for certain iterative MDS matrices. Guided by these bounds and based on the ideas employed to identify them, we explore the design space of lightweight iterative MDS matrices with other dimensions and report on improved results. Whenever we are unable to find better results, we try to determine the bound of the optimal solution. As a result, the optimality of some previous results is proved.

Saber is a module lattice-based CCA-secure key encapsulation mechanism (KEM) which has been shortlisted for the second round of NIST's Post Quantum Cryptography Standardization project. To attain simplicity and efficiency on constrained devices, the Saber algorithm is serial by construction. However, on high-end platforms, such as modern Intel processors with AVX2 instructions, Saber achieves limited speedup using vector processing instructions due to its serial nature. In this paper we overcome the above-mentioned algorithmic bottleneck and propose a high-throughput software implementation of Saber, which we call `SaberX4', targeting modern Intel processors with AVX2 vector processing support. We apply the batching technique at the highest level of the implementation hierarchy and process four Saber KEM operations simultaneously in parallel using the AVX2 vector processing instructions. Our proof-of-concept software implementation of SaberX4 achieves nearly 1.5 times higher throughput at the cost of latency degradation within acceptable margins, compared to the AVX2-optimized non-batched implementation of Saber by its authors. We anticipate that both latency and throughput of SaberX4 will improve in the future with improved computer architectures and more optimization efforts.

Cryptosystems based on Learning with Errors or related problems are central topics in recent cryptographic research. One main witness to this is the NIST Post-Quantum Cryptography Standardization effort. Many submitted proposals rely on problems related to Learning with Errors. Such schemes often include the possibility of decryption errors with some very small probability. Some of them have a somewhat larger error probability in each coordinate, but use an error correcting code to get rid of errors. In this paper we propose and discuss an attack for secret key recovery based on generating decryption errors, for schemes using error correcting codes. In particular we show an attack on the scheme {\sf LAC}, a proposal to the NIST Post-Quantum Cryptography Standardization that has advanced to round 2. In a standard setting with CCA security, the attack first consists of a precomputation of special messages and their corresponding error vectors. This set of messages are submitted for decryption and a few decryption errors are observed. In a statistical analysis step, these vectors causing the decryption errors are processed and the result reveals the secret key. The attack only works for a fraction of the secret keys. To be specific, regarding {\sf LAC}256, the version for achieving the 256-bit classical security level, we recover one key among approximately \(2^{64}\) public keys with complexity \(2^{79}\), if the precomputation cost of \(2^{162}\) is excluded. We also show the possibility to attack a more probable key (say with probability \(2^{-16}\)). This attack is verified via extensive simulation. We further apply this attack to {\sf LAC}256-v2, a new version of {\sf LAC}256 in round 2 of the NIST PQ-project and obtain a multi-target attack with slightly increased precomputation complexity (from \(2^{162}\) to \(2^{171}\)). One can also explain this attack in the single-key setting as an attack with precomputation complexity of \(2^{171}\) and success probability of \(2^{-64}\).

Distributed randomness is very useful for many applications, such as smart contract, proof-of-stake-based blockchain, elliptic curve generation and lottery. Randomness beacon protocols are proposed, which are aimed at continuously distributed randomness generation. However, a reliable source of distributed randomness is gained with difficulty because of Byzantine behavior, which may lead to bias for distributed randomness. These Byzantine behaviors include, but not limited to, the “last actor” problem, DoS attack and collusion attack. Various cryptography schemes have been used to generate distributed randomness. Current constructions face challenging obstacles due to high complexity and bias problems. Given these barriers, we propose a new protocol that is the first precept to utilize attribute-based encryption in a commit-and-reveal scheme for distributed randomness (ABERand). Compared to existing public distributed randomness protocols, ABERand possesses distinguished flexibility, security and efficiency. It is primarily because of trading space for time. More specifically, we resolve the “last actor” problem and make ABERand an intensive out- put randomness beacon with communication complexity O(n3), computation complexity O(1), verification complexity O(n) and communication complexity O(n) of nodes adding/removing.

Data, an important asset in digital economy, has fueled the emergence of a new data trading market. Big data market can efficiently promote data trading and further increases the utility of data. However, to realize effective data trading, several challenges needs to be resolved. First, it needs to resolve disputes over data availability in the data trad- ing. Second, atomic exchange and payment fairness between the seller and the buyer are hard to guarantee. Third, data trading platform is the single-point-failure. In this paper, we resolve these challenges by pre- senting a valid blockchain-based data trading ecosystem. The ecosystem constructs a decentralized arbitration mechanism to address the dispute over data availability in data trading. The ecosystem also designs a sale contract and a deterministic public-key encryption algorithm to guaran- tee fairness of data trading between the seller and buyer. The features of blockchain is preventing single-point-failure of data trading platform. We prove the desirable security properties that a secure data trading ecosystem should have. Discussion of the presented ecosystem is given. To demonstrate availability, we implement our proposed data trading ecosystem using smart contract in Solidity and program in Java, and evaluate its performance.

Genetic data is an indispensable part of big data, promoting the advancement of life science and biomedicine. Yet, highly private genetic data also brings concerns about privacy risks in data shar- ing. In our work, we adopt the cryptographic prim- itive Secure Function Evaluation (SFE) to address this problem. A secure SFE scheme allows insti- tutions and hospitals to compute a function while preserving the privacy of their input data, and each participant knows nothing but their own input and the final result. In our work, we present privacy-preserving solutions for Human Leukocyte Antigen (HLA) matching and two popular biostatistics tests: Chi-squared test and odds ratio test. We also show that our protocols are compatible with multiple databases simultaneously and could feasibly han- dle larger-scale data up to genome-wide level. This approach may serve as a new way to jointly analyze distributed and restricted genetic data among insti- tutions and hospitals. Meanwhile, it can potentially be extended to other genetic analysis algorithms, allowing individuals to analyze their own genomes without endangering data privacy.

An elliptic curve known as Curve448 defined over the finite field $\mathbb{F}_p$, where $p=2^{448}-2^{224}-1$, has been proposed as part of the Transport Layer Security (TLS) protocol, version 1.3. Elements of $\mathbb{F}_p$ can be represented using 7 limbs where each limb is a 64-bit quantity. This paper describes efficient algorithms for reduction modulo $p$ that are required for performing field arithmetic in $\mathbb{F}_p$ using 7-limb representation. A key feature of our work is that we provide the relevant proofs of correctness of the algorithms. We also report efficient 64-bit assembly implementations for key generation and shared secret computation phases of the Diffie-Hellman key agreement protocol on Curve448. Timings results on the Haswell and Skylake processors demonstrate that the new 64-bit implementations for computing the shared secret are faster than the previously best known 64-bit implementations.

Traceable and linkable ring signature scheme (TLRS) plays a major role in the construction of auditable privacy-preserving blockchains, as it empowers the auditor with traceability of signers' identities. A recent work by Li gives a modular construction of TLRS by usage of classic ring signature, one-time signature and zero-knowledge proofs, and has security against malicious auditors. In this paper, we introduce sTLRS, a simpler modification of TLRS which is constructed directly from classic ring signature, without any additional one-time signatures or zero-knowledge proofs. sTLRS has public key size reduced by 80% and verification time reduced by over 50%, compared to TLRS. Moreover, we can further modify the sTLRS to achieve anonymity, unforgeability, linkability, nonslanderability and traceability against malicious auditors.

Private Function Evaluation (PFE) enables two parties to jointly execute a computation such that one of them provides the input while the other chooses the function to compute. According to the traditional security requirements, a PFE protocol should leak no more information, neither about the function nor the input, than what is revealed by the output of the computation. Existing PFE protocols inherently restrict the scope of computable functions to a certain function class with given output size, thus ruling out the direct evaluation of such problematic functions as the identity map, which would entirely undermine the input privacy requirement. We observe that when not only the input $x$ is confidential but certain partial information $g(x)$ of it as well, standard PFE fails to provide meaningful input privacy if $g$ and the function $f$ to be computed fall into the same function class. Our work investigates the question whether it is possible to achieve a reasonable level of input and function privacy simultaneously even in the above cases. We propose the notion of Controlled PFE (CPFE) with different flavours of security and answer the question affirmatively by showing simple, generic realizations of the new notions. Our main construction, based on functional encryption (FE), also enjoys strong reusability properties enabling, e.g. fast computation of the same function on different inputs. To demonstrate the applicability of our approach, we show a concrete instantiation of the FE-based protocol for inner product computation that enables secure statistical analysis (and more) under the standard Decisional Diffie--Hellman assumption.

In this paper we revisit the modular lattice signature scheme and its efficient instantiation known as pqNTRUSign. First, we show that a modular lattice signature scheme can be based on a standard lattice problem. The fundamental problem that needs to be solved by the signer or a potential forger is recovering a lattice vector with a restricted norm, given the least significant bits. We show that this problem is equivalent to the short integer solution (SIS) problem over the corresponding lattice. In addition, we show that by replacing the uniform sampling in pqNTRUSign with a bimodal Gaussian sampling, we can further reduce the size of a signature. An important new contribution, enabled by this Gaussian sampling version of pqNTRUSign, is that we can now perform batch verification of messages signed by the same public key, which allows the verifier to check approximately 24 signatures in a single verification process.

We present an actively secure, practical protocol to generate the distributed secret keys needed in the SPDZ offline protocol. The resulting distribution of the public and secret keys is such that the associated SHE `noise' analysis is the same as if the distributed keys were generated by a trusted setup. We implemented the presented protocol for distributed BGV key generation within the SCALE-MAMBA framework. Our method makes use of a new method for creating doubly (or even more) authenticated bits in different MPC engines, which has applications in other areas of MPC-based secure computation. We were able to generate keys for two parties and a plaintext size of 64 bits in around five minutes, and approximately eighteen minutes for a 128 bit prime.