Verifiable Secret-Sharing (VSS) is a fundamental primitive in secure distributed computing. It is used as an important building block in several distributed computing tasks, such as Byzantine agreement and secure multi-party computation. VSS has been widely studied in various dimensions over the last three decades and several important results have been achieved related to the fault-tolerance, round-complexity and communication efficiency of VSS schemes. In this article, we consider VSS schemes with perfect security, tolerating computationally unbounded adversaries. We comprehensively survey the existing perfectly-secure VSS schemes in three different settings, namely synchronous, asynchronous and hybrid communication settings and provide the full details of each of the existing schemes in these settings. The aim of this survey is to provide a clear knowledge and foundation to researchers who are interested in knowing and extending the state-of-the-art perfectly-secure VSS schemes.

In this paper, we propose a new public-key cryptosystem based on a quasigroup with the special property of "restricted-commutativity". We argue its security empirically and present constructions for key exchange and digital signature. To the best of our knowledge, our primitive and construction have no known polynomial-time attack from quantum computers yet. We note that quasigroups with such property had been independently proposed for use in public-key cryptography and termed "entropic" quasigroups or "entropoids" by D.Gligoroski.

Proxy signature is a kind of digital signature, in which a user called original signer can delegate his signing rights to another user called proxy signer and the proxy signer can sign messages on behalf of the original signer. Certificateless proxy signature (CLPS) means proxy signature in the certificateless setting in which there exists neither the certificate management issue as in traditional PKI nor private key escrow problem as in Identity-based setting. Up to now, a number of CLPS schemes have been proposed, but some of those schemes either lack formal security analysis or turn out to be insecure and others are less efficient because of using costly operations including bilinear pairings and map-to-point hashing on elliptic curve groups. In this paper, we formalize the definition and security model of CLPS schemes. We then construct a pairing-free CLPS scheme from the standard ECDSA and prove its security in the random oracle model under the discrete semi-logarithm problem’s hardness assumption as in the provable security result of ECDSA.

Newly designed block ciphers are required to show resistance against known attacks, e.g., linear and differential cryptanalysis. Two widely used methods to do this are to employ an automated search tool (e.g., MILP, SAT/SMT, etc.) and/or provide a wide-trail argument. In both cases, the core of the argument consists of bounding the transition probability of the statistical property over an isolated non-linear operation, then multiply it by the number of such operations (e.g., number of active S-boxes). In this paper we show that in the case of linear cryptanalysis such strategies can sometimes lead to a gap between the claimed security and the actual one, and that this gap can be exploited by a malicious designer. We introduce RooD, a block cipher with a carefully crafted backdoor. By using the means of the wide-trail strategy, we argue the resistance of the cipher against linear and differential cryptanalysis. However, the cipher has a key-dependent iterative linear approximation over 12 rounds, holding with probability 1. This property is based on the linear hull effect although any linear trail underlying the linear hull has probability smaller than 1.

A software watermarking scheme enables one to embed a ``mark " (i.e., a message) into a program without significantly changing the functionality. Moreover, any removal of the watermark from a marked program is futile without significantly changing the functionality of the program. At present, the construction of software watermarking mainly focuses on watermarking pseudorandom functions (PRFs), watermarking public key encryption, watermarking signature, etc. In this work, we construct new watermarking PRFs from lattices which provide collusion resistant and public extraction. Our schemes are the first to simultaneously achieve all of these properties. The key to the success of our new constructions lies in two parts. First, we relax the notion of functionality-preserving. In general, we require that a marked program (approximately) preserve the input/output behavior of the original program. For our scheme, the output circuit is divided into two parts, one for PRF output and the other for auxiliary functions. As a result, we only require the PRF output circuit to satisfy functionality-preserving. Second, the marking method we use is essentially different form the previous scheme. In general, the mark program will change the output of some special point. The extraction algorithm determines whether the circuit is marked by determining whether the output of some special points has been changed. In our schemes, we use the constrained signature to mark a PRF circuit.

This paper presents two modifications for Loidreau’s code-based cryptosystem. Loidreau’s cryptosystem is a rank metric code-based cryptosystem constructed by using Gabidulin codes in the McEliece setting. Recently a polynomial-time key recovery attack was proposed to break Loidreau’s cryptosystem in some cases. To prevent this attack, we propose the use of subcodes to disguise the secret codes in Modification I. In Modification II, we choose a random matrix of low column rank over F q to mix with the secret matrix. According to our analysis, these two modifications can both resist the existing structural attacks. Additionally, we adopt the systematic generator matrix of the public code to make a reduction in the public-key size.

Grain-128AEAD is one of the second-round candidates of the NIST lightweight cryptography standardization process. There is an existing body of third-party analysis on the earlier versions of the Grain family that provide insights on the security of Grain-128AEAD. Different from the earlier versions, Grain-128AEAD reintroduces the key into the internal state during the initialization. The designers claim that internal state recovery no longer results in key recovery, due to this change. In this paper, we analyze this claim under different scenarios.

Efficient shuffle arguments are essential in mixnet-based e-voting solutions. Terelius and Wikström (TW) proposed a 5-round shuffle argument based on unique factorization in polynomial rings. Their argument is available as the Verificatum software solution for real-world developers, and has been used in real-world elections. It is also the fastest non-patented shuffle argument. We will use the same basic idea as TW but significantly optimize their approach. We generalize the TW characterization of permutation matrices; this enables us to reduce the communication without adding too much to the computation. We make the TW shuffle argument computationally more efficient by using Groth's coefficient-product argument (JOC, 2010). Additionally, we use batching techniques. The resulting shuffle argument is the fastest known $\leq 5$-message shuffle argument, and, depending on the implementation, can be faster than Groth's argument (the fastest 7-message shuffle argument).

Zero-knowledge proofs allow a prover to convince a verifier of the veracity of a statement without revealing any other information. An interesting class of zero-knowledge protocols are those following the MPC-in-the-head paradigm (Ishai et al., STOC ’07) which use secure multiparty computation (MPC) protocols as the basis. Efficient instances of this paradigm have emerged as an active research topic in the last years, starting with ZKBoo (Giacomelli et al., USENIX ’16). Zero-knowledge protocols are a vital building block in the design of privacy-preserving technologies as well as cryptographic primitives like digital signature schemes that provide post-quantum security. This work investigates the security of zero-knowledge protocols following the MPC-in-the-head paradigm. We provide the first machine-checked security proof of such a protocol on the example of ZKBoo. Our proofs are checked in the EasyCrypt proof assistant. To enable a modular security proof, we develop a new security notion for the MPC protocols used in MPC-in-the-head zero-knowledge protocols. This allows us to recast existing security proofs in a black-box fashion which we believe to be of independent interest.

An algebraic differential fault attack (ADFA) is an attack in which an attacker combines a differential fault attack and an algebraic technique to break a targeted cipher. In this paper, we present three attacks using three different algebraic techniques combined with a differential fault attack in the bit-flip fault model to break the SIMON block cipher. First, we introduce a new analytic method that is based on a differential trail between the correct and faulty ciphertexts. This method is able to recover the entire master key of any member of the SIMON family by injecting faults into a single round of the cipher. In our second attack, we present a simplified Grobner basis algorithm to solve the faulty system. We show that this method could totally break SIMON ciphers with only 3 to 5 faults injected. Our third attack combines a fault attack with a modern SAT solver. By guessing some key bits and with only a single fault injected at the round T - 6, where T is the number of rounds of a SIMON cipher, this combined attack could manage to recover a master key of the cipher. For the last two attacks, we perform experiments to demonstrate the effectiveness of our attacks. These experiments are implemented on personal computers and run at very reasonable timing

Anonymous routing is one of the most fundamental online privacy problems and has been studied extensively for decades. Almost all known approaches for anonymous routing (e.g., mix-nets, DC-nets, and others) rely on multiple servers or routers to engage in some {\it interactive} protocol; and anonymity is guaranteed in the {\it threshold} model, i.e., if one or more of the servers/routers behave honestly. Departing from all prior approaches, we propose a novel {\it non-interactive} abstraction called a Non-Interactive Anonymous Router (NIAR), which works even with a {\it single untrusted router}. In a NIAR scheme, suppose that $n$ senders each want to talk to a distinct receiver. A one-time trusted setup is performed such that each sender obtains a sending key, each receiver obtains a receiving key, and the router receives a {\it token} that ``encrypts'' the permutation mapping the senders to receivers. In every time step, each sender can encrypt its message using its sender key, and the router can use its token to convert the $n$ ciphertexts received from the senders to $n$ {\it transformed ciphertexts}. Each transformed ciphertext is delivered to the corresponding receiver, and the receiver can decrypt the message using its receiver key. Imprecisely speaking, security requires that the untrusted router, even when colluding with a subset of corrupt senders and/or receivers, should not be able to compromise the privacy of honest parties, including who is talking to who, and the message contents. We show how to construct a communication-efficient NIAR scheme with provable security guarantees based on the standard Decisional Linear assumption in suitable bilinear groups. We show that a compelling application of NIAR is to realize a Non-Interactive Anonymous Shuffler (NIAS), where an untrusted server or data analyst can only decrypt a permuted version of the messages coming from $n$ senders where the permutation is hidden. NIAS can be adopted to construct privacy-preserving surveys, differentially private protocols in the shuffle model, and pseudonymous bulletin boards. Besides this main result, we also describe a variant that achieves fault tolerance when a subset of the senders may crash. Finally, we further explore a paranoid notion of security called full insider protection, and show that if we additionally assume sub-exponentially secure Indistinguishability Obfuscation and as sub-exponentially secure one-way functions, one can construct a NIAR scheme with paranoid security.

The random probing model is a leakage model in which each wire of a circuit leaks with a given probability $p$. This model enjoys practical relevance thanks to a reduction to the noisy leakage model, which is admitted as the right formalization for power and electromagnetic side-channel attacks. In addition, the random probing model is much more convenient than the noisy leakage model to prove the security of masking schemes. In a recent work, Ananth, Ishai and Sahai (CRYPTO 2018) introduce a nice expansion strategy to construct random probing secure circuits. Their construction tolerates a leakage probability of $2^{-26}$, which is the first quantified achievable leakage probability in the random probing model. In a follow-up work, Belaïd, Coron, Prouff, Rivain and Taleb (CRYPTO 2020) generalize their idea and put forward a complete and practical framework to generate random probing secure circuits. The so-called expanding compiler can bootstrap simple base gadgets as long as they satisfy a new security notion called random probing expandability (RPE). They further provide an instantiation of the framework which tolerates a $2^{-8}$ leakage probability in complexity $\mathcal{O}(\kappa^{7.5})$ where $\kappa$ denotes the security parameter. In this paper, we provide an in-depth analysis of the RPE security notion. We exhibit the first upper bounds for the main parameter of a RPE gadget, which is known as the amplification order. We further show that the RPE notion can be made tighter and we exhibit strong connections between RPE and the strong non-interference (SNI) composition notion. We then introduce the first generic constructions of gadgets achieving RPE for any number of shares and with nearly optimal amplification orders and provide an asymptotic analysis of such constructions. Last but not least, we introduce new concrete constructions of small gadgets achieving maximal amplification orders. This allows us to obtain much more efficient instantiations of the expanding compiler: we obtain a complexity of $\mathcal{O}(\kappa^{3.9})$ for a slightly better leakage probability, as well as $\mathcal{O}(\kappa^{3.2})$ for a slightly lower leakage probability.

In the quantum random oracle model, the adversary may make quantum superposition queries to the random oracle. Since even a single query can potentially probe exponentially many points, classical proof techniques are hard to be applied. For example, recording the oracle queries seemed difficult. In 2018, Mark Zhandry showed that, despite the apparent difficulties, it is in fact possible to ‘record’ the quantum queries. He has defined the compressed oracle, which is indistinguishable from the quantum random oracle, and records information the adversary has gained through the oracle queries. It is a technically subtle work, which we believe to be a challenging work to grasp fully. Our aim is to obtain a mathemathically clean, simple reinterpretation of the compressed oracle technique. For each partial function, we define what we call the formation and the completion of that partial function. The completions describe what happens to the real quantum random oracle, and the formations describe what happens to the compressed oracle. We will show that the formations are 'isomorphic' to the completions, giving an alternative proof that the compressed oracle is indistinguishable from the quantum random oracle.

We present a novel protocol XORBoost for both training gradient boosted tree models and for using these models for inference in the multiparty computation (MPC) setting. Similarly to [AEV20], our protocol supports training for generically split datasets (vertical and horizontal splitting, or combination of those) while keeping all the information about the features and thresholds associated with the nodes private, thus, having only the depths and the number of the binary trees as public parameters of the model. By using optimization techniques reducing the number of oblivious permutation evaluations as well as the quicksort and real number arithmetic algorithms from the recent Manticore MPC framework [CDG+21], we obtain a scalable implementation operating under information-theoretic security model in the honest-but-curious setting with a trusted dealer. On a training dataset of 25,000 samples and 300 features in the 2-player setting, we are able to train 10 regression trees of depth 4 in less than 1.5 minutes per tree (using histograms of 128 bins).

We consider the problem of round-optimal unbounded MPC: in the first round, parties publish a message that depends only on their input. In the second round, any subset of parties can jointly and securely compute any function $f$ over their inputs in a single round of broadcast. We do not impose any a-priori bound on the number of parties nor on the size of the functions that can be computed. Our main result is a semi-malicious two-round protocol for unbounded MPC in the plain model from the hardness of the standard learning with errors (LWE) problem. Prior work in the same setting assumes the hardness of problems over bilinear maps. Thus, our protocol is the first example of unbounded MPC that is post-quantum secure. The central ingredient of our protocol is a new scheme of attribute-based secure function evaluation (AB-SFE) with public decryption. Our construction combines techniques from the realm of homomorphic commitments with delegation of lattice basis. We believe that such a scheme may find further applications in the future.

The Kannan-Fincke-Pohst lattice enumeration algorithm is the classical method for solving the shortest vector problem in lattices. It is also a fundamental tool for most lattice reduction algorithms that provide speed-length tradeoffs. As this algorithm allows efficient parallel implementations, it is likely that implementing it on modern graphics processing units (GPUs) can significantly improve performance. We provide such an implementation that is compatible with the fplll lattice reduction library [fplll16] and achieves a considerable speedup in higher lattice dimensions, compared to current, multithreaded versions. For this, we use the CUDA technology that provides an abstract language for programming GPUs. [fplll16] The FPLLL development team. “fplll, a lattice reduction library”. 2016. URL: https://github.com/fplll/fplll

Multivariate cryptography is dominated by schemes supporting various tweaks, or ``modifiers,'' designed to patch certain algebraic weaknesses they would otherwise exhibit. Typically these modifiers are linear in nature--- either requiring an extra composition with an affine map, or being evaluated by a legitimate user via an affine projection. This description applies to the minus, plus, vinegar and internal perturbation modifiers, to name a few. Though it is well-known that combinations of various modifiers can offer security against certain classes of attacks, cryptanalysts have produced ever more sophisticated attacks against various combinations of these linear modifiers. In this article, we introduce a more fundamentally nonlinear modifier, called Q, that is inspired from relinearization. The effect of the Q modifier on multivariate digital signature schemes is to maintain inversion efficiency at the cost of slightly slower verification and larger public keys, while altering the algebraic properties of the public key. Thus the Q modifier is ideal for applications of digital signature schemes requiring very fast signing and verification without key transport. As an application of this modifier, we propose new multivariate digital signature schemes with fast signing and verification that are resistant to all known attacks.

We formally prove that the C implementation of the X25519 key-exchange protocol in the TweetNaCl library is correct. We prove both that it correctly implements the protocol from Bernstein's 2006 paper, as standardized in RFC 7748, as well as the absence of undefined behavior like arithmetic overflows and array out-of-bounds errors. We also formally prove, based on the work of Bartzia and Strub, that X25519 is mathematically correct, i.e., that it correctly computes scalar multiplication on the elliptic curve Curve25519. The proofs are all computer-verified using the Coq theorem prover. To establish the link between C and Coq we use the Verified Software Toolchain (VST).

At EUROCRYPT 2021, Bao et al. proposed an automatic method for systematically exploring the configuration space of meet-in-the-middle (MITM) preimage attacks. We further extend it into a constraint-based framework for finding exploitable MITM characteristics in the context of key-recovery and collision attacks by taking the subtle peculiarities of both scenarios into account. Moreover, to perform attacks based on MITM characteristics with nonlinear constrained neutral words, which have not been seen before, we present a procedure for deriving the solution spaces of neutral words without solving the corresponding nonlinear equations or increasing the overall time complexities of the attack. We apply our method to concrete symmetric-key primitives, including SKINNY, ForkSkinny, Romulus, Saturnin, Grostl, Whirlpool, and hashing modes with AES-256. As a result, we identify the first 23-round key-recovery attack on SKINNY-$n$-$3n$ and the first 24-round key-recovery attack on ForkSkinny-$n$-$3n$ in the single-key model. Moreover, improved (pseudo) preimage or collision attacks on round-reduced Whirlpool, Grostl, and hashing modes with AES-256 are obtained. In particular, employing the new representation of the AES key schedule due to Leurent and Pernot (EUROCRYPT 2021), we identify the first preimage attack on 10-round AES-256 hashing.

Given two ciphertexts generated with a public-key encryption scheme, the problem of plaintext equality consists in determining whether the ciphertexts hold the same value. Similarly, the problem of plaintext inequality consists in deciding whether they hold a different value. Previous work has focused on building new schemes or extending existing ones to include support for plaintext equality/inequality. We propose generic and simple zero-knowledge proofs for both problems, which can be instantiated with various schemes. First, we consider the context where a prover with access to the secret key wants to convince a verifier, who has access to the ciphertexts, on the equality/inequality without revealing information about the plaintexts. We also consider the case where the prover knows the encryption’s randomness instead of the secret key. For plaintext equality, we also propose sigma protocols that lead to non-interactive zero-knowledge proofs. To prove our protocols’ security, we formalize notions related to malleability in the context of public-key encryption and provide definitions of their own interest.

We extend the prior provable related-key security analysis of (generalized) Feistel networks (Barbosa and Farshim, FSE 2014; Yu et al., Inscrypt 2020) to the setting of expanding round functions, i.e., n-bit to m-bit round functions with n < m. This includes Expanding Feistel Networks (EFNs) that purely rely on such expanding round functions, and Alternating Feistel Networks (AFNs) that alternate expanding and contracting round functions. We show that, when two independent keys $K_1,K_2$ are alternatively used in each round, (a) $2\lceil\frac{m}{n}\rceil+2$ rounds are sufficient for related-key security of EFNs, and (b) a constant number of 4 rounds are sufficient for related-key security of AFNs. Our results complete the picture of provable related-key security of GFNs, and provide additional theoretical support for the AFN-based NIST format preserving encryption standards FF1 and FF3.

Increasing privacy consciousness has popularized the use of end-to-end encryption (E2EE). In this paper, we discuss the security of SFrame, an E2EE mechanism proposed to the Internet Engineering Task Force for video/audio group communications over the Internet. Despite being a quite recent project, SFrame has been deployed in several real-world applications. The original specification of SFrame is evaluated herein to find critical issues that can cause impersonation (forgery) attacks with a practical complexity by a malicious group member. Further investigations have revealed that these issues are present in several publicly available SFrame implementations. Therefore, we provide several countermeasures against all the proposed attacks and considerations from performance and security perspectives toward their implementation.

Large semigroups and groups of transformations of finite affine space of dimension n with the option of computability of the composition of n arbitrarily chosen elements in polynomial time are described in the paper. Constructions of such families are given together with effectively computed homomorphisms between members of the family. These algebraic platforms allow us to define protocols for several generators of subsemigroup of affine Cremona semigroups with several outputs. Security of these protocols rests on the complexity of the word decomposition problem, It allows to introduce algebraic protocols expanded to cryptosystems of El Gamal type which are not a public key system. In particular symbiotic combination of these protocol of Noncommutative cryptography with one time pad encryption is given. Some of these nonclassical multivariate cryptosystems are implemented with platforms of cubical transformations.

Zero-Knowledge (ZK) Proofs for disjunctive statements have been a focus of a long line of research. Classical results such as Cramer {\em et al.} [CRYPTO'94] and Abe {\em et al.} [AC'02] design generic compilers that transform certain classes of ZK proofs into ZK proofs for disjunctive statements. However, communication complexity of the resulting protocols in these results ends up being proportional to the complexity of proving all clauses in the disjunction. More recently, Heath {\em et al.} [EC'20] exploited special properties of garbled circuits to construct efficient ZK proofs for disjunctions, where the proof size is only proportional to the length of the largest clause in the disjunction. However, these techniques do not appear to generalize beyond garbled circuits. In this work, we focus on achieving the best of both worlds. We design a \textit{general framework} that compiles a large class of {unmodified} $\Sigma$-protocols, each for an individual statement, into a new $\Sigma$-protocol that proves a disjunction of these statements. Our framework can be used both when each clause is proved with the same $\Sigma$-protocol and when different $\Sigma$-protocols are used for different clauses. The resulting $\Sigma$-protocol is concretely efficient and has communication complexity proportional to the communication required by the largest clause, with additive terms that are only logarithmic in the number of clauses. We show that our compiler can be applied to many well-known $\Sigma$-protocols, including classical protocols (\emph{e.g.} Schnorr [JC'91] and Guillou-Quisquater [CRYPTO'88]) and modern MPC-in-the-head protocols such as the recent work of Katz, Kolesnikov and Wang [CCS'18] and the Ligero protocol of Ames {\em et al.} [CCS'17]. Finally, since all of the protocols in our class can be made non-interactive in the random oracle model using the Fiat-Shamir transform, our result yields the first generic non-interactive zero-knowledge protocol for disjunctions where the communication only depends on the size of the largest clause.

We study the notion of indistinguishability obfuscation for null quantum circuits (quantum null-iO). We present a construction assuming: * The quantum hardness of learning with errors (LWE). * Post-quantum indistinguishability obfuscation for \emph{classical} circuits. * A notion of ``dual-mode'' classical verification of quantum computation (CVQC). We give evidence that our notion of dual-mode CVQC exists by proposing a scheme that is secure assuming LWE in the quantum random oracle model (QROM). Then we show how quantum null-iO enables a series of new cryptographic primitives that, prior to our work, were unknown to exist even making heuristic assumptions. Among others, we obtain the first witness encryption scheme for QMA, the first publicly verifiable non-interactive zero-knowledge (NIZK) scheme for QMA, and the first attribute-based encryption (ABE) scheme for BQP.

Modern implementations of homomorphic encryption (HE) rely heavily on polynomial arithmetic over a finite field. This is particularly true of the CKKS, BFV, and BGV HE schemes. Two of the biggest performance bottlenecks in HE primitives and applications are polynomial modular multiplication and the forward and inverse number- theoretic transform (NTT). Here, we introduce Intel® Homomorphic Encryption Acceleration Library (Intel® HEXL), a C++ library which provides optimized implementations of polynomial arithmetic for Intel® processors. Intel HEXL takes advantage of the recent Intel® Advanced Vector Extensions 512 (Intel® AVX512) instruction set to provide state- of-the-art implementations of the NTT and modular multiplication. On the forward and inverse NTT, Intel HEXL provides up to 7.2x and 6.7x speedup, respectively, over a native C++ implementation. Intel HEXL also provides up to 6.0x speedup on the element-wise vector-vector modular multiplication, and 1.7x speedup on the element-wise vector-scalar modular multiplication. Intel HEXL is available open-source at https://github.com/intel/hexl under the Apache 2.0 license and has been adopted by the Microsoft SEAL and PALISADE homomorphic encryption libraries.

We propose an efficient quantum algorithm for a specific quantum state discrimination problem. An immediate corollary of our result is a polynomial time quantum algorithm for the Dihedral Coset Problem with a smooth modulus. This, in particular, implies that $\text{poly}(n)$-unique-SVP is in BQP.

The Ring-LWE over two-to-power cyclotomic integer rings has been the hard computational problem for lattice cryptographic constructions. Its hardness and the conjectured hardness of approximating ideal SIVP for ideal lattices in two-to-power cyclotomic fields have been the fundamental open problems in lattice cryptography and the computational number theory. In our previous paper we presented a general theory of subset attack on the Ring-LWE with not only the Gaussian error distribution but also general error distributions. By the usage of our subset attack from sublattice quadruples we prove that the decision Ring-LWE (then the search version) over two-to-power cyclotomic integer rings with certain sufficiently large polynomially bounded modulus parameters when degrees d_n = 2^{n-1} going to the infinity can be solved by a polynomial (in d_n) time algorithm for wide error distributions with widths in the range of Peikert-Regev-Stephens-Davidowitz hardness reduction results in their STOC 2017 paper. Hence we also prove that approximating idealSIV Ppoly(dn) with some polynomial factors for ideal lattices in two-to-power cyclotomic fields can be solved within the quantum polynomial time. Therefore post-quantum lattice cryptographic constructions can not be based on the ”hardness” of Ring-LWE over two-to-power cyclotomic integer rings even in the classical computational model.

Digital signatures are used to verify the authenticity of digital messages, that is, to know with a high level of certainty, that a digital message was created by a known sender and was not altered in any way. This is usually achieved by using asymmetric cryptography, where a secret key is used by the signer, and the corresponding public key is used by those who wish to verify the signed data. In many use-cases, such as blockchain, the history and order of the signed data, thus the signatures themselves, are important. In blockchains specifically, the threat is forks, where one can double-spend its crypto-currency if one succeeds to publish two valid transactions on two different branches of the chain. We introduce a single private/public key pair signature scheme using verifiable random function, that binds a signer to its signature history. The scheme enforces a single ordered signatures' history using a deterministic verifiable chain of signature functions that also reveals the secret key in case of misbehaviors.

Blockchain-based cryptocurrencies offer an appealing alternative to Fiat currencies, due to their decentralized and borderless nature. However the decentralized settings make the authentication process more challenging: Standard cryptographic methods often rely on the ability of users to reliably store a (large) secret information. What happens if one user's key is lost or stolen? Blockchain systems lack of fallback mechanisms that allow one to recover from such an event, whereas the traditional banking system has developed and deploys quite effective solutions. In this work, we develop new cryptographic techniques to integrate security policies (developed in the traditional banking domain) in the blockchain settings. We propose a system where a smart contract is given the custody of the user's funds and has the ability to invoke a two-factor authentication (2FA) procedure in case of an exceptional event (e.g., a particularly large transaction or a key recovery request). To enable this, the owner of the account secret-shares the answers of some security questions among a committee of users. When the 2FA mechanism is triggered, the committee members can provide the smart contract with enough information to check whether an attempt was successful, and nothing more. We then design a protocol that securely and efficiently implements such a functionality: The protocol is round-optimal, is robust to the corruption of a subset of committee members, supports low-entropy secrets, and is concretely efficient. As a stepping stone towards the design of this protocol, we introduce a new threshold homomorphic encryption scheme for linear predicates from bilinear maps, which might be of independent interest. To substantiate the practicality of our approach, we implement the above protocol as a smart contract in Ethereum and show that it can be used today as an additional safeguard for suspicious transactions, at minimal added cost. We also implement a second scheme where the smart contract additionally requests a signature from a physical hardware token, whose verification key is registered upfront by the owner of the funds. We show how to integrate the widely used universal two-factor authentication (U2F) tokens in blockchain environments, thus enabling the deployment of our system with available hardware.

Code that is highly optimized poses a problem for program-level verification: programmers can employ various clever tricks that are non-trivial to reason about. For cryptography on low-power devices, it is nonetheless crucial that implementations be functionally correct, secure, and efficient. These are usually crafted in hand-optimized machine code that eschew conventional control flow as much as possible. We have formally verified such code: a library which implements elliptic curve cryptography on 8-bit AVR microcontrollers. The chosen implementation is the most efficient currently known for this microarchitecture. It consists of over 3000 lines of assembly instructions. Building on earlier work, we use the Why3 platform to model the code and prove verification conditions, using automated provers. We expect the approach to be re-usable and adaptable, and it allows for validation. Furthermore, an error in the original implementation was found and corrected, at the same time reducing its memory footprint. This shows that practical verification of cutting-edge code is not only possible, but can in fact add to its efficiency—and is clearly necessary.

Anonymous identity-based identification scheme in the ad-hoc group is a multi-party cryptographic primitive that allows participants to form an ad-hoc group and prove membership anonymously in such a group. In this paper, we cryptanalyze an ad-hoc anonymous identity-based identification scheme proposed by Barapatre and Rangan and show that the scheme is not secure against key-only universal impersonation attack. We note that anyone can impersonate as a valid group member to convince the honest verifier successfully, even without knowing the group secret key. Moreover, we proposed a fix on the scheme and provide a security proof for our fixed scheme. The fixed scheme we proposed fulfills the security requirements of an ad-hoc anonymous identity-based identification scheme that are correctness, soundness, and anonymity.

Data trading is an emerging business, in which data sellers provide buyers with, for example, their private datasets and get paid from buyers. In many scenarios, sellers prefer to sell pieces of data, such as statistical results derived from the dataset, rather than the entire dataset. Meanwhile, buyers wish to hide the results they retrieve. Since it is not preferable to rely on a trusted third party (TTP), we are wondering, in the absence of TTP, whether there exists a \emph{practical} mechanism satisfying the following requirements: the seller Sarah receives the payment if and only if she \emph{obliviously} returns the buyer Bob the \emph{correct} evaluation result of a function delegated by Bob on her dataset, and Bob can only derive the result for which he pays. Despite a lot of attention data trading has received, a \emph{desirable} mechanism for this scenario is still missing. This is due to the fact that general solutions are inefficient when the size of datasets is considerable or the evaluated function is complicated, and that existing efficient cryptographic techniques cannot fully capture the features of our scenario or can only address very limited computing tasks. In this paper, we propose the \emph{first desirable} mechanism that is practical and supports a wide variety of computing tasks --- evaluation of arbitrary functions that can be represented as polynomials. We introduce a new cryptographic notion called \emph{blind polynomial evaluation} and instantiate it with an explicit protocol. We further combine this notion with the blockchain paradigm to provide a \emph{practical} framework that can satisfy the requirements mentioned above.

Unclonable encryption, introduced by Broadbent and Lord (TQC'20), is an encryption scheme with the following attractive feature: given a ciphertext, an adversary cannot create two ciphertexts both of which decrypt to the same message as the original ciphertext. We revisit this notion and show the following: - Reusability: The constructions proposed by Broadbent and Lord have the disadvantage that they either guarantee one-time security (that is, the encryption key can only be used once to encrypt the message) in the plain model or they guaranteed security in the random oracle model. We construct unclonable encryption schemes with semantic security. We present two constructions from minimal cryptographic assumptions: (i) a private-key unclonable encryption scheme assuming post-quantum one-way functions and, (ii) a public-key unclonable encryption scheme assuming a post-quantum public-key encryption scheme. -Lower Bound and Generalized Construction: We revisit the information-theoretic one-time secure construction of Broadbent and Lord. The success probability of the adversary in their construction was guaranteed to be $0.85^n$, where $n$ is the length of the message. It was interesting to understand whether the ideal success probability of (negligibly close to) $0.5^n$ was unattainable. We generalize their construction to be based on a broader class of monogamy of entanglement games (while their construction was based on BB84 game). We demonstrate a simple cloning attack that succeeds with probability $0.71^n$ against a class of schemes including that of Broadbent and Lord. We also present a $0.75^n$ cloning attack exclusively against their scheme. - Implication to Copy-Protection: We show that unclonable encryption, satisfying a stronger property, called unclonable-indistinguishability (defined by Broadbent and Lord), implies copy-protection for a simple class of unlearnable functions. While we currently don't have encryption schemes satisfying this stronger property, this implication demonstrates a new path to construct copy-protection.

We consider a set of security and privacy problems under reliability and storage constraints that can be tackled by using codes and particularly focus on the secret-key agreement problem. Polar subcodes (PSCs) are polar codes (PCs) with dynamically-frozen symbols and have a larger code minimum distance than PCs with only statically-frozen symbols. A randomized nested PSC construction, where the low-rate code is a PSC and the high-rate code is a PC, is proposed for successive cancellation list (SCL) and sequential decoders. This code construction aims to perform lossy compression with side information, i.e., Wyner-Ziv (WZ) coding. Nested PSCs are used in the key agreement problem with physical identifiers and two terminals since WZ-coding constructions significantly improve on Slepian-Wolf coding constructions such as fuzzy extractors. Significant gains in terms of the secret-key vs. storage rate ratio as compared to nested PCs with the same list sizes are illustrated to show that nested PSCs significantly improve on all existing code constructions. The performance of the nested PSCs is shown to improve with larger list sizes, unlike the nested PCs considered. A design procedure to efficiently construct nested PSCs and possible improvements to the nested PSC designs are also provided.

A Statistical Information Theoretic Secure (SITS) system utilizing the Chinese Remainder Theorem (CRT), coupled with Fully Homomorphic Encryption (FHE) for Distributed Communication-less Secure Multiparty Computation (DCLSMPC) of any Distributed Unknown Finite State Machine (DUFSM) is presented. Namely, secret shares of the input(s) and output(s) are passed to/from the computing parties, while there is no communication between them throughout the computation. We propose a novel approach of transition table representation and polynomial representation for arithmetic circuits evaluation, joined with a CRT secret sharing scheme and FHE to achieve SITS communication-less within computational secure execution of DUFSM. We address the severe limitation of FHE implementation over a single server to cope with a malicious or Byzantine server. We use several distributed memory-efficient solutions that are significantly better than the majority vote in replicated state machines, where each participant maintains an FHE replica. A Distributed Unknown Finite State Machine (DUFSM) is achieved when the transition table is secret shared or when the (possible zero value) coefficients of the polynomial are secret shared, implying communication-less SMPC of an unknown finite state machine.

In proof-of-stake (PoS) blockchains, stakeholders that extend the chain are selected according to the amount of stake they own. In S\&P 2019 the ``Ouroboros Crypsinous'' system of Kerber et al.\ (and concurrently Ganesh et al.\ in EUROCRYPT 2019) presented a mechanism that hides the identity of the stakeholder when adding blocks, hence preserving anonymity of stakeholders both during payment and mining in the Ouroboros blockchain. They focus on anonymizing the messages of the blockchain protocol, but suggest that potential identity leaks from the network-layer can be removed as well by employing anonymous broadcast channels. In this work we show that this intuition is flawed. Even ideal anonymous broadcast channels do not suffice to protect the identity of the stakeholder who proposes a block. We make the following contributions. First, we show a formal network-attack against Ouroboros Crypsinous, where the adversary can leverage network delays to distinguish who is the stakeholder that added a block on the blockchain. Second, we abstract the above attack and show that whenever the adversary has control over the network delay -- within the synchrony bound -- loss of anonymity is inherent for any protocol that provides liveness guarantees. We do so, by first proving that it is impossible to devise a (deterministic) state-machine replication protocol that achieves basic liveness guarantees and better than $(1-2\f)$ anonymity at the same time (where $\f$ is the fraction of corrupted parties). We then connect this result to the PoS setting by presenting the tagging and reverse tagging attack that allows an adversary, across several executions of the PoS protocol, to learn the stake of a target node, by simply delaying messages for the target. We demonstrate that our assumption on the delaying power of the adversary is realistic by describing how our attack could be mounted over the Zcash blockchain network (even when Tor is used). We conclude by suggesting approaches that can mitigate such attacks.

We study uncloneable quantum encryption schemes for classical messages as recently proposed by Broadbent and Lord. We focus on the information-theoretic setting and give several limitations on the structure and security of these schemes: Concretely, 1) We give an explicit cloning-indistinguishable attack that succeeds with probability $\frac12 + \mu/16$ where $\mu$ is related to the largest eigenvalue of the resulting quantum ciphertexts. 2) For a uniform message distribution, we partially characterize the scheme with the minimal success probability for cloning attacks. 3) Under natural symmetry conditions, we prove that the rank of the ciphertext density operators has to grow at least logarithmically in the number of messages to ensure uncloneable security. 4) The \emph{simultaneous} one-way-to-hiding (O2H) lemma is an important technique in recent works on uncloneable encryption and quantum copy protection. We give an explicit example which shatters the hope of reducing the multiplicative "security loss" constant in this lemma to below 9/8.

The k-XOR problem can be generically formulated as the following: given many n-bit strings generated uniformly at random, find k distinct of them which XOR to zero. This generalizes collision search (two equal elements) to a k-tuple of inputs. This problem has become ubiquitous in cryptanalytic algorithms, including variants in which the XOR operation is replaced by a modular addition ($k$-SUM) or other non-commutative operations (e.g., the composition of permutations). The case where a single solution exists on average is of special importance. At EUROCRYPT 2020, Naya-Plasencia and Schrottenloher defined a class of ``quantum merging algorithms'' for the k-XOR problem, obtained by combining quantum search. They represented these algorithms by a set of ``merging trees'' and obtained the best ones through linear optimization of their parameters. In this paper, we give a simplified representation of merging trees that makes their analysis easier. We give better quantum algorithms for the Single-solution k-XOR problem by relaxing one of the previous constraints, and making use of quantum walks. Our algorithms subsume or improve over all previous quantum algorithms for Single-solution k-XOR. For example, we give an algorithm for 4-XOR (or 4-SUM) in quantum time $\widetilde{\mathcal{O}}(2^{7n/24})$.

In this work, we study disappearing cryptography in the bounded storage model. Here, a component of the transmission, say a ciphertext, a digital signature, or even a program, is streamed bit by bit. The stream is too large for anyone to store in its entirety, meaning the transmission effectively disappears once the stream stops. We first propose the notion of online obfuscation, capturing the goal of disappearing programs in the bounded storage model. We give a negative result for VBB security in this model, but propose candidate constructions for a weaker security goal, namely VGB security. We then demonstrate the utility of VGB online obfuscation, showing that it can be used to generate disappearing ciphertexts and signatures. All of our applications are not possible in the standard model of cryptography, regardless of computational assumptions used.

We push a little further the study of two characterizations of almost perfect nonlinear (APN) functions introduced in our recent monograph. We state open problems about them, and we revisit in their perspective a well-known result from Dobbertin on APN exponents. This leads us to new results about APN power functions and more general APN polynomials with coefficients in a subfield F_{2^k} , which ease the research of such functions and of differentially uniform functions, and simplifies the related proofs by avoiding tedious calculations. In a second part, we give slightly simpler proofs than in the same monograph, of two known results on Boolean functions, one of which deserves to be better known but needed clarification, and the other needed correction.

Existing proofs for Discrete Log (DL) based multi-signature schemes give essentially no guarantee if the schemes are implemented, as they are in practice, in 256-bit groups. This is because the current reductions, which are in the standard model and from DL, are loose. We show that relaxing either the model or the assumption suffices to obtain tight reductions. Namely we give (1) tight proofs from DL in the Algebraic Group Model, and (2) tight, standard-model proofs from well-founded assumptions other than DL. We first do this for the classical 3-round schemes, namely BN and MuSig. Then we give a new 2-round multi-signature scheme, HBMS, as efficient as prior ones, for which we do the same. These multiple paths to security for a single scheme are made possible by a framework of chain reductions, in which a reduction is broken into a chain of sub-reductions involving intermediate problems. Overall our results improve the security guarantees for DL-based multi-signature schemes in the groups in which they are implemented in practice.

It has been common knowledge that for a stream cipher to be secure against generic TMD tradeoff attacks, the size of its internal state in bits needs to be at least twice the size of the length of its secret key. In FSE 2015, Armknecht and Mikhalev however proposed the stream cipher Sprout with a Grain-like architecture, whose internal state was equal in size with its secret key and yet resistant against TMD attacks. Although Sprout had other weaknesses, it germinated a sequence of stream cipher designs like Lizard and Plantlet with short internal states. Both these designs have had cryptanalytic results reported against them. In this paper, we propose the stream cipher Atom that has an internal state of 159 bits and offers a security of 128 bits. Atom uses two key filters simultaneously to thwart certain cryptanalytic attacks that have been recently reported against keystream generators. In addition, we found that our design is one of the smallest stream ciphers that offers this security level, and we prove in this paper that Atom resists all the attacks that have been proposed against stream ciphers so far in literature. On the face of it, Atom also builds on the basic structure of the Grain family of stream ciphers. However, we try to prove that by including the additional key filter in the architecture of Atom we can make it immune to all cryptanalytic advances proposed against stream ciphers in recent cryptographic literature.

Side-channel attacks are a threat to secrets stored on a device, especially if an adversary has physical access to the device. As an effect of this, countermeasures against such attacks for cryptographic algorithms are a well-researched topic. In this work, we deviate from the study of cryptographic algorithms and instead focus on the side-channel protection of a much more basic operation, the comparison of a known attacker-controlled value with a secret one. Comparisons sensitive to side-channel leakage occur in tag comparisons during the verification of message authentication codes (MACs) or authenticated encryption, but are typically omitted in security analyses. Besides, also comparisons performed as part of fault countermeasures might be sensitive to side-channel attacks. In this work, we present a formal analysis on comparing values in a leakage resilient manner by utilizing cryptographic building blocks that are typically part of an implementation anyway. Our results indicate that there is no need to invest additional resources into implementing a protected comparison operation itself if a sufficiently protected implementation of a public cryptographic permutation, or a (tweakable) block cipher, is already available. We complement our contribution by applying our findings to the SuKS message authentication code used by lightweight authenticated encryption scheme ISAP, and to the classical Hash-then-PRF construction.

Cryptanalysis of symmetric-key ciphers, e.g., linear/differential cryptanalysis, requires an adversary to know the internal structures of the target ciphers. On the other hand, deep learning-based cryptanalysis has attracted significant attention because the adversary is not assumed to have knowledge about the target ciphers with the exception of the algorithm interfaces. Such cryptanalysis in a blackbox setting is extremely strong; thus, we must design symmetric-key ciphers that are secure against deep learning-based cryptanalysis. However, almost previous attacks do not clarify what features or internal structures affect success probabilities. Although Benamira et al. (Eurocrypt 2021) and Chen et al. (ePrint 2021) analyzed Gohr’s results (CRYPTO 2019), they did not find any deep learning specific characteristic where it affects the success probabilities of deep learning-based attacks but does not affect those of linear/differential cryptanalysis. Therefore, it is difficult to employ the results of such cryptanalysis to design deep learning-resistant symmetric-key ciphers. In this paper, we propose deep learning-based output prediction attacks in a blackbox setting. As preliminary experiments, we first focus on two toy SPN block ciphers (small PRESENT-[4] and small AES-[4]) and one toy Feistel block cipher (small TWINE-[4]). Due to its small internal structures with a block size of 16 bits, we can construct deep learning models by employing the maximum number of plaintext/ciphertext pairs, and we can precisely calculate the rounds in which full diffusion occurs. Next, based on the preliminary experiments, we explore whether the evaluation results obtained by our attacks against three toy block ciphers can be applied to block ciphers with large block sizes, e.g., 32 and 64 bits. As a result, we demonstrate the following results, specifically for the SPN block ciphers: First, our attacks work against a similar number of rounds that the linear/differential attacks can be successful. Next, our attacks realize output predictions (precisely ciphertext prediction and plaintext recovery) that are much stronger than distinguishing attacks. Then, swapping or replacing the internal components of the target block ciphers affects the average success probabilities of the proposed attacks. It is particularly worth noting that this is a deep learning specific characteristic because swapping/replacing does not affect the average success probabilities of the linear/differential attacks. Finally, by analyzing the influence of the differences in the characteristics of three S-boxes (i.e., the original PRESENT S-box and two known weak S-boxes) on deep learning specific characteristics, we clarify that the resistance of the target ciphers to differential/linear attacks can affect the success probability of deep learning-based attacks. We also confirm whether the proposed attacks work on the Feistel block cipher. We expect that our results will be an important stepping stone in the design of deep learning-resistant symmetric-key ciphers.

Branching program is an important component of indistinguishability obfuscation (IO) schemes, its size greatly influences the efficiencies of corresponding IO schemes. There are two major candidates of branching programs, Bar86 branching program and IK00 branching program. Bar86 branching program was shown to efficiently recognize NC$^1$ circuits. In specific, a Boolean circuit of depth $d$ can be recognized by a Bar86 branching program of length not larger than $4^d$ (Therefore of size not larger than $5^2 \times 4^d$). In this short paper we present similar result about IK00 branching program. We show that IK00 branching program efficiently recognizes NC$^1$ circuits, that is, a Boolean circuit of depth $d$ can be recognized by an IK00 branching program of size not larger than $(n+1) \times 4^d$, where $n$ is input length. Our result may be a negative evidence for IK00 branching program to efficiently recognize polynomial-time computable functions.

In our previous paper we introduced a novel SNARK-based construction, called Zendoo, that allows Bitcoin-like blockchains to create and communicate with sidechains of different types without knowing their internal structure. We also introduced a specific construction, called Latus, allowing creation of fully verifiable sidechains. But in there we omitted a detailed description of an incentive scheme for Latus that is an essential element of a real decentralized system. This paper fills the gap by introducing details of the incentive scheme for the Latus sidechain. Represented ideas can also be adopted by other SNARK-based blockchains to incentivize decentralized proofs creation.

In 1989, Shamir presented an efficient identification scheme (IDS) based on the permuted kernel problem (PKP). After 21 years, PKP was generalized by Lampe and Patarin, who were able to build an IDS similar to Shamir's one, but using the binary field. This binary variant presented some interesting advantages over Shamir's original IDS, such as reduced number of operations and inherently resistance against side-channel attacks. In the security analysis, considering the best attacks against the original PKP, the authors concluded that none of these existing attacks appeared to have a significant advantage when attacking the binary variant. In this paper, we propose the first attack that targets the binary PKP. The attack is analyzed in detail, and its practical performance is compared with our theoretical models. For the proposed parameters originally targeting 79 and 98 bits of security, our attack can recover about 100% of all keys using less than $2^{63}$ and $2^{77}$ operations, respectively.

State-separating proofs (SSP) is a recent methodology for structuring game-based cryptographic proofs in a modular way, by using algebraic laws to exploit the modular structure of composed protocols. While promising, this methodology was previously not fully formalized and came with little tool support. We address this by introducing SSProve, the first general verification framework for machine-checked state-separating proofs. SSProve combines high-level modular proofs about composed protocols, as proposed in SSP, with a probabilistic relational program logic for formalizing the lower-level details, which together enable constructing machine-checked cryptographic proofs in the Coq proof assistant. Moreover, SSProve is itself fully formalized in Coq, including the algebraic laws of SSP, the soundness of the program logic, and the connection between these two verification styles. To illustrate SSProve we use it to mechanize the simple security proofs of ElGamal and PRF-based encryption. We also validate the SSProve approach by conducting two more substantial case studies: First, we mechanize an SSP security proof of the KEM-DEM public key encryption scheme, which led to the discovery of an error in the original paper proof that has since been fixed. Second, we use SSProve to formally prove security of the sigma-protocol zero-knowledge construction, and we moreover construct a commitment scheme from a sigma-protocol to compare with a similar development in CryptHOL. We instantiate the security proof for sigma-protocols to give concrete security bounds for Schnorr's sigma-protocol.

Code-based cryptographic schemes are highly regarded among the quantum-safe alternatives to current standards. Yet, designing code-based signatures using traditional methods has always been a challenging task, and current proposals are still far from the target set by other post-quantum primitives (e.g. lattice-based). In this paper, we revisit a recent work using an innovative approach for signing, based on the hardness of the code equivalence problem. We introduce some optimizations and provide a security analysis for all variants considered. We then show that the new parameters produce instances of practical interest.

Recently, a light-weight authenticated key-exchange (AKE) scheme has been proposed. The scheme provides mutual authentication. It is asymmetric in nature by delegating complex cryptographic operations to resource-equipped servers, and carefully managing the workload on resource-constrained Smart meter nodes by using Physically Unclonable Functions. The prototype Smart meter built using commercial-off-the-shelf products is enabled with a low-cost countermeasure against load-modification attacks, which goes side-by-side with the proposed protocol. An attack against this AKE scheme has been recently proposed claiming that the server can be breached to mount spoofing attacks. It relies on the assumption that the result of an attack against authenticated key-exchange protocol is determined before the attacker learns the session key. In this short paper, we discuss the attack’s validity and describe the misinterpretation of the AKE protocol’s security definition.

Broadbent and Islam (TCC '20) proposed a quantum cryptographic primitive called quantum encryption with certified deletion. In this primitive, a receiver in possession of a quantum ciphertext can generate a classical certificate that the encrypted message is deleted. Though they proved that their construction is information theoretically secure, a drawback is that the construction is limited to the setting of one-time symmetric key encryption (SKE) where a sender and receiver have to share a common key in advance and the key can be used only once. In this paper, we construct a (reusable-key) public key encryption (PKE) and attribute-based encryption (ABE) with certified deletion. Our PKE with certified deletion is constructed assuming the existence of IND-CPA secure PKE, and our ABE with certified deletion is constructed assuming the existence of indistinguishability obfuscation and one-way function.

We extend a basic key agreement model with a hidden identifier source to a multi-user model with joint secrecy and privacy constraints over all entities that do not trust each other. Different entities that use different measurements of the same remote source through broadcast channels (BCs) to agree on mutually-independent local secret keys are considered. This model is the proper multi-user extension of the basic model since the encoder and decoder pairs are not assumed to trust other pairs, unlike assumed in the literature. Strong secrecy constraints imposed jointly on all secret keys, which is more stringent than separate secrecy leakage constraints for each secret key considered in the literature, are satisfied. Inner bounds for maximum key rate, and minimum privacy-leakage and storage rates are proposed for any finite number of entities. Inner and outer bounds for degraded and less-noisy BCs are given to illustrate cases with strong privacy. A multi-enrollment model that is used for common physical unclonable functions (PUFs) is also considered to establish inner and outer bounds for key-leakage-storage regions that differ only in the Markov chains imposed. For this special case, the encoder and decoder measurement channels have the same channel transition matrix and secrecy leakage is measured for each secret key separately. We illustrate cases for which it is useful to have multiple enrollments as compared to a single enrollment and vice versa.

Differential privacy has been widely applied to provide privacy guarantees by adding random noise to the function output. However, it inevitably fails in many high-stakes voting scenarios, where voting rules are required to be deterministic. In this work, we present the first framework for answering the question: ``How private are commonly-used voting rules?" Our answers are two-fold. First, we show that deterministic voting rules provide sufficient privacy in the sense of distributional differential privacy (DDP). We show that assuming the adversarial observer has uncertainty about individual votes, even publishing the histogram of votes achieves good DDP. Second, we introduce the notion of exact privacy to compare the privacy preserved in various commonly-studied voting rules, and obtain dichotomy theorems of exact DDP within a large subset of voting rules called generalized scoring rules.

There is a difference between a system having no known attacks and the system being secure---as cryptographers know all too well. Once we begin talking about the implementations of systems this issue becomes even more prominent since the amount of material which needs to be scrutinised skyrockets. Historically, lack of transparency and low standards for e-voting system implementations have resulted in a culture where open source code is seen as a gold standard; however, this ignores the issue of the comprehensibility of that code. In this work we make concrete empirical recommendations based on our, and others, experiences and findings from examining the source code of e-voting systems. We highlight that any solution used for significant elections should be well designed, carefully analysed, deftly built, accurately documented and expertly maintained. Until e-voting system implementations are clear, comprehensible, and open to public scrutiny security standards are unlikely to improve.

We present Orthros, a 128-bit block pseudorandom function. It is designed with primary focus on latency of fully unrolled circuits. For this purpose, we adopt a parallel structure comprising two keyed permutations. The round function of each permutation is similar to Midori, a low-energy block cipher, however we thoroughly revise it to reduce latency, and introduce different rounds to significantly improve cryptographic strength in a small number of rounds. We provide a comprehensive, dedicated security analysis. For hardware implementation, Orthros achieves the lowest latency among the state-of-the-art low-latency primitives. For example, using the STM 90nm library, Orthros achieves a minimum latency of around 2.4 ns, while other constructions like PRINCE, Midori-128 and QARMA_{9}-128-\sigma_{0} achieve 2.56 ns, 4.10 ns, 4.38 ns respectively.

In this paper, we propose a novel concept named Physically Related Function(PReF) which are devices with hardware roots of trust. It enables secure key-exchange with no pre-established/embedded secret keys. This work is motivated by the need to perform key-exchange between lightweight resource-constrained devices. We present a proof-of-concept realization of our contributions in hardware using FPGAs.

Topology-hiding broadcast (THB) enables parties communicating over an incomplete network to broadcast messages while hiding the topology from within a given class of graphs. THB is a central tool underlying general topology-hiding secure computation (THC) (Moran et al. TCC’15). Although broadcast is a privacy-free task, it was recently shown that THB for certain graph classes necessitates computational assumptions, even in the semi-honest setting, and even given a single corrupted party. In this work we investigate the minimal assumptions required for topology-hiding communication: both Broadcast or Anonymous Broadcast (where the broadcaster’s identity is hidden). We develop new techniques that yield a variety of necessary and sufficient conditions for the feasibility of THB/THAB in different cryptographic settings: information theoretic, given existence of key agreement, and given existence of oblivious transfer. Our results show that feasibility can depend on various properties of the graph class, such as connectivity, and highlight the role of different properties of topology when kept hidden, including direction, distance, and/or distance-of-neighbors to the broadcaster. An interesting corollary of our results is a dichotomy for THC with a public number of at least three parties, secure against one corruption: information-theoretic feasibility if all graphs are 2-connected; necessity and sufficiency of key agreement otherwise.

Quantum-access security, where an attacker is granted superposition access to secret-keyed functionalities, is a fundamental security model and its study has inspired results in post-quantum security. We revisit, and fill a gap in, the quantum-access security analysis of the Lamport one-time signature scheme (OTS) in the quantum random oracle model (QROM) by Alagic et al.~(Eurocrypt 2020). We then go on to generalize the technique to the Winternitz OTS. Along the way, we develop a tool for the analysis of hash chains in the QROM based on the superposition oracle technique by Zhandry (Crypto 2019) which might be of independent interest.

Federated learning (FL) is an emerging distributed machine learning paradigm which addresses critical data privacy issues in machine learning by enabling clients, using an aggregation server (aggregator), to jointly train a global model without revealing their training data. Thereby, it improves not only privacy but is also efficient as it uses the computation power and data of potentially millions of clients for training in parallel. However, FL is vulnerable to so-called inference attacks by malicious aggregators which can infer information about clients’ data from their model updates. Secure aggregation restricts the central aggregator to only learn the summation or average of the updates of clients. Unfortunately, existing protocols for secure aggregation for FL suffer from high communication, computation, and many communication rounds. In this work, we present SAFELearn, a generic design for efficient private FL systems that protects against inference attacks that have to analyze individual clients' model updates using secure aggregation. It is flexibly adaptable to the efficiency and security requirements of various FL applications and can be instantiated with MPC or FHE. In contrast to previous works, we only need 2 rounds of communication in each training iteration, do not use any expensive cryptographic primitives on clients, tolerate dropouts, and do not rely on a trusted third party. We implement and benchmark an instantiation of our generic design with secure two-party computation. Our implementation aggregates 500~models with more than 300K parameters in less than 0.5 seconds.

The problem of Blockwise Isomorphism of Polynomials was introduced by Santoso at PQCrypto 2020 as a generalization of the problem of Isomorphism of Polynomials. In the present paper, we describe how to solve this problem with circulant matrices, used in Santoso's Diffie-Hellman type encryption scheme.

Bitcoin can process only a few transactions per second, which is insufficient for a global payment network. The Lightning Network (LN) aims to address this challenge. The LN allows for low-latency bitcoin transfers through a network of payment channels. In contrast to regular Bitcoin transactions, payments in the LN are not globally broadcast. Thus it may improve not only Bitcoin’s scalability but also privacy. However, the probing attack allows an adversary to discover channel balances, threatening users’ privacy. Prior work on probing did not account for the possibility of multiple (parallel) channels between two nodes. Naive probing algorithms yield false results for parallel channels. In this work, we develop a new probing model that accurately accounts for parallel channels. We describe jamming-enhanced probing that allows for full balance information extraction in multi-channel hops, which was impossible with earlier probing methods. We quantify the attacker’s information gain and propose an optimized algorithm for choosing probe amounts for multi-channel hops. We demonstrate its efficiency based on real-world data using our own probing-focused LN simulator. Finally, we discuss countermeasures such as new forwarding strategies, intra-hop payment split, rebalancing, and unannounced channels.

This report considers combining three well-known optimization methods for elliptic curve scalar multiplication: Gallant--Lambert--Vanstone (GLV) for complex multiplication endomorphisms $[i]$ and $[i+1]$; 3-bit fixed windows (signed base 8); and Hisil--Wong--Carter--Dawson (HWCD) curve arithmetic for twisted Edwards curves. An $x$-only Diffie--Hellman scalar multiplication for curve $2y^2=x^3+x$ over field size $8^{91}+5$ has arithmetic cost $947\textbf{M} + 1086\textbf{S}$, where $\textbf{M}$ is a field multiplication and $\textbf{S}$ is a field squaring. This is approximately $(3.55\textbf{M} + 4.07\textbf{S})$/bit, with $1\textbf{S}$/bit for input decompression and $1\textbf{S}$/bit for output normalization. Optimizing speed by allowing uncompressed input points leads to an estimate $(3.38\textbf{M}+2.95\textbf{S})$/bit. To mitigate some side-channel attacks, the secret scalar is only used to copy curve points from one array to another: the field operations used are fixed and independent of the secret scalar. The method is likely vulnerable to cache-timing attacks, nonetheless.

We construct two tightly secure signature schemes based on the computational Diffie-Hellman (CDH) and factoring assumptions in the random oracle model. Our schemes are proven secure in the multi-user setting, and their security loss is constant and does not depend on the number of users or signing queries. They are the first schemes that achieve this based on standard search assumptions, as all existing schemes we are aware of are either based on stronger decisional assumptions, or proven tightly secure in the less realistic single-user setting. Under a concrete estimation, in a truly large scale, the cost of our CDH-based scheme is about half of Schnorr and DSA (in terms of signature size and running time for signing).

Threshold and blind signature schemes have found numerous applications in cryptocurrencies, e-cash, e-voting and other privacy-preserving technologies. In this work, we make advances in bringing lattice-based constructions for these primitives closer to practice. 1. Threshold Signatures. For round optimal threshold signatures, we improve the only known construction by Boneh et al. [CRYPTO'18] as follows: a. Efficiency. We reduce the amount of noise flooding from $2^{\Omega(\lambda)}$ down to $\sqrt{Q_S}$, where $Q_S$ is the bound on the number of generated signatures and $\lambda$ is the security parameter. By using lattice hardness assumptions over polynomial rings, this allows to decrease signature bit-lengths from $\widetilde{O}(\lambda^3)$ to $\widetilde{O}(\lambda)$. b. Towards Adaptive Security. The construction of Boneh et al. satisfies only selective security, where all the corrupted parties must be announced before any signing queries are made. We improve this in two ways: in the ROM, we obtain partial adaptivity where signing queries can be made before the corrupted parties are announced but the set of corrupted parties must be announced all at once. In the standard model, we obtain full adaptivity, where parties can be corrupted at any time but this construction is in a weaker pre-processing model where signers must be provided correlated randomness of length proportional to the number of signatures, in an offline pre-processing phase. 2. Blind Signatures. For blind signatures, we improve the state of art lattice-based construction by Hauck et al.[CRYPTO'20] as follows: a. Round Complexity. We improve the round complexity from three to two -- this is optimal. b. Efficiency. Again, we reduce the amount of noise flooding from $2^{\Omega(\lambda)}$ down to $\sqrt{Q_S}$, where $Q_S$ is the bound on the number of signatures and $\lambda$ is the security parameter. c. Number of Signing Queries. Unlike the scheme from Hauck et al., our construction enjoys a proof that is not restricted to a polylogarithmic number of signatures. Using lattice hardness assumptions over rings, we obtain signatures of bit-lengths bounded as $\widetilde{O}(\lambda)$. In contrast, the signature bit-length in the scheme from Hauck et al. is $\Omega(\lambda^3 + Q_S \cdot \lambda)$. Concretely, we can obtain blind/threshold signatures of size $\approx 3$ KB using a variant of Dilithium-G with $\approx 128$ bit-security, for adversaries limited to getting $256$ signatures. In contrast, parameters provided by Hauck et al. lead to blind signatures of $\approx 7.73$ MB, for adversaries limited to getting 7 signatures, while concrete parameters are not provided for the construction of threshold signatures by Boneh et al.

Proxy signature (PS) is a kind of digital signature, in which an entity called original signer can delegate his signing rights to another entity called proxy signer. Designated verifier signature (DVS) is a kind of digital signature where the authenticity of any signature can be verified by only one verifier who is designated by the signer when generating it. Designated verifier proxy signature (DVPS) combines the idea of DVS with the concept of proxy signature (PS) and is suitable for being applied in many scenarios from e-tender, e-voting, e-auction, e-health and e-commerce, etc. Many DVPS schemes have been proposed and Identity-based DVPS (IBDVPS) schemes have also been discussed. Certificateless public-key cryptography (CL-PKC) is acknowledged as an appealing paradigm because there exists neither the certificate management issue as in traditional PKI nor private key escrow problem as in Identity-based setting. A number of certificateless designated verifier signature (CLDVS) schemes and many certificateless proxy signature (CLPS) schemes have been proposed. However, to the best of our knowledge, the concept of Certificateless Designated Verifier Proxy Signature (CLDVPS) has not been appeared in the literature. In this paper, we formalize the definition and the security model of CLDVPS schemes. We then construct the first CLDVPS scheme and prove its security.

This note solves the open problem of finding a closed formula for the bias of a rotational differential-linear distinguisher proposed in IACR ePrint 2021/189 (EUROCRYPT 2021), completely generalizing the results on ordinary differential-linear distinguishers due to Blondeau, Leander, and Nyberg (JoC 2017) to the case of rotational differential-linear distinguishers.

Motivated by the goal of designing versatile and flexible secure computation protocols that at the same time require as little interaction as possible, we present new multiparty reusable Non-Interactive Secure Computation (mrNISC) protocols. This notion, recently introduced by Benhamouda and Lin (TCC 2020), is essentially two-round Multi-Party Computation (MPC) protocols where the first round of messages serves as a reusable commitment to the private inputs of participating parties. Using these commitments, any subset of parties can later compute any function of their choice on their respective inputs by just sending a single message to a stateless evaluator, conveying the result of the computation but nothing else. Importantly, the input commitments can be computed without knowing anything about other participating parties (neither their identities nor their number) and they are reusable across any number of desired computations. We give a construction of mrNISC that achieves standard simulation security, as classical multi-round MPC protocols achieve. Our construction relies on the Learning With Errors (LWE) assumption with polynomial modulus, and on the existence of a pseudorandom function (PRF) in $\mathsf{NC}^1$. We achieve semi-malicious security in the plain model and malicious security by further relying on trusted setup (which is unavoidable for mrNISC). In comparison, the only previously known constructions of mrNISC were either using bilinear maps or using strong primitives such as program obfuscation. We use our mrNISC to obtain new Multi-Key FHE (MKFHE) schemes with threshold decryption: $\bullet$ In the CRS model, we obtain threshold MKFHE for $\mathsf{NC}^1$ based on LWE with only $\textit{polynomial}$ modulus and PRFs in $\mathsf{NC}^1$, whereas all previous constructions rely on LWE with super-polynomial modulus-to-noise ratio. $\bullet$ In the plain model, we obtain threshold levelled MKFHE for $\mathsf{P}$ based on LWE with $\textit{polynomial}$ modulus, PRF in $\mathsf{NC}^1$, and NTRU, and another scheme for constant number of parties from LWE with sub-exponential modulus-to-noise ratio. The only known prior construction of threshold MKFHE (Ananth et al., TCC 2020) in the plain model restricts the set of parties who can compute together at the onset.

This article discusses existing attacks and known weaknesses of BLS aggregate signatures. The goal is clarify the threat model of BLS aggregate signatures, what security properties that they have and do not have. It’s unfortunate that the weaknesses are not documented anywhere in BLS RFC draft v4 [1]. Confusion, ambiguity, misunderstanding all may cause security issues in practice. We hope that this article can help cryptographic practitioners make informed decisions when using BLS aggregate signatures and deploy mitigations at the application/protocol layer because BLS aggregate signatures might not have security guarantees that you need.

We investigate the existence of constant-round post-quantum black-box zero-knowledge protocols for $\mathbf{NP}$. As a main result, we show that there is no constant-round post-quantum black-box zero-knowledge argument for $\mathbf{NP}$ unless $\mathbf{NP}\subseteq \mathbf{BQP}$. As constant-round black-box zero-knowledge arguments for $\mathbf{NP}$ exist in the classical setting, our main result points out a fundamental difference between post-quantum and classical zero-knowledge protocols. Combining previous results, we conclude that unless $\mathbf{NP}\subseteq \mathbf{BQP}$, constant-round post-quantum zero-knowledge protocols for $\mathbf{NP}$ exist if and only if we use non-black-box techniques or relax certain security requirements such as relaxing standard zero-knowledge to $\epsilon$-zero-knowledge. Additionally, we also prove that three-round and public-coin constant-round post-quantum black-box $\epsilon$-zero-knowledge arguments for $\mathbf{NP}$ do not exist unless $\mathbf{NP}\subseteq \mathbf{BQP}$.

We propose protocols for obliviously evaluating finite-state machines, i.e., the evaluation is shared between the provider of the finite-state machine and the provider of the input string in such a manner that neither party learns the other's input, and the states being visited are hidden from both. For alphabet size $|\Sigma|$, number of states $|Q|$, and input length $n$, previous solutions have either required a number of rounds linear in $n$ or communication $\Omega(n|\Sigma||Q|\log|Q|)$. Our solutions require 2 rounds with communication $O(n(|\Sigma|+|Q|\log|Q|))$. We present two different solutions to this problem, a two-party one and a setting with an untrusted but non-colluding helper.

The Tor anonymity network is often abused by some attackers to (anonymously) convey attack traffic. These attacks abuse Tor exit relays (i.e., the relays through which traffic exits Tor) by making it appear the attack originates there; as a result, many website operators indiscriminately block all Tor traffic (by blacklisting all exit IPs), reducing the usefulness of Tor. Recent research shows that majority of these attacks are ones that generate high traffic volume (e.g., Denial-of-Service attacks). This suggests that a simple solution such as throttling traffic flow at the Tor exits may permit early detection of these attacks, improve overall reputation of exits, and eventually prevent blanket blocking of Tor exits. However, naively monitoring and throttling traffic at the Tor exits can endanger the privacy of the network's users. This paper introduces ZXAD (pronounced "zed-zad"), a zero-knowledge based _private_ Tor exit abuse detection system that permits identification of otherwise unlinkable connections that are part of a high-volume attack. ZXAD does not reveal any information, apart from the fact that some user is conveying a high volume of traffic through Tor. We formally prove the correctness and security of ZXAD. We also measure two proof-of-concept implementations of our zero-knowledge proofs and show that ZXAD operates with low bandwidth and processing overheads.

Given $2n$-to-$n$ compression functions $h_1,h_2,h_3$, we build a new $5n$-to-$n$ compression function $\mathrm{T}_5$, using only $3$ compression calls: $\mathrm{T}_5(m_1, m_2, m_3, m_4, m_5) := h_3( h_1(m_1, m_2)\oplus m_5, h_2(m_3, m_4)\oplus m_5) \oplus m_5$. We prove that this construction matches Stam's bound, by providing $\tilde{O}(q^2/2^n)$ collision security and $O(q^3/2^{2n}+ nq/2^n)$ preimage security (the latter term dominates in the region of interest, when $q<2^{n/2}$). In particular, it provides birthday security for hashing $5$ inputs using three $2n$-to-$n$ compression calls, instead of only $4$ inputs in prior constructions. Thus, we get a sequential variant of the Merkle-Damgård (MD) hashing, where $t$ message blocks are hashed using only $3t/4$ calls to the $2n$-to-$n$ compression functions; a $25\%$ saving over traditional hash function constructions. This time reduces to $t/4$ (resp. $t/2$) sequential calls using $3$ (resp. $2$) parallel execution units; saving a factor of $4$ (resp. $2$) over the traditional MD-hashing, where parallelism does not help to process one message. We also get a novel variant of a Merkle tree, where $t$ message blocks can be processed using $0.75(t-1)$ compression function calls and depth $0.86 \log_2 t$, thereby saving $25\%$ in the number of calls and $14\%$ in the update time over Merkle trees. We provide two modes for a local opening of a particular message block: conservative and aggressive. The former retains the birthday security, but provides longer proofs and local verification time than the traditional Merkle tree. For the aggressive variant, we reduce the proof length to a $29\%$ overhead compared to Merkle trees ($1.29\log_2 t$ vs $\log_2 t$), but the verification time is now $14\%$ faster ($0.86\log_2 t$ vs $\log_2 t$). However, birthday security is only shown under a plausible conjecture related to the 3-XOR problem, and only for the (common, but not universal) setting where the root of the Merkle tree is known to correspond to a valid $t$-block message.

We give an exposition of supersingular isogeny graphs, quaternion ideal graphs and Bruhat–Tits trees, and of their connections. Bruhat–Tits trees are combinatorial objects whose vertices and edges have a very simple representation as two-by-two matrices, which, as we show, is useful for understanding certain aspects of the corresponding elliptic curves and isogenies. Moreover Bruhat–Tits trees can be given an orientation and a notion of depth that we translate into the setting of supersingular isogeny graphs. We give some suggestions towards using Bruhat–Tits trees as a tool for cryptanalysis of certain cryptosystems based on supersingular isogeny graphs.

The construction of linear (minimal) codes from functions over finite fields has been greatly studied in the literature since determining the parameters of linear codes based on functions is rather easy due to the nice structures of functions. In this paper, we derive 3-weight and 4-weight linear codes from weakly regular plateaued unbalanced functions in the recent construction method of linear codes over the odd characteristic finite fields. The Hamming weights and their weight distributions for proposed codes are determined by using the Walsh transform values and Walsh distribution of the employed functions, respectively. We next derive projective 3-weight punctured codes with good parameters from the constructed codes. These punctured codes may be almost optimal due to the Griesmer bound, and they can be employed to design association schemes. We lastly show that all constructed codes are minimal, which approves that they can be employed to design high democratic secret sharing schemes.

We introduce a new approach to realize incrementally verifiable computation (IVC), in which the prover recursively proves the correct execution of incremental computations of the form $y=F^{(\ell)}(x)$, where $F$ is a (potentially non-deterministic) computation, $x$ is the input, $y$ is the output, and $\ell > 0$. Unlike prior approaches to realize IVC, our approach avoids succinct non-interactive arguments of knowledge (SNARKs) entirely and arguments of knowledge in general. Instead, we introduce and employ folding schemes, a weaker, simpler, and more efficiently-realizable primitive, which reduces the task of checking two instances in some relation to the task of checking a single instance. We construct a folding scheme for a characterization of $\mathsf{NP}$ and show that it implies an IVC scheme with improved efficiency characteristics: (1) the "recursion overhead" (i.e., the number of steps that the prover proves in addition to proving the execution of $F$) is a constant and it is dominated by two group scalar multiplications expressed as a circuit (this is the smallest recursion overhead in the literature), and (2) the prover's work at each step is dominated by two multiexponentiations of size $O(|F|)$, providing the fastest prover in the literature. The size of a proof is $O(|F|)$ group elements, but we show that using a variant of an existing zkSNARK, the prover can prove the knowledge of a valid proof succinctly and in zero-knowledge with $O(\log{|F|})$ group elements. Finally, our approach neither requires a trusted setup nor FFTs, so it can be instantiated efficiently with any cycles of elliptic curves where DLOG is hard.

Side-channel attacks are a serious problem in the implementation of cryptosystems. Masking is an effective countermeasure to this problem and it has been actively studied for implementations of block ciphers. An obstacle to efficient masked implementation is the complexity of an evaluation of multiplication, which is quadratic in the order of masking. A natural approach to this problem is to explore ways to reduce the number of multiplications required to compute an S-box. Algebraic decomposition is another interesting approach proposed by Carlet et al. in 2015, which gives a way to represent an S-box as composition of polynomials with low algebraic degrees. In this paper, for the algebraic decomposition, we propose to use a special type of low-algebraic-degree polynomials, which we call generalized multiplication (GM) polynomials. The masking scheme for multiplication can be applied to GM polynomials, which is more efficient than the masking scheme for general low-algebraic-degree polynomials. Our performance evaluation based on some experimental results shows the effectiveness of masked implementation using the proposed decomposition compared to masked implementation using the decomposition of Carlet et al.

The supersingular isogeny-based key encapsulation (SIKE) suite stands as an attractive post-quantum cryptosystem with its relatively small public keys. Public key sizes in SIKE can further be compressed by computing pairings and solving discrete logarithms in certain subgroups of finite fields. This comes at a cost of precomputing and storing large discrete logarithm tables. In this paper, we propose several techniques to optimize memory requirements in computing discrete logarithms in SIKE, and achive to reduce table sizes by a factor of 4. We implement our techniques and verify our theoretical findings.

In recent years a new type of block ciphers and hash functions over a (large) field, such as MiMC and GMiMC, have been designed. Their security, particularly over a prime field, is mainly determined by algebraic cryptanalysis techniques, such as Gröbner basis and interpolation attacks. In SAC 2019, Li and Preneel presented low memory interpolation cryptanalysis against the MiMC and Feistel-MiMC designs. In this work we answer the open question posed in their work and show that low memory interpolation cryptanalysis can be extended to unbalanced Feistel networks (UFN) with low degree functions, and in particular to the GMiMC design. Our attack applies to UFNs with expanding and contracting round functions keyed either via identical (univariate) or distinct round keys (multivariate). Since interpolation attacks do not necessarily yield the best possible attacks over a binary extension field, we focus our analysis on prime fields GF(p). Our next contribution is to develop an improved technique for a more efficient key recovery against UFNs with expanding round function. We show that the final key recovery step can be reduced not only to the gcd but also to the root finding problem. Despite its higher theoretical complexity, we show that our approach has a particularly interesting application on Sponge hash functions based on UFNs, such as GMiMCHash. We illustrate for the first time how our root finding technique can be used to find collision, second preimage and preimage attacks on (reduced round) members of the GMiMCHash family. In addition, we support our theoretical analysis with small-scale experimental results.

Multiparty computation protocols (MPC) are said to be \emph{secure against covert adversaries} if the honest parties are guaranteed to detect any misbehavior by the malicious parties with a constant probability. Protocols that, upon detecting a cheating attempt, additionally allow the honest parties to compute certificates, which enable third parties to be convinced of the malicious behavior of the accused parties, are called \emph{publicly verifiable}. In this work, we make several contributions to the domain of MPC with security against covert adversaries. We identify a subtle flaw in a protocol of Goyal, Mohassel, and Smith (Eurocrypt 2008) and show how to modify their original construction to obtain security against covert adversaries. We present generic compilers that transform arbitrary passively secure preprocessing protocols, i.e. protocols where the parties have no private inputs, into protocols that are secure against covert adversaries and publicly verifiable. Using our compiler, we construct the first efficient variants of the BMR and the SPDZ protocols that are secure and publicly verifiable against a covert adversary that corrupts all but one party and also construct variants with covert security and identifiable abort. We observe that an existing impossibility result by Ishai, Ostrovsky, and Seyalioglu (TCC 2012) can be used to show that there exist certain functionalities that cannot be realized by parties, that have oracle-access to broadcast and arbitrary two-party functionalities, with information-theoretic security against a covert adversary.

Cryptographic objects with updating capabilities have been proposed by Bellare, Goldreich and Goldwasser (CRYPTO'94) under the umbrella of incremental cryptography. They have recently seen increased interest, motivated by theoretical questions (Ananth et al., EC'17) as well as concrete practical motivations (Lehmann et al., EC'18; Groth et al. CRYPTO'18; Klooss et al., EC'19). In this work, the form of updatability we are particularly interested in is that primitives are key-updatable and allow to update old cryptographic objects, e.g., signatures or message authentication codes, from the old key to the updated key at the same time without requiring full access to the new key (i.e., only via a so-called update token). Inspired by the rigorous study of updatable encryption by Lehmann and Tackmann (EC'18) and Boyd et al. (CRYPTO'20), we introduce a definitional framework for updatable signatures (USs) and message authentication codes (UMACs). We discuss several applications demonstrating that such primitives can be useful in practical applications, especially around key rotation in various domains, as well as serve as building blocks in other cryptographic schemes. We then turn to constructions and our focus there is on ones that are secure and practically efficient. In particular, we provide generic constructions from key-homomorphic primitives (signatures and PRFs) as well as direct constructions. This allows us to instantiate these primitives from various assumptions such as DDH or CDH (latter in bilinear groups), or the (R)LWE and the SIS assumptions. As an example, we obtain highly practical US schemes from BLS signatures or UMAC schemes from the Naor-Pinkas-Reingold PRF.

This paper proposes a new ultra lightweight cipher RAGHAV. RAGHAV is a Substitution-Permutation (SP) network, which operates on 64 bit plaintext and supports a 128/80 bit key scheduling. It needs only 994.25 GEs by using 0.13µm ASIC technology for a 128 bit key scheduling. It also needs less memory i.e. 2204 bytes of FLASH memory , which is less as compared to all existing S-P network lightweight ciphers. This paper presents a complete security analysis of RAGHAV, which includes basic attacks like linear cryptanalysis and differential cryptanalysis. This paper also covers advanced attack like zero correlation attack, Biclique attack, Algebraic attack, Avalanche effect, key collision attack and key schedule attack. In this cipher,use of block permutation helps the design to improve the throughput. RAGHAV cipher uses 8 bit permutations with S-Box which results in better diffusion mechanism. RAGHAV consumes very less power around 24mW which is less as compared to all existing lightweight ciphers. RAGHAV cipher scores on all design metrics and is best suited for applications like IoT.

This paper presents a unified approach to quantifying the information leakages in the most general code-based masking schemes. Specifically, by utilizing a uniform representation, we highlight first that all code-based masking schemes' side-channel resistance can be quantified by an all-in-one framework consisting of two easy-to-compute parameters (the dual distance and the number of conditioned codewords) from a coding-theoretic perspective. In particular, we use signal-to-noise ratio (SNR) and mutual information (MI) as two complementary metrics, where a closed-form expression of SNR and an approximation of MI are proposed by connecting both metrics to the two coding-theoretic parameters. Secondly, considering the connection between Reed-Solomon code and SSS (Shamir's Secret Sharing) scheme, the SSS-based masking is viewed as a particular case of generalized code-based masking. Hence as a straightforward application, we evaluate the impact of public points on the side-channel security of SSS-based masking schemes, namely the polynomial masking, and enhance the SSS-based masking by choosing optimal public points for it. Interestingly, we show that given a specific security order, more shares in SSS-based masking leak more information on secrets in an information-theoretic sense. Finally, our approach provides a systematic method for optimizing the side-channel resistance of every code-based masking. More precisely, this approach enables us to select optimal linear codes (parameters) for the generalized code-based masking by choosing appropriate codes according to the two coding-theoretic parameters. Summing up, we provide a best-practice guideline for the application of code-based masking to protect cryptographic implementations.

Deep learning has played an important role in many fields. It shows significant potential to cryptanalysis. Differential cryptanalysis is an important method in the field of block cipher cryptanalysis. The key point of differential cryptanalysis is to find a differential distinguisher with longer rounds or higher probability. Firstly, we describe how to construct the ciphertext pairs required for differential cryptanalysis based on deep learning. Based on this, we train 9-round and 8-round differential distinguisher of SIMON32 based on deep residual neural networks. Secondly, we explore the impact of the input difference patterns on the accuracy of the distinguisher based on deep learning. For the input difference with Hamming weight of 1, the accuracy of 9-round distinguisher is different between the first 16 bits and the last 16 bits for non-zero bit positions. This is mainly caused by that its nonlinear operation is mainly concentrated in the first 16 bits. We also find that the accuracy of the distinguisher is different even if the input differences come from the differential characteristics with the same probability. Finally, we construct a last subkey recovery attack on 11-Round SIMON32 with practical data and time complexities. Our attack only uses about 29 chosen plaintexts and only needs about 45s for an attack with a success rate of over 90% using our workstation, which does not exceed 2^18:5 11-round encryption. At the same time, we extend the neural 9-round distinguisher to a 11-round distinguisher based on SAT, and propose a last subkey recovery attack on 13-Round SIMON32 using 2^12:5 chosen plaintexts with a success rate of over 90%. Compared with traditional approach, the complexity of the method based on deep learning is lower, both in time complexity and data complexity.

Plateaued functions as an extension of bent functions play a significant role in cryptography, coding theory, sequences and combinatorics. In 2019, Hod\v{z}i\'{c} et al. designed Boolean plateaued functions in spectral domain and provided some construction methods in spectral domain. However, in their constructions, the Walsh support of Boolean $s$-plateaued functions in $n$ variables, when written as a matrix of order $2^{n-s} \times n$, contains at least $n-s$ columns corresponding to affine functions on $\mathbb{F}_{2}^{n-s}$. They proposed an open problem to provide constructions of Boolean $s$-plateaued functions in $n$ variables whose Walsh support, when written as a matrix, contains strictly less than $n-s$ columns corresponding to affine functions. In this paper, we focus on the constructions of generalized $s$-plateaued functions from $V_{n}$ to $\mathbb{Z}_{p^k}$, where $V_{n}$ is an $n$-dimensional vector space over $\mathbb{F}_{p}$, $p$ is a prime, $k\geq 1$ and $n+s$ is even when $p=2$. Firstly, inspired by the work of Hod\v{z}i\'{c} et al., we give a complete characterization of generalized plateaued functions with affine Walsh support in spectral domain and provide some construction methods of generalized plateaued functions with (non)-affine Walsh support in spectral domain. In our constructions of generalized $s$-plateaued functions with non-affine Walsh support, the Walsh support, when written as a matrix, can contain strictly less than $n-s$ columns corresponding to affine functions. When $p=2, k=1$, these constructions provide an answer to the open problem in \cite{Hodzic2}. Secondly, we provide a generalized indirect sum construction method of generalized plateaued functions, which can also be used to construct (non)-weakly regular generalized bent functions. In particular, we show that the canonical way to construct Generalized Maiorana-McFarland bent functions can be obtained by the generalized indirect sum construction method and we illustrate that the generalized indirect sum construction method can be used to construct bent functions not in the completed Generalized Maiorana-McFarland class. Furthermore, based on this construction method, we give constructions of plateaued functions in the subclass \emph{WRP} of the class of weakly regular plateaued functions and vectorial plateaued functions.

Blockchain has been practiced in crypto-currencies and crossborder banking settlement. However, no clear evidence that a distributed ledger network (or Blockchain) is built within domestic payment systems, although many experts believe that Blockchain has wide applicability in various industries and disciplines. As the author’s best knowledge, no one has published a clear architecture and a feasible framework for a Blockchain-based banking network. Thus, \how Blockchain can be implemented in domestic banking systems" is a big challenge. The most important contribution of this work is to give a feasible and viable framework resolving that problem. The author investigates a Blockchain-based payment framework, more explicitly, a decentralized banking architecture running on the top of existing banking cores. The Blockchain network has two tiers: master nodes (block generators) and normal nodes (validators). The consensus mechanism is introduced as a composition of Proof of Stake, Proof of Reputation and/or practical Byzantine Fault Tolerance. In addition, nomination and approval mechanisms are added to the governance to enhance legal compliance and compatibility with real Fintech space. Some qualitative analysis is provided to show that the proposed Blockchain banking framework offers better security, scalability and decentralization, while easily adapt with different national regulation environments, among other Blockchains. In the application aspects, the framework is implementable and deployable for decentralized payment network and smartcontract infrastructure for domestic markets, then enable a complete and unified digitized space for cloud banking and financial services.

In this note, we conduct a cryptanalysis of the paper published by Zhu et al. on Future Generation Computer Systems in 2021. We demonstrate that their quantum-resistant identity-based proxy signcryption scheme cannot achieve the confidentiality as they claimed.

We construct public-coin time- and space-efficient zero-knowledge arguments for $\mathbf{NP}$. For every time $T$ and space $S$ non-deterministic RAM computation, the prover runs in time $T \cdot \mathrm{polylog}(T)$ and space $S \cdot \mathrm{polylog}(T)$, and the verifier runs in time $n \cdot \mathrm{polylog}(T)$, where $n$ is the input length. Our protocol relies on hidden order groups, which can be instantiated with a trusted setup from the hardness of factoring (products of safe primes), or without a trusted setup using class groups. The argument-system can heuristically be made non-interactive using the Fiat-Shamir transform. Our proof builds on DARK (Bünz et al., Eurocrypt 2020), a recent succinct and efficiently verifiable polynomial commitment scheme. We show how to implement a variant of DARK in a time- and space-efficient way. Along the way we: 1. Identify a significant gap in the proof of security of DARK. 2. Give a non-trivial modification of the DARK scheme that overcomes the aforementioned gap. The modified version also relies on significantly weaker cryptographic assumptions than those in the original DARK scheme. Our proof utilizes ideas from the theory of integer lattices in a novel way. 3. Generalize Pietrzak's (ITCS 2019) proof of exponentiation ($\mathsf{PoE}$) protocol to work with general groups of unknown order (without relying on any cryptographic assumption). In proving these results, we develop general-purpose techniques for working with (hidden order) groups, which may be of independent interest.

The deep learning-based side-channel analysis represents an active research domain. While it is clear that deep learning enables powerful side-channel attacks, the variety of research scenarios often makes the results difficult to reproduce. In this paper, we present AISY - a deep learning-based framework for profiling side-channel analysis. Our framework enables the users to run the analyses and report the results efficiently while maintaining the results' reproducible nature. The framework implements numerous features allowing state-of-the-art deep learning-based analysis. At the same time, the AISY framework allows easy add-ons of user-custom functionalities.

Constant advancements in quantum computing bring closer the reality of current public key encryption schemes becoming computationally feasible to be broken. Many developers working in the industry are just finding out about this and will be rapid to look into changing their web applications to be secure in the quantum era. This paper documents a tried and tested construction for a quantum-resistant, end-to-end encryption scheme which has been implemented in a real-life online web application. The implementation is shown to work well without significant impact on the performance time in comparison to its pre-quantum counterpart.

CRYSTALS-Dilithium as a lattice-based digital signature scheme has been selected as a finalist in the PQC standardization process of NIST. As part of this selection, a variety of software implementations have been evaluated regarding their performance and memory requirements for platforms like x86 or ARM Cortex-M4. In this work, we present a first set of FPGA implementations for the low-end Xilinx Artix-7 platform, evaluating the peculiarities of the scheme in hardware, reflecting all available round-3 parameter sets. As a key component in our analysis, we present results for a specifically adapted NTT core for the Dilithium cryptosystem, optimizing this component for an optimal LUT and FF utilization by efficient use of special purpose DSPs. Presenting our results, we aim to shed further light on the performance of lattice-based cryptography in low-cost and high-throughput configurations and their respective potential use-cases in practice.

The MPC-in-the-head construction (Ishai et al., STOC'07) give zero-knowledge proofs from secure multiparty computation (MPC) protocols. This paper presents an efficient MPC protocol for permuting a vector of values, making use of the relaxed communication model that can be handled by the MPC-in-the-head construction. Our construction allows more efficient ZK proofs for relations expressed in the Random Access Machine (RAM) model. As a standalone application of our construction, we present batch anonymizable ring signatures.

We construct a publicly verifiable, non-interactive delegation scheme for any polynomial size arithmetic circuit with proof-size and verification complexity comparable to those of pairing based zk-SNARKS. Concretely, the proof consists of $O(1)$ group elements and verification requires $O(1)$ pairings and $n$ group exponentiations, where $n$ is the size of the input. While known SNARK-based constructions rely on non-falsifiable assumptions, our construction can be proven sound under any constant size ($k\geq 2$) $k$-Matrix Diffie-Hellman ($k$-MDDH) assumption. However, the size of the reference string as well as the prover's complexity are quadratic in the size of the circuit. This result demonstrates that we can construct delegation from very simple and well-understood assumptions. We consider this work a first step towards achieving practical delegation from standard, falsifiable assumptions. Our main technical contributions are first, the introduction and construction of what we call "no-signaling, somewhere statistically binding commitment schemes". These commitments are extractable for any small part $x_S$ of an opening $x$, where $S\subseteq [n]$ is of size at most $K$. Here $n$ is the dimension of $x$ and $x_S=(x_i)_{i\in S}$. Importantly, for any $S'\subseteq S$, extracting $x_{S'}$ can be done independently of $S\setminus S'$. Second, we use of these commitments to construct more efficient "quasi-arguments"' with no-signaling extraction, introduced by Paneth and Rothblum (TCC 17). These arguments allow extracting parts of the witness of a statement and checking it against some local constraints without revealing which part is checked. We construct pairing-based quasi arguments for linear and quadratic constraints and combine them with the low-depth delegation result of Gonzáles et. al. (Asiacrypt 19) to construct the final delegation scheme.

Quantum computers are about to herald a new age of cryptography. As a fundamental building block in today’s digitalized world, Digital Signature Schemes (DSS) provide the ability to authenticate messages exchanged over untrusted channels. Unfortunately, virtually all currently used DSS are built upon mathematical problems that can efficiently be solved using quantum computers, thus rendering schemes such as RSA and ECC insecure. Due to its conservative security properties, the eXtended Merkle Signature Scheme (XMSS) is an outstanding candidate for a quantum-secure DSS which has already been standardized by NIST and IETF. In this paper we present the first full hardware accelerator for XMSS whose generic design approach allows matching the requirements of several projected use-cases. In particular, we provide a full design exploration regarding the choice of parameters and hash functions to identify configurations for optimal performance and area utilization.

Dynamic group signature (DGS) allows a user to generate a signature on behalf of a group, while preserving anonymity. Although many existing DGS schemes have been proposed in the random oracle model for achieving efficiency, their security proofs require knowledge extractors that cause loose security reductions. In this paper, we first propose a new practical DGS scheme whose security can be proven without knowledge extractors in the random oracle model. Moreover, our scheme can also be proven in the strong security model where an adversary is allowed to generate group managers’ keys maliciously. The efficiency of our scheme is comparable to existing secure DGS schemes in the random oracle model using knowledge extractors. The security of our scheme is based on a new complexity assumption that is obtained by generalizing the Pointcheval-Sanders (PS) assumption. Although our generalized PS (GPS) assumption is interactive, we prove that, under the symmetric discrete logarithm (SDL) assumption, the new GPS assumption holds in the algebraic group model.

Schnorr's signature scheme provides an elegant method to derive signatures with security rooted in the hardness of the discrete logarithm problem, which is a well-studied assumption and conducive to efficient cryptography. However, unlike pairing-based schemes which allow arbitrarily many signatures to be aggregated to a single constant sized signature, achieving significant non-interactive compression for Schnorr signatures and their variants has remained elusive. This work shows how to compress a set of independent EdDSA/Schnorr signatures to roughly half their naive size. Our technique does not employ generic succinct proofs; it is agnostic to both the hash function as well as the specific representation of the group used to instantiate the signature scheme. We demonstrate via an implementation that our aggregation scheme is indeed practical. Additionally, we give strong evidence that achieving better compression would imply proving statements specific to the hash function in Schnorr's scheme, which would entail significant effort for standardized schemes such as SHA2 in EdDSA. Among the others, our solution has direct applications to compressing Ed25519-based blockchain blocks because transactions are independent and normally users do not interact with each other.

We study post-quantum zero-knowledge (classical) protocols that are sound against quantum resetting attacks. Our model is inspired by the classical model of resetting provers (Barak-Goldreich-Goldwasser-Lindell, FOCS `01), providing a malicious efficient prover with oracle access to the verifier's next-message-function, fixed to some initial random tape; thereby allowing it to effectively reset (or equivalently, rewind) the verifier. In our model, the prover has quantum access to the verifier's function, and in particular can query it in superposition. The motivation behind quantum resettable soundness is twofold: First, ensuring a strong security guarantee in scenarios where quantum resetting may be possible (e.g., smart cards, or virtual machines). Second, drawing intuition from the classical setting, we hope to improve our understanding of basic questions regarding post-quantum zero knowledge. We prove the following results: Black-Box Barriers: Quantum resetting exactly captures the power of black-box zero knowledge quantum simulators. Accordingly, resettable soundness cannot be achieved in conjunction with black-box zero knowledge, except for languages in $\BQP$. Leveraging this, we prove that constant-round public-coin, or three message, protocols cannot be black-box post-quantum zero-knowledge. For this, we show how to transform such protocols into quantumly resettably sound ones. The transformations are similar to classical ones, but their analysis is significantly more challenging due to the essential difference between classical and quantum resetting. A Resettably-Sound Non-Black-Box Zero-Knowledge Protocol: Under the (quantum) Learning with Errors assumption and quantum fully-homomorphic encryption, we construct a post-quantum resettably-sound zero knowledge protocol for $\NP$. We rely on non-black-box simulation techniques, thus overcoming the black-box barrier for such protocols. From Resettable Soundness to The Impossibility of Quantum Obfuscation: Assuming one-way functions, we prove that any quantumly-resettably-sound zero-knowledge protocol for $\NP$ implies the impossibility of quantum obfuscation. Combined with the above result, this gives an alternative proof to several recent results on quantum unobfuscatability.

This article discusses the decoding of Gabidulin codes and shows how to extend the usual decoder to any supercode of a Gabidulin code at the cost of a significant decrease of the decoding radius. Using this decoder, we provide polynomial time attacks on the rank–metric encryption schemes Ramesses and Liga.

In this paper, we improve the theoretical background of the attacks on the DSA schemes given in [1, 29], and we present some new more practical attacks.

We study the round complexity of secure multiparty computation (MPC) in the challenging model where full security, including guaranteed output delivery, should be achieved at the presence of an active rushing adversary who corrupts up to half of parties. It is known that 2 rounds are insufficient in this model (Gennaro et al., Crypto 2002), and that 3 round protocols can achieve computational security under public-key assumptions (Gordon et al., Crypto 2015; Ananth et al., Crypto 2018; and Badrinarayanan et al., Asiacrypt 2020). However, despite much effort, it is unknown whether public-key assumptions are inherently needed for such protocols, and whether one can achieve similar results with security against computationally-unbounded adversaries. In this paper, we use Minicrypt-type assumptions to realize 3-round MPC with full and active security. Our protocols come in two flavors: for a small (logarithmic) number of parties $n$, we achieve an optimal resiliency threshold of $t\leq \lfloor (n-1)/2\rfloor$, and for a large (polynomial) number of parties we achieve an almost-optimal resiliency threshold of $t\leq 0.5n(1-\epsilon)$ for an arbitrarily small constant $\epsilon > 0$. Both protocols can be based on sub-exponentially hard injective one-way functions in the plain model. If the parties have an access to a collision resistance hash function, we can derive statistical everlasting security for every NC1 functionality, i.e., the protocol is secure against adversaries that are computationally bounded during the execution of the protocol and become computationally unlimited after the protocol execution. As a secondary contribution, we show that in the strong honest-majority setting ($t<n/3$), every NC1 functionality can be computed in 3 rounds with everlasting security and complexity polynomial in $n$ based on one-way functions. Previously, such a result was only known based on collision-resistance hash function.